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

小波图像编码和分形图像编码是两种不同的图像编码方法，二者各有其特点，又都存在一定的局限性[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可以近似于R_j，由此可以得到一组仿射变换组ψ₁，ψ₂…ψ_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 所示。具体过程是：