基于小波变换与分形相结合的图像压缩

小波

第20卷第2期

2004年6月长　沙　交　通　学　院　学　报JOURNALOFCHANGSHACOMMUNICATIONSUNIVERSITYVol.20No.2June2004　　文章编号:1000-9779(2004)02-0056-04

基于小波变换与分形相结合的图像压缩

杨　洁,李曙红,唐贤瑛,孙丰玉

(长沙理工大学,湖南长沙　410076)

摘　要:研究小波变换与分形压缩相结合的图像压缩方法,用分形图像压缩算法,对高频系数进行零树编码,带图像能量高特点的问题,关键词:小波变换;分形压缩;零树编码

中图分类号:TP391　　　文献标识码:　　,,数字图像信息作为最重要的信息之一,被愈来愈广泛的使用。,但是图像通信的应用日益广泛与当前通信容量有限相冲突,特,更难以传输与存储,极大地制约了图像通信的发展。为了解决这个问题,图像压缩技术引起了广泛的关注,在短短的几十年时间内,提出了许多压缩的方法,诸如DPCM、DCT、VQ等方法,并形成了基于DCT等技术的国际标准,如JPEG、MPEG、H.261等[1]。随着人们对图像压缩技术的广泛应用,这些方法的缺陷也暴露出来了,如考虑到高压缩比时,出现了严重的方块效应。为此,人们经过不断的实践与探索,又不断提出了一些新的压缩方法,例如分形图像压缩、小波变换压缩、数论变换压缩、人工神经网络压缩等,其中分形图像压缩和小波变换图像压缩是当前的研究热点。本文采用分形与小波变换相结合的编码方法,提出了一种图像压缩的集成方法。实验表明,该方法在显示图像特征和减少块状效应方面效果较好。

1　小波变换

自1988年,Mallat提出多分辨分析概念,将小波变换用于信号处理,给出了信号和图像分解为不同频率通道信号的算法和重构思想,开创了小波变换在图像处理应用的先河,使得小波变换成为当前图像压缩的热点;但是小波变换本身并不能起到压缩数据的作用,用其他一些编码算法对小波系数进行编码,才能达到压缩数据的目的。而小波变换的实质:从一个具有正则性、局部性和振荡性的基本函数ψ(x)出发,经伸缩平移得到函数簇{|a|1/2ψ(ax-b)|a,b∈R},由此得到函数离散化后构成L2(R)空间的规范正交基,并用于表示或逼近信号。很多研究表明,从逼近的观点上来说,只用很少的小波系数可以得到许多不同图像的精确逼近。

由于小波变换实现信号的低频长时特性和高频短时特性同时得到处理,有效克制了傅氏变换在处理非平稳的复杂图像信号时所存在的局限性,因而小波变换在图像压缩中得到广泛的重视。小波变换图像压缩是首先对图像进行多级小波分解,然后对每层的小波系数进行量化,最后对量化后的系数进行编码,而小波基的选择是一个涉及编码效果的关键问题[2]。目前普遍采用的是由世界著名的小波分析学者InridDaubechies提出的Daubechies函数构造的紧支集的规范正交小波基。本文也采用Daubechies函数构造的小波函数db1,利用此函数完成对图像进行尺度3的分解。其表达式为:

)(1)[imageC,imageS]=wavedec2(image,3‘,db1’

式中:imageS表示各系数长度的矩阵;imageC表示图像的分解系数矩阵,

Ξ收稿日期:2003-09-25

),女,长沙理工大学工程师.作者简介:杨　洁(1966—

小波

第2期　　　　　　　　杨　洁等:基于小波变换与分形相结合的图像压缩　　　　　　　　　57

imageC=[A[3]|H[3]|V[3]|D[3]|…|H[1]|V[1]|D[1])(2)

其中:向量A为低频系数;向量H为水平高频系数;向量V为垂直高频系数;向量D为斜线高频系数。低频系数及其高频系数的提取分别用appcoef2()与detcoef2()函数[3]。

本文将分形图像压缩的方法应用到对低频系数的编码,以解决采用零树编码对整幅图像统一编码时,没有考虑最低频的子带图像能量高的特点,同时也减少分形压缩在图像恢复时方块效应带来的影响。由于高频系数部分包含着图像细节部分,为了使图像恢复的效果比较好,采用零树编码对高频系数进行编码。

2　分形图像压缩

自1987年美国数学家BarnsleyMF缩,Barnsley,但是由于当时的分形压缩计算量大,,在计算机上无法自动实现,所以在当时没有引起太大的注意。自](IteratedFunctionSystems,简称IFS)理论后,把度,他又把IFS的思想应用到图像压缩中,使分形用于图像压,从而导致了分形图像压缩的快速发展。目前,常用的图像分割方式有均匀块状的周期性分割和基于四叉树分解[4]的分层块状分割。

