基于9-7整数小波零树的分形压缩算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于9-7整数小波零树的分形压缩算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：对分形压缩编码进行了研究，提出了基于9-7整数小波零树的改进的分形算法。它首先对图像整数小波分解，然后对于分形编码，针对小波高频系数无直流分量的特点 ,通过加入误差校正矩阵,减少了误差累积现象。实验结果表明相对于经典的分形和零树混合编码方式,在图像比特率方面和压缩比上,都有很大的提高。
关键词：分形图像编码；整数小波；零树
中图分类号：TP391 文献标识码：A文章编号：1009-3044(2007)12-21693-02
The Fractal Image Coding Based on 9-7-tap Integer Wavelet Zerotree
GAO Shang-bing,YAN Yun-xiang,ZHAO Wen-dong,Ma Dai
(Department of Computer engineering，Huaiyin Institute ofTechlonogy，Huaiyin 223001，China)
Abstract: On the research of fractal image coding, this paper presents an improved fractal coding algorithm on the basis of 9-7-tap integer wavelet zerotree. In the improved algorithm, at first the image is decomposed by using integer wavelet, then on the fractal coding ,we change the conventional MSE because we use the error emendation matrix to revise wavelet coefficient. The result presented in the paper show that there are a higher compressing rate and PSNR of the image than the classic fractal and zerotree mixed coding method.
Key words:fractal image coding;integer wavelet;zerotree
1 引言
目前分形零树的混合编码一般利用零树 结构，即先把图像的小波系数分解成互不交叠的图像树集合和有交叠的相似树集合，然后在相似树集合中寻找与图像树最佳分形匹配的相似树。图像经小波变换后所表示出来的同方向、不同分辨率的子带图像的相似性，为分形 编码提供了很大的扩展空间，而图像经小波变换后所表示出来的能量分布特点同样也为零树编码打下了基石。比如基于小波系数零树结构的分形预测图像编码 提出了一种基于小波系数零树结构的分形预测图像编码方法，首先按照零树结构在同方向不同分辨率的各子带图像上确定要预测的图像块，将这些图像块串起来构成一棵与零树相类似的图像树，然后，对每一图像块，在同方向低一级分辨率子带图像上寻找与其最佳分形匹配的相似块，而这些相似块也按照零树结构上下延伸，以产生多棵相似树，其中与图像树最接近的相似树就是图像树的预测树。但是这种方法仅仅利用了小波系数的第二个特点，即同方向多级小波子带之间具有相似性，忽略了真正意义上的零树。因此提出了一种新的分形零树混合编码。
2 基于小波系数分类的分形零树混合编码
2.1 选取9-7滤波器，通过提升方案构造9-7整数小波
小波零树一般采用的是离散小波变换（DWT）即第一代小波变换,该变换运算量较大，产生的是浮点数，由于计算机有限字长的影响，往往不能精确重构信号，同时也浪费了大量的时间。而整数小波变换不仅继承了第一代小波的多分辨率分析的优点，而且逆变换实现简单、快速和直接；意义很明确，边界处理很容易,能够很好地实现信号的重构。因此可以采用提升结构的可逆整数小波变换。
构造整数变换的提升算法主要分为三个步骤：分裂(split)，预测(predict)和更新(update) 。
其中分裂：信号按照其序数的奇偶性分为两组
xe[n]=x[1n], x0[n]=x[2n+1] （1）
预测：将滤波器P作用于偶信号xe[n]，得到奇信号的预测值，再将该预测值与奇信号x0[n]相减，得到奇信号的预测误差d[n]。
d[n]=x0[n]-P(xe[n]) （2）
更新：将滤波器U作用于奇信号的预测误差，然后用来对偶信号进行校正。
c[n]=xe[n]+U(d[n])（3）
双正交（9，7）小波基具有良好的能量集中性，消失矩较大，适用于有损压缩，因此选用（9，7）小波基。图1即（9，7）小波基的提升方案。图中α=-1.586134342,β=-0.0529801185,γ=0.8829110762,δ=0.4435068522,ζ=1.149604398。
图1 （9，7）小波基的提升方案
2.2 小波系数特征结构分析
一副图像经过三级小波分解后形成了十个子带，如图2所示。小波系数的分布特点是越往低频子带系数值越大，包含的图像信息越多，如图2中的LL3子带。而越往高频子带系数值越小，包含的图像信息越少。就是在数值相同的情况下，由于低频子带反映的是图像的低频信息，对视觉比较重要，而高频子带反映的是图像的高频信息，对视觉来说不太重要。这样对相同数值的系数选择先传较低频的系数的重要比特，后传输较高频系数的重要比特。
图2 三级小波分解图
2.3 算法过程
零树是一种数据结构，一个小波系数x，对于给定的门限T，如果|x|
其核心算法编码步骤为：
(1)对图像进行M级小波变换，产生3M +1个子带图像；
(2)最低分辨率的子带图像 (LL1，HL1，LH1，HH1)，其占有90%的能量，且是分形预测的基础，采用无失真或失真较少的图像编码方法来编码；
(3)对于HL方向上依据零树结构分解成一棵棵小波树，设置门限T，识别出零树、孤立零和重要系数。对于小波零树，不进行传输；对于孤立零，我们引入一种新的处理方式，设置误差矩阵，每个误差矩阵的大小和小波子带的大小相同，在孤立零的相应位置存储孤立零；对于重要系数，按以下步骤进行分形预测编码：
首先，图像树R和相似树D的划分。图像树R为经门限T判别后剩余的非零树，由于在步骤(2)中低频部分 (HL1)采用无失真或失真较少的图像编码方法来编码，那么在分形预测编码中不参与编码，所以图像树R是从HL2中 2×2块开始的小波树；依据分形预测编码的思想，相似树D是从HL1中 2×2块开始的有重叠的小波树，由于最高频部分不参与图像树的相似匹配，则相似树D不包含最高频部分，如图3所示。
图3 图像树R和相似树D
其次，分形匹配。由于进行分形预测的小波子带处于高频部分，不包含直流分量，故选取距离误差为：
对于每个选定图像树R的每一级子带依据最佳分形匹配原则找到相应的子带相似块，并由该相似块依据小波树结构形成相似树D，由于图像树R包括不同频率的小波子带，对于 的所有小波子带可能形成多个不同的相似树D，分别计算图像树R和多个不同相似树D之间的距离，误差最小的相似树就是图像树R的分形预测相似树。虽然这种距离误差的选取避免了偏移量，但是这种基于小波系数的分形预测编码过程是由低分辨率子带分形预测高分辨率子带的过程，就不可避免的出现误差累积现象，会大大影响图像恢复质量，为了避免这种现象，我们可以充分利用存储孤立零的误差校正矩阵。根据上面我们得到的图像树和对应的相似树以及压缩因子S，可以求得误差矩阵，由前面设定的门限T，找到该误差矩阵中大于门限T的值，存储到误差校正矩阵中的相应位置，由于孤立零和重要系数是不重叠的，那么对应的误差校正值也不会重叠。这样该相似树所处的位置以及相应的分形变换S以及误差校正矩阵就是该图像树R的分形预测码。
最后，找到所有图像树的最佳匹配相似树，并存储相应的分形预测码，完成了该方向上的重要小波系数的编码，还应该存储该方向上的误差校正矩阵，这样就完成了该方向整体小波系数的编码。
解码步骤：
(1)恢复低频子带图像。
(2)根据分形传输的相似树D的位置找到低频子带图像(HL1,LH1,HH1)中相似块，由分形迭代得到高一级分辨率子带图像。
(3)对于得到的高一级分辨率子带图像，由解
码步骤(2)得到更高一级分辨率子带图像，直到得到所有的小波系数。这样得到的只是重要小波系数，加入存储的误差校正矩阵，就完成了整个小波系数的解码。
(4) 在LH方向按编码步骤(3)进行编码。
(5) 在HH方向，由于HVS特性，可以把编码步骤(3)中的门限T适当进行调整，使得T增大， 或者根据不同的压缩效果把所有的HH方向的小波系数置零。
3 实验结果
以下在PIV2.0G/256M计算机上通过Matlab实现程序，以512*512*8bit标准图像Lena为例进行3层小波分解，改进算法与文献算法做比较，实验结果如图4，表1。
图4 标准图像(Lena)恢复效果对照
表1编码结果比较
图4是在两个算法在恢复后的图像PSNR值几乎相等的情况（文献算法PSNR=30.37，改进算法是30.31）下图像的恢复效果对照图，可以看出在PSNR值几乎一样的情况下，本文算法的恢复后的图像比文献算法恢复的图像的压缩比大得多。
由表1可见，本方法与文献[3]相比，在基本相
同的信噪比情况下，图像压缩比大大提高了，在基本相同压缩比情况下，图像信噪比提高了，而且在保证图像的主观效果下，压缩比更是大大提高。
4 结束语
本文以分层树集合分割排序(SPIHT)编码算法为基础，对图像三层9-7整数小波变换以后先对图像数小波分解，然后对于分形编码，针对小波高频系数无直流分量的特点,改变了传统误差距离的选取,通过加入误差校正矩阵,减少了误差累积现象。但是还有一些需改进的地方，比如重要小波系数的排列次序，这有待进一步研究。
参考文献:
[1]Shapiro J M. Embedded image coding using zerotree of wavelet coefficients. IEEE Trans. Signal Processing, 1993,41(12):3445-3462.
[2] Arnaud E. Jacquin, Fractal Image Coding: A Review[J].IEEE Transcations on Image Processing, October 1993,VOL.81,NO.10:1451-1465.
[3]谢鑫,马争鸣.基于小波系数零树结构的分形预测图像编码[J],中国图像图形学报,2000,5A(11) :920- 924.
[4]W. Sweldens. The lifting scheme :A construction of second generation wavelets[R].Technical Report 1995:6, Industrial Mathematics Initiative，Department of Mathematics, University of South Carolina,1995.
“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”