一种基于小波域的分形图像编码改进算法*

娄 莉

(西安石油大学 计算机学院,陕西 西安710065)

小波图像编码和分形图像编码是两种不同的图像编码方法，二者各有其特点，又都存在一定的局限性[1-3]。一幅图像经过小波变换后，其相同方向但不同分辨率的子图像具有较强的相似性，这种相似性正好与分形编码的特点具有互补性。自1995年以来，Rinaldo和Calvagno首次提出并实现了一种小波与分形图像编码相结合的算法[4]。此后，又出现多种小波变换与分形相结合的图像编码算法[5-8]。这些算法，有的证明了小波域的分形图像解码可以通过低分辨率小波系数向高分辨率系数连续外推实现，即解码无需循环迭代，是无条件收敛的；有的通过采用平滑小波基消除重构图像在高压缩比时的方块效应；有的推导出仿射变换的收缩因子取值不受限制，能保证解码收敛；同时小波系数的树状结构提供了自然高效的Domain块分类方法等[9]。此外，还有一些研究集中在分形块的类别划分[10]以及基于小波零树结构的分形预测[11]等。

本文在此基础上，通过分析基本分形图像编码的压缩算法，提出一种基于小波域的分形图像编码改进算法。这种改进算法包括两部分：(1)根据图像小波分解后各子图像包含的不同能量，考虑各子图像所代表的方向、纹理特征等信息，对各子图采用非均匀的分形编码方案，即在进行小波域的分形编码时，分形块的选取不一定全是正方形，对于不同方向的纹理特征的小波子图像选取不同形状的分形块；(2)根据图像的小波变换系数在同一方向不同分辨率、同一分辨率不同方向之间都存在相关性，对每一图像块，在同一方向低一级分辨率的子带图像上寻找与其最佳分形匹配的相似块，由这些相似块形成一棵一棵预测树，解码端通过对预测树的分形预测恢复出各级图像块。实验证明，这种改进算法能够大大提高分形编码的速度，并取得较高的压缩比。

1 基本分形编码压缩算法

基本分形编码压缩算法的主要内容：将待编码的图像分割成互不重叠的子块(Range Block),称为图像块R，同时将图像分割成可以相互重叠的大一些的块(Domain Block)，称为相似块D。对分割后的R块和D块进行分类，如：变换平缓的平滑区域、变换突然的边缘区域和变换缓和的中间型区域等，使相匹配的块具有相同的区域性质。对分类后相同区域的每一个R块Rj寻找可以匹配的 D块 Dj，使得 Dj通过仿射函数 ψj可以近似于 Rj，由此可以得到一组仿射变换组 ψ1，ψ2…ψN，即分形迭代系统。只要该系统的变换是收敛的，且比原系统简单，就实现了分形压缩[12]。基本分形编码算法主要在图像分割后对R块和D块进行搜索匹配的过程，其压缩比较高，但是压缩时的计算量较大，编码压缩时间很长。

2 基于小波域的分形图像编码改进算法

本文的改进算法包括两部分：小波域分形编码过程中分形块形状的选取以及分形预测树的形成。

2.1 小波域分形编码过程中分形块形状的选取

在上述基本分形压缩编码过程中，在确定R块和D块的形状时，对各小波分解子图取的均是正方形。由于图像小波分解后，各子图包含的能量有所不同，其代表的方向、纹理等特征信息也不相同，因此，可以考虑在进行小波域的分形编码时,分形块的选取可以不选正方形，而是依据小波分解子图的不同方向的纹理特征选取不同形状的子块。

以512×512的 8 bit图 1为例进行实验，计算结果表明，不同方向的子图由于其纹理特征信息不同，在LH、HL、HH区域中,其水平和垂直方向的相关性不相同，所以在不同方向的分解子图像中采用不同形状的块进行分形编码，可使其编码时间更短，图像恢复效果更好。例如，在LH区域，通过计算分析，行相关长度大于列相关长度，图像以水平纹理为主，可采用4×2的矩形进行R块和D块的分割；在HL区域，行相关长度小于列相关长度，图像以竖直纹理为主，可采用2×4的矩形进行R块和D块的分割；而在HH区域，行相关长度与列相关长度接近，则可以采用正方形来分割。同时，由于左上角的低频子图包含了图像的大部分能量，因此仍采用2×2正方形子块的选取，不参加计算。图像块的分割方法如图2所示。应用均匀分块和非均匀分块的压缩效果比较如图3所示。

2.2 分形预测树的形成过程

