快速的層次樹集合分劃編碼算法

摘要:設計了一個改進算法，它僅需對小波分解矩陣進行一遍掃描即可確定層次樹集合分劃編碼(SPIHT)算法所需的所有D(i，j)和L(i，j)重要性并完成對所有(i，j)子系數的編碼，使得按照SPIHT的排序方法編碼時只需查找存放D(i，j)和L(i，j)的重要性及(i，j)子系數的編碼表，從而大大提高了SPIHT的編碼速度#65377;

關鍵詞:圖像編碼;層次樹集合分劃編碼;搜索冗余;編碼速度

中圖分類號:TP3016文獻標志碼:A

文章編號:10013695(2007)04008003

嵌入式小波零樹編碼(EZW)算法是一種最早且最成功的小波圖像編碼算法，是一種有效且計算簡單的圖像壓縮技術#65377;它利用零樹有效地表示不重要系數的數據結構，以提高編碼效率#65377;但對于某些不重要系數結構，零樹并不總能有效地表示它們#65377;SaidA.和PearlmanW.A.根據EZW的基本思想，提出了一種新的且性能更優的編碼方法，即層次樹中集合分劃編碼(SPIHT)算法#65377;該方法利用空間方向樹的分劃集合來更有效地表示不重要系數結構，從而大大提高編碼效率^[1~9]#65377;

SPIHT作為EZW的改進算法，還具有如下優點^[1，5，6]:①可獲得較好的重構圖像質量#65380;較高的峰值信噪比#65377;對于彩色圖像尤其如此#65377;②優化的漸進圖像傳輸特性#65377;③可生成完全嵌入式的編碼文件#65377;④簡單的量化算法#65377;⑤快速的編碼和解碼操作，且編碼與解碼幾乎是對稱的#65377;⑥具有廣泛的應用，且編碼算法是完全自適應的#65377;⑦可用于無損壓縮#65377;⑧可按準確的位率或失真度編碼#65377;⑨可有效結合誤差防止措施#65377;

雖然SPIHT是一個號稱編碼和解碼速度快#65380;計算復雜度低的算法，但它仍然存在大量的搜索和計算冗余#65377;SPIHT是利用空間方向樹的分劃集合D(i，j)和L(i，j)來有效表示不重要系數結構#65377;算法的大部分操作都是判斷D(i，j)和L(i，j)的重要性;每次判斷都要搜索(i，j)的子孫或非直系子孫，使空間方向樹特別是低層系數要被多遍掃描，大大降低了編碼速度#65377;為了解決這個問題，許多人作了改進嘗試^[4，7~9]#65377;其中比較有意義的改進是通過找出某些子帶或系數集中的最大值，使得掃描時可先比較閾值和這些最大值，僅當掃描閾值小于某個子帶或系數集中的最大值時，該子帶或系數集才被掃描，從而在一定程度上減少了搜索冗余^[4，7]#65377;但是當某些較小系數子集的最大值未確定時，該子集中的系數仍可能被重復掃描，因此并未完全解決搜索冗余的問題#65377;另外，在他們的改進算法中，即使一個系數集的最大值已找出，當對該系數集進行編碼時，仍需重復搜索該系數集以進行編碼，因此也存在著搜索冗余的問題#65377;于是，本文從另一個思考角度提出了一種快速算法#65377;該算法只需對小波系數矩陣進行一遍掃描即可確定SPIHT的整個執行過程所需的所有D(i，j)和L(i，j)的重要性并完成對所有(i，j)的子系數編碼，使得以后的操作若要判別D(i，j)和L(i，j)的重要性來編碼時，只需查表即可#65377;因此，可大大提高編碼速度#65377;

1SPIHT編碼算法

1.1算法描述

設X是一個小波系數坐標集:X={(i，j)|i，j為某些非負整數}#65377;若X中有某個坐標位置對應的系數絕對值大于或等于閾值T，則稱X是重要的;否則稱X是不重要的#65377;

SPIHT算法還需用到下列記號:

(1)H表示所有樹根的坐標集合#65377;對于K層小波分解，H為LLK∪LHK∪HLK∪HHK中所有系數的坐標構成的集合#65377;

(2)O(i，j)表示節點(i，j)的所有直系兒子節點#65377;除LLK#65380;LHK#65380;HLK#65380;HHK之外，對其他任意系數坐標(i，j)均有O(i，j)={(2i，2j)，(2i，2j+1)，(2i+1，2j)，(2i+1，2j+1)}#65377;

(3)D(i，j)表示節點(i，j)的所有子孫的坐標集#65377;

(4)L(i，j)表示節點(i，j)的所有非直系子孫的坐標集，即L(i，j)=D(i，j)-O(i，j)#65377;

SPIHT算法的主要步驟如下^[5，6，8]:

(1)選定閾值和初始化有序表#65377;令T=2m，其中m=[log2(max0≤i，j

(2)排序掃描#65377;分以下兩大步進行:

①依次檢查LIP中的各個系數(i，j)，確定其是否重要#65377;

若(i，j)是重要系數，則輸出“1”，再按系數的正#65380;負分別輸出符號位“1”或“0”，然后從LIP中刪除(i，j)，并將其添加到LSP的尾部#65377;

若(i，j)是不重要系數，則輸出“0”#65377;

②依次處理LIS中的各個表項:

對于D型表項D(i，j)

若D(i，j)是重要的，則輸出符號“1”，并根據分集規則，將它分成四個子節點(k，l)∈O(i，j)和L(i，j)，然后先依次處理這四個子節點(k，l)#65377;若(k，l)是重要系數，則輸出“1”及其符號位，再將(k，l)添加到LSP的尾部;若(k，l)不是重要系數，則輸出“0”，并將(k，l)添加到LIP的尾部#65377;當(i，j)的兒子節點處理完畢后，再處理L(i，j)#65377;若L(i，j)≠Φ，則將L(i，j)移到LIS的尾部;若L(i，j)=Φ，則將L(i，j)從LIS表中刪除#65377;若D(i，j)是不重要的，則輸出符號“0”#65377;

對于L型表項L(i，j)

若L(i，j)是重要的，則輸出符號“1”，并根據分集規則，將它分成四個D型表項D(k，l)，(k，l)∈O(i，j)，并將它們依次添加到LIS表的尾部，然后將L(i，j)從LIS中刪除;若L(i，j)是不重要的，則輸出符號“0”#65377;

將LIS中的初始表項及掃描過程中添加到其中的所有表項全部處理完畢之后，本次排序掃描過程結束#65377;

(3)精細掃描#65377;對于LSP中的每個表項(i，j)，若(i，j)不是在剛剛進行過的掃描過程(2)中添加的，則輸出|ci，j|的二進制表示中第m個最重要的位#65377;其中T=2m是掃描過程中設定的閾值#65377;

(4)進行下一次排序掃描和精細掃描#65377;選定新閾值T=2m-1，返回到步驟(2)#65377;

1.2算法分析

在SPIHT算法的每次排序掃描中，主要的費時操作就是對一系列(i，j)判斷D(i，j)和L(i，j)的重要性，即要搜索以(i，j)為根的四叉樹#65377;掃描是從LIS={(i，j)D|(i，j)∈H且(i，j)具有子孫}開始的，即從第K個分解層開始的#65377;假設(i，j)處于第K層，且有重要兒孫系數在第一層，則搜索以(i，j)為根的四叉樹的時間為

∑K-1i=14i=(4K-4)/3

由于第K層有三個方向子帶，每個子帶有N2/22K個系數，搜索以第K層系數為根的四叉樹的總代價為3N2/22K∑K-1i=14i=N2(1-41-K)當D(i，j)和L(i，j)都非空時，以(i，j)為根的四叉樹要搜索兩次#65377;因此處理第K層的D(i，j)和L(i，j)(即(i，j)屬于第K層)的搜索時間為2N2(1-41-K)#65377;類似地，處理第K-1層的D(i，j)和L(i，j)的搜索時間為2N2(1-42-K)，…，處理第l層的D(i，j)和L(i，j)的搜索時間為2N2(1-41-l)(2≤l≤K)#65377;因此，每次編碼掃描處理所有的D(i，j)和L(i，j)的搜索時間最壞為

T=∑Kl=22N2(1-41-l)=2N2[K-2-(1-41-K)/3]≈2(K-2)N2

另外，對所有i#65380;j，當D(i，j)被確定為1而需要對(i，j)的四個子系數編碼時，又需要對這些子系數重復掃描，因此搜索時間再次增加:

T≈2(K-2)N2+N2≈(2K-3)N2

