一種基于改進ＥＺＷ算法的圖像壓縮方法

(1.中國科學院 遙感應用研究所 遙感信息國家重點實驗室， 北京 100101； 2.北京交通大學 交通運輸學院， 北京 100044） 

摘 要：在EZW算法的基礎上提出了一種適合大型圖像壓縮的改進算法，該算法首先將巨型圖像分解為若干幅小的圖像塊，對這些小圖像子塊進行小波變換后，先用EZW對其進行編碼，再用Huffman技術對其進行二次編碼。該方法既能夠保證利用小波系數之間的層次關系，又能提高圖像的壓縮率。還提出了一種自適應讀寫圖像的方法，根據圖像的大小自動調用不同的讀寫方式，為大型圖像在Web上實時發布和漫游提供了技術基礎。

關鍵詞： 小波; EZW; 圖像壓縮; 自適應讀寫

中圖法分類號： TP391文獻標識碼： A

文章編號： 1001 3695(2006)08 0174 03



Improved EZW Algorithm for Image Compression 

LI Jin ping1， RUI Xiao ping2， YANG Chong jun1

(1.The State Key Laboratory of Remote Sensing Information Sciences， Institute of Remote Sensing Applications，Chinese Academy of Sciences， Beijing 100101， China; 2.School of Traffic Transportation， Beijing Jiaotong University， Beijing 100044， China)

Abstract: This paper presents an improved EZW algorithm for massive image compression. This method divides the massive image into some sub blocks. Based on the wavelet transformation for these sub blocks， it first uses EZW coding for them and then uses Huffman coding for them. This method can ensure that makes the best use of the hiberarchy relationship of wavelet coefficients and also can improve the compress rate. The authors brings out an adaptive reading/writing method according to the size of image， which is composed of two parts strip reading/writing and block reading/writing， the cache mechanisms of these two parts are also introduced in this paper. The authors apply this method into browsing massive image on Web and get a good effect.

Key words: Wavelet; EZW ; Image Compression; Adaptive Reading/Writing

隨著現代信息社會對通信業務要求的不斷增長，圖像通信與通信網容量的矛盾日益突出，特別是具有龐大數據量的數字圖像通信，更是難以在網絡上實時傳輸與瀏覽。這樣就使圖像信息在網絡上進行數據共享變得非常困難，成為了圖像通信發展中的“瓶頸”問題。因此對于高比率圖像壓縮算法的需求尤為迫切，圖像壓縮問題成了越來越多的科研工作者的研究熱點。這些年來關于小波變換圖像壓縮算法的研究和應用都十分活躍。國外一些公司將這種技術用于Internet環境中的圖像數據傳輸，提供商業化的服務，對于緩解網絡帶寬不足、加快圖像信息傳播速度起到了很好的推進作用。作為一種優秀的圖像壓縮算法，小波變換在這一領域具有非常好的應用前景，也應該能夠發揮關鍵性的作用，同時也必將對這種技術在我國的推廣和應用起到有力的推動作用[1，2]。

1 EZW算法簡介

圖像通過小波變換后產生大量不重要的數據，通常需要經過量化處理和編碼處理，拋棄不重要的數據才能實現圖像的壓縮。零樹編碼是當前小波圖像壓縮算法中最常用的編碼技術。基于零樹編碼的規則，Shapiro等人首先提出了嵌入式零樹編碼（Embedded image coding using Zerotree of Wavelets coefficients，EZW）算法[3]，該算法是第一個使用零樹編碼的小波圖像壓縮算法，它利用小波圖像中各級子帶間的相似性，對系數按重要性進行排序，然后對系數進行逐級量化，最終得到按系數重要性排序的比特流。EZW算法的這種內嵌編碼方式使得圖像在網絡上累進傳輸成為可能，并且用戶可以根據需要任意確定圖像壓縮的比率，因此，EZW算法一經提出就受到了廣泛的關注。

EZW算法的基本流程是：圖像經過小波變換后，首先對其系數進行量化處理，按照2的整數冪從高到低排列量化閾值（通過量化閾值，對小波變換后的所有系數進行調整，將重要的系數保留，將不重要的系數忽略，從而讓圖像得到任意比例的壓縮），結合低尺度系數與高尺度系數分布關系，生成四種符號，即正重要系數(POS)、負重要系數(NEG)、孤立零點(IZ)和零樹根(ZTR)；逐級遞減量化閾值，按掃描順序搜索重要系數，根據搜索結果形成重要系數坐標序列，輸出索引；小波系數幅值逐級細化，在每一級量化閾值上，根據重要系數坐標序列輸出這些坐標在該閾值上的1比特值[4]。

這種EZW編碼算法對圖像的壓縮比例非常大，圖像還原的效果比較滿意，但該算法也存在一些缺陷，如必須開辟與圖像比例為 1∶ 1 的內存塊，然后對圖像進行多次掃描，進而還原整個圖像的小波系數代碼，不方便進行分塊等。本文在分析嵌入式零樹編碼的基礎上，提出了一種EZW的改進算法，下面將詳細描述本算法的實現過程。

2 改進的EZW算法

為了能夠保證大型圖像在網絡上的實時傳輸，通常需要將圖像進行分塊處理，用戶操作的圖像只是整個圖像中的一小塊。也就是說，在對圖像進行操作時，只要對用戶關心的區域進行小波壓縮即可，而沒有必要將整個圖塊全部讀入內存并進行壓縮運算。因此作者提出分塊EZW算法對圖像進行處理，該算法將圖像分割為一定大小的塊，對每一塊分別進行小波變換和EZW編碼，這樣就突破了EZW不能進行的圖像漫游（分級瀏覽）局限。

2.1 EZW和Huffman雙重編碼機制

通過實驗，作者發現EZW的編碼結果依然存在冗余數據，還可以進一步進行壓縮。可見，EZW并非是最優編碼，還可以進一步進行優化。針對EZW算法的特點，筆者在EZW編碼后，繼續使用Huffman編碼，進一步對圖像數據進行壓縮。 這種雙重編碼的方式一方面能夠保證EZW算法利用小波系數之間的層次關系，另一方面可以更大地提高圖像壓縮比率。這里重點介紹在EZW編碼基礎上再進行Huffman編碼的實現過程。

Huffman編碼的基本思想是：先統計出有多少像素，每一個像素出現的概率。然后按照概率的大小，進行排序，大概率在前，小概率在后。接著將最小的兩個概率變成一個單元二叉樹，較大概率的放在左葉節點，較小的放在右葉節點，同時新生成一個節點，該節點的概率為兩個葉節點的概率和，將該節點按大小插入到原代碼列中并刪除那兩個節點，如此反復，最終生成Huffman樹。按照生成的Huffman樹對代碼進行編碼，規則為左0右1。本文將像素出現的概率分為八類，則進行Huffman編碼的步驟可以敘述如下：

(1)將像素值按其概率分布，由大到小排列，像素分類如表1所示。

(2)最小的兩個概率變成一個單元二叉樹，較大概率的放在左葉節點，較小的放在右葉節點，同時新生成一個節點，該節點的概率為兩個葉節點的概率和。

(3)將新節點插入到原代碼列中，并刪除最小的兩個概率。 

(4)如此反復，直到原代碼列中只剩下一個節點，并且概率等于1，到此生成Huffman樹，如圖1所示。

(5)按照Huffman樹的結構對代碼進行編碼，如表2所示。規則為左0右1，如圖2所示。

對文件的代碼進行編碼時，生成代碼表，然后進行編碼，壓縮后的Huffman樹必須保存，以供后面使用。Huffman編碼是無損壓縮編碼，對于離散性較小的信息壓縮效果比較好，是所有無損壓縮編碼中編碼最優的。在壓縮階段，由于需要對所有代碼進行掃描，所以將會稍稍影響速度，但在解壓過程中，不會出現此類問題。

2.2 圖像的自適應讀寫

本文中的EZW算法是針對任意圖像塊的，因此必須設計一個適合任意大小圖像的自適應讀寫模塊，以供圖像的壓縮編碼使用。對于一幅圖像，首先要判斷其大小，如果給定圖像子塊大小，則可以對整個圖像作如下判斷：

(1)如果圖像不是大型圖像（大型圖像的長寬定義可以自己設置），則采用“帶讀寫”方法，按照子塊的高度和寬度直接按照特定的順序讀或寫。讀寫順序按照光柵掃描的順序從上至下，從左至右進行掃描。一次從左到右讀入一個條帶，并將條帶數據存放到內存中，再分別輸出每一塊的數據信息。

(2)如果圖像是大型圖像，則將該圖像分成若干個子塊，根據用戶需求（比如用戶拉框選擇確定的圖像范圍）對每一塊數據進行精確的定位，讀一塊，輸出一塊。對于塊，要求為正方形，且邊長必須被2ⁱ整除，i 為小波變換的級數，一般設定塊的大小為800×800或1 600×1 600。對于邊界上的塊，將其大小調整至符合要求，如在五級小波變換的情況下，如果邊界的長為27，就將其調整為32，如果邊界的寬為34，就將其調整為64，本文將兩者之差稱為拓展寬度。調整時調大不調小，在調整過程中，拓展的數據設置其顏色為白色（0xFF）。

在圖像子塊無縫壓縮時，輸出的矩陣保證能被2ⁱ整除，i 為小波變換的級數，其邊界數據將用相鄰的塊對應位置的數據進行填充。每一次寫數據時，將拓展的數據拋棄。

2.3 圖像讀寫的存儲分配和緩沖機制

由于顏色由RGB三種分量組成，為了提高速度，將三種分量同時讀入內存，為了節省內存，將三種分量分別進行小波壓縮處理。帶讀寫時，為了能夠以最佳的速度讀取數據，所以將讀寫文件的緩沖內存均設為一維數組，盡可能地一次讀滿緩沖區。一次將條帶數據讀入到一維數組中，輸出信息矩陣時，在該數組中尋找需要的數據；塊讀寫時，分 N 次將塊數據讀入到二維數組中，然后再將數據輸出。由于無縫壓縮讀取數據需要相鄰的行與列的邊沿數據，所以有必要開辟內存，將邊沿數據保存。在帶讀中，相鄰的列之間數據已經讀到內存中，所以無須再進行另外的保存；但相鄰的行之間需要進行數據保存，為此將建立一個寬度為圖像寬度，高為邊沿重疊寬度（取邊沿拓展寬度的兩倍）的緩沖區。

建立緩沖機制的總體思想是，在進行圖像數據讀寫時，已經讀入的數據不能完全拋棄，等到需要時能夠在內存中找到，而且占用內存必須盡可能地少。下面以邊沿拓展寬度為7為例說明讀寫圖像的緩沖機制。

針對帶讀方式，子塊兩側邊沿像素在帶讀的同時，數據已經在內存中將其找到，填充到要輸出的信息矩陣中就可以了。而對于相鄰之間的數據則需要建立條帶緩沖區。

建立條帶緩沖區的方法是：首先，先讀入7行數據，放在條帶緩沖區的7～14行，其中1～7行為拓展寬度，用白色表示。以后每讀入一個條帶的數據就將條帶的后14行數據復制到條帶緩沖區中，如此循環，如圖3所示。這樣，在處理條帶數據時就可以方便地從緩沖區中獲取相鄰邊界的14行數據，保證在小波運算時邊界不出現縫隙。

針對塊讀方式，與帶讀方式不同的是，在增加一個條帶緩沖區的同時，需要增加一個列邊沿緩沖區，寬度為邊沿重疊的寬度（邊沿拓展寬度的兩倍）。為了簡化緩沖機制，完全可以將列緩沖區和塊緩沖區合并在一起。與帶讀緩沖機制相似，首先讀入長為圖像寬度，寬為重疊寬度（7）的數據，存放在條帶緩沖區的后半部，然后再建立循環，進行塊讀，其中每行的首塊必須先讀入7列數據存放在列緩沖區，也就是塊緩沖區的7～14列，然后從15列開始將讀入的數據放入，以后每塊在讀數據以前，先將后14列數據復制到前14列。存儲機制如圖4所示。 

帶讀機制和塊讀機制本身并不復雜，但由于有重疊數據的要求，所以讀入的數據有一些不能丟棄，以備后用，并且還要處理邊界不規則的塊。值得注意的是由于有重疊數據的要求，邊界的塊處理和生成可能還牽涉到與邊界塊相鄰的塊的處理。

在帶讀機制的條件下，根據圖像的寬度（設為 W ），讀寫文件的所有緩沖區的大小為： W ×塊的邊長，設塊的邊長為 1 600 ，如果圖像的寬度為12 600（圖像文件大小為378MB），需要60MB的緩沖空間。對于小波運算來說，需要10MB以上的空間，所以本系統可能需要70MB左右的運行空間，設塊的邊長為800，則系統需要35MB左右的空間。保守一點來說，帶讀的運行機制對海量數據有一定的限制。如果圖像的寬度超過在設塊的大小為1 600像素，圖像寬度超過16 000時，對于內存配置在128MB的計算機來說，可能會出現問題，同時效率下降很大。

理論上來說，塊讀機制可以處理無上限的海量數據。設塊的邊長為1 600，如果圖像的寬度為12 600（圖像文件大小為378MB），緩沖區的大小不到10MB，加上小波運算需要的空間，系統只需要25MB左右的內存就可以了。

3 實例

筆者采用Daubchies緊支集小波濾波器對圖像進行壓縮測試，選用圖像塊為1 600×1 600，邊界拓展為16像素，占塊的1%。分別用Winzip，傳統的EZW算法和EZW+Huffman雙重編碼算法對圖像壓縮，發現采用本文所述的方法后，壓縮比率能夠在傳統EZW算法壓縮的基礎上進一步提高20%～40%左右。圖5和圖6是本文用到的兩個圖片，用這三種方法測試的結果如表3所示。

但是由于采用了兩次編碼機制，因此程序的效率有所下降，本文所述的分塊壓縮，將感興趣的圖像大小限制在一定的范圍內，對于圖像子塊來說，采用雙重編碼后，程序運行效率沒有受到很大影響。

4 結論

海量圖像在網絡上實時傳輸是近些年圖像處理的熱點問題。隨著互聯網的普及和圖像應用范圍的不斷擴大，對圖像編碼提出的要求也越高，不僅要求算法具有高的壓縮比，還要求有許多新的功能，如漸進編解碼、從有損壓縮到無損壓縮等。利用EZW算法進行圖像數據的壓縮，可以較好地實現數據累進傳輸和實時壓縮的問題。本文在EZW算法的基礎上將大型圖像分塊處理，對每個子塊采用EZW編碼+Huffman編碼的雙重編碼機制進行壓縮，進一步提高了壓縮的比率，同時采用了具有緩沖機制的自適應的讀寫方式讀寫圖像數據，能夠滿足用戶在網絡上瀏覽任意區域圖像的要求。

實際上，對于大型圖像來說，可以根據用戶熱點的區域來統計哪些子塊經常被訪問，對于這些經常被訪問的子塊，可以預先在用戶第一次瀏覽網頁時建立緩沖機制，這樣就可以更快地讓用戶在大型圖像中分級漫游，這也是筆者目前正在深入研究的工作。

參考文獻：

[1]章毓晉.圖像工程上冊[M].北京:清華大學出版社，2000.3-4.

[2] 張立保，王珂.一種基于整數小波變換的圖像編碼算法[J].軟件學報，2003，14(8):1433-1438.

[3] Shapiro J M. Embedded Image Coding Using Zerotree of Wavelet Coefficients[J]. IEEE Trans. Signal Processing， 1993，41(12):3445-3462. 

[4] 王向陽，楊紅穎.一種改進的嵌入式零樹小波圖像編碼算法[J].計算機研究與發展，2002，39(6):737-742. 

作者簡介：李津平(1974-)，男，助理研究員，博士，主要研究方向為網絡地理信息系統;芮小平(1975-)，男，講師，博士，主要研究方向為三維地理信息系統;楊崇俊(1954-)，男，研究員，博導，博士，主要研究方向為網絡地理信息系統。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。