基于整数小波变换和嵌入零树的图像压缩算法

摘要:小波变换因其具有良好的时、频局部化性能,在图像压缩编码中得到广泛的应用。尤其提升小波的出现使无损压缩成为可能。该文采用整数小波对图像进行四级二维小波变换,根据系数特点介绍了一种小波零树的图像编码算法,给出了具体的算法编码实例,并用512×512的Lena图像对算法进行了仿真实验。

关键词:提升算法;整数小波;嵌入零树编码;图像压缩

中图分类号:TP317文献标识码:A 文章编号:1009-3044(2010)11-2724-03

An Image Compression Algorithm Based on Integer Wavelet Transform and Embedded Zerotree

ZHANG Chun-xiang,CHEN Xiao-long

(Jiangxi Tourism and Commerce Vocational College, Electrical and Mechanical Engineering Branch,Jiangxi 330100,China)

Abstract: Wavelet transform has got widely used in image compressing because of its good local characteristics in time and frequency domain. In particular, the realization of the lifting wavelet makes lossless compression possible. By using integer wavelet transform, one image is transformed into four scaling two dimension wavelet field. Besides, an image wavelet encoding arithmetic is introduced according to the character of wavelet coefficients, and a case study of the arithmetic coding is presented. Finally, a simulation is carried out with a Lena image of 512 ×512.

Key words: lifting algorithm,;interger wavelet; embedded zerotree encoding; image compression

近年来,人们对整数小波变换(IWT)在图像压缩领域中的应用研究越来越感兴趣。整数小波变换作为新一代图像压缩标准JPEG2000的核心部分已经得到广泛研究.Shapiro提出的零树编码[1]则是当前小波图像压缩算法中最常用的编码技术. IWT是一种有限精度的计算,又是整数到整数的变换。如果将整数小波变换与嵌入式零树编码有机地结合起来,不仅可以发挥整数小波变换的优点,还能大幅度提高图像的压缩效率。

在提升格式(lifting scheme)[2-3]下建立的整数小波变换具有变换可逆、整数存储及只有加减和移位运算等优点.可以将整数小波变换中截断取整看成对图像加噪的过程,从修改整数小波变换的角度改善了压缩效果,虽然改进了编码算法,但该算法立足于整数小波变换的调整,提高了编解码的复杂度和不可靠性。该文介绍了一种基于小波零树的无损图像压缩编码算法,并用提升方法对图像进行分解,对512×512的Lena图像进行算法仿真实验。

1 整数小波变换(IWT)

传统小波由同一母函数经过平移和伸缩运算后得到不同分辨率下的小波基函数。小波函数被定义为在L2(R ) 空间上的母小波 ψ(x ) 的二进伸缩和平移, 即小波函数为:ψi,k(x) =ψ(2ix- k) , 被称之为第1 代小波。在实际应用中第1 代小波存在一些问题: 1) 信号经过小波变换后产生的是浮点数, 受计算机有限字长的影响, 往往不能精确地重构信号; 2) 对图像的尺寸有要求, 并不能对所有尺寸的图像进行变换; 3) 对内存的需求量较大。这样构造的小波基函数难以得到其整数表示形式。为克服上述问题, 引入另外一种小波实现算法――“提升”算法[2]。

1.1 小波变换的“提升”算法

“提升”算法是由Wim Sweldens 等人提出的一种新的小波构造方法, 它在构造小波的方式上不是用傅里叶变换和基于傅里叶变换的尺度收缩, 而是直接通过简单地分裂、预测和更新等一系列步骤来完成对一列数字信号的变换。“提升”算法的基本思想是将现有的小波滤波器分解成基本的构造模块, 分步骤完成小波变换。因此, 可以将小波变换分解成3个过程: 分裂(split)、预测(predict) 和更新(update)。

1) 分裂。将输入信号si分为2个较小的子集si-1和d i-1, d i-1也称为小波子集。最简单的分裂方法是将输入信号s根据奇偶性分为2组, 对应于这种分裂所产生的小波被称之为懒小波(Lazy Wavelet) ,分裂过程表示为F(si) = (si-1, di-1) , 其中F(si)为分裂过程。

