1  引言

由于數字視頻業務具有帶寬需求較高、服務質量需求高、點對多點的廣播流需

求頻繁、系統資源需求量大、并發業務需求量大等特點，這就要求視頻節目的

編碼能夠提供盡可能大的壓縮比和嵌入式碼流，編碼速度盡可能快，解碼后輸

出的圖像和視頻質量盡量與原圖像和視頻相近.由于小波圖像編碼方法具有多分

辨率、多質量控制、嵌入式碼流等優點，因此它非常適合于數字圖像和視頻的編碼，它已成為了視頻編碼領域所熱捧的對象.MPEG-4的靜態紋理編碼采用了基于

小波變換的編碼技術^[1,5] .

在MPEG-4的靜態紋理編碼中，經過小波變換之后最低頻子帶系數是分開編碼

的，而對于高頻系數的編碼，用戶則可以選用下列三種不同的量化模式之一

：（1）單層量化模式；（2）多層量化模式；（3）位平面二值量化模式.其中

位平面二值量化模式（簡稱BQ）采用的是預測性嵌入式零樹編碼算法

(Predicative Embedded Zero-tree Wavelet Coding Algorithm，簡稱PEZW)^[1,6] .

PEZW是在改進EZW算法的基礎上獲得的更高效和更具擴展性的編碼算法，這是通過更好的基帶預測編碼方法(DPCM)、改進的零樹編碼符號集、更好的算術編碼上下文模型獲得的.盡管PEZW響應了視頻壓縮對靜態紋理編碼提出的高要求，但本

文作者經過分析和實驗發現PEZW的計算方法仍然不夠經濟合理，在一定程度上影

響了編碼速度，如果將文章[2]提出的EZW算法的統一模式應用到PEZW的編碼

中，還可進一步簡化PEZW的計算方法，提高PEZW的編碼速度.

2  原有的預測性嵌入式零樹編碼算法

1993年Shapiro提出了嵌入式零樹編碼算法(EZW)，其基本思想就是：在小波變換完成之后，按照從最高有效位(MSB)到最低有效位(LSB)的次序對有效系數進行編碼^[3,4] .而PEZW對EZW進行了多項擴展：PEZW把最低頻子帶系數與其他高頻子帶系數分開編碼，而且用預測編碼方法來編碼；采用基于樹的編碼方法對高頻段進行編碼，在編碼中采用了編碼效率更高的新符號集和更靈活的上下文編碼模型.因此，PEZW進一步提高了EZW的編碼效率^[1,7] .

PEZW的量化編碼可以概括為如下步驟：

(1)    令 是一個輸入信號的小波變換系數； 是所有系數中的最大量值，即 .選擇一個閾值 ，其中 是一個整數， 是一個常數，且滿足 . 每進入一次新的掃描閾值減半.

(2)置 ，當 小于等于預定的最小閾值或編碼輸出達到預定字節數時編碼終止.

(3) 主掃描：用與每個系數 相比較，把系數編碼為ZTRZ(零樹根),ZTRV(大系數零樹根),IZER(孤立零),IVAL(大系數)四種符號之一.用算術編碼器和對應于當前上下文的統計模型編碼這些符號.把標號為ZTRV或IVAL的系數保存到有效系數表中.用符號 代替標號為IVAL的有效系數.為對應于當前符號的頻率計數器加1.

(4)從掃描：從有效系數表中的每個系數中取出對應于當前位平面高度的1位，將其發送到解碼器.

(5)給 增加1，初始化頻率計數器，返回步驟(2).

3  按照EZW的統一模式改進的預測性嵌入式零樹編碼算法

3.1 PEZW編碼算法存在的問題

預測性嵌入式零樹編碼算法(PEZW)保持了原始EZW算法的基本結構和良好性能，大大改進了EZW的編碼效率。但仔細分析PEZW，仍可發現它還存在不少缺點：

(1)PEZW在編碼每個小波樹時，要先把小波系數的樹形結構轉化成線性序，其中包括多個步驟，要使用比較繁瑣的數據結構，算法思想復雜難懂.如果按文章[1]提出的EZW的統一模式，則可使用層次樹的優先搜索策略很簡便地實現小波樹到線性序的轉換，從而大大簡化數據結構，降低算法的復雜度，進一步提高算法的編碼速度.

