一種改進的嵌入式零樹小波圖像編碼算法

黃 慶

（南昌大學 信息工程學院，江西 南昌 330031）

0 引言

隨著社會的發展，圖像編碼壓縮技術已經應用于人們生活和工作的各個方面。在其理論研究和應用技術方面都取得了很大的進展，特別是近20年來的成果尤其令人矚目。

圖像壓縮所解決的問題是盡量減少表示數字圖像時需要的數據量，圖像壓縮的基本原理是減少數據之間的冗余，從統計數學的角度來分析，就是將二維像素陣列變換為一個在統計上無關聯的數據集合。未經壓縮的圖像數據量十分龐大，這就給圖像在存儲、傳輸方面造成了諸多困難，因此在傳輸前必須對圖像進行處理。基于離散傅里葉變換（DCT）的圖像壓縮，由于將圖像分成相互獨立的小塊，然后分別對這些小塊進行DCT變換，這就引起了方塊效應。小波變換不僅具有頻率壓縮特性，而且同時具有空間域壓縮特性。這些特性一方面表現為大部分的圖像能量集中在最低頻率的子圖像中，并從低頻到高頻呈遞減分布趨勢；另一方面，個子圖像對應相同空間位置的像素之間存在這較強的空間相關性。因此，基于小波變換個子帶系數的分布特點，基于小波變換的嵌入式圖像編碼技術取得了快速發展。

自從嵌入式編碼的構想提出以來，學者們提出了各種嵌入式編碼方案。由Shapiro[1]提出的EZW算法被認為是現今最好的圖像壓縮算法之一。EZW算法利用分解后小波系數的特點，用零樹的數據結構來組織小波系數，實現了圖像的高效壓縮。

1 零樹的表示方法

變換編碼的主要思想是使變換系數矩陣經過量化后，產生大量的零符號。那么，后續的問題就是如何高效地表示非零符號，包括位置和幅度。而量化無非是設定一個閥值T，當符號的幅度大于T則量化為非零，反之為零。在這里規定幾個術語：對于給定閥值T，如果符號共4個系數是根節點的子節點，1HH子帶內則稱X為重要系數；否則，稱X為非重要系數。

可以構造零樹的數據結構來對小波系數進行有效地組織。假如以3HH子帶內的第(,)i j個系數作為根節點，則2HH 子帶內(2,2)i j、(2 1,2)i j+ 、共16個系數是根節點的孫節點，這棵樹有三層共21個系數值。當然，樹的根節點也可以在其他子帶內定義，如果在2LH子帶內(,)i j系數作為根節點，則在1LH子帶內有4個子節點，它沒有孫節點，子帶1LH、1HL、內的系數都沒有子孫節點，因此它們不構成樹的根節點。

2 小波系數的掃描方式

小波系數的掃描方式如圖 1所示：對于一個3尺度的變換，掃描從最低頻率子帶3LL開始，依次掃描3HL,3LH和3HH，然后進入第2層，按照同樣的方式進行。這種方式保證了在訪問某一節點時，其父節點已全部掃描。

圖1 小波系數掃描流程

掃描中訪問的每個系數本分成3種類別：第一類零樹根，用T標示；第二類稱為孤零，用Z標示，表示當前系數是非重要系數，但它的子孫系數中至少有一個重要系數；第三類是重要系數，表示當前系數是一個重要系數，且正數用（POS）表示，負數用（NEG）表示。這4種情況用2 bit標示即可。通過對各子帶的掃描，形成一個符號表，根據系數的類別將 T，Z放入表中，在掃描的過程中遇到零樹根，再對其子孫系數進行判斷[2]。

3 經典的EZW算法的缺陷

通過對算法進行仿真，發現EZW算法在掃描的過程中，越往后零樹根出現的概率越高，這就造成了重復掃描，浪費了掃描時間，為了解決這個問題[3]，文中提出了一種改進的 EZW 算法，用 6個標志位代替 EZW 算法中的4個標志位對小波系數進行量化，實驗證明，改進后的算法與原EZW算法相比，提高了編碼效率。

4 改進的EZW算法

EZW 算法沒有充分利用小波變換后各子帶系數的特點，為了確定輸入系數的類型，需要對該系數及后代進行搜素掃描，導致了二進制符號流存在大量冗余，從而使編碼效率下降[4]。針對EZW存在的不足，文中提出了一種改進的EZW算法，與EZW的不同之處在于能夠實現零樹結構的快速判斷。為了判斷系數是零樹根還是孤零，其實只需讓該系數及子孫后代中的最大值與當前閥值進行比較，這樣就能夠減少掃描的時間，從而提高了編碼效率。將主掃描所產生的碼流進行哈夫曼編碼，再將編碼后的比特率與量化產生的比特流組合進行算術編碼，這樣就實現了壓縮比與編碼效率的提高[5]。

