基于视觉阈值的分形图像压缩算法研究

郭慧 贺杰

［摘要］ 本文提出一种基于视觉阈值的四叉树分割方案，应用于定义域块和值域块的划分，并引入人类视觉系统理论，对传统的定义域块的搜索方法进行了改进，将其与基本的分形图像压缩算法通过实验进行了比较。实验结果表明，在保证重建图像质量的前提下，当视觉阈值为30、60、90 时，该算法的编码速度是基本算法的8~27倍，是一种有效的图像压缩方法。

［关键词］ 视觉阈值； 分形； 图像压缩； 四叉树； 人类视觉系统

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2012 . 02. 031

［中图分类号］TP391［文献标识码］A［文章编号］1673 - 0194（2012）02- 0055- 02

１引言

在信息技术领域，图像压缩已经成为一个十分重要的课题。目前出现的图像压缩技术已达到上百种，但是压缩比和压缩效果不佳，且编码、解码时间过长，远不能满足当前信息时代的需要。分形图像编码技术是一种思想新颖的图像压缩技术，具有压缩比率高、解码分辨率无关、解码速度快等优点，受到了国际科学界的广泛关注。但是，分形编码技术具有不对称性，虽然具有很高的压缩比且能快速解码，但是编码时间非常长，使得该技术一直没有得到广泛应用。因此对如何加快分形编码速度方面的研究将具有重要的理论意义和实际意义。

２分形图像压缩的基本原理

图像数据的分形压缩是利用图像的自相似和自仿射性质，寻找生成该图像的若干局部ＩＦＳ，将所得的局部ＩＦＳ参数保存起来，形成编码文件（即压缩后的图像），这就是编码过程。分形压缩的理论基础是迭代函数系统定理和拼贴定理。至于解码过程，是从任意一个初始图像出发，用编码文件中的局部ＩＦＳ参数，经过若干次迭代生成不变集，所得到的就是与原图像近似的一个图像。

２．１经典的分形图像压缩算法

Ｊａｃｑｕｉｎ首次成功实现了分形图像压缩的全自动算法［１］，该算法成为分形图像压缩的一个新的里程碑，其编码算法的主要步骤如下：

步骤１：对大小为Ｍ × Ｍ的原始图像Ｇ进行正方形分割，得到互不重叠且大小相同的２ｋ × ２ｋ的图像子块，将其称为值域块，用Ｒ表示，以下相同。

步骤２： 对于每一个Ｒ块，在原始图像Ｇ中找出一个尺寸为２ｋ ＋ １ × ２ｋ ＋ １的子块Ｄ（称之为定义域块，用Ｄ表示，以下相同），确保对Ｄ 进行灰度仿射变换及空间变换后，所得到的Ｄ′与Ｒ之间的平方误差值最小。

步骤３：对于每一个值域块Ｒ，记录下面５个参数：

（１） 搜索到的最佳匹配子块Ｄ的左上角坐标（ｄｘ，ｄｙ）。

（２） 使Ｒ与Ｄ成为最佳匹配的等距变换的序号ｎ（一共有８种等距变换）。

（３） 灰度对比度因子ｗ，灰度平移因子ｇ。

以上参数便为原始图像的ＩＦＳ码，解码时可从任意一个初始图像出发，利用这些ＩＦＳ码，经过１０次迭代生成不变集，得到与原图近似的重建图像。

３基于视觉阈值分割的分形图像编码算法

Ｊａｃｑｕｉｎ的算法是将图像分割成固定尺寸的方块，但图像的自相似性不一定会精确地落在给定尺寸的方块内，因此影响了压缩效果。于是学者们提出了更多的分割方法。由Ｆｉｓｈｅｒ等人提出的四叉树分割法［２］最大特点在于可依据匹配误差及压缩比自适应地调整子块和父块的尺寸，尽可能合理地分割图像。与Ｊａｃｑｕｉｎ的基本分形压缩算法相比，虽然解码图像质量有一定下降，但具备灵活的分块机制和较高的压缩比，使其较为流行。ＨＶ分割法将原始图像分割成一系列矩形子块，对于搜索不到匹配父块的子块，水平或垂直地将其划分为两个矩形区域，在划分时须使矩形子块的边与图像中出现的水平边、垂直边位置对应，使得子块与父块的图像内容具备自相似性，故能更好地进行匹配。

３．１ 基于视觉阈值分割的分形图像编码算法的提出

