一種改進的嵌入式零樹小波編碼方法

胡靜濤，陳 衛(wèi)

( 陸軍軍官學院5 系，合肥 230031)

圖像數(shù)據(jù)壓縮就是通過減少圖像數(shù)據(jù)之間的冗余來減少數(shù)據(jù)量，從而達到減少存儲空間，提高傳輸效率的目的［1］。上個世紀90年代后，圖像壓縮編碼研究取得了一系列的階段性新成果，基于零樹的編碼法首先由A.S.Lewis 和G.Knowles 提出［2］，其特點是根據(jù)小波系數(shù)在同方向子帶中的相似性，利用一種稱為小波樹的樹形結(jié)構(gòu)來組織小波系數(shù)，使其能去除頻域和空間域中的相關性［3］。接著Shapiro 結(jié)合比特平面編碼方法設計了一種更好的零樹編碼方法—嵌入式零樹小波編碼( EZW)方法［4］，Shaprio 提出的嵌入式零樹小波算法，它有效地利用了小波系數(shù)的特性，實現(xiàn)了圖像的可分級編碼。但也存在算法時間長和空間復雜度過高的缺點。

1 嵌入式零樹小波編碼

1.1 嵌入式編碼

嵌入式編碼即編碼器把待編碼的比特流按照重要性的不同進行排序，根據(jù)目標碼率要求隨時結(jié)束編碼;對于給定的碼流，解碼器也能夠在任意點結(jié)束解碼，并可以得到相應目標碼率的解碼圖像。從均方誤差的角度看，幅值較大的系數(shù)所包含的信息量相對較大，一旦丟失引起的失真度也較大。為了減少失真度，在處理過程中優(yōu)先編碼和傳輸幅值較大的系數(shù)［5］。

嵌入式編碼即將變換系數(shù)按照幅值從大到小排列，首先傳輸幅值最大的變換系數(shù)的位信息，也就是最重要的信息，然后傳輸次重要系數(shù)，最后傳輸?shù)南禂?shù)最不重要［6］。在傳輸前所有的變換系數(shù)用二進制的方式表示，如圖1。

1.2 零樹小波編碼

1.2.1 小波樹結(jié)構(gòu)

小波分解后，各個分辨率子帶中的系數(shù)并不是完全獨立的，圖像的子帶之間有結(jié)構(gòu)的自相似性，具有結(jié)構(gòu)冗余［7］。各分辨率子帶系數(shù)間有如下的對應關系［8］。

1)除了最高分辨率的子帶外，每一個小波系數(shù)都與同空間方向的高一級分辨率等級內(nèi)的一組小波系數(shù)相聯(lián)系;

2)系數(shù)之間比較，處于低分辨率等級子帶的系數(shù)稱為父系數(shù)，在同一方向高一分辨率等級，并且與其在相同空間位置的所有系數(shù)稱為它的子系數(shù);

3)對于一個給定的父系數(shù)，與其在同空間方向，且分辨率等級更高的所有子系數(shù)，稱為它的子孫系數(shù);

4)除了最低分辨率的子帶，所有的父系數(shù)都有4 個子系。

圖1 按幅度排序信息的二進制表示

圖2 為一個采用上述方式進行三級分解的小波樹。其中箭頭方向表示，由父系數(shù)子帶指向子系數(shù)子帶［9］。

圖2 子帶間的父子關系

在對小波系數(shù)編碼時，對小波系數(shù)的掃描應保證沒有子孫系數(shù)在其父系數(shù)之前被掃描。對一個N 級分解小波變換，掃描從最低頻子帶LLN開始，然后掃描HLN，LHN，HHN，再掃描下一分辨率等級的子帶HLN-1，LHN-1，HHN-1，如此繼續(xù)，最后掃描HH1。如圖3 所示。

圖3 小波系數(shù)掃描順序示意圖

要想在解碼端恢復出原圖像，需要傳送小波系數(shù)的排序信息和位信息。如果每個小波系數(shù)的排序信息和位信息都要傳送的話，這樣需要的數(shù)據(jù)花銷是非常大的，根本就達不到壓縮的目的，但是零樹結(jié)構(gòu)的存在解決了這個難題［10］。