分形预测树的形成原理是:应用Davis把零树的概念引入到分形图像编码的理论，把分形图像编码中的相似块和图像块扩大到相似树(Domain Tree)和图像树(Range Tree),从而使得相似块与图像块之间的分形匹配转化为相似树与图像树之间的分形匹配。在此基础上，可以在各级小波分解的子图像中寻找与图像块R最佳分形匹配的代表块，再由各级代表块按照零树结构产生一棵代表树，通过计算比较各级图像树R与代表树的距离，确定距离最小的代表树就是图像树R的预测树。

结合小波域图像分割形状的分析，对图1进行如图2所示的小波域分割，得到基于小波域的分形预测树的形成图如图4所示。具体过程是：

(1)首先对图像进行多次小波变换，产生各个子带图像。通过对图像行、列相关性的计算分析，确定各子带小波域图像分割的形状。为了保证信噪比，对最低分辨率的子带图像 LL1、HL1、LH1、HH1不编码。

(2)同时在水平、垂直、对角线3个方向上形成一棵一棵图像树，即零树。 如 LH 方向上的 R=(R1，R2，R3，R4）就是其中一棵图像树，而 D=(D1，D2，D3，D4)表示 HL 方向上的相似树。然后在LH1中寻找与图像块R2最佳分形匹配的代表块E1，再由E1按照零树结构产生一棵代表树 E=(E1，E2，E3)。 同理，在 LH2中寻找与图像块 R3最佳分形匹配的代表块 F2，并生成代表树 F=(F1，F2，F3)。在LH3中寻找与图像块R4最佳分形匹配的代表块 G3，并生成代表树 G=(G1，G2，G3)。

(3)分别计算图像树 R与 3棵代表树 E、F、G的距离，距离最小的代表树就是图像树R的预测树。然后将预测树在相应层次的位置以及经历的几何变换和仿射变换作为图像树R的分形预测编码。

(4)HL、HH方向按同样方式编码,只是构成的R块和D块的形状大小不同。这样，在改进算法中,编码只需对代表树中的一个代表块进行分形编码。而解码时，又可依据这个代表块通过零树结构推出其他代表块，再分形预测图像块R。

由于前面针对小波分解图的能量分配特性已经采用了非均匀的分形块形状的选取，再结合这种分形预测编码方法，其结果大大提高了分形编码的速度，缩短了编码时间，在提高压缩比方面也取得了良好的效果。

3 实验结果

实验采用图1所示图像，分别用基本分形编码方法和本文的改进算法进行实验，其重建图像如图5所示。基本分形编码时各子图中图像块大小为4×4，相似块大小为8×8，改进算法中对小波分解图像块的分割方法如图 2所示，相似块大小取为图像块大小的 2×2倍，实验结果如表1所示。

表1 性能比较结果

本文提出基于小波域的分形图像编码改进算法是将小波域分形与分形预测方法相结合，由表1可知，与基本分形算法相比，在恢复图像质量接近的情况下，压缩比提高约2倍，信噪比下降2 dB，而编码时间大大缩短，提高了编码速度，表明在提高压缩比方面，效果良好。

[1]余松煜，张文军，孙军.现代图像信息压缩技术[Ml.北京:科学出版社，1998.

[2]陈守吉，张立明.分形与图像压缩[M].上海：上海科技教育出版社，1998.

[3]BRENDT W，GERHARD D J.A review of the fractal image coding literature[J].IEEE Transactions on Image Processing,1999,8(12):1716-1729.

[4]RINALDO R,CALVAGNO G.Image coding by block prediction of multiresolution subimages[J].IEEE Transaction On Image Processing,1995,IP-4(7):909-920.

[5]DAVIS G.A wavelet-based analysis of fractal image compression[J].IEEE Transactions on Image Processing,1998,7(2):141-154.

[6]DAVIS G.Adaptive self-quantization of wavelet subtrees:a wavelet-based theory of fractal images compression[C].SPIE Conf.on Mathematical Imaging:Wavelet application in Signal and Image Processing,San Diego:1995:265-279.

[7]WALLE A V D.Merging fractal image compression and wavelet transform methods[C].In Fractal Image Coding Analysis:A NATO Series Book,Yuval Fisher,Ed.New York:Springer Verlag,1996:523-597.

[8]KRUPNIK H,MALAH D,KARNIN E.Fractal representation of images via the discrete wavelet transform[C].In IEEE 18th Conference ofEE,Israel:1995,3:187-191.

[9]张宗念，马义德，余英林.基于方向性零树小波的分形图像编码[J]．电子科学学刊，2000，22(5):780-783.

[10]周艳，吴敏金.基于方向剖分的小波域分形图像压缩[J]．华东师范大学学报（自然科学版），2002，3(9)：20-23.

[11]谢鑫，马争鸣.基于小波系数零树结构的分形预测图像编码[J].中国图像图形学报，2000，5（11）：920-924.

[12]JACQUIN A E.Fractal image coding:A Review[J].Proc.of IEEE,1993,81(10):1451-1465.