图像压缩有无损压缩和有损压缩两种压缩方式。有损压缩能够获得较高的压缩比,广泛地应用于各种图像处理中,由于医学图像、遥感图像等获取成本很高,图像信息有着特殊用途,不能丢弃细节信息,需使用无损压缩。随着电子行业软硬件技术和网络的发展,人们对图像质量的要求日益提高,即使人们日常的生活照片(例如,孩子的成长照、风景照等),很多人也希望能够完整地保存下来,但是存储这些图像数据给存储设备和网络传输带来很大压力,而无损压缩能够在减小存储空间的同时不会丢失任何信息,能满足人们对图像品质要求,能够完整保存图像信息,所以无损压缩是必不可少的技术手段^[1]。

无损压缩是没有任何信息损失的压缩,即100%重建原图像,无损压缩的极限由其信息熵决定。图像的信息熵不一样,同一种算法对不同的图像压缩比就不一样。常见的无损压缩方法有游程编码、LZW编码、熵编码、预测编码等。本文采用小波变换结合SPIHT编码进行图像的压缩。 1 小波基的选择

正交变换能够有效地消除图像像素间的相关性,其中小波变换拥有很好的时-频特性,能很好地描述图像的频率特性,且不会出现离散余弦变换在低码率下的方块效应,能够获得相同位率下更好的压缩性能。在图像压缩应用中,小波基的正交性、紧支撑性、对称性、正则性和消失矩都是影响图像压缩效果的关键因素^[2,3]。选取时要对上述性质综合考虑,但还没有发现一个小波基对各种类型的图像都表现出最佳的能量压缩性能和最好的相关性的消除能力,通过大量实验研究人员还是找到了一些对各种情况总体上相对较好的小波基,例如用于有损压缩的Daubechies(9/7)(9/7中9和7分别表示小波分解和合成时系数的个数)小波基和用于无损压缩的Le Gall 5/3小波基。有损压缩能够获得较高的压缩比,在图像压缩中有着广泛的应用,因而对Daubechies(9/7)小波基的研究也非常多。无损压缩所能取得的压缩比十分有限,使得其应用有了一定的局限性,因而Le Gall 5/3小波基的研究相对就比较少^[4,5,6,7]。本文研究的是图像的无损压缩,选择综合性能相对较好的Le Gall 5/3整数小波作为小波变换的小波基。 2 Le Gall 5/3提升小波变换

Le Gall 5/3提升小波是2阶消失距的对称双正交小波^[2],5/3变换是整数到整数变换。基本思想是通过由基本小波(lazy wavelet)逐步构建出一个具有更加良好性质的新小波,其实现步骤有3 步:分解(split)、预测(predict)和更新(update)。分解是将数据分为偶数序列和奇数序列2个部分,预测是用分解的偶数序列预测奇数序列,得到的预测误差为变换的高频分量,更新是由预测误差来更新偶数序列,得到变换的低频分量。其正变换公式为^[2]

由于Le Gall 5/3整数小波变换在变换中只有加减法,虽然在取整的过程中由于正变换和逆变换都会出现0.5,但是由于在正变换中多(少)了0.5,相应的在逆变换就会少(多)了0.5,这样经过取整,误差为0,那么也就是实现了无损压缩^[4]。非整数的小波变换,例如有损压缩中应用广泛的Daubechies(9/7)小波,因其运算中涉及浮点运算而无法精确重建。

3 SPIHT编解码^[8]

图像数据经过二维小波变换后,小波系数数据量并没有减小,为进行压缩,需要对小波系数进行编码,编码主要根据小波系数之间的相关性。小波系数的相关性主要存在同一子带内,也存在于不同子带之间。SPIHT编码也主要是根据同一子带内以及不同子带间的相关性进行的。不同分解层间的相关性采用链表(树)形式进行组织。每一级的一个节点在下一级存在与之对应的4个节点,一般认为当前该节点重要,其后代对应的4个节点也重要。 4 算法解析

本文采用Le Gall 5/3提升小波对图像进行整数小波变换,用SPIHT算法对小波系数编码。图像压缩的基本流程如图 1所示。

图 1

Fig. 1

图 1 图像压缩编码流程 Fig. 1 Coding progress of image compression

小波变换把图像信号分解成为4个信号:低频子带LL和3个方向的信号。3个方向信号又分为水平方向HL,垂直方向LH和对角线方向HH,再次分解低频子带LL又可得到四个子带(LL、HL、LH、HH)。所以总的子带数为3K+1,其中K为小波分解阶数。图像做小波分解时,分解到什么程度才能达到最佳的压缩效果,要根据图像的复杂度和滤波器的长度来确定的。从子带的信息熵可以进行定量的确定。一个子带分解成4个子带的熵的和如果不比原子带的熵就不值得分解了,例如信号X的熵定义为

