Զѧ
ACTA AUTOMATICA SINICA
1999ꡡ255ڡVol.25 No.5 1999



ģͶֱֽͼѹ
˴
ժҪͼģ.ģ͵Ķֱֽ⣬һµͼѹ.ͨͼģ͵Ķֱֽ⡢ѹعʵͼĶֱ⡢ѹع.һСͼѹδʹùС˲飬С˲㷨O(n)ʱ.ʵ÷ܻýϺõͼѹ.
ؼʡͼѹֱС˲飬߶ȿռ.
IMAGE COMPRESSION USING MULTIRESOLUTION DECOMPOSITION OF TRIANGULAR MESH MODEL
LI WenshunLI Jiegu
(Institute of Image Processing & Pattern Recognition, Shanghai Jiaotong Univ., Shanghai200030)
AbstractIn this paper, a triangular mesh model of image is constructed. Based on multiresolution decomposition of the triangular mesh model, a new image compression method is proposed. Multiresolution decomposition, compression and reconstruction of image are implemented through multiresolution analysis of the triangular mesh model of image. A new wavelet filter bank is constructed, which has never been used in wavelet image compression before. The filter bank algorithm has O(n) running time. The exprimental resnlts show that the proposed method can achieve satisfactory image comprossion performance.
Key wordsTriangular mesh, image compression, multiresolution analysis, wavelet filter bank, scalar space.
1
Сͼ(ͼѹ)ܵ߶ȵӣԭף14оǰźŷֲεطֽΪͷֱʵƽźźСϸź.ÿ㵱УƽźźСϸźŶع߷ֱϢ.ͨСϵСɴﵽѹĿ.ͼѹУʹõĳ߶ȺСĲͬвͬС˲.97(Tap)˲5ݡD4˲2ݼHaar˲6.ʹõĳ߶ȺСΪֶԺɴĸ˲(ֽ˲ϳ˲)Ϊϡ󣬸˲㷨O(n)ʱ.⣬ͼѹʹõĶάСͨΪһάС7.СڷֽⶨϸԵϵĺֽһάС.ֽڶѹķֲơĶֱʱ༭ȣ8.ͼҶΪ߶ȹһͼģʵͼֽ⡢ѹعҲɿӦ֮һ.
2ͼģͼ߶Ⱥѡȡ
ֱоʵǺͺռ.ˣͼΪһźڷֽ֮ǰ뽫䶨Ϊĳϵĺ.ͼͨΪھϵĶάI=g(x,y)x,yֱΪˮƽʹֱλ.ｫͼͼ1ʾϸϣÿص㶼ӦһͬλõǶ.ǶػҶֵΪ߶ȣ򹹳ͼģ.ڷǷλεϸͼ񣬿ɽΪϸ.ڵǶӦĸ߶ֵΪ.һȫƽ̹ģֱֽӦһСϵΪ㣬ѹûжӰ.عֻȡͼӦָͼ.ָͼʱֻ轫صĻҶֵȡΪǶĸ߶ֵ.



ͼ1ϸ
ͼģͣҲף8һԷֶԺΪ߶Ⱥ.Ӧÿ򶥵һͼ2ʾĳ߶Ⱥji(x).ǶiֵΪ1ڵ㶼ݼΪ0طȫΪ0.ȻڵjMj(x)ɱʾ£
Mj(x)=Ʀji(x).Vji(1)
xVjiΪ񶥵iĸ߶ֵ.ɼj񶼰ڪji(x)ųɵĿռУji(x)ȷΪjһ.߶ȿռǶǶֱһҪ.VjΪji(x)ųɵĳ߶ȿռ䣬Vj+1Ϊj+1i(x)ųɵĳ߶ȿռ.Զ׼ji(x)=j+1i(x)+12Ʀj+1k(x)kΪiڵj+1ڶ.ˣ߶ȿռǶ.



