基于整數小波變換和嵌入零樹的圖像壓縮算法

摘要:小波變換因其具有良好的時、頻局部化性能，在圖像壓縮編碼中得到廣泛的應用。尤其提升小波的出現使無損壓縮成為可能。該文采用整數小波對圖像進行四級二維小波變換，根據系數特點介紹了一種小波零樹的圖像編碼算法，給出了具體的算法編碼實例，并用512×512的Lena圖像對算法進行了仿真實驗。

關鍵詞:提升算法;整數小波;嵌入零樹編碼;圖像壓縮

中圖分類號:TP317文獻標識碼:A 文章編號:1009-3044(2010)11-2724-03

An Image Compression Algorithm Based on Integer Wavelet Transform and Embedded Zerotree

ZHANG Chun-xiang，CHEN Xiao-long

(Jiangxi Tourism and Commerce Vocational College， Electrical and Mechanical Engineering Branch，Jiangxi 330100，China)

Abstract: Wavelet transform has got widely used in image compressing because of its good local characteristics in time and frequency domain. In particular， the realization of the lifting wavelet makes lossless compression possible. By using integer wavelet transform， one image is transformed into four scaling two dimension wavelet field. Besides， an image wavelet encoding arithmetic is introduced according to the character of wavelet coefficients， and a case study of the arithmetic coding is presented. Finally， a simulation is carried out with a Lena image of 512 ×512.

Key words: lifting algorithm，;interger wavelet; embedded zerotree encoding; image compression

近年來，人們對整數小波變換(IWT)在圖像壓縮領域中的應用研究越來越感興趣。整數小波變換作為新一代圖像壓縮標準JPEG2000的核心部分已經得到廣泛研究.Shapiro提出的零樹編碼[1]則是當前小波圖像壓縮算法中最常用的編碼技術. IWT是一種有限精度的計算，又是整數到整數的變換。如果將整數小波變換與嵌入式零樹編碼有機地結合起來，不僅可以發揮整數小波變換的優點，還能大幅度提高圖像的壓縮效率。

在提升格式(lifting scheme)[2-3]下建立的整數小波變換具有變換可逆、整數存儲及只有加減和移位運算等優點.可以將整數小波變換中截斷取整看成對圖像加噪的過程，從修改整數小波變換的角度改善了壓縮效果，雖然改進了編碼算法，但該算法立足于整數小波變換的調整，提高了編解碼的復雜度和不可靠性。該文介紹了一種基于小波零樹的無損圖像壓縮編碼算法，并用提升方法對圖像進行分解，對512×512的Lena圖像進行算法仿真實驗。

1 整數小波變換(IWT)

傳統小波由同一母函數經過平移和伸縮運算后得到不同分辨率下的小波基函數。小波函數被定義為在L2(R ) 空間上的母小波 ψ(x ) 的二進伸縮和平移， 即小波函數為:ψi，k(x) =ψ(2ix- k) ， 被稱之為第1 代小波。在實際應用中第1 代小波存在一些問題: 1) 信號經過小波變換后產生的是浮點數， 受計算機有限字長的影響， 往往不能精確地重構信號; 2) 對圖像的尺寸有要求， 并不能對所有尺寸的圖像進行變換; 3) 對內存的需求量較大。這樣構造的小波基函數難以得到其整數表示形式。為克服上述問題， 引入另外一種小波實現算法——“提升”算法[2]。

1.1 小波變換的“提升”算法

“提升”算法是由Wim Sweldens 等人提出的一種新的小波構造方法， 它在構造小波的方式上不是用傅里葉變換和基于傅里葉變換的尺度收縮， 而是直接通過簡單地分裂、預測和更新等一系列步驟來完成對一列數字信號的變換。“提升”算法的基本思想是將現有的小波濾波器分解成基本的構造模塊， 分步驟完成小波變換。因此， 可以將小波變換分解成3個過程: 分裂(split)、預測(predict) 和更新(update)。

1) 分裂。將輸入信號si分為2個較小的子集si-1和d i-1， d i-1也稱為小波子集。最簡單的分裂方法是將輸入信號s根據奇偶性分為2組， 對應于這種分裂所產生的小波被稱之為懶小波(Lazy Wavelet) ，分裂過程表示為F(si) = (si-1， di-1) ， 其中F(si)為分裂過程。

