论文部分内容阅读
摘要：对一种无损压缩算法进行了研究，该算法采用整数小波对图像数据进行变换，对小波子带数据进行多级树集合分裂排序（set partitioning in hierarchical trees，SPIHT）编码，实现图像的无损压缩。探讨了图像无损压缩的极限问题，并对图像信息熵进行了估算。采用六幅标准灰度图像对该算法的压缩效果和时间消耗进行测试，结果证明，该算法运算速度快，并能获得较高的压缩比具有一定的实用价值。
关键词：无损图像压缩； 整数小波； 多级树集合分裂排序
中图分类号： TP 911 文献标志码： A doi： 10.3969/j.issn.1005-5630.2015.01.012
Abstract：This paper studied a lossless compression algorithm. The algorithm transforms the image data by integer wavelet， achieving lossless compression with coding wavelet sub-band data with set partitioning in hierarchical trees （SPIHT）. The limitation of lossless image compression is probed and image information entropy is estimated. Six pieces of standard grayscale images are used to test the compression algorithm and evaluate time consuming. The results of simulation show that it has fast rate， and can obtain a higher compression ratio. Thus， the algorithm is practical.
Keywords：lossless image compression； integer wavelet； set partitioning in hierarchical trees（SPIHT）
引 言
图像压缩有无损压缩和有损压缩两种压缩方式。有损压缩能够获得较高的压缩比，广泛地应用于各种图像处理中，由于医学图像、遥感图像等获取成本很高，图像信息有着特殊用途，不能丢弃细节信息，需使用无损压缩。随着电子行业软硬件技术和网络的发展，人们对图像质量的要求日益提高，即使人们日常的生活照片（例如，孩子的成长照、风景照等），很多人也希望能够完整地保存下来，但是存储这些图像数据给存储设备和网络传输带来很大压力，而无损压缩能够在减小存储空间的同时不会丢失任何信息，能满足人们对图像品质要求，能够完整保存图像信息，所以无损压缩是必不可少的技术手段[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-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所示。
4.1 小波变换的阶数[2]
小波变换把图像信号分解成为4个信号：低频子带LL和3个方向的信号。3个方向信号又分为水平方向HL，垂直方向LH和对角线方向HH，再次分解低频子带LL又可得到四个子带（LL、HL、LH、HH）。所以总的子带数为3K+1，其中K为小波分解阶数。图像做小波分解时，分解到什么程度才能达到最佳的压缩效果，要根据图像的复杂度和滤波器的长度来确定的。从子带的信息熵可以进行定量的确定。一个子带分解成4个子带的熵的和如果不比原子带的熵就不值得分解了，例如信号X的熵定义为
4.2 小波变换的图像边缘延拓[9]
小波的分解和重构都是建立在假设数据双向无限的，由于计算机的处理能力有限，处理的数据也一定是有限的，这样会在图像的边界部分产生边界效应，即产生很大的失真。因此有必要对图像数据的边界进行延拓，增加图像数据的长度和宽带，使得边界延拓到图像数据的外围，避免对图像数据产生噪声。常用小波边界延拓包括有：补零、光滑常数延拓、周期延拓和对称延拓。实际处理中对称延拓和周期延拓应用较多。一般来说由小波基的性质来选择延拓方法，如果小波基是对称的，选用对称延拓就比较合适。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）。因此考虑到边界问题，需要在序列的前补两个，后补一个。采用对称延拓，即为
4.3 图像无损压缩的极限讨论
从信息论来讲，无损压缩所能达到最大压缩效率是由图像的信息熵H（x）决定的。但是无损压缩到底能做什么程度，现在还没有有效的方法来做出准确的预测。由于图像的像素之间存在着强烈的相关性，使得精确计算图像信息熵几乎难以实现[10]。文献[10]利用多尺度条件熵和记忆性度量来估计图像无损压缩的极限，实现起来有一定的难度，不同图像高阶熵模型不尽相同，可信度较高的全位面条件熵不容易计算。文献[11]提出了另一种粗略评估方法，因为正交变换具有去相关的性质，对图像数据做正交变换能够在一定程度上去除数据间相关性，而正交变换并不会改变数据的信息熵，完成正交变换的图像数据的统计特性近似符合高斯分布，高斯分布的各个样本近似于相互独立，可以用计算变换后系数的一阶熵来近似图像数据的信息熵。文献[11]中采用计算离散小波变换（discrete wavelet transform，DWT）系数的N阶熵，在这里计算图像的1阶熵到5阶熵。选用6幅标准测试灰度图像如表1所示。
以上各阶熵只是对图像信息熵的粗略估计，由于小波变换不能完全消除图像像素间的相关性，实际上图像的信息熵要低于我们计算的熵。
5 实验分析
选择6幅常用标准测试灰度图像，对本文算法进行实验分析，6幅图像如图2所示。可以看出图2（a）Barbara、图2（b）Goldhill、图2（d）Baboon的内容细节信息较为丰富，含有大量的纹理信息，较难获得较高压缩比，图2（c）Bridge的细节信息较少，图像内容较为简单，一般来说能获得较好的压缩比，图2（e）Boats和图2（f）Lena是图像处理人员常用的测试图像，纹理信息和结构信息均较为适中，很具有代表性，相应的压缩处理时所能获得的压缩性能也较为中庸。
测试硬件环境为ThinkPad T400，操作系统为Windows XP SP3，软件环境为Visual Studio6.0，编程语言为C语语言。上述六幅图像均为512×512，8 bits的灰度图像。
测试了上述图像在Le Gall 5/3整数提升小波在小波阶数从2到8阶的无损压缩比和程序运行时间，测量值如图3、图4所示。
从图3中，可以看出小波分解阶数达到4阶后，再增加小波分解阶数所带来的压缩比提升极为有限，而过高时反而略有下降，这是因为图像所含纹理信息量不同，数据间的依赖关系也不同。从表1的数据可以看出除了纹理信息最为丰富的图2（d）Baboon外，其他图像均5阶小波分解达到最优压缩效果。图2（d）Baboon的内容较为丰富，含有大量纹理信息，为了更好表示图像信息需要的小波分解阶数也较多，在6阶分解时达到最优压缩效果。SPIHT算法利用了子带内部和子带之间的相关性，当小波分解过多时，效果会受到影响。从图4中，可以看出随着小波分解阶数的增加，算法消耗的时间也相应增加，从表2的数据中可以看出时间消耗的增加并不显著。纹理信息最少的图2（e）Bridge需要的运行时间最少，纹理信息最为丰富的图2（d）Baboon需要的运行时间最多。从处理各幅图像所用时间来看，该算法完全可以满足实时处理的需要，在降低存储空间的同时，图像质量丝毫没有受到影响。
6 结 论
介绍Le Gall 5/3整数小波变换和SPIHT算法，并将其用于图像的无损压缩，对压缩过程中小波变换对图像边缘的影响加以讨论，确定了周期延拓的方案，以降低图像边缘部分的失真。对无损压缩的极限进行了讨论，利用正交变换不改变图像信息熵的特性，把图像数据经过正交变换后求其熵，对图像信息熵粗略估计，对无损压缩极限进行了粗略预测。选取六幅标准图像对该算法加以验证分析，从时间消耗和压缩效果两个方面来看，该种算法具有广泛的应用价值。
参考文献：
[1] ALARABEYYAT A，AL-HASHEMI S，KHDOUR T，et al.Lossless image compression technique using combination methods[J].Journal of Software Engineering and Applications，2012，5（10）：752-763.
[2] 周兵，李波，李炜.小波图像编码器研究进展[J].计算机科学，2002，29（1）：57-62.
[3] 武永红.基于小波变换的图像无损压缩算法研究[D].重庆：重庆大学，2012.
[4] 闫红梅，李科，吴东梅.SPIHT的超光谱图像无损压缩算法[J].西安科技大学学报，2009，29（5）：598-602.
[5] 张宁，吴银花，金龙旭，等.适于航天应用的高速SPIHT图像压缩算法[J].液晶与显示，2011，26（6）：847-852.
[6] 陈斌，崔志明.JPEG2000的Le Gall（5，3）有损压缩重构优化[J].计算机应用，2006，26（5）：1048-1050.
[7] 姜会亮，胡学龙，郭振民，等.整数（5，3）小波变换结合SPIHT的无损图像压缩[J].计算机工程与应用，2005，41（14）：69-70.
[8] SAID A，PEARLMAN W A.A new，fast and efficient image codec based on set partitioning in hierarchical trees[J].IEEE Transactions on Circuits and Systems for Video Technology，1996，6（3）：243-250.
[9] 潘志刚.低比特率合成孔径雷达数据压缩算法研究[D].北京：中国科学院研究生院，2006.
[10] 张宁，章毓晋，刘青棣，等.利用多尺度条件熵和记忆性度量估计图像无损压缩极限[J].清华大学学报（自然科学版），2000，40（9）：32-36.
[11] CALDERBANK A R，DAUBECHIES I，SWELDENS W，et al.Wavelet transforms that map integers to integers[J].Applied and Computational Harmonic Analysis，1998，5（3）：332-369.
（编辑：程爱婕）
关键词：无损图像压缩； 整数小波； 多级树集合分裂排序
中图分类号： TP 911 文献标志码： A doi： 10.3969/j.issn.1005-5630.2015.01.012
Abstract：This paper studied a lossless compression algorithm. The algorithm transforms the image data by integer wavelet， achieving lossless compression with coding wavelet sub-band data with set partitioning in hierarchical trees （SPIHT）. The limitation of lossless image compression is probed and image information entropy is estimated. Six pieces of standard grayscale images are used to test the compression algorithm and evaluate time consuming. The results of simulation show that it has fast rate， and can obtain a higher compression ratio. Thus， the algorithm is practical.
Keywords：lossless image compression； integer wavelet； set partitioning in hierarchical trees（SPIHT）
引 言
图像压缩有无损压缩和有损压缩两种压缩方式。有损压缩能够获得较高的压缩比，广泛地应用于各种图像处理中，由于医学图像、遥感图像等获取成本很高，图像信息有着特殊用途，不能丢弃细节信息，需使用无损压缩。随着电子行业软硬件技术和网络的发展，人们对图像质量的要求日益提高，即使人们日常的生活照片（例如，孩子的成长照、风景照等），很多人也希望能够完整地保存下来，但是存储这些图像数据给存储设备和网络传输带来很大压力，而无损压缩能够在减小存储空间的同时不会丢失任何信息，能满足人们对图像品质要求，能够完整保存图像信息，所以无损压缩是必不可少的技术手段[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-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所示。
4.1 小波变换的阶数[2]
小波变换把图像信号分解成为4个信号：低频子带LL和3个方向的信号。3个方向信号又分为水平方向HL，垂直方向LH和对角线方向HH，再次分解低频子带LL又可得到四个子带（LL、HL、LH、HH）。所以总的子带数为3K+1，其中K为小波分解阶数。图像做小波分解时，分解到什么程度才能达到最佳的压缩效果，要根据图像的复杂度和滤波器的长度来确定的。从子带的信息熵可以进行定量的确定。一个子带分解成4个子带的熵的和如果不比原子带的熵就不值得分解了，例如信号X的熵定义为
4.2 小波变换的图像边缘延拓[9]
小波的分解和重构都是建立在假设数据双向无限的，由于计算机的处理能力有限，处理的数据也一定是有限的，这样会在图像的边界部分产生边界效应，即产生很大的失真。因此有必要对图像数据的边界进行延拓，增加图像数据的长度和宽带，使得边界延拓到图像数据的外围，避免对图像数据产生噪声。常用小波边界延拓包括有：补零、光滑常数延拓、周期延拓和对称延拓。实际处理中对称延拓和周期延拓应用较多。一般来说由小波基的性质来选择延拓方法，如果小波基是对称的，选用对称延拓就比较合适。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）。因此考虑到边界问题，需要在序列的前补两个，后补一个。采用对称延拓，即为
4.3 图像无损压缩的极限讨论
从信息论来讲，无损压缩所能达到最大压缩效率是由图像的信息熵H（x）决定的。但是无损压缩到底能做什么程度，现在还没有有效的方法来做出准确的预测。由于图像的像素之间存在着强烈的相关性，使得精确计算图像信息熵几乎难以实现[10]。文献[10]利用多尺度条件熵和记忆性度量来估计图像无损压缩的极限，实现起来有一定的难度，不同图像高阶熵模型不尽相同，可信度较高的全位面条件熵不容易计算。文献[11]提出了另一种粗略评估方法，因为正交变换具有去相关的性质，对图像数据做正交变换能够在一定程度上去除数据间相关性，而正交变换并不会改变数据的信息熵，完成正交变换的图像数据的统计特性近似符合高斯分布，高斯分布的各个样本近似于相互独立，可以用计算变换后系数的一阶熵来近似图像数据的信息熵。文献[11]中采用计算离散小波变换（discrete wavelet transform，DWT）系数的N阶熵，在这里计算图像的1阶熵到5阶熵。选用6幅标准测试灰度图像如表1所示。
以上各阶熵只是对图像信息熵的粗略估计，由于小波变换不能完全消除图像像素间的相关性，实际上图像的信息熵要低于我们计算的熵。
5 实验分析
选择6幅常用标准测试灰度图像，对本文算法进行实验分析，6幅图像如图2所示。可以看出图2（a）Barbara、图2（b）Goldhill、图2（d）Baboon的内容细节信息较为丰富，含有大量的纹理信息，较难获得较高压缩比，图2（c）Bridge的细节信息较少，图像内容较为简单，一般来说能获得较好的压缩比，图2（e）Boats和图2（f）Lena是图像处理人员常用的测试图像，纹理信息和结构信息均较为适中，很具有代表性，相应的压缩处理时所能获得的压缩性能也较为中庸。
测试硬件环境为ThinkPad T400，操作系统为Windows XP SP3，软件环境为Visual Studio6.0，编程语言为C语语言。上述六幅图像均为512×512，8 bits的灰度图像。
测试了上述图像在Le Gall 5/3整数提升小波在小波阶数从2到8阶的无损压缩比和程序运行时间，测量值如图3、图4所示。
从图3中，可以看出小波分解阶数达到4阶后，再增加小波分解阶数所带来的压缩比提升极为有限，而过高时反而略有下降，这是因为图像所含纹理信息量不同，数据间的依赖关系也不同。从表1的数据可以看出除了纹理信息最为丰富的图2（d）Baboon外，其他图像均5阶小波分解达到最优压缩效果。图2（d）Baboon的内容较为丰富，含有大量纹理信息，为了更好表示图像信息需要的小波分解阶数也较多，在6阶分解时达到最优压缩效果。SPIHT算法利用了子带内部和子带之间的相关性，当小波分解过多时，效果会受到影响。从图4中，可以看出随着小波分解阶数的增加，算法消耗的时间也相应增加，从表2的数据中可以看出时间消耗的增加并不显著。纹理信息最少的图2（e）Bridge需要的运行时间最少，纹理信息最为丰富的图2（d）Baboon需要的运行时间最多。从处理各幅图像所用时间来看，该算法完全可以满足实时处理的需要，在降低存储空间的同时，图像质量丝毫没有受到影响。
6 结 论
介绍Le Gall 5/3整数小波变换和SPIHT算法，并将其用于图像的无损压缩，对压缩过程中小波变换对图像边缘的影响加以讨论，确定了周期延拓的方案，以降低图像边缘部分的失真。对无损压缩的极限进行了讨论，利用正交变换不改变图像信息熵的特性，把图像数据经过正交变换后求其熵，对图像信息熵粗略估计，对无损压缩极限进行了粗略预测。选取六幅标准图像对该算法加以验证分析，从时间消耗和压缩效果两个方面来看，该种算法具有广泛的应用价值。
参考文献：
[1] ALARABEYYAT A，AL-HASHEMI S，KHDOUR T，et al.Lossless image compression technique using combination methods[J].Journal of Software Engineering and Applications，2012，5（10）：752-763.
[2] 周兵，李波，李炜.小波图像编码器研究进展[J].计算机科学，2002，29（1）：57-62.
[3] 武永红.基于小波变换的图像无损压缩算法研究[D].重庆：重庆大学，2012.
[4] 闫红梅，李科，吴东梅.SPIHT的超光谱图像无损压缩算法[J].西安科技大学学报，2009，29（5）：598-602.
[5] 张宁，吴银花，金龙旭，等.适于航天应用的高速SPIHT图像压缩算法[J].液晶与显示，2011，26（6）：847-852.
[6] 陈斌，崔志明.JPEG2000的Le Gall（5，3）有损压缩重构优化[J].计算机应用，2006，26（5）：1048-1050.
[7] 姜会亮，胡学龙，郭振民，等.整数（5，3）小波变换结合SPIHT的无损图像压缩[J].计算机工程与应用，2005，41（14）：69-70.
[8] SAID A，PEARLMAN W A.A new，fast and efficient image codec based on set partitioning in hierarchical trees[J].IEEE Transactions on Circuits and Systems for Video Technology，1996，6（3）：243-250.
[9] 潘志刚.低比特率合成孔径雷达数据压缩算法研究[D].北京：中国科学院研究生院，2006.
[10] 张宁，章毓晋，刘青棣，等.利用多尺度条件熵和记忆性度量估计图像无损压缩极限[J].清华大学学报（自然科学版），2000，40（9）：32-36.
[11] CALDERBANK A R，DAUBECHIES I，SWELDENS W，et al.Wavelet transforms that map integers to integers[J].Applied and Computational Harmonic Analysis，1998，5（3）：332-369.
（编辑：程爱婕）