ѧ
JOURNAL OF SOFTWARE
1999 6 10 Vol.10 No.6 1999



һָĽСͼѹ㷨*
ġ   Ϊ
ժҪС任ͼѹ㷨ڽϵʱֵGibbsЧӦһֱδܵõܺõĽ,Ҫԭ,ֵMSE(mean square error)׼ͼԵӦСϵ˽ٵı.ϸShapiroSaid & PearlmanСѹ㷨Ļ,ƸƵͼԵӦϵӦȷԭ㷨˸Ľ,ӦĶԱʵ.µҪڣʶѹϵ˼,С任Ŀռֲ,˿Խзǳıط,Ӷһ̶ϼGibbsЧӦӰ.
ؼʡͼѹ,С任,㷨,Ӿ,Ӧ,ʶѹ.
ͼšTP391

An Improved Zero-tree Wavelet Image Compression Algorithm
XIA Yong TIAN Jie DAI Ru-wei
(AI Laboratory Institute of Automation The Chinese Academy of Sciences Beijing 100080)
AbstractGibbs phenomenon, which occurs in the wavelet-based image compression algorithms under low bit rates, remains an open question for many years. The main cause is that purely-pixel-value-based MSE(mean square error) criteria can not allocate enough bits to the wavelet coefficients corresponding to edges in image. With detail analysis of zero-tree wavelet image compression algorithm originally proposed by Shapiro and then well-modified by Said and Pearlman, the algorithm is improved by suppressing high frequency noises as well as adaptively quantizing coefficients around edges. Experimental results are comparatively given. The main contribution of this paper is the idea of combination of recognition and compression. With the aid of the spatial localization property of wavelet transform, a very flexible bit allocation scheme can be realized, and therefore Gibbs phenomenon is reduced to some extent.
Key wordsImage compression, wavelet transform, zero-tree algorithm, human visual characteristics, adaptive quantization, recognition and compression.
ͼѹڶýϢĴʹ洢Ҫ,ɢұ任˶뼼JPEG(joint picture expert group),MPEG1,MPEG2,H.261H.263ȱ׼ʵеõ˹㷺Ӧ,ʶýͨŵMPEG4׼Ҳ.
С任ھõĿռ-Ƶʾֲԣ1,رʺӦڷƽźŵķ2.Ӵ3ݺͶС任㷨4ݵоС任ľֹͼѹ㷨ȳ˽Ϻõѹܣ58.
Ȼ,Сѹ㷨йϵһûеõܺõĽ,ǵʽϵʱֵıԵģ,νGibbsЧӦ.䱾,ҪΪЩ㷨MSE(mean square error)׼¹,MSE׼ܺܺõؿ̻ͼıԵƽ̹Ĳ.,ף9ݵѹ㷨JPEGȽ,PSNR(peak signal-noise ratio)޼,ӾЧȴԲͬ,˵MSE׼Ż㷨ʱԴﵽܺõӾЧ.ߵʵҲ,Ϊĳ,СϵķֵȷڱеҪԵMSE׼Ҫ.Ӿ֪ĽǶȿ,ͼؾͳԲͬĸ۵Ӿ׼вǴƽȵĵλ,,ֵMSE׼۵Ӿжһƫ10.
ͼѹоȻԱ任ƵΪ,ռı㷨ҲһֱܵǵĹע9,11.ʵ,㷨ǶԭʼͼĳʽԤʹ֮ʺڱ:ǰȽͼƵķֽ,ܹ۶ԸƵвͬԷֱԲͬƵд;Ƚͼпռķָ,ԽԲͬͼԴ.,෽ǻģ12,ˣǿ,˼ĽϿܻһѹ㷨.
,Сѹ㷨пӾ.ر,֪ͼбԵҪ,ͨԵλ,ӦӦ,ڶӦԭʼͼԵСϵñȽϾϸ,ԴﵽõӾЧ.ַʵʵһָӾԽͼ.
µ1ϸѹ㷨.ڴ˻,2Ľ㷨,ҪĸĽǸƵƺͱԵϵӦ.3Ƕʵ.
1 㷨ķ
С任ѹ㷨һõĿռ-ƵʾֲԺͼϵֲֵ.ף6EZW(enboded zero-tree wavelet)㷨ǶPOS,NEG,IZ,ZTR4ʶԷֵԤͱ,ֵ£,һСϵԤһСϵ.㷨ͨʹֵָʽݼʵ,ıӦķֵСֲεؽ,ʵ˶ͼ𽥱ƽı.
ף7ݸһΪϸSPIHT(set partitioning in hierarchical trees)㷨.˼,κλڱȽϵ㷨ִ·֧ıȽϽض.㷨ʽͬ,ʵʲȴС.ҪĸĽ,ֵʱû,1صĲԺֵ.ʵ,൱ڴʱѽŽ˻.ĺô,Ƚ˱,ּӿ㷨ִ.,㷨лԷ֪,SPIHT㷨ɨEZW㷨Ĵɨ貽,ִӳһ,ǰͨʱϵĲﵽͬϵؽ.仰˵,ҪﵽͬѹЧ,SPIHT㷨ֻҪٵı,Ӷ㷨.
ף8ָ,ṹʵ˶СϵЧӦ,Ϊ.,ԴϵԽһı.,ʽʧ¾ͿԽŻ,SFQ(spacial frequent quantization)㷨.㷨дһķչ13,㷨ܵ߻ͨﵽ14,15.
Ȼ,ף8ݳ,ȻSFQ㷨PSNRSPIHTEZW㷨Ⱦкܴ,ӾЧȴûԵĸĽ,ҪGibbsЧӦȻ.,㷨δܽһĻС任ѹ㷨ڵıԵģ.
2 Ľı㷨
㷨Ŀǰõһѹ㷨,ǵĿڴ˻ϾܵGibbsЧӦ.㷨ĸĽҪ,ֵͨ˲ƸƵԼʶͼԵӦСϵнΪϸ,ͼ1ʾ.Сֽ룬ǲϸ,μף1,57.

