用于纹理图像压缩的分形算法的改进

曲波 高强 李大华 于晓

摘要：纹理是图像中的重要部分，包含了大量的信息。纹理部分大多数为背景而被人所忽视。针对纹理图像本身很强的自相似形以及分形算法中D块池搜索时间过长和匹配原则过于繁琐的问题，提出了一种结合矢量量化的方法，并对R块和D块采用了一种新的匹配原则。首先对D块池中的D块进行矢量量化处理，优化码书以减少搜索时间。然后提出了一种新的匹配原则IAM（图像活动能量测度）并通过这个参数来配对R块和D块，从而实现分形编码。

关键词：纹理图像；分型算法；矢量量化；IAM

分形图像编码算法是目前研究较为广泛的编码方法之一，对其研究已有近二十年的历史。Mandelblot在早期提出了分形的理论，[1]Barnsley最早将分形的概念引入到图像压缩编码领域，[2]但其编码过程需要人工干预[3]；1989年Jacquin提出局部迭代函数系统（PIFS）的概念，实现了分块的自动分形图像编码算法，[4]使分形图像编码取得了突破性进展，成为后人研究和扩展的起点。该算法具有许多优点：它突破以往熵压缩编码的界限，在编码过程中，采用了类似描述的方法，而解码时通过迭代完成的，且具有分辨率无关的解码特性等。[5]

纹理一直都是图像处理中的一个关注点，对纹理图像很难下一个确切的定义，类似于布纹、草地、砖砌地面等具有重复性结构的图像称为纹理图像。一般来说纹理图像中的灰度分布具有某种周期性，即便灰度变化是随机的，它也具有一定的统计特性。J.K.霍金斯认为纹理的标志有三要素：一是某种局部的序列性，在该序列更大的区域内不断的重复；二是序列是由基本部分非随机排列组成的；三是各部分大致都是均匀的统一体，纹理区域内任何地方都有大致相同的结构尺寸。[6]

对于一般性的图像，我们可以将之看成是纹理加上细节而成，细节对于一副图像而言是蕴含重要信息的部分，而纹理部分大部分是用来作为背景的，具有强烈的区域相似性，而這部分往往又是人眼容易忽视的地方，所以这一部分的PSNR值要求不需要很高，所以我们可以采用次最优的方法来还原纹理图像以便获得更高的压缩比。

鉴于纹理图像自身的特殊性以及分形编码对于自相似性的一种支持，所以本文中将分形算法应用于纹理图像的压缩中。对于分形算法，很多文章都提出了了改进的方法，比如文献[7]提出叉迹的方法[7]，文献[8]提出的分数盒维数的方法[8]和文献[9]提出的无搜索方案[9]。在本文中，通过将矢量量化的方法引入分形算法之中，提出一种LBGfractal相结合的分形算法以获得更高的压缩比，并提出一种新的块匹配标准，最后通过匹配公式的改进加快了解码的收敛速度，这样就在保证一定的PSNR的基础上提高了纹理图像的压缩效率。

1LBGFractal算法

首先我们来回顾一下传统的分形算法的流程。

1.1对图像进行预处理分割

将初始大小为N×N的灰度图像I分割成互不相交的大小为R×R的方块Ri（Rangeblock，称为值域块），即I=∪N/RiRi，且Ri∩Rj=（代表空集），Ri是分形压缩中的每一个编码单元。

1.2建立搜索空间

用2R×2R的截取窗口沿原图像的水平和垂直方向（即x、y轴）分别以步长Δh和Δv移动，每一次移动后的截取方块就构成了匹配块Di（Domainblock，称为定义域块），所有这样的匹配块Di，就构成了搜索空间SD。

1.3寻找最优匹配块

在搜索空间内，对每一值域块Ri，通过最小均方误差（MSE）原则寻找误差最小的匹配块Di，使Di经适当的仿射变换ωi来逼近Ri，即DiωiRi，使之满足

dRi，ωiDi=‖Ri-siAGDi+oi‖2

=minDI2‖RisiAGDi+oi‖2（1）

其中，G为固定的几何变换，完成从Domain块到Range块的空间压缩映射，通常用四点平均法（2×2采样）；A为8种对称旋转变换之一，si和oi分别是灰度变换的尺度因子和偏移因子。

1.4生成编码

通过搜索得到满足的变换群集ωixi，yi，ai，si，oi（其中xi、yi表示Di的位置）就构成了PIFS，将PIFS记录下来并进行ωi量化编码，即得到每个Ri得分形码（Fractalcodes）。

1.5迭代解码