如果给定子带S_K要进一步分解成S_K+1、W_K+1¹、W_K+1²、W³_K+1 4个子带,它们的熵分别记为H(S_K+1),H(W_K+1¹),H(W_K+1²),H(W_K+1³),由于熵和编码所需的比特数直接对应,为了实现图像的压缩,分解后的四个子带编码所需的比特数应小于分解前的子带编码所需的比特数,即有

小波的分解和重构都是建立在假设数据双向无限的,由于计算机的处理能力有限,处理的数据也一定是有限的,这样会在图像的边界部分产生边界效应,即产生很大的失真。因此有必要对图像数据的边界进行延拓,增加图像数据的长度和宽带,使得边界延拓到图像数据的外围,避免对图像数据产生噪声。常用小波边界延拓包括有:补零、光滑常数延拓、周期延拓和对称延拓。实际处理中对称延拓和周期延拓应用较多。一般来说由小波基的性质来选择延拓方法,如果小波基是对称的,选用对称延拓就比较合适。Le Gall 5/3小波的小波基是对称的双正交小波,因此本文算法采用对称延拓。例如,假设原始序列为x(0),x(1),x(2),…,x(2n－1),通过提升变为两个长度均为n的序列。要计算 c(2n-1)需要补x(2n),而计算d(0)需要补c(-1),计算c(-1)需要补x(-1),x(-2)。因此考虑到边界问题,需要在序列的前补两个,后补一个。采用对称延拓,即为

x(1),x(0),x(0),x(1),x(2),…,x(2n－1),x(2n),x(2n)。

从信息论来讲,无损压缩所能达到最大压缩效率是由图像的信息熵H(x)决定的。但是无损压缩到底能做什么程度,现在还没有有效的方法来做出准确的预测。由于图像的像素之间存在着强烈的相关性,使得精确计算图像信息熵几乎难以实现^[10]。文献^[10]利用多尺度条件熵和记忆性度量来估计图像无损压缩的极限,实现起来有一定的难度,不同图像高阶熵模型不尽相同,可信度较高的全位面条件熵不容易计算。文献^[11]提出了另一种粗略评估方法,因为正交变换具有去相关的性质,对图像数据做正交变换能够在一定程度上去除数据间相关性,而正交变换并不会改变数据的信息熵,完成正交变换的图像数据的统计特性近似符合高斯分布,高斯分布的各个样本近似于相互独立,可以用计算变换后系数的一阶熵来近似图像数据的信息熵。文献^[11]中采用计算离散小波变换(discrete wavelet transform,DWT)系数的N阶熵,在这里计算图像的1阶熵到5阶熵。选用6幅标准测试灰度图像如表 1所示。

表 1(Table 1)

表 1 图像熵 Tab. 1 Image entropy 熵阶 熵值 图2(a)Barbara 图2(b)Goldhill 图2(c)Bridge 图2(d)Baboon 图2(e)Boats 图2(f)Lena 图像一阶熵 7.632 1 7.477 8 5.792 2 7.357 9 7.123 8 7.445 5 DWT一阶熵 5.635 9 5.355 5 4.317 8 6.313 9 5.031 5 4.975 0 DWT二阶熵 5.260 8 4.946 4 3.972 5 6.158 3 4.641 8 4.477 6 DWT三阶熵 5.171 8 4.865 6 3.894 0 6.123 9 4.572 8 4.378 3 DWT四阶熵 5.154 2 4.849 1 3.875 2 6.114 2 4.557 8 4.358 8 DWT五阶熵 5.150 8 4.845 0 3.870 5 6.110 8 4.554 3 4.354 6

表 1 图像熵 Tab. 1 Image entropy

图像的一阶熵

图像的二阶熵

以上各阶熵只是对图像信息熵的粗略估计,由于小波变换不能完全消除图像像素间的相关性,实际上图像的信息熵要低于我们计算的熵。 5 实验分析

选择6幅常用标准测试灰度图像,对本文算法进行实验分析,6幅图像如图 2所示。可以看出图 2(a)Barbara、图 2(b)Goldhill、图 2(d)Baboon的内容细节信息较为丰富,含有大量的纹理信息,较难获得较高压缩比,图 2(c)Bridge的细节信息较少,图像内容较为简单,一般来说能获得较好的压缩比,图 2(e)Boats和图 2(f)Lena是图像处理人员常用的测试图像,纹理信息和结构信息均较为适中,很具有代表性,相应的压缩处理时所能获得的压缩性能也较为中庸。