ͼ1ı㷨ͼ
2.1 
ԭʼͼеڱ任бΪֲȽϹķֵϴСϵ.ݴ,ȶжλ,Ȼֵ˲Щϵķֵ.ͼ2еHӦλ,˲ԺõϵֵС,ÿƵӴķή,ӦأЧʵõ.

ͼ2ϵֵ˲
2.2 Сϵ
ǲף15иĻӾϵͳhuman visual systemԵֵ,ÿӴǸHVSеҪ,ʵó,1.
1 HVSֵ

LLLHHLHH
114.0523.0423.0458.83
211.1114.6914.6928.43
311.3612.7112.7119.55
414.5014.1614.1617.87
522.7019.6219.6220.60
643.3233.3133.3129.24


,ǿǱԵӦСϵӦ.ԭʼͼеıԵСֽ,ڸƵӴжӦھһṹķֵϴһϵڽķֵСϵ.С任пռֲ,Щϵһλĳ֮.ȼֵϴϵλ,Ȼ÷ֽ˲λúͳ弤ӦȼԵйصϵڵ.,ǾһοɷάB9/7Сֽ5,ˮƽֱֱеͨͨ˲2-²õLHӴ,ͼĳԵһEСϵжӦĴСΪ53,ͼ3(a)ͼ3(b)ͼ3(c)ֱHLӴ(35ľ)HH(33ľ)Ӵ.

(a)LHӡ(b)HLӴ(c)HHӴ
ͼ3ƵӴбԵһ
ʶΧ,ѡȡС,ͼԵ˵õ˱ֽ֮Ϊϸıֺȵı,ӶͼӾЧ.رҪָ,ǸʶĽ,ʹñطǳ.
㷨:СϵΪcoeffiݣj,ӦıԵedgeiݣjݺnbriݣj,
Step 1. coeffiݣjݺԤֵTband,ʼԵedgeiݣj;
Step 2. edgeiݣjнСԤֵLengthıԵӦֵ0;
Step 3. edgeiݣjݺ͸ӴбԵ,ʼnbriݣj;
Step 4. ÿһСϵcoeffiݣj
nbriݣjݣ1,coeffiݣj/=little-quant-step-size; /* Ե */
nbriݣjݣ0,coeffiݣj/=big-quant-step-size; /* Ե */
3 ʵ
㷨8bpp 512512 LenaͼѹĽJPEGEZW6㷨PNSRȽϼ2,ѹ64ͼͼ4ʾ.ӱпԿ,㷨PSNRJPEGEZW㷨ֱԼ2.5dB0.7dB.ͼ5ʾΪ㷨SPIHT7ѹ64ʱLena粿ͼıȽ.ͼԵֵӾЧԵĸ,˵㷨ܹϺõؿ˷GibbsЧӦ.
2 㷨JPEGEZW㷨ѹLenaͼPSNR(dB)Ƚ