(2)PEZW在建立零樹圖時，也使用了多個步驟，沒有清楚地使用四叉樹的層次結構關系，使算法復雜難懂.另外，PEZW還使用了多余的數據結構.如果應用EZW的統一模式來建立零樹圖，則可簡化算法步驟，提高計算速度，減少內存開銷.

(3)在PEZW的位平面編碼中，主掃描是從樹的頂層到底層依次進行，循環執行.在掃描某層系數結點的過程中，又需根據上一層掃描確定的本層需掃描的子集數及每個子集的起止位置，再執行兩層循環，依次掃描本層所需掃描的各個結點.其中循環嵌套層數較多，在掃描每層系數結點的過程中，還需計算下層所需掃描的子集數及各子集的起止位置，這些繁瑣的操作無疑會增加算法的復雜度，浪費內存開銷，降低編碼速度.如果應用EZW編碼算法的統一模式，則可用寬度優先策略對四叉樹進行層次掃描，僅需一個FIFO表和一層循環，即可實現對四叉樹的掃描.因此，可降低算法的復雜度，提高編碼速度.

3.2改進的PEZW編碼算法

鑒于PEZW中存在的問題，易知可以應用EZW算法的統一模式^[1]來改進PEZW，降低PEZW算法的復雜性，提高其編碼速度.改進的PEZW的編碼算法的具體步驟如下：

(1) 用預測編碼方法(DPCM)對最低頻子帶進行編碼；

(2) 對于高頻子帶，按照圖1所示的樹根順序，即 ， ， ,…, , , , ,…, ,…, , , ,…, ,依次對這 個樹進行編碼.

 圖1  PEZW的高頻段樹編碼的順序

編碼以 為根的樹的步驟如下：

（2.1）使用先進先出表和寬度優先策略掃描四叉樹，按照父子坐標換算關系： ，讀入小波樹中的系數，產生一個小波系數的線性數組.

（2.2）建立線性序小波樹的零樹圖。按照從高頻到低頻的順序，對線性序小波樹進行逆向掃描，依次處理從第 層（次底層）到第1層（頂層）的系數：

（a）對于第層的小波系數，若它具有線性序號j，則比較它的序號為 的4個子系數的絕對值，并將最大系數絕對值存于數組元素 [ j]中；

（b）對于第層以上 的小波系數，如果它具有線性序號，則比較它在第 層的4個序號為 的子小波系數值與 ， ， ， 的大小，計算出其中最大絕對值，并將該值存于數組元素[j]中.