图 2

Fig. 2

图 2 标准测试图像 Fig. 2 Standard test images

测试硬件环境为ThinkPad T400,操作系统为Windows XP SP3,软件环境为Visual Studio6.0,编程语言为C语语言。上述六幅图像均为512×512,8 bits的灰度图像。

测试了上述图像在Le Gall 5/3整数提升小波在小波阶数从2到8阶的无损压缩比和程序运行时间,测量值如图 3、图 4所示。

图 3

Fig. 3

图 3 6幅图像达到的压缩比 Fig. 3 Compression ratio of six images

图 4

Fig. 4

图 4 压缩6幅图像各自消耗的时间 Fig. 4 Consumed time of image compression

从图 3中,可以看出小波分解阶数达到4阶后,再增加小波分解阶数所带来的压缩比提升极为有限,而过高时反而略有下降,这是因为图像所含纹理信息量不同,数据间的依赖关系也不同。从表 1的数据可以看出除了纹理信息最为丰富的图 2(d)Baboon外,其他图像均5阶小波分解达到最优压缩效果。图 2(d)Baboon的内容较为丰富,含有大量纹理信息,为了更好表示图像信息需要的小波分解阶数也较多,在6阶分解时达到最优压缩效果。SPIHT算法利用了子带内部和子带之间的相关性,当小波分解过多时,效果会受到影响。从图 4中,可以看出随着小波分解阶数的增加,算法消耗的时间也相应增加,从表 2的数据中可以看出时间消耗的增加并不显著。纹理信息最少的图 2(e)Bridge需要的运行时间最少,纹理信息最为丰富的图 2(d)Baboon需要的运行时间最多。从处理各幅图像所用时间来看,该算法完全可以满足实时处理的需要,在降低存储空间的同时,图像质量丝毫没有受到影响。

表 2(Table 2)

表 2 各阶小波分解所得压缩比 Tab. 2 Compression ratio with wavelet transform of different order 小波分解阶数 压缩比 图 2(a)Barbara 图2(b)Goldhill 图2(c)Bridge 图2(d)Baboon 图2(e)Boats 图2(f)Lena 2阶分解 1.442 901 1.474 429 1.777 077 1.213 382 1.573 858 1.597 477 3阶分解 1.514 619 1.528 788 1.777 077 1.213 382 1.639 587 1.660 273 4阶分解 1.525 367 1.536 537 1.872 01 1.250 022 1.650 24 1.680 526 5阶分解 1.525 541 1.537 204 1.887 23 1.256 366 1.649 778 1.681 712 6阶分解 1.524 733 1.536 891 1.886 875 1.256 512 1.648 022 1.680 355 7阶分解 1.524 241 1.536 497 1.885 213 1.255 318 1.647 346 1.679 596 8阶分解 1.524 161 1.536 013 1.884 208 1.254 900 1.646 901 1.679 258

表 2 各阶小波分解所得压缩比 Tab. 2 Compression ratio with wavelet transform of different order

表 3(Table 3)

表 3 压缩各幅图像消耗时间 Tab. 3 Consumed time of compression image 小波分解阶数 压缩时间/s 图2(a)Barbara 图2(b)Goldhill 图2(c)Bridge 图2(d)Baboon 图2(e)Boats 图2(f)Lena 2阶分解 0.578 0.578 0.531 0.656 0.578 0.578 3阶分解 0.593 0.609 0.562 0.671 0.593 0.593 4阶分解 0.609 0.609 0.562 0.671 0.593 0.593 5阶分解 0.625 0.609 0.562 0.678 0.593 0.593 6阶分解 0.625 0.625 0.562 0.687 0.609 0.593 7阶分解 0.625 0.625 0.578 0.703 0.609 0.609 8阶分解 0.640 0.625 0.578 0.703 0.609 0.609

表 3 压缩各幅图像消耗时间 Tab. 3 Consumed time of compression image

介绍Le Gall 5/3整数小波变换和SPIHT算法,并将其用于图像的无损压缩,对压缩过程中小波变换对图像边缘的影响加以讨论,确定了周期延拓的方案,以降低图像边缘部分的失真。对无损压缩的极限进行了讨论,利用正交变换不改变图像信息熵的特性,把图像数据经过正交变换后求其熵,对图像信息熵粗略估计,对无损压缩极限进行了粗略预测。选取六幅标准图像对该算法加以验证分析,从时间消耗和压缩效果两个方面来看,该种算法具有广泛的应用价值。