零樹的數(shù)據(jù)結(jié)構(gòu):對于一個小波系數(shù)xi，如果對于一個給定的門限T，＞T，則稱該小波系數(shù)為重要系數(shù)，否則為不重要系數(shù)［25］。正重要系數(shù)用符號POS( positive)表示，負重要系數(shù)用符號NEG( negative)表示。如果該系數(shù)為不重要系數(shù)，但是其子孫系數(shù)中有重要系數(shù)，則該系數(shù)為孤立零點，用IZ( isolated)表示。如果該系數(shù)為不重要系數(shù)，但是其子孫系數(shù)中沒有重要系數(shù)，且該系數(shù)的父系數(shù)為重要系數(shù)，則該系數(shù)為零樹根，用ZTR( zerotree)表示，該系數(shù)和其子孫系數(shù)就形成了一個零樹，在低分辨率上的那個小波系數(shù)被稱為母體，是樹根;在高分辨率上同方向相應位置上的那些小波系數(shù)稱為孩子。通過這種零樹結(jié)構(gòu)，巧妙地編碼，使用于描述重要系數(shù)的位置信息大大減少。

1.2.2 逐次逼近量化

在EZW 算法中使用的是逐次逼近量化( successive approximation quantization，SAQ)方法。逐次逼近量化的主要思想是，通過逐次使用閾值序列T0，T1，…，TN-1來判斷小波系數(shù)的重要性，并確定其類型碼和幅值碼［11］。

在整個編( 解)碼過程中，始終存在著兩個過程—主掃描和輔掃描，它們交替進行，逐次提高量化精度。主掃描對應一張不斷更新的主表，輔掃描對應一張不斷更新的副表。通過這兩個過程對重要系數(shù)、零樹根和孤立零點構(gòu)成的重要圖進行編碼，。實質(zhì)上是對重要系數(shù)的位置和幅值編碼。

2 EZW 算法的不足

雖然EZW 算法存在許多優(yōu)點，算法簡單，編碼效率高。但是也存在著一些不足，主要表現(xiàn)在以下幾個方面［5］:

1)在編碼的過程中要形成許多棵零樹，每生成一棵零樹需要對數(shù)據(jù)掃描兩遍，而且每一棵零樹必須要在前一棵零樹生成之后才能生成，造成編碼效率低。對于一個小于閾值T的小波系數(shù)，為了判斷其是孤立零還是零樹根，必須對其所有后代系數(shù)進行掃描，勢必增加編碼時間，導致編碼速度較慢。

2)通過前面的分析我們知道，經(jīng)過小波變換后的系數(shù)重要程度不同。低頻系數(shù)重要，而高頻系數(shù)相對不重要。但是EZW 對所有頻域不加區(qū)分，進行同等重要程度的編碼，沒有充分利用小波變換后系數(shù)的特點。。

3)在EZW 算法中樹間存在大量的冗余，但是EZW 算法沒有利用樹與樹之間的關系來減小樹間冗余。

4)同一子帶中相鄰系數(shù)之間有一定的相關性，在高頻系數(shù)中表現(xiàn)的尤為突出，通過子帶的集合可以進一步地壓縮數(shù)據(jù)。但是EZW 算法并沒有對這種相關性進行充分的利用。

3 EZW 算法的改進

3.1 頻率優(yōu)先性

根據(jù)小波變換的理論可知，一幅圖像經(jīng)過小波變換后雖然其數(shù)據(jù)和總能量沒有減少，但是其能量分布產(chǎn)生了比較大的變化。在低頻系數(shù)子帶中聚集了原始圖像的大部分能量，高頻系數(shù)只占有圖像的一小部分能量。本文中的改進算法是把高頻子帶系數(shù)和低頻子帶系數(shù)分開處理。針對低頻子帶系數(shù)，單獨對其進行無失真編碼，采用差分脈沖編碼調(diào)制( DPCM)，對編碼后的碼流再進行熵編碼，進一步壓縮碼流，提高壓縮效率。

DPCM 預測編碼的系統(tǒng)原理框圖［12］，如圖4。

圖4 DPCM 原理圖

3.2 重要子帶編碼［13］

在原始嵌入式零樹編碼中，為了找到重要系數(shù)和確定零樹根的位置，為了確定一個小波系數(shù)是零樹根還是孤立零，往往需要掃描整棵四叉樹和大量重復的掃描，時間復雜度高，同時消耗了大量的內(nèi)存。