假設SPIHT的整個執行過程要進行m(=[log2(max0≤i，j1，約為掃描一遍系數矩陣所需時間的η(2K-3)倍#65377;因此SPIHT算法中確實存在大量的搜索冗余#65377;

2快速SPIHT編碼算法

從上面的SPIHT算法分析可知，判別D(i，j)和L(i，j)的重要性是很費時的，因此有必要剔除算法中的多余搜索和計算#65377;為此，筆者發現了一個快速算法，它僅需對小波系數矩陣進行一遍掃描即可確定SPIHT的各次編碼掃描所需的所有D(i，j)和L(i，j)中的重要性并準備好(i，j)的子系數編碼#65377;

2.1算法描述

Input:圖像的K層小波分解系數矩陣W=(ci，j)1≤i，j≤N(N×N為圖像大小，N=2m，K≤m)#65377;

Output:存放各系數節點是否存在重要兒孫標記及其直系子系數的代碼的表:

D(N，N，m+1)=struct(′significant′，[]，′code′，[]);

存放各系數節點是否存在重要非直系兒孫標記的表L(N，N，m+1)#65377;

其中m=[log2(max1≤i，j≤N{|ci，j|})]#65377;

Begin

forl←1toKdo//循環迭代處理第1~K個分辨率層

fororient←1to3do//HLl#65380;LHl#65380;HHl的子帶方向數分別為1#65380;2#65380;3

/*第l層的每個方向子帶有2-lN×2-lN個系數，按2-l-1N行和2-l-1N列且每四個系數一組的形式處理各組系數*/

forx←1to2-l-1Ndo

fory←1to2-l-1Ndo

(1)計算每組四個系數的行列坐標:

x1=2x-1，y1=2y-1;i1=x1+2-lN×[orient/2]，

j1=y1+2-lN×(orient-2×[orient/2]);

x2=2x-1，y2=2y;i2=x2+2-lN×[orient/2]，

j2=y2+2-lN×(orient-2×[orient/2]);

x3=2x，y3=2y-1;i3=x3+2-lN×[orient/2]，

j3=y3+2-lN×(orient-2×[orient/2]);

x4=2x，y4=2y;i4=x4+2-lN×[orient/2]，

j4=y4+2-lN×(orient-2×[orient/2]);

并求出這組系數的父系數坐標:

ip=1+[(i1-1)/2];jp=1+[(j1-1)/2];

(2)求出四個系數的絕對最大值及其所在的閾值區間:

Mc=max{|ci1，j1|，|ci2，j2|，|ci3，j3|，|ci4，j4|};Mx=[log2(|Mc|)]

(3)若l>1

①還需找出使

D(i1，j1，k1).significant=1;D(i2，j2，k2).significant=1;

D(i3，j3，k3).significant=1;D(i4，j4，k4).significant=1;

的正整數足標k1#65380;k2#65380;k3#65380;k4，并求出k1#65380;k2#65380;k3#65380;k4中的最大值:

My=max{k1，k2，k3，k4};

②置該組系數的父系數相對于閾值區間[2My，2My+1)有重要子孫的標志而相對于更高的閾值區間無重要子孫的標志:

L(ip，jp，My).significant=1;L(ip，jp，p).significant=0，My

③再求出Mx和My中的最大值:

Mx=max{Mx，My}

(4)置該組系數的父系數相對于閾值區間[2Mx，2Mx+1)有重要子孫的標志而相對于更高的閾值區間無重要子孫的標志:

D(ip，jp，Mx).significant=1;D(ip，jp，p).significant=0，Mx

(5)為本組四個系數編碼:

①若|ci，j|≥2Mx，則為它編碼1;若ci，j>0則再加符號位1，否則再加符號位0;若|ci，j|<2Mx，則為它編碼0#65377;

②將四個系數的編碼組成一個數組序列s，并將其賦值給父節點的code域:

D(ip，jp，Mx).code=s;

2.2算法分析

上述改進算法僅需對小波系數矩陣進行一遍掃描即可確定SPIHT的整個執行過程所需的所有D(i，j)和L(i，j)的重要性值，并完成對所有(i，j)的子系數編碼#65377;處理時間約為2N2，僅為SPIHT的總搜索和編碼時間η(2K-3)N2的1/[η(K-15)](η>1)#65377;因此它確實是一個快速有效的算法#65377;

3實驗結果

為了比較SPIHT的原算法與改進算法的性能，本文用MATLAB語言編程實現了這兩個算法，并在PC機(IntelPentium4240GHzCPU，256MB內存)上運行算法程序進行試驗#65377;測得這兩種算法的搜索時間(不包含編碼時間)及其比率如表1所示#65377;

表1兩種算法搜索時間比較

圖像的大小小波分解層數編碼掃描遍數原算法第一遍的搜索時間(s)改進算法的總搜索時間(s)時間比率大于

上面的數據表明原算法的搜索時間為改進算法搜索時間的幾十倍，當分解層數增大時這個比率也增大#65377;由此可見，改進算法確實能夠大大減少搜索冗余，提高SPIHT的執行速度#65377;

4結束語

SPIHT作為EZW的改進算法，具有重構圖像質量好#65380;漸進傳輸特性好#65380;峰值信噪比高#65380;計算復雜度較低#65380;位速率易于控制等優點#65377;但它仍然存在著大量的搜索冗余，降低了編碼速度#65377;為此，本文提出了一個改進算法，只需對小波系數矩陣進行一遍掃描即可確定SPIHT整個執行過程所需的所有D(i，j)和L(i，j)的重要性，并完成對所有(i，j)的子系數編碼#65377;其搜索時間明顯少于原算法的搜索時間#65377;因此，使用改進搜索算法能大大提高SPIHT的編碼速度#65377;

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