2) 预测。在基于原始数据相关性的基础上, 用偶数序列s i-1的预测值P (s i-1) 去预测(或者内插) 奇数序列d i-1, 即将滤波器P 对偶数信号作用以后作为奇信号的预测值, 奇信号的实际值与预测值相减得到残差信号。实际中, 虽然不可能从子集si-1中准确地预测子集d i-1, 但是P (s i-1) 有可能很接近d i-1, 因此可以使用P (s i-1) 和d i-1的差来代替原来的d i-1, 这样产生的d i-1比原来的d i-1包含更少的信息。于是得到

di-1 = d i-1- P(si-1)(1)

这里, 已经可以用更小的子集s i-1和小波子集di-1来代替原信号集si。重复分割和预测过程, 经n 步以后原信号集可用{sn , d n, … , s1, d1}来表示。

3) 更新。为了使原信号集的某些全局特性在其子集s i-1中继续保持, 例如, 希望分解后的子图像s i-1仍然保持原来整个图像的亮度值, 即s i-1和原图有相同的像素平均亮度值, 必须进行更新。更新的思想是要找一个更好的子集si-1, 使得它保持原图的某一标量特性Q (x ) (例如均值、消失矩等不变) , 即有Q (si-1) = Q (si)。可以利用已经计算的小波子集di-1对si-1进行更新, 从而使得后者保持特Q(x) ,即要构造一个算子U去更新si-1。定义如下:

si-1= si-1+ U (di-1) (2)

分解重构见图1。

1.2 整数小波变换[3-4,7]

基于提升算法的小波分解操作, 其输出结果仍然为小数。从式(1) 和(2) 可以看出, 输出结果的小数部分是由其中的“预测”和“更新”滤波器引入的, 对其取整即可得到整数变换结果, 取整操作相当于对原来的小波滤波器系数作了很小的改动,但是小波分解的特性仍然保留。具体公式为di-1= di-1- ?WP(si-1), s i-1= si-1+ ?WU(di-1),其中?Wx是取不大于x的最大整数运算。逆变换仅仅需要将上面“+ ”和“- ”号互换及顺序颠倒。

2 小波零树编码

2.1图像的小波变换与系数的分布特点[1,5]

根据提升小波的步骤对图像进行小波分解,图像分解后分割成四个频带:低频、水平、垂直和对角方向,低频部分可继续再分解。若把第一次分解得到的四个子图,记为LL1、HL1、LH1、HH1,第二次再对低频的LL1进行分解得到四个子图,记为LL2、HL2、LH2、HH2,依次类推直到满足要求为止。

图像经m级小波变换后得到不同分辨率的子图个数K=3m+1,各高频子图上的小波系数具有统计分布特性相似,系数间存在相关性。随着分解层数的增加,小波系数的范围越来越大,分辨率最低的子图LL的小波系数的范围最大;高分辨率子图上大部分数值接近于0,频率越高,系数的范围越接近于0,不为0的小波系数主要集中在LL低频带;对一幅图像来说,大部分信息保留在低频部分,高频部分只包含其对应图像边缘、轮廓等的细节信息。

2.2 图像小波系数的嵌入式零树编码

2.2.1零树的定义[6]

经过m级小波变换的小波图像,对于低频子图中的某一系数而言,与其对应的具有相同空间定位的高频子图中的系数称为是它的子孙,从图像的低频层开始依照子孙关系延伸,得到树形结构。图2是三级小波变换的系数树结构。小波零

树建立的假设基础:若在粗尺度下小波系数小于给定的阈值T,则在较细尺度下相同方向上的所有系数都几乎小于T。

2.2.2 EZW零树编码算法原理

零树编码是针对小波系数零树结构进行的,利用了小波系数的空间-频率局部化特性和级间系数幅值分布的相似性,通过阈值逐次减半方式实现逐级编码。

根据变换后的小波系数确定初始阈值T0=2INT(log2(max)),其中max为小波系数的最大值,INT为取整操作。根据阙值K将系数分为四种情况:P表示该系数绝对值大于等于门限且为正,N表示该系数绝对值大于等于门限且为负,T表示该系数不重要且它的所有后代不重要,Z表示该系数不重要但它的后代中有重要系数。为了利用不同尺度下子带的相关性,采用Z字形的顺序扫描。

EZW编码算法在一阈值下经过两个过程:主扫描(Dominant_pass)和副扫描(Subordinate_pass)。然后将阈值降为原来的一半,步骤同上。当阈值不断降低,就实现了逐次逼近的嵌入式编码。其过程可以描述为:

K = K0;

Do{

Dominant_pass(image);

Subordinate_pass(image);

K = K/2;

}while(K>0);

