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

1、基于ADL 小波變換的圖像壓縮算法林 娜,倪 林,劉 權(中國科學技術大學電子工程與信息科學系,合肥 230027摘 要:提出一種基于自適應方向提升(ADL小波變換的圖像壓縮算法。根據灰度共生矩陣角二階矩的差異,將圖像分割成平坦性不同的分塊。對紋理信息較少的塊,采用一般提升小波變換以減少變換時間。對紋理信息較多的塊,采用方向提升小波以提高變換效果。結合多級樹集合分裂編碼和算術編碼對變換系數和方向信息分別進行編碼。實驗結果表明,與ADL 算法相比,該算法能有效減少方向小波變換時間。關鍵詞:圖像壓縮;自適應方向提升;灰度共生矩陣;角二階矩;多級樹集合分裂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計 算

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

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

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

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

10、 45°, 90°, 135° 4個方向。作者簡介:林 娜(1987-,女,碩士研究生,主研方向:視覺信息處理,圖像壓縮;倪 林,副教授、博士;劉 權,碩士研究生 收稿日期:2011-04-29 E-mail :lin7453200 計算機工程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中的求和都是在整個窗口進行。其中角二階矩是一種對圖像灰度分布均勻性的度量。當數值分布較集中于主對角線附近時,其相對應的AS

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

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

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

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

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

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

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

18、系數和能量平均值上,將本文方法和一般提升小波變換做比較?？紤]變換后高頻系數平均幅度和高頻平均能量,比較變換后的第1層高頻。本文方法和CDF9/7方法第1層高頻子帶能量和系數的平均值的比較結果如表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可以看出,利用本文方法進行變換后高頻能量顯著減少,高頻系數的平均幅度得到降低。如Barbara圖,它

19、的高頻分量的平均系數值下降到了4.55,能量也有大幅度的下降。其他的圖像也有較明顯的下降。這說明本文提出的方法能更好地自適應于圖像的紋理信息,減少了圖像變換后的信息冗余,為以后的壓縮、去噪等提供有力的條件。改進后方法在計算復雜度上和ADL5方法的實驗結果比較如表2所示,主要比較特征是計算時間?？梢钥吹?運用本方法可有效減少運算時間,提高程序運行的效率。表2 進行5級小波變換的計算時間比較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小波相比較有非常明顯的提高。而且在低比特率時,本文的算法優(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經過CDF9/7小波、ADL算法和本文算法所得到的壓縮效果比較(比特率均為0.3 bpp?？梢钥闯?CDF9/7的壓縮效果有很大的提升。對比于ADL的方法,雖然在高比特率的情況下,信噪比有所下降,但在低比特率的情況下,信噪比相對上升。(a原圖(bCDF9/7(cADL (d本文方法圖3 Lena圖像壓縮效果比較(a原圖(bCDF9/7(cADL (d本文方法圖4 Barbara圖像壓縮效果比較6 結束語本文提出了一

22、種基于灰度共生矩陣圖像分塊的方向提升小波變換算法。通過灰度共生矩陣中的角二階矩方法來自適應地檢測圖像的平坦性,每個分塊自適應地選擇提升小波變換,從而減少算法復雜度。實驗結果表明,該算法與傳統(tǒng)方向提升小波變換算法相比,在保證圖像壓縮性能前提下,能大幅減少計算時間。下一步工作將研究如何提高圖像紋理性分塊的準確性。參考文獻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