四叉树分割法、ＨＶ分割法及其后续的一些改进方案，基本思路都是把图像分割成矩形，但均未考虑到人类视觉系统（ＨＶＳ）的特性，故无法确保图像子块间的相似性一定能落在矩形块内。由于人眼对灰度的分辨能力仅有几十个数量级，故在一幅相邻像素灰度值相近的的灰度图像中，即便其包含的信息量较为丰富，人眼也难以精确地识别和提取。这说明了人类视觉系统的一个显著特性就是非均匀、非线性的认知图像，即人眼并不能完全感知到图像中的任意细节和变化。因此，如能把压缩过程中一些由数量化误差引起的解码图像变化控制在人眼无法察觉的范围内，就能够在ＨＶＳ认可的相同图像质量下获得较高的压缩比。

本文提出了一种基于视觉阈值分割的分形编码方案，是在改进的四叉树法的图像块分割过程中，引入了检测像素灰度值一致性的步骤，即划分过程中要确保同一块内的各像素灰度值的取值范围不超过给定的阈值Ｓ。Ｓ的取值一般为几十个数量级，这是由人类视觉系统的特性决定的。

与Ｆｉｓｈｅｒ等人提出的四叉树分割法相比，本文提出的算法主要改进的方面为：

（１） 对值域块的分割方案。若值域块内所有像素灰度值的两个最值之差超过给定阈值，则把该值域块分割成4个尺寸相同的子块，直至小于给定阈值或达到预设的图像分割尺度时，则分割过程停止，最后得到多种不同尺寸的Ｒ块。本方案将ＨＶＳ的视觉阈值这一特性纳入了考量，按照一致性准则，图像块的相似性必定落在矩形内。

（２） 对定义域块的分割方案。首先将Ｍ × Ｍ的原始图像Ｇ整体进行水平与垂直的１／２的子采样，得到子采样图像Ｇ′，其尺寸为（Ｍ／２） × （Ｍ／２），该方法通过对图像整体的一次子采样即实现了对全部Ｄ块的缩放，大大加快了编码速度。随后采用对值域块的分割方案对采样图像Ｇ′进行定义域块分割，最后得到多种不同尺寸的Ｄ块。

（３） 对搜索Ｄ块方案的改进。寻找与某一Ｒ块形成最佳匹配的Ｄ块，只需搜索Ｄ池的一个子集，该子集中所有Ｄ块的尺寸均与该Ｒ块相同，故避免了对Ｄ池进行全域搜索，有效地缩小了搜索范围。因此，本文算法总的搜索空间仅仅为不同尺寸值域块的总数和定义域块的总数的乘积之和的８倍，之所以要乘以８是因为每个定义域块还存在８种等距变换。

显然，这种基于视觉阈值的分割方案能极大地缩小搜索空间，从而也能显著地降低编码时间，并且由于引入ＨＶＳ的视觉阈值分割方案，也保证了重建图像的质量。设原始图像Ｇ的尺寸为Ｍ × Ｍ，以下是编码算法的详细步骤：

步骤１：给定视觉阈值Ｑ，将Ｇ分割为４个尺寸相同的正方形子块，对每个子块进行一致性标准检测，即检测子块内像素灰度值的取值范围不超过阈值Ｑ。

步骤２：设置分割Ｒ块时的深度范围，即Ｒ块尺寸的最大值、最小值。

步骤３：若子块尺寸分割已达最小深度范围，即便其各像素灰度值的范围大于Ｑ，仍停止分割；否则若块内像素灰度值范围大于Ｑ，则将其分割为４个更小的正方形子块，并对这些子块进行深度范围检测和像素灰度值范围检测。

步骤４：循环执行步骤３，当全部方块的像素灰度值范围均不超过Ｑ时（即满足一致性标准），退出循环，得到所有Ｒ块。

步骤５：对Ｇ进行水平与垂直的１／２的子采样，得到次采样图像Ｇ′，其尺寸为（Ｍ／２） × （Ｍ／２），将Ｇ′分成4个大小相同的方块，判断每个方块是否满足一致性标准。

步骤６：重复步骤３，直到所有的方块都满足一致性标准才结束。得到多种尺寸的Ｄ块，形成Ｄ块池。

步骤７：对任意Ｒ块，在Ｄ块池中搜索一个尺寸相同的最佳匹配Ｄ块。使得Ｄ经空间位置变换和等距变换后，与Ｒ块具有最小平方误差。