分形图像压缩主要是利用图像自相似的特点通过IFS来实现的,其理论基础是IFS定理和拼贴定理[5]。IFS是由一完备空间(X,d)和一组有限的压缩变换wi:X→X(i=1,2,…,N)组成,并记作{X:wi,i=1,2,…,N},每个迭代函数系统都有一个吸引子,该吸引子可表示成一幅图像。

拼贴定理指出:设(X,d)是完备度量空间,给定L∈H(x)和数ε>0,如能选到一个

IFS{X:wi,i=1,2,…,N}

的压缩率为0<s<1,且满足

εh(L,∪wi(L))≤i=1N(3)

ε则h(L,A)≤/(1-s)或等价地

h(L,A )≤(1-s)-13h(L,∪wi(L))≤ε/(1-s)i=1N(4)

其中:A 为该IFS的吸引子;h为Hausdorff度量;H(x)为完备度量空间(X,d)的一个子集。

分形图像编码就是根据某种图像分割,找出每个压缩变换wi:Di→Ri的系数(Di为域块,Ri为值块):

wi(Ri)=s(Ri)S(n+1)τ(Ri)D(Ri)+o(Ri)(5)

式中:D(Ri)∈{D1,D2,…,Dm}为域块;τ(Ri)∈{τ1,τ2,…,τ8}为8种对称变换(详细介绍可查阅参考文献[6]);S(n+1:R22(n+1)→R22n为下抽样算子;s(Ri)∈{s1,s2,…,sn}为缩放系数(ScalingFactor);o(Ri)∈{o1,o2,…,ot}<R{o1,o2,…,ot},R为偏移量(offset)。

3　图像压缩算法

本文的图像压缩是对小波变换所得的系数进行编码。其中,对于低频系数编码是应用分形图像压缩算法;对于高频系数,为了保证图像恢复后仍保留图像的细节部分,采用了零树编码。图像压缩步骤如下。

1)调用要压缩的图像,利用Matlab上的小波变换函数完成尺度3的分解,得到低频系数矩阵A和高频系数矩阵B。

2)对于低频系数采用分形图像压缩的方法,具体过程如下:

小波

　　　　　　　　　　　　长　沙　交　通　学　院　学　报　　　　　　　　　　　第20卷　58

①输入低频系数可表示为f(x,y,g)的数字系列,其中x、y为坐标,g为坐标(x,y)上对应的系数;

②将低频系数分为n个互不重叠的值域块Ri(i=1,2,…,n),并且∪Ri=A;让Dj(j=1,2,…,i=1

m)代表比Ri大的尺寸的图像子块,并且满足Di∩Dj≠<,i≠j;n

③将低频系数矩阵A分成互不相叠的子块Ri做取块操作,符号记为BRK,LA;

④搜索与其自相似的父块Dj,将Dj做伸缩、旋转和平移操作,父块的取块变换符号为

D(LP(K,L)AνBⅡ(K,L)A),通过Aν后父块Dj与子块Ri有相同的尺寸(其中P(K,L)表示对应于(K,L)

[6]上的父块的0°、90°、180°、270°以及关于x轴、y轴、y=x直线、y=-x直线等8);