文中提出的算法采用增加2種類型來對小波系數進行標識[6]，分別是1P和1N，若該系數是一個重要系數且該系數的后代子孫均為次重要系數，就用1P或1N標示該系數，在后續掃描中對這些系數跳過不處理，這樣做能有效地減少掃描時間，提高編碼效率[7]。系數類型判斷流程如圖2所示。

圖2 小波系數判斷流程

首先輸入一個系數，將該系數與閥值進行比較，若大于閥值，則該系數被判為重要系數，再判斷該系數的子孫中是否有大于閥值的，若有則輸出P或者N，否則輸出1P或1N，并對該系數的后代進行標示，以便在后續的掃描中將其跳過不處理。如果該系數小于閥值但該系數的后代中有大于該閥值的，則 輸出孤立零 Z，否則輸出零樹根 T。將發現的重要系數幅值記錄下來[8]，同時將該系數置0，這是為了后續掃描閥值減少時，不影響零樹的出現。在進行住掃描后緊接著是副掃描，副掃描的目的是對已發現的重要系數進行更細化的表示[9]。表1和表2分別顯示了 EZW 算法和文中算法對 Lena，Barbara 和 Camera 標準圖像在終止閾值為 16 時的符號個數、百分比和編碼時間。主掃描中標志位有 6 個（P, N, Z, T,1P和1N）需要3比特來編碼，從表1和表2中可以看出它們在掃描過程中出現的頻率是不同的，P出現的概率大概為10%，零樹根Z出現的概率大概為20%。

5 實驗結果及分析

為了將文中提出的算法與傳統的 EZW 算法進行比較，選用大小為512*512的3幅灰度圖像Lena、Barbara 和 Camera作為實驗。對原始圖像采用整數正交小波變換進行 4級分解。表 1 和表 2分別顯示了采用 EZW 算法和文中算法對 Lena、Barbara和 Camera 標準圖像在閾值為 16 時的結果。

標志位符號

Lena Barbara Camera

符號個數 百分比 符號個數 百分比 符號個數 百分比

表1 EZW算法在閾值為16時符號個數和百分比

表2 文中算法在閾值為16時符號個數和百分比

實驗結果表明：改進后的算法掃描時間相當于原始算法的1/2，標示符雖然增加了2個，但總標示符數量卻減少了，量化之后的比特位也減少了。圖3為 Lena、Barbara 和 Camera 標準圖像在閾值為32時的原圖與重構圖像。表 3 是3 幅圖像在不同閾值的壓縮倍數和峰值信噪比。文中改進的EZW算法與原 EZW 算法在相同的峰值信噪比下的壓縮倍數比較，可以看出文中算法重新設置標志位類型和二次壓縮的方法大大提高了壓縮比，明顯優于 EZW算法，尤其在中高比特率時，效果更明顯。

圖3 Lena、Barbara和Camera標準圖像在閾值為32時的原圖與重構圖像

表3 EZW算法與文中算法的結果

6 結語

通過以上的實驗可以看出，改進之后的算法與經典算法相比較，性能有了很大的提升，這使得改進算法離實際運用更近一步。改進算法通過減少標記符號提高了性能。改進的新算法有如下優點：①通過增加2個系數標示符號，減少了重復掃描時間，從而避免了產生大量冗余比特流，提高了圖像編碼效率；②通過多級編碼實現了圖像壓縮比的提高。

[1] SHAPIRO J M. Embedded Image Coding Using Zerotree of Wavelet Coefficients[J].IEEE Trans Signal Processing,1993, 41(12):3445-3462.

[2] PUJOL F A,MORA H,SANCHEZ J L,et al.EZW-Based Image Compression with Omission and Restoration of Wavelet Subbands[J]. Electronics Letters,2007,58(32): 134-141.

[3] PATEL S,SRINIVASAN S.Modified Embedded Zerotree Wavelet Algorithm for Fast Implementation of Wavelet Image Codec[J]. Electronics Letters, 2000,36(20): 1713-1714.

[4] PENEDO S R M,SEAM R. An Improved EZW Algorithm based on Set Partitioning in Hierarchical Trees Using Wavelet Regularity[C]// International Conference on Image Processing. Singapore,Piscataway,N J:Institute of Electrical and Electronics Engineers,2004:3169-3172.

[5] DEEVER A,HEMAMI S.Efficient Sign Coding and Estimation of Zero-Quantized Coefficients in Embedded Wavelet Image Codecs[J]. IEEE Transaction On Image Processing, 2003, 12(04): 420-430.

[6] 鄭偉,崔躍利,王芳.基于小波變換的圖像壓縮編碼研究綜述[J].通信技術, 2008,41(02):83-85.

[7] 李淑云,朱桂斌,楊琬.基于提升小波的圖像水印算法[J].通信技術,2007,40(12):73-82.

[8] 張磊，趙維. 基于 DCT的圖像低頻域數字水印方法[J].信息安全與通信保密,2007(03):85-86.

[9] 王艷,李秀瀅.基于小波變換的信息隱藏技術的改進[J].信息安全與通信保密,2012(02):23-32.