2) 預測。在基于原始數據相關性的基礎上， 用偶數序列s i-1的預測值P (s i-1) 去預測(或者內插) 奇數序列d i-1， 即將濾波器P 對偶數信號作用以后作為奇信號的預測值， 奇信號的實際值與預測值相減得到殘差信號。實際中， 雖然不可能從子集si-1中準確地預測子集d i-1， 但是P (s i-1) 有可能很接近d i-1， 因此可以使用P (s i-1) 和d i-1的差來代替原來的d i-1， 這樣產生的d i-1比原來的d i-1包含更少的信息。于是得到

di-1 = d i-1- P(si-1)(1)

這里， 已經可以用更小的子集s i-1和小波子集di-1來代替原信號集si。重復分割和預測過程， 經n 步以后原信號集可用{sn ， d n， … ， s1， d1}來表示。

3) 更新。為了使原信號集的某些全局特性在其子集s i-1中繼續保持， 例如， 希望分解后的子圖像s i-1仍然保持原來整個圖像的亮度值， 即s i-1和原圖有相同的像素平均亮度值， 必須進行更新。更新的思想是要找一個更好的子集si-1， 使得它保持原圖的某一標量特性Q (x ) (例如均值、消失矩等不變) ， 即有Q (si-1) = Q (si)。可以利用已經計算的小波子集di-1對si-1進行更新， 從而使得后者保持特Q(x) ，即要構造一個算子U去更新si-1。定義如下:

si-1= si-1+ U (di-1) (2)

分解重構見圖1。

1.2 整數小波變換[3-4，7]

基于提升算法的小波分解操作， 其輸出結果仍然為小數。從式(1) 和(2) 可以看出， 輸出結果的小數部分是由其中的“預測”和“更新”濾波器引入的， 對其取整即可得到整數變換結果， 取整操作相當于對原來的小波濾波器系數作了很小的改動，但是小波分解的特性仍然保留。具體公式為di-1= di-1- ?骔P(si-1)」， s i-1= si-1+ ?骔U(di-1)」，其中?骔x」是取不大于x的最大整數運算。逆變換僅僅需要將上面“+ ”和“- ”號互換及順序顛倒。

2 小波零樹編碼

2.1圖像的小波變換與系數的分布特點[1，5]

根據提升小波的步驟對圖像進行小波分解，圖像分解后分割成四個頻帶:低頻、水平、垂直和對角方向，低頻部分可繼續再分解。若把第一次分解得到的四個子圖，記為LL1、HL1、LH1、HH1，第二次再對低頻的LL1進行分解得到四個子圖，記為LL2、HL2、LH2、HH2，依次類推直到滿足要求為止。

圖像經m級小波變換后得到不同分辨率的子圖個數K=3m+1，各高頻子圖上的小波系數具有統計分布特性相似，系數間存在相關性。隨著分解層數的增加，小波系數的范圍越來越大，分辨率最低的子圖LL的小波系數的范圍最大;高分辨率子圖上大部分數值接近于0，頻率越高，系數的范圍越接近于0，不為0的小波系數主要集中在LL低頻帶;對一幅圖像來說，大部分信息保留在低頻部分，高頻部分只包含其對應圖像邊緣、輪廓等的細節信息。

2.2 圖像小波系數的嵌入式零樹編碼

2.2.1零樹的定義[6]

經過m級小波變換的小波圖像，對于低頻子圖中的某一系數而言，與其對應的具有相同空間定位的高頻子圖中的系數稱為是它的子孫，從圖像的低頻層開始依照子孫關系延伸，得到樹形結構。圖2是三級小波變換的系數樹結構。小波零

樹建立的假設基礎:若在粗尺度下小波系數小于給定的閾值T，則在較細尺度下相同方向上的所有系數都幾乎小于T。

2.2.2EZW零樹編碼算法原理

零樹編碼是針對小波系數零樹結構進行的，利用了小波系數的空間-頻率局部化特性和級間系數幅值分布的相似性，通過閾值逐次減半方式實現逐級編碼。

根據變換后的小波系數確定初始閾值T0=2INT(log2(max))，其中max為小波系數的最大值，INT為取整操作。根據闕值K將系數分為四種情況:P表示該系數絕對值大于等于門限且為正，N表示該系數絕對值大于等于門限且為負，T表示該系數不重要且它的所有后代不重要，Z表示該系數不重要但它的后代中有重要系數。為了利用不同尺度下子帶的相關性，采用Z字形的順序掃描。

EZW編碼算法在一閾值下經過兩個過程:主掃描(Dominant_pass)和副掃描(Subordinate_pass)。然后將閾值降為原來的一半，步驟同上。當閾值不斷降低，就實現了逐次逼近的嵌入式編碼。其過程可以描述為:

K = K0;

Do{

Dominant_pass(image);

Subordinate_pass(image);

K = K/2;

}while(K>0);

