基于分形与改进的SPIHT算法的图像压缩方法

张 忠,王 玮,丁 群

摘 要:为了避免分形编码所固有的方块效应,进一步提高图像编码的工作效率和重构图像的质量,对分形编码和小波零树编码进行优化组合,提出一种分形与改进的SPIHT算法相结合的图像压缩方法。基本方法是,对小波分解后的低频子带进行基于信息熵的快速分形编码,以减少编码时间;对包含图像细节边缘信息的高频子带进行改进的SPIHT编码,以舍去算法中对显著系数的排序扫描过程,减少算法的复杂度,同时提高重构图像的峰值信噪比。实验表明,相对于经典分形编码和小波域内的分形编码,该方法在相同压缩比下,提高了编码效率和重构图像的质量,是一种高效快速的编码方法。

关键词:分形;小波变换;信息熵;SPIHT;图像压缩

中图分类号:TN911.73文献标识码:A

文章编号:1004-373X(2009)20-048-03

Image Compression Method Based on Fractal and Improved SPIHT

ZHANG Zhong,WANG Wei,DING Qun

(Department of Electronic Engineering,Heilongjiang University,Harbin,150080,China)

Abstract:In order to avoid blocking artifacts of fractal coding,to enhance the efficiency of image coding and the quality of reconstructed image,the optimum combination of fractal coding and wavelet zero-tree coding are studied.An image coding method based on the merits of improved SPIHT and fractal image compression technology is proposed.The low-frequency area after wavelet decomposition is factual coded based on entropy to shorten coding time.The high-frequency ones including detail information of image are coded by improved SPIHT,which casts out the process of significantly coefficients to reduce its complexity and improve the PSNR of reconstructed image.Experiments show that this new method can improve the speed of coding as well as the quality of encoded image compared with classical fractal coding and fractal coding based on wavelet.It is a fast and efficient image compression method.

Keywords:fractal;wavelet transform;entropy;SPIHT;image compression

0 引 言

小波变换具有良好的时频局部特性及多分辨率特性,压缩效率优于传统压缩算法,但并无特别明显的效率提高。Shapiro提出的零树编码方案[1]采用全新的零树数据结构,用以表征小波系数的空间自相似性,可以有效地利用系数的空间分布特性,从而达到较高的压缩比和信噪比。分形编码[2,3]突破了基于局域内相关冗余的传统编码方法的局限性,有着优良的特性。但由于算法本身的特性,编码过程的复杂性仍很高,耗费时间很长,编码质量也不理想,这些不足使其应用受到很大的限制。

小波编码和分形编码都是图像压缩技术研究的主要方向,但二者都存在一定的局限性。利用小波与分形混合的图像编码方法对图像进行压缩,使两种算法相得益彰,已经成为目前发展的趋势[4]。

1 分形图像编码

分形图像压缩的理论基础是迭代函数系统IFS(Iterated Function System)、吸引子定理和拼贴定理[5]。分形图像编码的任务就是寻找方法来求出IFS的参数即图像的分形编码。分形图像解码则是用某种算法求出该IFS的吸引子。这里对其理论基础不再赘述,仅简要介绍其实现过程,进而提出一种基于信息熵的快速分形图像压缩方法。

1.1 基本分形图像压缩的实现过程

(1) 对原始图像进行分割。将大小为N×N的图像I分割成互不相交且大小为K×K的值域块R(Rangeblock),形成值域块库;同时再将图像I分割成相互重叠的大小为2K×2K的定义域块D(Domainblock),形成定义域块库。

(2) 寻找最优匹配块。对每一值域块Ri,在定义域块库中找到一个与之相匹配的定义域块Di及一种合适的仿射变换ωi,使其在所规定的失真下ωi(Di)与Ri最接近。

(3) 获得分形码。通过比较ωi(Di)与Ri之间的误差,记录下ωi(xi,yi,ai,si,oi)。其中ai为8种对称旋转变换之一;si和oi分别是灰度变换的尺度因子和偏移因子。对ωi(xi,yi,ai,si,oi)进行量化、编码、传输(或存储),完成该值域块的编码。待所有的Ri都被编码后,即完成了对原始图像的分形编码。

1.2 基于信息熵的快速分形图像压缩

编码速度太慢一直是基本分形图像压缩实用化的最大障碍。为了缩短搜索时间,在匹配之前按照图像的特征,将D块和R块进行分类,匹配时只在同一类中进行搜索比较。信息熵是图像所含信息的度量。由于图像块的信息熵是惟一的,即使该图像块经过仿射变换后,其信息熵始终不变[6,7]。因此利用信息熵作为一种分类标准对R块和D块进行分类。

假设具有灰度m(0≤m≤255)的像素点在图像中出现的概率为pm,对于灰度图像,图像的信息熵[8]可定义为:E=∑255m=0H(pm)=-∑255m=0pmlog pm(其中pm表示整幅图像中灰度为m像素出现的概率)。

