基于ADL小波变换的图像压缩算法

1、计 算 机 工 程 第 37 卷 第21期V ol.37 No.21 Computer Engineering文章编号：10003428(201121019903·图形图像处理·2011年11月November 2011文献标识码：A中图分类号：TP911.73基于ADL 小波变换的图像压缩算法林 娜，倪 林，刘 权(中国科学技术大学电子工程与信息科学系，合肥 230027摘 要：提出一种基于自适应方向提升(ADL小波变换的图像压缩算法。根据灰度共生矩阵角二阶矩的差异，将图像分割成平坦性不同的分块。对纹理信息较少的块，采用一般提升小波变换以减少变换时间。对纹理信息较多的块，

2、采用方向提升小波以提高变换效果。结合多级树集合分裂编码和算术编码对变换系数和方向信息分别进行编码。实验结果表明，与ADL 算法相比，该算法能有效减少方向小波变换时间。关键词：图像压缩；自适应方向提升；灰度共生矩阵；角二阶矩；多级树集合分裂Image Compression Algorithm Based on Adaptive Directional Lifting Wavelet TransformLIN Na, NI Lin, LIU Quan(Department of Electronic Engineering and Information Science, University

3、of Science and Technology of China, Hefei 230027, China 【Abstract 】Based on the general Adaptive Directional Lifting(ADL promotion transformation, this paper proposes an image compression algorithm based on ADL wavelet transform. Using this algorithm, the image is divided into flat and non flat bloc

4、k according to different angle second moment of Gray Level Co-occurrence Matrix(GLCM. For each block, the lifting scheme is adaptively selected to reduce the computation of directional lifting wavelet. For the flat blocks, it uses ordinary horizontal and the vertical promotion directly to reduce the

5、 time. For the non flat blocks, it uses the directional lifting wavelet to enhance the result. Experimental results show that this algorithm can dramatically reduce the computational time compared with the tradditional ADL method.【Key words】image compression; Adaptive Directional Lifting(ADL; Gray L

6、evel Co-occurrence Matrix(GLCM; angle second moment; Set Partition in Hierarchical Trees(SPIHT DOI: 10.3969/j.issn.1000-3428.2011.21.0681 概述离散小波变换提供了多分辨率的图像显示方式和完美的图像重构能力，被广泛应用于图像分析、压缩编码等领域，如静止图像压缩的国际标准JPEG2000。文献1提出了一种新的不依赖于傅里叶变换的小波构造方案提升小波变换，该方法不仅得到了一种新的小波变换，还减少了现有小波变换的计算复杂度。实践证明，所有的小波变换都可以通过提升方法实

7、现，因此，提升小波变换也被称为第2代小波变换。但一般的提升小波变换结果都是通过对图像的行/列进行一维提升变换得到的，只能处理水平和竖直方向上的图像信息。由于自然图像存在丰富的纹理信息，因此采用一般的提升方法不能很好地利用图像的纹理特征，处理后高频存在冗余，影响后续的工作。为解决这个问题，研究者们相继提出Contourlet 变换2、Curvelet 变换3、Bandelet 变换4等变换方法。这些方法都取得了很好的效果，但仍存在计算复杂度高、滤波器设计复杂等问题，导致在实际的压缩中，这些方法应用较少。近年来，学者们提出了方向提升变换5-6的方法，通过基于空间方向预测提升小波来实现小波的方向性，

8、并且降低计算复杂度。但是这种方向需要在做变换时进行插值运算，并且还要判断选择最优方向，运算量比较大。本文提出一种基于灰度共生矩阵7的自适应方向提升小波压缩算法，该算法结合方向提升的优点，将图像分为需要进行提升小波变换和方向提升小波变换的2个部分，在压缩比提高的同时降低算法运算的复杂度。2 图像纹理性分块本文使用灰度共生矩阵来自适应区分图像的纹理和非纹理部分，从而可对图像中的不同部分采取不同的提升方法。由于纹理是由灰度分布在空间位置上反复出现形成的，是相邻像素的灰度相关性的表现，因此在图像空间中相隔一定距离的两像素间也会存在一定的灰度关系，这种关系被称为是图像中灰度的空间相关性。共发矩阵就是基于

9、这种特性来描述成对象素的灰度组合分布，通过考察像素对出现的频率，构造一种条件概率来反映图像的纹理特征。共生矩阵的表达式的定义为：设f (x , y 为一幅二维数字图像，大小为M×N，灰度级别为N ，则满足一定空间关系的灰度共生矩阵可以定义为：p (i , j =count (x 1, y 1,(x 2, y 2 M ×N |f (x 1, y 1 =i , f (x 2, y 2 =j (1其中，count 表示统计的像素点数。若(x 1, y 1 与(x 2, y 2 间距离为d ，两者与坐标横轴的夹角为，则可以得到各种间距及角度的灰度共生矩阵P (i , j , d ,

10、 。通常方向为0°, 45°, 90°, 135° 4个方向。作者简介：林 娜(1987 ，女，硕士研究生，主研方向：视觉信息处理，图像压缩；倪 林，副教授、博士；刘 权，硕士研究生 收稿日期：2011-04-29 E-mail ：lin7453200 计 算 机 工 程 2011年11月5日 从共发矩阵抽中取纹理特征的定量值有2种常用度量7： (1角二阶矩ASMASM =P (i , j (2ij2h (m , n =x o (m , n P x e (m , n ，其中，P (.为预测算子。(2对比度度量CONCON =(i j 2P (i , j

11、(3i i(3更新。用h (m , n 来更新数据x e (m , n ，以保持原始数据x e (m , n 的某种特性。如保持平均值不变，该操作记为l (m , n =x e (m , n +U h (m , n ，其中，U (.为更新算子。 普通提升只是对图像在水平/垂直方向上做变换，但每个像素点不一定在水平和垂直方向上的相关性最强，因此，本文使用方向提升的方法。如图2代表1/4代表1/2点。假设点x (m , 2n+1 在图2中箭头所示方向上的点与预估计像素点的相关性最强。式(2和式(3中的求和都是在整个窗口进行。其中角二阶矩是一种对图像灰度分布均匀性的度量。当数值分布较集中于主对角线附

12、近时，其相对应的ASM 值较大，即灰度均匀，这种均匀是局部的均匀；反之，ASM 值则较小。这里用ASM 作为区分图像纹理和非纹理部分的标准。将图像分成16×16的小块，对每个分块计算它的共生矩阵和角二阶矩，利用式(4自适应判断图像的平坦性：1 ASM threshold(4 CH =0 ASM >threshold其中，阈值threshold 定义为图像的所有分块的角二阶矩的平均值，通过式(5得到。threshold =ASM i N =1M i , j j =1N ×M(5CH=1表示该分块有着很大的灰度变换，纹理比较丰富，需要采用方向提升才能很好减少高频部分；CH

13、=0表示该分块的灰度变化不大，比较平坦，可以采用一般的提升变换。利用本文方法对测试图Barbara(512×512像素 进行评估，得到测试图像的纹理分块图如图1所示，可以看到利用角二阶矩能有效地区分纹理和非纹理区域。图2 预测过程将原先的提升预测算子沿方向修正，即对提升部分进行如下改进：P x (m , n =p i x e (m +sign(i 1tg(, n +i (6ei其中，有多个方向上的点时位于非整数点上，需要插值得到需要位置上的点的值。本文采用sinc 函数来进行插值。更新过程和预测过程相似，将预测得到的系数以方向提升的方式来更新偶数行的值。更新算子由式(7取代。(a原图

14、 (b方向信息图U h (m , n =u j h (m +sign(j tg(, n +j (7j图1 测试图的方向信息图3 自适应方向预测提升变换一般的提升方法只是在水平和垂直方向上对图像进行变换，但由于变换提供的方向信息固定且有限，对图像中的非垂直或竖直方向的纹理信息不能很好地稀疏。ADL 的提升方法利用了图像中的纹理信息，解决了一般提升小波的问题。为得到更好的结果，通常选取很多的方向，通过一定的准则选取最优方向，这些方向上的点不一定是位于整数点的，需要通过插值来实现。这样无形地就增加了计算的复杂度和方向信息编码的开销。进行一般提升变换时会发现一个现象，在图像纹理比较多的地方，变换后的高

15、频分量会比纹理相对少的地方来的大。这就表明，在图像纹理多的地方可以用方向提升的方法，而在纹理比较少的地方使用一般提升方法，这样一来，不仅减少方向编码的位数，同时也在一定程度上减少了由于插值和判断最优方向所带来的一定计算量。3.1 提升算法提升小波的实现过程分为3个步骤：分裂，预测和更新。 (1分裂。可将原始数据x (m , n 分为2个集合：偶数集合x e (m , n 和奇数集合x o (m , n 。(2预测。保持偶数集合x e (m , n 不变，通过内插细分的方法预测奇数集合，预测值与实际值的差值为h (m , n ，即其中，U (.为更新算子。这里更新的方向与预测的方向一致。本文采用

16、CDF9/7小波的提升格式。3.2 方向预测为了减少计算量，不对图像的纹理部分的每个点进行方向预测，而是将纹理部分分成16×16像素的块，对每块依照一定的准则进行最优方向的判断。方向判断的准则为：对每个分块在9个方向上作提升变换，计算每个子块对应方向上高频能量之和，选取高频能量最小的方向作为这个分块的自适应变换方向。为了保证方向选择的正确性和减少一定的计算量，这里采用5/3小波来判断分块的方向。5/3小波的提升格式为：1000d l =d l (s l +s l +1 /2(8 1011s s (d d /41/2=+l l l 1l4 编码过程先用本文方法对图像进行提升变换，将变换

17、后的系数和方向信息分别采用Spiht 和自适应算术编码方法进行编码。编码过程和一般的Spiht 编码相同，只是增加了方向信息编码部分，并将其放在码流的开头。为能完全解码出图像的方向信息，本文采用算术编码对图像方向信息进行编码。虽然增加了方向信息的编码，但方向信息量相对于图像本身数据量较少，所以，增加的编码信息不多。每一级的变换都可以得到分块图像的变换方向，在作图像压缩时，要对这些方向林 娜，倪 林，刘 权：基于ADL 小波变换的图像压缩算法 第37卷 第21期 201 进行编码，相对于一般提升变换，这就增加了一定的计算量，但本文将图像分为纹理和非纹理部分，在变换时采用了不同的提升方向，从而减少

18、计算量和方向编码的信息。5 实验结果与分析笔者通过实验来验证本文方法的有效性。测试图像选择为Lena(512×512像素 和Barbara(512×512像素 图像。从变换后的高频部分的系数和能量平均值上，将本文方法和一般提升小波变换做比较。考虑变换后高频系数平均幅度和高频平均能量，比较变换后的第1层高频。本文方法和CDF9/7方法第1层高频子带能量和系数的平均值的比较结果如表1所示。表1 高频部分的平均熵值和能量比较图像平均熵值CDF9/7Lena 3.26 Barbara 6.31 Women 5.20本文方法高频能量CDF9/7本文方法(a原图 (bCDF9/7(cA

19、DL (d本文方法图3 Lena图像压缩效果比较2.94 3.6e+006 2.5e+006 4.55 1.3e+007 5.6e+006 4.67 6.0e+006 3.5e+006(a原图 (bCDF9/7可以看出，利用本文方法进行变换后高频能量显著减少，高频系数的平均幅度得到降低。如Barbara 图，它的高频分量的平均系数值下降到了4.55，能量也有大幅度的下降。其他的图像也有较明显的下降。这说明本文提出的方法能更好地自适应于图像的纹理信息，减少了图像变换后的信息冗余，为以后的压缩、去噪等提供有力的条件。改进后方法在计算复杂度上和ADL 5方法的实验结果比较如表2所示，主要比较特征是计

20、算时间。可以看到，运用本方法可有效减少运算时间，提高程序运行的效率。(cADL (d本文方法图4 Barbara图像压缩效果比较6 结束语本文提出了一种基于灰度共生矩阵图像分块的方向提升小波变换算法。通过灰度共生矩阵中的角二阶矩方法来自适应地检测图像的平坦性，每个分块自适应地选择提升小波变 表2 进行5级小波变换的计算时间比较 s换，从而减少算法复杂度。实验结果表明，该算法与传统方图像 ADL方法 本文方法Lena 6.34 4.05 向提升小波变换算法相比，在保证图像压缩性能前提下，能大幅减少计算时间。下一步工作将研究如何提高图像纹理性Barbara 6.30 4.10分块的准确性。 Wom

21、en 6.36 4.07Baboon 6.354.60参考文献对比3种算法的压缩性能峰值信噪比(Peak Signal toNoise Ratio, PSNR。将方向信息编码后放在码流的头部。由表3可以看出，尽管需要编码方向信息，但本文的方法和ADL 的压缩性能与CDF9/7小波相比较有非常明显的提高。而且在低比特率时，本文的算法优于ADL 。其原因在于，本文算法得到的方向信息少，因此，在低比特率的情况下效果较好。表3 PSNR比较 dB比特率/bppLenaCDF9/7 ADL 本文方法BarbaraCDF9/7 ADL 本文方法1 Sweldens W. The Lifting Schem

22、e: A New Philosophy in Biortho-gonal Wavelet ConstructionsC/Proc. of SPIE Conference on Wavelet Applications in Signal and Image Processing III. San Diego, USA: SPIE Press, 1995: 68-79.2 Do M N, Vetterli M. The Contourlet Transform: An EfficientDirectional Multiresolution Image RepresentationJ. IEEE Trans. on Image Processing, 2005, 14(12: 2091-2106.3 Starck J L, Candes E J, Donoho D L. The Curvelet Transform forImage DenoisingJ. IEEE Trans. on Image Processing, 2002, 11(6: 670-684.4 Pennec E L, Mallat S. Sparse Geometric Image Rep