ͼ2ڵĶiĳ߶Ⱥji(x)
Ƕ׵ĳ߶ȿռ䣬ͿڿռжڻԷֱռ估.fgVjڻ£
<f,g>=f(x).g(x)dx(2)
лΪ.
3С
3.1С
Ƕ׵ĳ߶ȿռ䲢жڻͿVj+1ռйСj=(j0(x)j1(x)j2(x)).jɵĿռWjΪVjVj+1еռ.覵j+1ΪVj+1Ļj+1=(Oj+1(x)Nj+1(x)).Oj+1(x)жӦھɶ(ͼ1еİ׵)ĳ߶ȺɣNj+1(x)жӦ¶(ͼ1еĺڵ)ĳ߶Ⱥ.ｫС.ȣ(jNj+1(x))ΪVj+1Ļ.(jNj+1(x))(Oj+1(x)Nj+1(x))໥ԱʾҲVj+1Ļ.˶Vj+1еMj+1(x)ɱʾΪj.Pj+Nj+1(x).Qj.Nj+1(x)ϵΪ0j.PjΪMj+1(x)Vjռһƽѱƽ.
Ϊ˵õѱƽɼNj+1(x)WjռͶӰͶӰΪj.þʾ£
Nj+1(x)=j+j.aj.(3)
Mj+1(x)(j,j)ΪʾjϵɵõVjռѱƽ.
3.2С
ʽ(3)֪ajС.Զi(ָj+1¶)ji(x).ʽ(3)
ji(x)=Nj+1i(x)-Ʀjk(x).jk(4)
ʽkΪj+1ľɶ.
ΪʵӦõҪСľֲ֧Сʱ뿼ǵ.Ϊˣʽ(4)ԶNj+1i(x)Ħjk(x)ϵΪ0ֻȡNj+1i(x)ڵĦjk(x)ϵΪ0СΪ1.ʾΪʽ
ji(x)=Nj+1i(x)-jm(x).ajm-jn(x).ajn(5)
ʽm,nΪiڵj+1ɶ.
mnλõĲͬɷӦajm,ajn.Ϊ
1) m,nֱڵԵϣ
2) m,nͬһԵϣ
3) mΪԵԽߵĽ㣬nڣ
4) mΪԵԽߵĽ㣬nڱԵϣ
5) mڱԵϣnڣ
6) m,nڣ
7) mΪԵĽҲڶԽϣnڱԵ.
г鷽ȡӦajm,ajnе6)Ϊڲһ.µķΪ
(6)
ʽajm=ajn=528õajmajn1.
1µajm,ajnֵ

1234567
ajm5165282544259225685282544
ajn5165285441592534528544