以任意灰度图像（与待解码图像尺寸相同）作为初始点集，读取PIFS中每一编码块Ri对应的仿射变换的参数，按与编码过程中相同的顺序作用到初始点集。反复迭代至收敛后，所得到的吸引子就是最终的解码图像。[10]

通过上述编码流程我们可以看出，Domain块所构成的D块池SD是相当庞大的，对于一副512×512的图像来说，R块大小定义为4×4，D块大小定义为8×8，那么SD就会有4096个D块，这不管对于搜索还是存储都是很大的负担。而在这4096个D块中，存在着相当大的冗余，也就存在继续压缩的可能性。[11]因此我们引入矢量量化中的LBG算法。LBG算法的中心思想是最近邻合并原则，通过将距离最近的两个矢量进行合并产生一个新的矢量来代替原来的两个矢量从而达到缩减码书大小的目的。

将LBG算法与传统的Fractal算法结合的LBGFractal算法的流程如下：

1）将原始大小N×N的图像（本实验中采用的是512×512大小）分割成R×R大小的R块（本实验中采用的是4×4大小），构成初始编码块的集合。

2）用2R×2R大小的截取窗口沿原图像的水平和垂直方向分别以一定步长移动（本实验步长大小取的是R块大小），每次截取的窗口就成为一个D块，通过这种方法最终得到初始的D块池。

3）采用LBG算法对于初始的D块池进行矢量量化，缩减码书大小。

4）对于每一个R块，在新形成的D块池中通过匹配原则（本文采取的是IAM匹配原则）来寻找最优匹配快。

5）通过搜索最后形成R块的分形码，这种算法的分形码由4部分构成，D块池码字的编号，尺度因子s，亮度偏移因子o和旋转因子a。

通过上面的算法流程可以看出，由于原始的分形算法要记录D块的位置（横坐标和纵坐标），而本算法中只需要记录相应码字的索引号，因此减少了分形码的存储和传输的压力，也达到了进一步压缩的要求。

对于纹理图像而言，它具有相对于普通的自然图或者肖像图更强的全局自相似性，这也从一个侧面暗示出纹理图像形成的D块池的码书可以拥有更少的码字，因此LBGFractal算法对于纹理图像能得到更好的压缩效果。

2评价标准的改进

传统的分形编码所采用的块相似评价标准是MSE，MSE的中心思想就是图像块相应像素点相减，然后做平方和。由于MSE中涉及到了乘法运算，所以在程序处理的时候会有额外的消耗。

本文中采用另外一种评价标准IAM[12]（ImageActivityMeasure），定义如下：

LAM=1X×Y[∑X-1i=1∑Yj=1Ii，j-Ii+1，j

+∑Xi=1∑Y-1j=1Ii，j-Ii，j+1]（2）

从公式（2）可以看出，IAM主要是用来计算图像的水平和垂直方向的梯度值，下面来说明块相似和IAM之间的关系。

对于传统的分形编码来说，最后误差公式为：

E（R，D）=‖R-r-I‖2-s2·‖D-d-I‖2（3）

从公式（3）我们可以看出，如果要使最后的误差很小，就是要让R-r-I与s·D-d-I尽量接近，在这里我们做一下改动，如果Ri，j-r-I与s·Di，j-d-I的差值很小，并且Ri+1，j-r-I与s·Di+1，j-d-I的差值也很小，那么从这个角度来看Ri，j-r-I-Ri+1，j-r-I的差值就会与s·Di，j-d-I-s·Di+1，j-d-I很接近，根据a-b

SymbolcB@ a-b，所以从上述结果上可以推断出Ri，j-Ri+1，j与s·Di，j-Di+1，j（梯度）会大体上接近，也就是说我们找的R块和D块之间的匹配性可以用这两个量之间的比较来得到大体的结果。而如果匹配块的每一个梯度值都比较接近的话，它们的和也会比较接近，也就说∑Ri，j-Ri+1，j的结果值和∑s·Di，j-Di+1，j的结果值会很接近，现在讨论的横向的梯度，可以用同样的方法说明纵向的梯度也满足这个性质，最后得到的∑Ri，j-Ri+1，j+Ri，j-Ri，j+1和∑s·Di，j-Di+1，j+s·Di，j-Di，j+1很接近，也就说明如果两个块相匹配的话，IAMR应该和s·IAMD很接近，而从s=〈R-r-I，D-d-I〉/‖D-d-I‖2可以看出，如果两个块很接近的话，s的值应该接近于1，也就说最后我们可以认定如果R块和D块相似的话，IAMR应该相似于IAMD。

通过上面的证明可以看出，IAM可以作为一个块的特征值来作比较，我们也可以用块的IAM值来进行相似度比较，但是这种比較并不是最优匹配，只能达到一种次最优的匹配。由于我们采用的图像大小都是2的整数幂，所以IAM的计算中只涉及到加法和右移的计算，算法复杂度也小于MSE。