1.00.80.50.40.250.20.1250.1
JPEG37.9536.7634.8433.4131.4230.3128.24-
EZW639.55-36.2835.0233.17-30.23-
㷨40.2639.1937.0336.0633.9232.9530.8629.95

ע:PSNR=10.log10(2552/MSE),λΪdB,MSEΪ.

(a) JPEG㷨 (b) 㷨
ͼ4

(a) SPIHT㷨 (b) 㷨
ͼ5
4 
ڻعƵ㷨ռ㷨˼Ļ,̽˼ϵĿ.ϸоѹ㷨,ӸƵơͼԵԼӦСϵнΪϸȷ˸Ľ,ȡ˺ܺõӾЧ.Ϊ,ʶѹϵ˼·ʵֻӾԵľֹͼֵýһо.
*оõ863߿ƼĿ.
߼顡,1973,˶ʿ,ҪоΪͼѹ,ýͨ,ģʽʶ,˹.
,1960,ʿ,оԱ,ʿʦҪоΪҽѧͼ,ģʽʶ,ͼѧý.
Ϊ,1932,оԱ,ʿʦ,йѧԺԺʿ,ҪоΪ˹,ģʽʶ,,ϵͳѧ.
ͨѶϵ:ݣ100080,йѧԺԶо
ߵλйѧԺԶо˹ʵҡ100080
ο
1 Daubechies I. Orthonormal bases of compactly supported wavelets. Communication of Pure and Applied Mathematics, 1988,410():909996
2 Rioul O, Vetterli M. Wavelet and signal processing. IEEE Transactions on Signal Processing, 1991,39(1):1438
3 Woods J W, O'Nell S D. Subband coding of images. IEEE Transactions on Acoustics, Speech and Signal Processing, 1986,34(5):12781288
4 Mallat S. A theory for multiresolution signal decomposition: the wavelet representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989,11(7):674693
5 Antonini M, Barlaud M, Mathieu P et al. Image coding using wavelet transform. IEEE Transactions on Image Processing, 1992,1(2):205220
6 Shapiro J M. Embedded image coding using zerotrees of wavelet coefficients. IEEE Transactions on Signal Processing, 1993,41(12):34453462
7 Said A, Pearlman W. A new, fast, and efficient image codec based on set partitioning in hierarchical trees. IEEE Transactions on Circuits and System Video Technology, 1996,6(3):243249
8 Xiong Z, Ramchandran K, Orchard M T. Space-frequency quantization for wavelet image coding. IEEE Transactions on Image Processing, 1997,6(5):677693
9 Radha H, Vetterli M, Leonardi R. Image compression using binary partition trees. IEEE Transactions on Image Processing, 1996,5(12):16101624
10 Ran X, Farvardin N. A perceptually motivated three-component image model (Part ): application to image compression. IEEE Transactions on Image Processing, 1995,4(4):430447
11 Kunt M, Ikonomopoulos A, Kocher M. Second-generation image coding techniques. Proceedings of IEEE, 1985,73(4):549574
12 Mohsenian N, Nasrabadi N M. Edge-based subband VQ techniques for image and video. IEEE Transactions on Circuits and System Video Technology, 1994,4(1):5367
13 Creusere C D. A new method of robust image compression based on the embedded zero-tree wavelet algorithm. IEEE Transactions on Image Processing, 1997,6(10):14361442
14 Luo J, Chen C W, Parker K J et al. A scene adaptive and signal adaptive quantization for subband image and video compression using wavelets. IEEE Transactions on Image Processing, 1997,7(2):343357
15 Watson A B, Yang G Y, Solomon J A et al. Visibility of wavelet quantization noise. IEEE Transactions on Image Processing, 1997,6(8):11641175
1998-04-21յԭ,1998-06-29յ޸ĸ