(2.3）從最高位平面到最低位平面依次編碼.

(2.3.1）編碼某個位平面時，主掃描采用寬度優先策略和先進先出表對四叉樹進行層次掃描，零樹根或大系數零樹根的所有子孫結點被舍棄而不掃描，非零樹根和非大系數零樹根的下一層子結點被追加到先進先出表，待后續編碼.具體步驟如下：

(a) 對于已在前面的位平面編碼中編碼為大系數符號IVAL或大系數零樹根符號ZTRV的結點，在當前位平面中不被編碼.如果該結點不是樹中最低層結點，則將其下一層的四個子結點加入先進先出表.轉下一個結點的編碼.

(b) 對于未在前面位平面中編碼為大系數符號IVAL或大系數零樹根符號ZTRV的結點應分情況處理：

l     如果當前結點處于最低層，則當其系數絕對值大于等于當前閾值時，將其編碼為大系數符號，并將其系數值存入有效系數表，待細化掃描；否則當其系數絕對值小于當前閾值時，將其編碼為孤立零IZER.如果當前結點不是處于最低層且零樹圖表明其下不是一個零樹，則當其系數絕對值大于等于當前閾值時，將其編碼為大系數符號IVAL，并將其系數值存入有效系數值表，待細化掃描，否則當其系數絕對值小于當前閾值時，將其編碼為孤立零IZER，再將其下一層的4個子系數加入先進先出表，待后續編碼.

l     如果當前結點不是處于最低層且零樹圖表明其下是一個零樹，則當結點絕對值大于等于當前閾值時，將其編碼為大系數零樹根符號，并將其系數值存入有效系數值表，待細化掃描，否則若當前系數絕對值小于當前閾值時，將其編碼為零樹根符號ZTRZ.

（c）計算當前零樹符號的上下文并進行算術編碼，即用當前位平面編號 和小波樹的當前層號 確定當前系數的上下文 ，然后用此上下文對當前零樹符號進行算術編碼，將編碼的比特流輸出到緩沖區.

（2.3.2）有效系數的細化編碼

掃描有效系數列表，對在當前位平面之前出現的各有效系數在當前位平面的細化位進行編碼.用當前位平面編號及當前有效系數在小波樹中的層號計算細化比特位的上下文，并用此上下文對細化比特位進行算術編碼.

表1  改進的PEZW與原PEZW的編碼速度比較

原PEZW和改進的PEZW壓縮brea_cif.yuv后解碼所得的圖像如下圖所示.

 (a)原PEZW編解碼圖像（PSNR=30db） (b) 改進的PEZW編解碼圖像（PSNR=30db）

(c)原PEZW編解碼圖像（PSNR=40db）   (d) 改進的PEZW編解碼圖像（PSNR=40db）

圖2 原PEZW和改進的PEZW具有相同的編解碼效果

由上面表1和圖2的實驗數據可見，改進的PEZW比原PEZW在進行視頻靜態紋理編碼時具有更快的速度和相同的PSNR效果.這說明按照EZW的統一模式改進得到的PEZW是有效的.

4  結 論

由于小波圖像編碼方法具有多分辨率、多質量控制、嵌入式碼流等優點，因此它非常適合于數字圖像和視頻的編碼，它已成為了視頻編碼領域所熱捧的對象.在MPEG-4的靜態紋理編碼的BQ模式中就采用了小波圖像的位平面編碼方法（即PEZW），雖然PEZW中已有統一模式的 EZW編解碼算法思想的萌芽，但沒有完全實現統一模式的 EZW編解碼思想，因此算法比較復雜，編碼速度比較慢.為此，本文作者應用EZW編解碼算法的統一模式對PEZW進行改進，可大大降低算法的復雜度，提高編解碼速度.

如今PEZW的編碼速度已優化到極點，要進一步改進PEZW就應該通過改進編碼符號集或零樹符號編碼的上下文模型來實現.

參考文獻

[1] Liang J.. Highly Scalable Image Coding for Multimedia Application [J]. The IEEE Conf. on Acoustics, Speech and

Signal Processing, Phoenix, AZ, 1999: 11-19.

[2] Zhong C.X., Huang M.H.. An Improvement to Embedded Image Coding Using Zero-trees of Wavelet Coefficients [J]. Journal of Information and Computational Science, 2006, 3(3):657-664.

[3] J. M. Shapiro. Embedded Image Code Using Zero-tree of Wavelet Coefficients [J]. IEEE Trans. on Signal Processing, 1993, 41(12):3445-3462.

[4] J. M. Shapiro. A Fast Technique for Identifying Zero-trees in the EZW Algorithm [J]. The IEEE Conf. on Acoustics, Speech and Signal Processing, Atlanta,Geogia,1996:1444-1458.

 [5] 婁東升.  MPEG-4中靜止圖像編碼方法的探索與研究.北京廣播學院學報(自然科學版) [J] , 2002,12(4):49-55.

LOU Dong-sheng. Research on Still Image Coding Method in MPEG-4 [J]. Journal of Beijing Broadcasting Institute (Science and Technology), 2002,12(4):49-55.

[6]石旭利. 小波變換和算術編碼在MPEG4中的應用[J].電視技術，2001，05：7-9.

Shi Xu-li. Application of Wavelet Transform and Arithmetic Coding in MPEG-4 [J]. Video Engineering, 2001，05:7-9.

[7]張亞妮,苗潤才. MPEG-4靜態紋理BQ模式編碼算法的改進[J]. 光子學報 ,2005,34(10):1593-1596.

Zhang Ya-ni, Miao Run-cai. Improved MPEG-4 VTC BQ Mode Coding Algorithm [J]. Acta Photonica Sinica, 2005, 34(10):1593-1596.

作者簡介：

鐘萃相(1965-),男，博士，研究方向為多媒體應用技術；現為江西師范大學軟

件學院教師。黃明和（1955-），男，研究方向為算法分析與設計、軟件工程

和多媒體應用技術；現為江西師范大學軟件學院教授，碩士生導師。

09112