3解码收敛速度的改进

分形算法的解码速度虽然很快，但是仍有改进的余地，比如减少收敛次数。下面的公式改进就可以减少一半的收敛次数。首先将拼贴公式做一下改变，将几何变换因子和旋转变换因子都融入进尺度因子s中，这样最开始的公式变为：

R=s·D+o·I（4）

这里的s=〈R-r-I，D-d-I〉/‖D-d-I‖2，o=r--s·d-，把o里面的后一项s·d-和前面的s·D合并，产生的新的R块的匹配公式是：

R=s·（D-d-I）+r-I（5）

这样就把后面的分成两部分，前一部分代表搜索过程的影响，而后面的是要编码的R块的本质属性，跟搜索的方案是无关的，而且这样收敛的速度也会加快。

4实验结果及结论

实验计算机配置为IntelPentium4D506CPU、1GBDDRRAM，软件采用QT图形界面、C++语言编写，实验图像普通肖像图选择的是512×512大小的Lena灰度图，纹理图像选择的是512×512大小的Brick图，512×512大小的Chips图和512×512大小的Grassland图。

实验图选用的是Lena和Brick。通过图1可以看出纹理图像只需要原始码书大小的三分之一就可以得到和原始码书相同的解码效果，而普通的肖像图则需要更大的码书才能得到和原始差不多的结果，换言之，就是码书大小对于普通图像的影响要强于纹理图，普通图像所需要的信息更多，这也是由于纹理图像具有更强的全局自相似性决定的。

实验图选用的是Chips纹理图。通过结果可以发现在码书比较小的时候使用IAM作为评价标准和MSE很类似，因为在D块池小的情况下出现错误匹配的概率也会相应减少。

实验图选用的是Grassland纹理图。通过图3可以看出原公式需要6次迭代才能达到稳定，而新的公式只需要3次就达到稳定。

实验图选用的是Lena和Brick。通过图4的率失真曲线可以看出，随着压缩倍数的提高，普通肖像图（lena）的PSNR值下降很明显，而纹理图（brick）在压缩倍数高于3的时候才产生明显下降，到压缩倍数15的时候，肖像图的PSNR值降幅达到5，而纹理图只有1，这说明在肉眼接受的范围内，纹理图比肖像图具有更好的压缩性。

通过上述实验结果可以看出，本文提出的LBGFractal算法可以加快纹理图像的编码速度，加大纹理图像的压缩比和加快解码的收敛速度，从而可以得到对于纹理图像较好的压缩效果。后面的工作可以将现有方法和其他图像的特征量，比如盒维数，[13]结合起来，以期待得到更好的结果。

参考文献：

[1]MandelbrotB.B.，TheFractalGeometryofNature[J]，SanFrancisco：Freeman，1982.

[2]BarnsleyM.F.，FractalEverywhere，AcademicPress[J]，Boston，1988.

[3]BarnsleyM.F.，HurdL.P.，FractalImageCompression[J]，AKPetersLtd.，Boston，1992.

[4]JacquinA.G.，FractalImageCoding：AReview[J]，ProceedingsoftheIEEE，1993.81（10）.

[5]JacquinA.G.，ImageCodingBasedonAFractalTheoryofIteratedContractiveImageTransformations[J]，IEEETrans.ImageProcess，1992.1（1）.

[6]阮秋琦.數字图像处理学（第二版）.电子工业出版社，413417.

[7]何传江，蒋海龙，黄席樾.快速分形图像编码的一种特征方法[J].电子学报，2004，（11）.

[8]何传江，黄娟娟，李高平.基于分数盒维数的快速分形图像编码[J]，中国图象图形学报，2007，（03）.

[9]ShenFurao，OsamuHasegawa，Afastnosearchfractalimagecodingmethod[J]，SignalProcessing：imagecommunication，2004，（6）.

[10]何传江，黄席樾.分形图像编码技术的算法研究[D]/重庆大学博士学位论文，2004.

[11]FengJ.，Fractionalfractalgeometryforimageprocessing[D].EvanstonIllinois，USA：NorthwesternUniversity，2000.

[12]崔朝辉，刘冀伟，王志良，曲波.分形图像编码算法的参数选择对算法性能的影响[J].智能系统学报，2010，（31）.

[13]于子凡，杜贵君，林宗坚.图像盒子维数特征计算方法改进[J].测绘科学，2006，（31）.

作者简介：曲波（1984），男，汉族，山东烟台人，硕士，工程师，海上平台中控系统及设备设施维护。