如果在掃描中事先就能確定重要系數(shù)可能存在的位置，只對重要系數(shù)存在的子帶進行掃描，對不存在重要系數(shù)的子帶不掃描，這樣將在一定程度上減少掃描時間，提高壓縮速度。由小波變換原理我們可以知道，一幅圖像經(jīng)過N 級小波變換分解后，形成了3N+1 個子帶。首先，尋找每個子帶中的小波系數(shù)的最大值。即IK(1，2，3，…，3N+1)中小波系數(shù)的絕對值的最大值tK，其中1 ＜k ＜3N+1。圖5 給出3 級圖像小波分解后的每個子帶系數(shù)絕對值的最大值的示意圖。

第一次掃描時確定初始閾值T0，其確定方法與原始EZW方法相同。對于每一個子帶將其絕對值最大值tK與T0進行比較，若tK＞T0，則該子帶稱為重要子帶;若tK＜T0，則該子帶稱為不重要子帶。開始掃描時，仍然按照morton 掃描順序進行掃描。在整個編碼中用p 表示正重要系數(shù)，n 表示負重要系數(shù)，t 表示不重要系數(shù)，i 表示非重要子帶。當掃描時發(fā)現(xiàn)tK＜Ti時，用i 來表示這個不重要子帶，同時不用再掃描該子帶，直接掃描下一個子帶;當tK＞T0時，用p 表示正重要系數(shù)，n表示負重要系數(shù)，t 表示不重要系數(shù)，i 表示非重要子帶。

圖5 子帶系數(shù)最大值示意圖

3.3 熵編碼

對高頻系數(shù)編碼后形成的碼流進行熵編碼，減少數(shù)據(jù)量，本文采用霍夫曼編碼。

綜上所述，整個改進算法的流程如圖6。

圖6 改進算法的流程

4 實驗仿真

為了更直觀地說明算法的有效性，本文對改進算法進行實驗仿真。

實驗環(huán)境:Windows XP 系統(tǒng)，內(nèi)存1G，Matlab7.0。

測試圖像為Matlab7.0 中的測試圖像westconcordorthophoto。

對圖像采用db9/7 小波基對圖像進行3 級分解與重構(gòu)。

圖7 測試圖像westconcordorthophoto

仿真圖片對比∶壓縮比20∶1。

從上面得到的實驗圖像表明:

1)改進后的EZW 算法重構(gòu)圖像的質(zhì)量較高，主觀視覺效果較好，不產(chǎn)生任何方塊效應;

2)在低碼率時，改進算法的重構(gòu)圖像質(zhì)量優(yōu)于原EZW算法。

［1］劉峰.視頻圖像編碼技術(shù)及國際標準［M］.北京:北京郵電大學出版社，2005.

［2］Lewis A S，Knowles G. Image compression using 2 - D wavelet transform［J］. IEEE Trans. On Image Processing，1992，1(2):244-250.

［3］王文波.基于小波的圖像壓縮編碼［D］.成都:電子科技大學，2009.

［4］Shapiro J M. Embedded image coding using zerotrees of wavelet coefficients［J］. IEEE Trans.On Signal Processing，1993，41(12):3445-3462.

［5］成禮智，王紅霞，羅永.小波的理論與應用［M］.北京:科學出版社，2004.

［6］王向陽等.基于自適應小波變換的嵌入式圖像壓縮算法［J］.微電子學與計算機，2005，22(2):121-123.

［7］李亮.基于小波變換的靜態(tài)圖像壓縮編碼研究［D］.大連:大連交通大學，2009.

［8］張春田，蘇育挺，張靜.數(shù)字圖像壓縮編碼［M］.北京:清華大學出版社，2006.

［9］劉學鋒.基于小波零樹的嵌入式圖像編碼技術(shù)的研究與改進［D］.西安:西安科技大學，2006.

［10］薛冰. 嵌入式零樹小波編碼算法的改進與應用研究［D］.成都:電子科技大學，2008.

［11］陳冬，張?zhí)镂?，李東.位漸進逼近量化的EZW 改進算法［J］.哈爾濱工業(yè)大學學報，2010，42(5):779-783.

［12］姚敏，趙敏.改進的高效EZW 遙感圖像壓縮方法研究［J］.電子科技大學學報，2009，38(4):525-528.

［13］雷梅梅，余諒. 一種改進的嵌入式小波圖像編碼算法［J］.計算機工程與科學，2010，32(10):59-62.