其中主掃描實現以下3項任務:

1) 按一定的順序掃描小波系數，根據小波系數輸出碼流，設系數為x，當前閾值為K，其輸出規則如下:

如果x>K，則輸出P;

如果x<-K，則輸出N;

如果|x|〈K，且該系數后代中有重要系數，則輸出Z;

如果|x|〈K，且該系數后代中沒有重要系數，則輸出T;

2) 將所有的重要系數抽取出來，其絕對值放入被稱為附屬表的一維數組中。

3) 在重要系數的位置處填零。

輔掃描根據附屬表中存的系數輸出0或者1，0表示系數在下半區，即K到3/2 K之間，1表示系數在上半區，即3/2 K到2K之間。附屬表中的系數每次掃描結束根據重構值的大小重新排序。

最后當閾值K降為1時，根據主掃描和副掃描輸出的碼流就能無誤的表示出所有系數的值。要實現無損壓縮，還要對輸出的碼流進行熵編碼，一般采用算術編碼或者游程編碼。

2.3 解碼

解碼是編碼的逆過程。EZW解碼仍然采用主掃面和副掃描。主掃描從數據流中載入主掃描代碼來恢復系數的重要信息。采用與編碼時保存系數重構位置的同樣的掃描順序是至關重要的。當碰到代碼P或N，當前系數的位置加到輔助列表。當圖像中的所有系數已被掃描，主掃描就停止。輔掃描從數據流中為輔助列表中的每個系數載入1比特。這個比特與當前閾值相乘后加到正系數上或從負系數中減去。當預定的性能指標達到或數據流已為空時，解碼停止。

3 算法實例說明

圖3是一幅8×8的圖像經過3級分解后的小波系數，在此用它來說明EZW編碼算法。其中Di為第i次主掃描編碼結果，Si為i次副掃描。編碼結果。編碼結果如下:

D1:PNZTPTTTZTTTTTTPTT

S1: 1010

D2: ZTNPTTTTTTTT

S2: 100110

D3: ZZZZZZPPNPPNTTNNPTPTNTTTTTTTTPTTTTTTTPTTT

TTTTTTTTT

S3: 1010001111011011000

D4: ZZZZZZZTZTZNZZZZPTTPTPPTPNPTNTTTTTPTPNPP

PPTTTTTPTPTTTPNP

S4: 10111110110110100001110110100010010101100

D5: ZZZZZTZZZZZTPZZZTTPTTTTNPTPPTTPTTTNPPNT

TPTTPPTTT

S5: 111111010010100110111110100000010110100

00011011110011000111

D6: ZZZTTZTTTZTTTTTNNTTT

4 仿真實驗結果及其結論

本文選用512×512的Lena圖像進行了壓縮編碼實驗。每個像素用一個字節表示，像素值的大小界于0到255之間。壓縮編碼過程為:先對圖像進行整數小波變換，采用Daubechies(5，3)小波的提升算法實現，進行四級二維小波變換。然后進行EZW算法編碼，最后對碼流進行算術編碼[7]。實驗結果見表1，圖4是實驗原圖，圖5是不同壓縮比下的重構圖。

由實驗結果觀察可知，在壓縮比為8:1時基本上和原圖無差別;在壓縮比為16:1時，視覺效果和原圖有稍微差別，視覺效果較好，細節豐富。從圖可以看出，小波變換有效地克服了傳統余弦變換編碼在不同壓縮比下的方塊效應，因此小波變換已經成為當今圖像壓縮編碼的主要研究方向。

表1 EZW算法在不同比特率下的壓縮性能

參考文獻:

[1] Shapiro J M.Embedded Image Coding Using Zerotrees of Wavelet Coefficients[M].IEEE Transactions on Signal Processing，1993.

[2] Sweldens W.The lifting scheme:A custom-design construction of biorthogonal wavelets[J].Appl. Comput. Harmon. Anal，1996，3(2).

[3] Sweldens W.The lifting scheme:A construction of second generation wavelets， SIAM J.Math. Anal，1997，29(2).

[4] Adams M D.Reversible Integer-to-Integer Wavelet transforms for image compression: Performance evaluation and analysis[M].IEEE Transactions on Image Processing，2000.

[5] 白浩，劉於勛.一種改進的嵌入式圖像壓縮EZW編碼算法[J].通信技術，2008(1)

[6] 張旭東，盧國棟，馮健.圖像編碼基礎和小波壓縮技術-原理、算法和標準[M].北京:清華大學出版社，2004.

[7] 閆凡勇，張穎.基于小波變換的圖像壓縮技術[J].電腦知識與技術，2010(3).