其中主扫描实现以下3项任务:

1) 按一定的顺序扫描小波系数,根据小波系数输出码流,设系数为x,当前阈值为K,其输出规则如下:

如果x>K,则输出P;

如果x

如果|x|〈K,且该系数后代中有重要系数,则输出Z;

如果|x|〈K,且该系数后代中没有重要系数,则输出T;

2) 将所有的重要系数抽取出来,其绝对值放入被称为附属表的一维数组中。

3) 在重要系数的位置处填零。

辅扫描根据附属表中存的系数输出0或者1,0表示系数在下半区,即K到3/2 K之间,1表示系数在上半区,即3/2 K到2K之间。附属表中的系数每次扫描结束根据重构值的大小重新排序。

最后当阈值K降为1时,根据主扫描和副扫描输出的码流就能无误的表示出所有系数的值。要实现无损压缩,还要对输出的码流进行熵编码,一般采用算术编码或者游程编码。

2.3 解码

解码是编码的逆过程。EZW解码仍然采用主扫面和副扫描。主扫描从数据流中载入主扫描代码来恢复系数的重要信息。采用与编码时保存系数重构位置的同样的扫描顺序是至关重要的。当碰到代码P或N,当前系数的位置加到辅助列表。当图像中的所有系数已被扫描,主扫描就停止。辅扫描从数据流中为辅助列表中的每个系数载入1比特。这个比特与当前阈值相乘后加到正系数上或从负系数中减去。当预定的性能指标达到或数据流已为空时,解码停止。

3 算法实例说明

图3是一幅8×8的图像经过3级分解后的小波系数,在此用它来说明EZW编码算法。其中Di为第i次主扫描编码结果,Si为i次副扫描。编码结果。编码结果如下:

D1:PNZTPTTTZTTTTTTPTT

S1: 1010

D2: ZTNPTTTTTTTT

S2: 100110

D3: ZZZZZZPPNPPNTTNNPTPTNTTTTTTTTPTTTTTTTPTTT

TTTTTTTTT

S3: 1010001111011011000

D4: ZZZZZZZTZTZNZZZZPTTPTPPTPNPTNTTTTTPTPNPP

PPTTTTTPTPTTTPNP

S4: 10111110110110100001110110100010010101100

D5: ZZZZZTZZZZZTPZZZTTPTTTTNPTPPTTPTTTNPPNT

TPTTPPTTT

S5: 111111010010100110111110100000010110100

00011011110011000111

D6: ZZZTTZTTTZTTTTTNNTTT

4 仿真实验结果及其结论

本文选用512×512的Lena图像进行了压缩编码实验。每个像素用一个字节表示,像素值的大小界于0到255之间。压缩编码过程为:先对图像进行整数小波变换,采用Daubechies(5,3)小波的提升算法实现,进行四级二维小波变换。然后进行EZW算法编码,最后对码流进行算术编码[7]。实验结果见表1,图4是实验原图,图5是不同压缩比下的重构图。

由实验结果观察可知,在压缩比为8:1时基本上和原图无差别;在压缩比为16:1时,视觉效果和原图有稍微差别,视觉效果较好,细节丰富。从图可以看出,小波变换有效地克服了传统余弦变换编码在不同压缩比下的方块效应,因此小波变换已经成为当今图像压缩编码的主要研究方向。

表1 EZW算法在不同比特率下的压缩性能

参考文献:

[1] Shapiro J M.Embedded Image Coding Using Zerotrees of Wavelet Coefficients[M].IEEE Transactions on Signal Processing,1993.

[2] Sweldens W.The lifting scheme:A custom-design construction of biorthogonal wavelets[J].Appl. Comput. Harmon. Anal,1996,3(2).

[3] Sweldens W.The lifting scheme:A construction of second generation wavelets, SIAM J.Math. Anal,1997,29(2).

[4] Adams M D.Reversible Integer-to-Integer Wavelet transforms for image compression: Performance evaluation and analysis[M].IEEE Transactions on Image Processing,2000.

[5] 白浩,刘於勋.一种改进的嵌入式图像压缩EZW编码算法[J].通信技术,2008(1)

[6] 张旭东,卢国栋,冯健.图像编码基础和小波压缩技术-原理、算法和标准[M].北京:清华大学出版社,2004.

[7] 闫凡勇,张颖.基于小波变换的图像压缩技术[J].电脑知识与技术,2010(3).