3.3˲㷨
Vj+1ռеMj+1(x)ֽʵϾ(Oj+1(x),Nj+1(x))Ϊıʾȡ(i,j)Ϊıʾ.ֽ£
Mj+1(x)=Ʀj+1i(x).Vj+1i=Nj+1i(x).Nj+1i+Oj+1k(x).Oj+1k=
Nj+1i(x).Nj+1i+(jk(x)-12Nj+1ki(x)).Oj+1k=
Nj+1i(x).(Nj+1i-12Oj+1im-12Oj+1in)+Ʀjk(x).Oj+1k;(7)
Nj+1i-12Oj+1im-12Oj+1in=Wjiʽ(7)
Mj+1(x)=(ji(x)+jim(x).ajim+jin(x).ajin).Wji+Ʀjk(x).Oj+1k=(ji(x).Wji+Ʀjk(x).(Oj+1k+ajki.Wjki)=j.Wj+j.Vj
WjVjɱʾΪʽ
Vj=A.Vj+1Wj=B.Vj+1.
Wji=Nj+1i-12Oj+1im-12Oj+1inBΪϡ.Vjk=Oj+1k+ajki.WjkiУki(kڵj+1ڵ)ĸ6AҲΪϡ.ABΪֽ˲O(n)ʱ.
عǷ̵ֽ̣Mj(x)=ƪji(x).VjiмСϸźšƦji(x).WjiMj+1(x)=Ʀj+1i(x).Vj+1i.ع£
Mj+1(x)=Ʀji(x).Wji+Ʀjk(x).Vjk=(Nj+1i(x)-jim(x).ajim-jin(x).ajin).Wji+Ʀjk(x).Vjk=Nj+1i(x).Wji+Ʀjk(x).(Vjk-ajki.Wjki)(8)
Pjk=Vjk-ajki.Wjkiʽ(8)
Mj+1(x)=Nj+1i(x).(Wji+12Pjim+12Pjin)+Oj+1k(x).Pjk=j+1(P.Vj+Q.Wj)=j+1.Vj+1,
Vj+1=P.Vj+Q.WjΪعPQΪع˲ҲΪϡ.ع㷨ҲΪO(n)ʱ.
4ʵ
ǰѶ˲ƹ˱ȽϸĽ.Ϊ˿һ˲ܣSGI Indigo 2 ExtremeվһЩʵ.ͼ3(a)Ϊ512512ġLennaҶͼ.ϸԵĿǣΪ512512.ͼ3(b)ͼ3(f)Ϊԭͼ5ƽƽͼ3(f)Ϊԭͼ11024ƽ.Ǿֽ˲ĸĵƵƽźţźŵľ󲿷.


ͼ3LennaͼĶֱֽ
Ϊ˼Ϣأѹ.ϴֵӳ䵽Сֵ.ԭʼܵõȷĻָֻ԰Сϵ.ڵƵƽź(Ϊ)ֻӳ䵽ӽ.ͼƽСϵֵСʹЩСϵعͼҲܴʧ.ڱȽСϵСʱͬεСϵйһWji=Wji.ji(x)2.ڹһ֮СϵСĳֵTΪ0ֵT֮ϣ.
Էֽ֮Ǳ룬õı뷽г̱Huffmanʹ.ںܶСϵֵȽϺΪ0г̱ڴ˾иЧ.HuffmanʹС.
ѹعͼ÷ֵ䶨ʽ

fmaxͼҶȵֵf(x,y)ԭͼҶֵfc(x,y)عͼҶֵNͼ.PSNRԽ˵ѹعͼԽ.
ͼѹܣѹ.䶨ʽ

ͼ4(a)ΪĵƵƽźţͼ3(f)ʧ.ͼ4(b)ͼ4(f)ͼ4(a)뾭СϵĹ.عͼͼ4(f)ԭʼͼͼ3(a)ѹCRΪ58PNSRΪ31.2dB.нϺõͼѹܺ.


ͼ4(a)Сϸڵͼع
ͼ5(a)ϸڱȽϷḻ512512ͼͼ5(b)Ƿ5عͼ.عͼѹΪ27PSNRΪ26.7dB.ϸڽ϶࣬Сϵ϶࣬Դﵽߵѹ.


ͼ5ϸڽϷḻͼѹ
5ᡡ
ͼѹкܶ˲飬˲ѡӰͼѹܵҪ9.ĻͼģһСͼѹδʹù˲飬лһάСķֽʽ.˲ڷֽع̾ΪO(n)ʱ.һ˲ܻõͼѹܺһŶۣ˲й⣬뷽й.ʵ˲ܽг̱HuffmanͼѹܻýϺõѹܺ.ʵϣڶھϸԵϵĺø˲Ʒ˲зֽ⡢ѹع.Wang JάС任ѹҽѧͼ10ݣ÷Ҳܷҽѧͼѹ.⣬÷ڶѹķֲơĶֱʱ༭ֲʾ.
߼飺˴1972ڽ.1993λͨѧϢϵ̣1996Ϻͨѧģʽʶܿרҵ˶ʿѧλΪϺͨѧͼģʽʶоʿо.ڹѧڿϷ10ƪ.ҪоȤΪֱͼʶͼͼѹ.
ȡϺͨѧͼģʽʶоڣʿʦ.ʵ繤Э߼ԱйѧԺģʽʶʵҺͱѧϢѧίԱḱίԱҽίڶѧԱģʽʶ˹ܡ־ί.Ҫоģʽʶ𡢼ӾĿ١˹Ӧ.
ߵλϺͨѧͼģʽʶоϺ200030
ο
1Grossmann A, Morlet J. Decomposition of Hardy function into square integral wavelets of constant shape. SIAM J. Math. Anal.,198415723736
2Daubechies I. Orthonormal bases of compactly supported wavelets. Commun. Pure Appl.Math.,198841909996
3Mallat S. A theory for multiresolution signal decomposition:The wavelet representation.IEEE Trans.. Patt Anal. Machine Intell.,1989,7:674693
4Strang G T. Wavelets and dilation equations:A brief introduction,SIAM Rev198931614627
5Antonini M, Barlaud M, Mathieu P, Daubechies I. Image coding using wavelet transform.IEEE Trans. Image Processing,1992,1(2):205220.
6Albanesi M G, Delotto I. Image compression by the wavelet decomposition.Signal Processing,19923265274
7Daubechies I. Ten Lectures on Wavelets.SIAM,Philadelphia,1992
8Lounsbery J M. Multiresolution Analysis for Surface of Arbitrary Topological Type. Ph.D.thesis, Department of Computer Science and Engineering, University of Washington, September 1994
9Villasenor J D, Belzer B, Liao J. Wavelet filter evaluation for image compression.IEEE Trans. Image Precessing,1995,4:10531060
10Wang J, Huang H K. Medical image compression by using three-dimensional wavelet transformation.IEEE Trans. Medical Imaging,1996,15547554
ոڣ1997-10-20
޸ڣ1998-08-25