步骤８：记录每个Ｒ块的如下参数：最佳匹配Ｄ块的空间坐标（其左上角坐标ｄｘ，ｄｙ）、等距变换的编号ｉ、灰度对比度因子ｗ、灰度平移因子ｇ。

３．２实验结果

本节将本文提出的算法和基本的Ｊａｃｑｕｉｎ算法进行了实验比较，以期证明本文算法的有效性和正确性。在本实验中机器配置为：ＯＳ为Ｗｉｎｄｏｗｓ ＸＰ，ＣＰＵ为Ｐ４ ３．０Ｇ，ＲＡＭ为２Ｇ。实验环境为Ｍａｔｌａｂ ６．５，通过编程分别实现了这两种算法。在本实验中，基本Ｊａｃｑｕｉｎ算法的值域块的大小定义为４ × ４，定义域块的大小定义为８ × ８，定义域块的水平和垂直移动步长均设定为４；根据客观情况，为了获得较好的重建图像质量，方块（定义域块或值域块）所允许的最小与最大尺寸分别定义为４ × ４和８ × ８。根据ＨＶＳ的特性，阈值Ｑ通常是几十个数量级。以２５６ × ２５６ × ８的标准灰度图像Ｌｅｎａ和Ｇｏｌｄｈｉｌｌ为测试对象，本实验获得了Ｑ为３０、６０、９０的实验结果，如表１所示。

当采用Ｊａｃｑｕｉｎ的基本分形算法时，由于对图像进行分割后所获得的值域块的总数是一个固定值，如在本实验中即为：Ｓ ＝ ２５６／４ × ２５６／４ ＝ ４ ０９６，因而采用Ｊａｃｑｕｉｎ的基本分形算法时图像的压缩比为：Ｃ ＝ ２５６ × ２５６ × ８／（４ ０９６ × （６ ＋ ６ ＋ ３ ＋ ５ ＋ ７）） ＝４．７４。

而当采用本文算法时，压缩比是会随着阈值Ｑ的变化而变化的。表１中压缩比Ｃ的计算公式是：Ｃ ＝ ２５６ × ２５６ × ８／（Ｓ × （６ ＋ ６ ＋ ３ ＋ ５ ＋ ７）），其中Ｓ表示值域块的总数。其中，定义域块左上角的坐标值ｄｘ和ｄｙ被量化为６ ｂｉｔｓ和６ ｂｉｔｓ，等距变换的矩阵号ｉ被量化为３ ｂｉｔｓ，灰度对比度因子ｗ被量化为５ ｂｉｔｓ，灰度平移因子ｇ被量化为７ ｂｉｔｓ。本实验结果中的压缩比Ｃ是在熵编码前所获得的。

４结论

本文将改进的四叉树分割方案同时应用于定义域块和值域块的划分上。同时，基于人类视觉系统理论，对传统的定义域块的搜索方法进行了改进，提出了一种新的搜索方法。最后，基于基本分形算法，提出并实现了一种基于视觉阈值分割的分形图像压缩算法，并将其与基本分形算法通过实验进行了比较。实验结果表明该算法是一种有效的图像压缩方法。

主要参考文献

［１］ Ａ Ｅ Ｊａｃｑｕｉｎ． Ｉｍａｇｅ Ｃｏｄｉｎｇ Ｂａｓｅｄ ｏｎ ａ Ｆｒａｃｔａｌ Ｔｈｅｏｒｙ ｏｆ Ｉｔｅｒａｔｅｄ Ｃｏｎｔｒａｃｔｉｖｅ Ｉｍａｇｅ ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｍａｇｅ Ｐｒｏｃｅｓｓｉｎｇ，１９９２，１（１）：１８－３０．

［２］ Ｙ Ｆｉｓｈｅｒ． Ｆｒａｃｔａｌ Ｉｍａｇｅ Ｃｏｍｐｒｅｓｓｉｏｎ：Ｔｈｅｏｒｙ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎ［Ｍ］． Ｎｅｗ Ｙｏｒｋ，NY： Ｓｐｒｉｎｇｅｒ，１９９４．

［３］ 朱伟勇，于海，宋春林． 基于误差阈值和分层搜索的快速分形图像压缩方法［Ｊ］． 小型微型计算机系统， ２００５，２６（２）：２７７－２８０．

［４］ 何传江，黄席樾． 基于图像块叉迹的快速分形图像编码算法［Ｊ］． 计算机学报， ２００５， ２８（１０）： １７５３－１７５８．