根据上式算出每一个Ri块和Di块所对应的信息熵,分别记为EiR和EiD。设置阈值T,对每个Ri来说,找出满足|EiR-EjD|

2 SPIHT算法与分形相结合的图像压缩算法

2.1 算法的总体思路

在充分考虑小波变换后能量分布的特点[9],对小波变换的低频子带单独进行基于信息熵的快速分形图像压缩,这样在不显著影响重构图像质量的基础上,大幅度提高压缩速度;同时考虑到小波变换后的高频系数存在大量的零树,且越到高分辨带,零树越密集。然而分形图像编码只是对重要系数的编码性能较好,对于较多的零树情况,压缩比较低,所以对包含原图像中丰富的细节边缘信息的高频系数则采用改进的SPIHT算法,以增加重构图像的质量,从而减少由分形图像压缩所带来的方块效应。如图1,图2所示。

图1 分形与改进的SPIHT算法的图像编码示意图

2.2 改进的SPIHT 算法

SPIHT算法[10]对图像进行编解码时,相对于整个零树编解码过程,对显著系数的排序扫描过程占用了大部分零树编解码过程,而且随着量化级的逐渐精细,这个对显著系数的排序扫描过程也因为显著系数的增多而愈来愈长,因此舍去该排序过程,对House图像进行了分解重构,并将其结果与包含排序过程对图像进行分解重构的结果进行了比较,如表1所示。

表1 有无排序过程的重构图像的峰值信噪比PSNR的比较

8∶116∶132∶164∶1128∶1

有排序过程32.2229.3127.6825.7324.71

无排序过程32.1929.2827.6825.2324.71

从表1的结果可以看出,当低码率编码时,零树法中有无系数排序过程对编码结果毫无影响,而当压缩比较低时,增加排序过程所带来信噪比的提高也是很小的。

图2 分形与改进的SPIHT算法的图像解码示意图

3 实 验

为了测试本算法的性能,选取大小256×256的House,Lena图像进行了压缩实验。选取“Harr”小波基[8],其中小波变换的层数选为3。这样既兼顾了保证图像的大部分低频部分,同时有利于分形方法的有关图像空间结构的分析过程。测试结果如图3所示。实验数据见表2、表3。

图3 基于分形与改进SPIHT算法的House,Lena重构图像

表2 分形与改进的SPIHT算法对House图像的性能测试结果

算法名称PSNRRMSEt /s

基本分形图像压缩25.03204.35240.86

小波域内的分形图像压缩27.89105.65151.03

分形与改进的SPIHT算法27.92105.04101.43

表3 基于分形与改进的SPIHT算法对Lena图像的性能测试结果

算法名称PSNRRMSEt /s

基本分形图像压缩26.88133.35236.43

小波域内的分形图像压缩27.97103.54146.01

分形与改进的SPIHT算法28.4792.5598.41

以上实验数据表明,与小波域内的分形图像压缩、基本分形图像压缩方法相比,分形与改进的SPIHT算法,其结果在相同压缩比的情况下, PSNR有一定的提高,编码时间得以缩减。

4 结 语

提出一种改进的SPIHT算法与分形相结合的图像压缩算法,即在进行零树量化之前,对低频子带进行基于信息熵的快速分形图像压缩。这样不仅可以使对重构图像起重要作用的低频系数损失较少,而且使得在进行零树量化时的零树结构更加合理;对高频子带采用改进的SPIHT算法,即舍去占用大部分零树编码时间对显著系数的排序扫描过程,在不影响图像整体压缩比的情况下,提高了编码效率和重构图像的质量。

在保证重构图像质量的前提下,该算法缩短了图像编码时间。在相同压缩比的情况下,重构图像的峰值信噪比 PSNR 有一定的提高,因此在图像处理领域具有非常广阔的应用前景。

参考文献

[1]Shapiro J.Embedding Image Coding Using Zerotrees of Wavelet Coefficients[J].IEEE Trans.on Image Processing,1993,2(4):160-176.

[2]蔡光兴,王后珍.一种图像分形压缩的改进算法[J].湖北工业大学学报,2006,21(1):1-3.

[3]郭京蕾,吴勇.基于分类方法的分形图像压缩[J].计算机工程与设计,2007,28(4):890-892.

[4]杨静,崔志会.小波分形混合图像编码[J].科技信息,2008(18):64-65.

[5]张春田,苏育挺,张静.数字图像压缩编码[M].北京:清华大学出版社,2006.

[6]姜丹.信息论与编码[M].合肥:中国科学技术大学出版社,2004.

[7]吴盼密.基于小波与分形的图像压缩技术研究[D].长沙:长沙理工大学,2005.

[8]李天钢,王素品,秦辰.基于信息熵窗的小波低频子带弱目标图像的增强[J].西安交通大学学报,2006,40(2):187-190.

[9]刘文耀.小波图像编码与专用VISI设计[M].北京:电子工业出版社,2006.

[10]顾海明,王明翠.SPIHT算法的改进[J].青岛科技大学学报:自然科学版,2008,29(2):185-188.