D⑤如果BRBⅡ(K,L)A)…,am和b1,b2,…,K,LA和(LP(K,L)Aν

bm,使

R(BR(K),LK,LIK,LA)≈CK,LLP(K(6)

CK,L为父块的变换伸缩因子,hK,LI1矩阵,则式(6)两边的误差表为

dpmi=1(CK,Lbi+hK,L-ai)2(7)

其中m⑥搜索是改变各父块的变换,使其与子块之间的距离最短(即dp达到最小),利用求导可得到系数CK,L和hK,L,分别为

m(

CK,L=6maibi)-(6mai)(6

2mbi),　　hK,L=mm(

i=16m2bi)-(i=16

2m(bi)i=16mai-CK,Li=16mbi)(8)此时,有dp最小,则dp=m6ai+CK,L(CK,L2

i=1mi=16mbi-2i=16maibi+2hK,Li=16mbi)+hK,L(hK,Lm-2i=16mai)〕(9)

⑦对于每一个子块Ri都能找到一个最优匹配的父块Dj,使得dp达到最小,并记下一组参数(CK,L,hK,L,Ⅱ(K,L),P(K,L)),这样就完成了对一子块Ri的编码;

⑧对所有子块分别寻找对应的父块,是低频系数矩阵A上的每一子块Ri都用父块来覆盖,这就完成为整个低频系数矩阵的编码;

⑨低频系数解码,可以通过

A=

K,L∈Rτi6R(BRK,L)3BK,LA≈　　　　　　　　　　　　　　　　　　　

K,L∈Rτ6CK,L(BK,L)3LP(K,L)AνBRDⅡ(K,L)A+K,L∈Rτ6hK,L(BK,L)3BK,LI)RR(10)

来实现迭代,其中Rτ表示图像中所有的子块集,对于低频系数矩阵的迭代次数为10次。

3)高频系数进行零树编码以及解码,以保持图像的细节部分。

4)将低频部分重构图像以及高频部分的重构图像相融合。

至此,完成了对整幅图像的压缩及其压缩图像的恢复。

4　实验结果

本文用Woman图像,利用Matlab及C语言编程来进行实验,在对低频系数矩阵进行编码时应用了分形图像压缩算法,观其效果,以迭代10次的效果为好。压缩比都为16∶1(图1～图3)。

实验表明,该方法解决了分形图像压缩算法对整幅图像进行编码运行速度慢的问题(例如缩短了搜索与给定值域块最相匹配的定义域块的时间),同时消除了用分形图像压缩时的“块效应”,也体现最低

小波

第2期　　　　　　　　杨　洁等:基于小波变换与分形相结合的图像压缩　　　　　　　　　59

图1　

原始图像图2　本文算法迭代5

图3　10次后的结果

频的子带图像能量高的特点。

参考文献:

[1]　张海燕.图像压缩技术[J].(:831～836.

[2]　江　涛,朱光喜,汪[J].计算机辅助设计与图形学学报,2002,14

(10):897～[3]　胡昌华.基于的系统分析与设计———小波分析[M].西安:西安电子科技大学出版社,2001.

[4]　FisherY.Fractalimagecompression:Theoryandapplication[M].NewYork:Spring-Verlag,1995.

[5]　BarnsleyF.Fractaleverywhere[M].SanDiego:Academicpress,1988,83～96.

[6]　王耀南.计算机智能信息处理技术及应用[M].长沙:湖南大学出版社,1999.

ImageCompressionBasedontheCombinationof

WaveletTransformandFractal

YANGJie,LIShu2hong,TANGXian2ying,SUNFeng2yu

(ChangshaUniversityofScienceandTechnology,Changsha410076,China)

Abstract:Themethodofimagecompressioncombiningwavelettransformandfractalcompressionhasbeenstudied.Itisconsistedoffractalcodinginlow2frequencyofwavelettransformcoefficientandzero2treecodinginhigh2frequencypart.Itovercomesthedifficultythatzero2treecodedoesnotconsiderthehighenergytraitinlow2frequencyimageandcutsdownthedominoeffectofrecoveryimageinfractalcompression.

Keywords:wavelettransform;fractalcompression;zero-treecoding

本文来源：https://www.bwwdw.com/article/0mt1.html