基于ADL小波變換的圖像壓縮算法

1、基于ADL 小波變換的圖像壓縮算法林 娜,倪 林,劉 權(quán)(中國科學(xué)技術(shù)大學(xué)電子工程與信息科學(xué)系,合肥 230027摘 要:提出一種基于自適應(yīng)方向提升(ADL小波變換的圖像壓縮算法。根據(jù)灰度共生矩陣角二階矩的差異,將圖像分割成平坦性不同的分塊。對紋理信息較少的塊,采用一般提升小波變換以減少變換時(shí)間。對紋理信息較多的塊,采用方向提升小波以提高變換效果。結(jié)合多級樹集合分裂編碼和算術(shù)編碼對變換系數(shù)和方向信息分別進(jìn)行編碼。實(shí)驗(yàn)結(jié)果表明,與ADL 算法相比,該算法能有效減少方向小波變換時(shí)間。關(guān)鍵詞:圖像壓縮;自適應(yīng)方向提升;灰度共生矩陣;角二階矩;多級樹集合分裂Image Compression Algo

2、rithm Based on Adaptive Directional Lifting Wavelet TransformLIN Na, NI Lin, LIU Quan(Department of Electronic Engineering and Information Science, University of Science and Technology of China, Hefei 230027, China 【Abstract 】Based on the general Adaptive Directional Lifting(ADL promotion transforma

3、tion, this paper proposes an image compression algorithm based on ADL wavelet transform. Using this algorithm, the image is divided into flat and non flat block according to different angle second moment of Gray Level Co-occurrence Matrix(GLCM. For each block, the lifting scheme is adaptively select

4、ed to reduce the computation of directional lifting wavelet. For the flat blocks, it uses ordinary horizontal and the vertical promotion directly to reduce the time. For the non flat blocks, it uses the directional lifting wavelet to enhance the result. Experimental results show that this algorithm

5、can dramatically reduce the computational time compared with the tradditional ADL method.【Key words 】image compression; Adaptive Directional Lifting(ADL; Gray Level Co-occurrence Matrix(GLCM; angle second moment; Set Partition in Hierarchical Trees(SPIHT DOI: 10.3969/j.issn.1000-3428.2011.21.068計(jì) 算

6、機(jī) 工 程 Computer Engineering 第37卷 第21期V ol.37 No.21 2011年11月November 2011·圖形圖像處理· 文章編號:10003428(201121019903文獻(xiàn)標(biāo)識碼:A中圖分類號:TP911.731 概述離散小波變換提供了多分辨率的圖像顯示方式和完美的圖像重構(gòu)能力,被廣泛應(yīng)用于圖像分析、壓縮編碼等領(lǐng)域,如靜止圖像壓縮的國際標(biāo)準(zhǔn)JPEG2000。文獻(xiàn)1提出了一種新的不依賴于傅里葉變換的小波構(gòu)造方案提升小波變換,該方法不僅得到了一種新的小波變換,還減少了現(xiàn)有小波變換的計(jì)算復(fù)雜度。實(shí)踐證明,所有的小波變換都可以通過提升方法

7、實(shí)現(xiàn),因此,提升小波變換也被稱為第2代小波變換。但一般的提升小波變換結(jié)果都是通過對圖像的行/列進(jìn)行一維提升變換得到的,只能處理水平和豎直方向上的圖像信息。由于自然圖像存在豐富的紋理信息,因此采用一般的提升方法不能很好地利用圖像的紋理特征,處理后高頻存在冗余,影響后續(xù)的工作。為解決這個(gè)問題,研究者們相繼提出Contourlet 變換2、Curvelet 變換3、Bandelet 變換4等變換方法。這些方法都取得了很好的效果,但仍存在計(jì)算復(fù)雜度高、濾波器設(shè)計(jì)復(fù)雜等問題,導(dǎo)致在實(shí)際的壓縮中,這些方法應(yīng)用較少。近年來,學(xué)者們提出了方向提升變換5-6的方法,通過基于空間方向預(yù)測提升小波來實(shí)現(xiàn)小波的方向性

8、,并且降低計(jì)算復(fù)雜度。但是這種方向需要在做變換時(shí)進(jìn)行插值運(yùn)算,并且還要判斷選擇最優(yōu)方向,運(yùn)算量比較大。本文提出一種基于灰度共生矩陣7的自適應(yīng)方向提升小波壓縮算法,該算法結(jié)合方向提升的優(yōu)點(diǎn),將圖像分為需要進(jìn)行提升小波變換和方向提升小波變換的2個(gè)部分,在壓縮比提高的同時(shí)降低算法運(yùn)算的復(fù)雜度。2 圖像紋理性分塊本文使用灰度共生矩陣來自適應(yīng)區(qū)分圖像的紋理和非紋理部分,從而可對圖像中的不同部分采取不同的提升方法。由于紋理是由灰度分布在空間位置上反復(fù)出現(xiàn)形成的,是相鄰像素的灰度相關(guān)性的表現(xiàn),因此在圖像空間中相隔一定距離的兩像素間也會(huì)存在一定的灰度關(guān)系,這種關(guān)系被稱為是圖像中灰度的空間相關(guān)性。共發(fā)矩陣就是基

9、于這種特性來描述成對象素的灰度組合分布,通過考察像素對出現(xiàn)的頻率,構(gòu)造一種條件概率來反映圖像的紋理特征。共生矩陣的表達(dá)式的定義為:設(shè)f (x , y 為一幅二維數(shù)字圖像,大小為M×N ,灰度級別為N ,則滿足一定空間關(guān)系的灰度共生矩陣可以定義為:11221122(,(,(,|(,(,i j count x y x y M N f x y i f x y j =×=p(1其中,count 表示統(tǒng)計(jì)的像素點(diǎn)數(shù)。若(x 1,y 1與(x 2,y 2間距離為d ,兩者與坐標(biāo)橫軸的夾角為,則可以得到各種間距及角度的灰度共生矩陣P (i , j , d , 。通常方向?yàn)?°,

10、 45°, 90°, 135° 4個(gè)方向。作者簡介:林 娜(1987-,女,碩士研究生,主研方向:視覺信息處理,圖像壓縮;倪 林,副教授、博士;劉 權(quán),碩士研究生 收稿日期:2011-04-29 E-mail :lin7453200 計(jì)算機(jī)工程2011年11月5日 從共發(fā)矩陣抽中取紋理特征的定量值有2種常用度量7:(1角二階矩ASM2(,i jASM P i j=(2(2對比度度量CON2(,i iCON i j P i j=(3式(2和式(3中的求和都是在整個(gè)窗口進(jìn)行。其中角二階矩是一種對圖像灰度分布均勻性的度量。當(dāng)數(shù)值分布較集中于主對角線附近時(shí),其相對應(yīng)的AS

11、M值較大,即灰度均勻,這種均勻是局部的均勻;反之,ASM值則較小。這里用ASM作為區(qū)分圖像紋理和非紋理部分的標(biāo)準(zhǔn)。將圖像分成16×16的小塊,對每個(gè)分塊計(jì)算它的共生矩陣和角二階矩,利用式(4自適應(yīng)判斷圖像的平坦性:1ASM thresholdCHASM threshold=>(4其中,閾值threshold定義為圖像的所有分塊的角二階矩的平均值,通過式(5得到。,11N MASM i ji jthresholdN M=×(5CH=1表示該分塊有著很大的灰度變換,紋理比較豐富,需要采用方向提升才能很好減少高頻部分;CH=0表示該分塊的灰度變化不大,比較平坦,可以采用一般

12、的提升變換。利用本文方法對測試圖Barbara(512×512像素進(jìn)行評估,得到測試圖像的紋理分塊圖如圖1所示,可以看到利用角二階矩能有效地區(qū)分紋理和非紋理區(qū)域。(a原圖(b方向信息圖圖1 測試圖的方向信息圖3 自適應(yīng)方向預(yù)測提升變換一般的提升方法只是在水平和垂直方向上對圖像進(jìn)行變換,但由于變換提供的方向信息固定且有限,對圖像中的非垂直或豎直方向的紋理信息不能很好地稀疏。ADL的提升方法利用了圖像中的紋理信息,解決了一般提升小波的問題。為得到更好的結(jié)果,通常選取很多的方向,通過一定的準(zhǔn)則選取最優(yōu)方向,這些方向上的點(diǎn)不一定是位于整數(shù)點(diǎn)的,需要通過插值來實(shí)現(xiàn)。這樣無形地就增加了計(jì)算的復(fù)雜

13、度和方向信息編碼的開銷。進(jìn)行一般提升變換時(shí)會(huì)發(fā)現(xiàn)一個(gè)現(xiàn)象,在圖像紋理比較多的地方,變換后的高頻分量會(huì)比紋理相對少的地方來的大。這就表明,在圖像紋理多的地方可以用方向提升的方法,而在紋理比較少的地方使用一般提升方法,這樣一來,不僅減少方向編碼的位數(shù),同時(shí)也在一定程度上減少了由于插值和判斷最優(yōu)方向所帶來的一定計(jì)算量。3.1 提升算法提升小波的實(shí)現(xiàn)過程分為3個(gè)步驟:分裂,預(yù)測和更新。(1分裂?？蓪⒃紨?shù)據(jù)x(m, n分為2個(gè)集合:偶數(shù)集合x e(m, n和奇數(shù)集合x o(m, n。(2預(yù)測。保持偶數(shù)集合x e(m, n不變,通過內(nèi)插細(xì)分的方法預(yù)測奇數(shù)集合,預(yù)測值與實(shí)際值的差值為h(m, n,即(,(

14、,(,o eh m n x m n P x m n=,其中,P(.為預(yù)測算子。(3更新。用h(m, n來更新數(shù)據(jù)x e(m, n,以保持原始數(shù)據(jù)x e(m, n的某種特性。如保持平均值不變,該操作記為(,(,(,el m n x m n U h m n=+,其中,U(.為更新算子。普通提升只是對圖像在水平/垂直方向上做變換,但每個(gè)像素點(diǎn)不一定在水平和垂直方向上的相關(guān)性最強(qiáng),因此,本文使用方向提升的方法。如圖2所示。其中,代表1/4點(diǎn),代表1/2點(diǎn)。假設(shè)點(diǎn)x(m, 2n+1在圖2中箭頭所示方向上的點(diǎn)與預(yù)估計(jì)像素點(diǎn)的相關(guān)性最強(qiáng)。圖2 預(yù)測過程將原先的提升預(yù)測算子沿方向修正,即對提升部分進(jìn)行如下改進(jìn)

15、:(,(sign(1tg(,ex i eiP m n p x m i n i=+(6其中,有多個(gè)方向上的點(diǎn)時(shí)位于非整數(shù)點(diǎn)上,需要插值得到需要位置上的點(diǎn)的值。本文采用sinc函數(shù)來進(jìn)行插值。更新過程和預(yù)測過程相似,將預(yù)測得到的系數(shù)以方向提升的方式來更新偶數(shù)行的值。更新算子由式(7取代。(,(sign(tg(,h jjU m n u h m j n j=+ (7其中,U(.為更新算子。這里更新的方向與預(yù)測的方向一致。本文采用CDF9/7小波的提升格式。3.2 方向預(yù)測為了減少計(jì)算量,不對圖像的紋理部分的每個(gè)點(diǎn)進(jìn)行方向預(yù)測,而是將紋理部分分成16×16像素的塊,對每塊依照一定的準(zhǔn)則進(jìn)行最優(yōu)

16、方向的判斷。方向判斷的準(zhǔn)則為:對每個(gè)分塊在9個(gè)方向上作提升變換,計(jì)算每個(gè)子塊對應(yīng)方向上高頻能量之和,選取高頻能量最小的方向作為這個(gè)分塊的自適應(yīng)變換方向。為了保證方向選擇的正確性和減少一定的計(jì)算量,這里采用5/3小波來判斷分塊的方向。5/3小波的提升格式為:1000110111(/2(/41/2l l l ll l l ld d s ss s d d+=+=+(84 編碼過程先用本文方法對圖像進(jìn)行提升變換,將變換后的系數(shù)和方向信息分別采用Spiht和自適應(yīng)算術(shù)編碼方法進(jìn)行編碼。編碼過程和一般的Spiht編碼相同,只是增加了方向信息編碼部分,并將其放在碼流的開頭。為能完全解碼出圖像的方向信息,本文

17、采用算術(shù)編碼對圖像方向信息進(jìn)行編碼。雖然增加了方向信息的編碼,但方向信息量相對于圖像本身數(shù)據(jù)量較少,所以,增加的編碼信息不多。每一級的變換都可以得到分塊圖像的變換方向,在作圖像壓縮時(shí),要對這些方向第37卷第21期 201 林娜,倪林,劉權(quán):基于ADL小波變換的圖像壓縮算法進(jìn)行編碼,相對于一般提升變換,這就增加了一定的計(jì)算量,但本文將圖像分為紋理和非紋理部分,在變換時(shí)采用了不同的提升方向,從而減少計(jì)算量和方向編碼的信息。5 實(shí)驗(yàn)結(jié)果與分析筆者通過實(shí)驗(yàn)來驗(yàn)證本文方法的有效性。測試圖像選擇為Lena(512×512像素和Barbara(512×512像素圖像。從變換后的高頻部分的

18、系數(shù)和能量平均值上,將本文方法和一般提升小波變換做比較?？紤]變換后高頻系數(shù)平均幅度和高頻平均能量,比較變換后的第1層高頻。本文方法和CDF9/7方法第1層高頻子帶能量和系數(shù)的平均值的比較結(jié)果如表1所示。表1 高頻部分的平均熵值和能量比較平均熵值高頻能量圖像CDF9/7 本文方法CDF9/7 本文方法Lena 3.26 2.94 3.6e+006 2.5e+006Barbara 6.31 4.55 1.3e+007 5.6e+006Women 5.20 4.67 6.0e+006 3.5e+006可以看出,利用本文方法進(jìn)行變換后高頻能量顯著減少,高頻系數(shù)的平均幅度得到降低。如Barbara圖,它

19、的高頻分量的平均系數(shù)值下降到了4.55,能量也有大幅度的下降。其他的圖像也有較明顯的下降。這說明本文提出的方法能更好地自適應(yīng)于圖像的紋理信息,減少了圖像變換后的信息冗余,為以后的壓縮、去噪等提供有力的條件。改進(jìn)后方法在計(jì)算復(fù)雜度上和ADL5方法的實(shí)驗(yàn)結(jié)果比較如表2所示,主要比較特征是計(jì)算時(shí)間?？梢钥吹?運(yùn)用本方法可有效減少運(yùn)算時(shí)間,提高程序運(yùn)行的效率。表2 進(jìn)行5級小波變換的計(jì)算時(shí)間比較s圖像 ADL方法本文方法Lena 6.34 4.05Barbara 6.30 4.10Women 6.36 4.07Baboon 6.35 4.60對比3種算法的壓縮性能峰值信噪比(Peak Signal t

20、oNoise Ratio, PSNR。將方向信息編碼后放在碼流的頭部。由表3可以看出,盡管需要編碼方向信息,但本文的方法和ADL的壓縮性能與CDF9/7小波相比較有非常明顯的提高。而且在低比特率時(shí),本文的算法優(yōu)于ADL。其原因在于,本文算法得到的方向信息少,因此,在低比特率的情況下效果較好。表3 PSNR比較 dBLena Barbara比特率/bpp CDF9/7 ADL 本文方法CDF9/7 ADL 本文方法0.125 30.50 30.84 30.89 24.44 26.34 26.460.250 33.68 34.13 34.09 27.08 29.23 29.160.500 36.8

21、2 37.20 37.17 30.84 33.11 33.011.000 39.95 40.15 40.12 35.82 37.60 37.54圖3和圖4是Lena和 Barbara經(jīng)過CDF9/7小波、ADL算法和本文算法所得到的壓縮效果比較(比特率均為0.3 bpp?？梢钥闯?CDF9/7的壓縮效果有很大的提升。對比于ADL的方法,雖然在高比特率的情況下,信噪比有所下降,但在低比特率的情況下,信噪比相對上升。(a原圖(bCDF9/7(cADL (d本文方法圖3 Lena圖像壓縮效果比較(a原圖(bCDF9/7(cADL (d本文方法圖4 Barbara圖像壓縮效果比較6 結(jié)束語本文提出了一

22、種基于灰度共生矩陣圖像分塊的方向提升小波變換算法。通過灰度共生矩陣中的角二階矩方法來自適應(yīng)地檢測圖像的平坦性,每個(gè)分塊自適應(yīng)地選擇提升小波變換,從而減少算法復(fù)雜度。實(shí)驗(yàn)結(jié)果表明,該算法與傳統(tǒng)方向提升小波變換算法相比,在保證圖像壓縮性能前提下,能大幅減少計(jì)算時(shí)間。下一步工作將研究如何提高圖像紋理性分塊的準(zhǔn)確性。參考文獻(xiàn)1 Sweldens W. The Lifting Scheme: A New Philosophy in Biortho-gonal Wavelet ConstructionsC/Proc. of SPIE Conference onWavelet Applications in Signal and Image Processing III.San Diego, USA: SPIE Press, 1995: 68-79.2 Do M N, Vetterli M. The Contourlet Transform: An Ef