基于S+P變換和EZW編碼的圖像壓縮算法

陳軼鳴， 夏景明， 陳愛月， 唐玲玲

(南京信息工程大學 電子與信息工程學院，江蘇 南京 210044)

0 引 言

隨著信息技術的高速發展，人們對于圖像數據的需求量也逐步加大，這給圖像數據的儲備、分析以及傳送提出了高要求。圖像數據的壓縮是圖像數據傳送的核心問題，如何實現快速編碼、高壓縮比以及重構圖像效果良好的壓縮算法一直是研究的熱門方向。Shapiro[1]提出了嵌入式零樹小波編碼(Embedded Zerotree Wavelet, EZW)，其利用多尺度系數的空間相似性構建零樹，且根據系數的重要權重選擇傳送順序，編碼速度高，支持多碼率解碼。陳冬等[2]提出了位漸進逼近量化的EZW改進算法， 該算法將區間逼近和重要系數二進制位結合起來，簡化了輔掃描的量化編碼過程。黃慶[3]提出了一種改進的EZW算法，該算法通過增加2個標識符，來避免連續出現零樹根，減少冗余的符號流。Naveen等[4]針對高效低動態范圍的圖像壓縮，提出了一種基于塊方式改進的EZW編碼算法，該算法采用塊中最少掃描次數作為圖像中所有塊的主和次掃描次數，減少了掃描次數，提高了壓縮效率。這些編碼算法的缺陷在于都采用了離散小波變換，在對圖像進行表達時，圖像的邊緣會產生大量的大權值系數。為了更有效地表達圖像的邊緣、輪廓以及紋理等信息，獲得質量優的重建圖像，本文將EZW編碼和S+P變換結合起來，提出了一種基于S+P變換改進的EZW編碼算法，以下簡稱為EZWSP編碼算法。

1 嵌入式零樹小波(EZW)算法

嵌入式零樹小波編碼(EZW)算法[5-6]，根據離散小波變換子帶系數的相關性進行編碼[7-8]，且編碼結果按重要性優先級排序，具體編碼步驟如下：

(1) 選擇閾值。EZW算法選用迭代閾值T0，T1，…，TL-1來表示小波系數的重要程度，Ti=Ti-1/2，i是掃描系數。初始閾值的選擇為：

T0=2lbMax{ci,j}

(1)

式中：{ci,j}是L級小波變換的變換系數；ci,j是ci,j的絕對值。

(2) 主掃描。采用“Zigzag”掃描順序，將小波系數進行掃描分類(P：正的重要系數；N：負的重要系數；ZT(T)：零樹根；IZ(Z)：孤立零點；)；采用主表記錄輸出的分類符號，且標記出P或N系數的索引。

(3) 輔掃描。主掃描結束后，對輸出符號為P或N的小波系數進行量化[9-10]。量化器的輸入間隔為[Ti-1, 2Ti-1)，將其等分為兩個量化區間，且采用輔表記錄輸出的量化結果“0”或“1”。

(4) 重新排序。將P或N類別的系數按照幅值區間進行排序，即[1.5Ti-1, 2Ti-1)區間系數在前，[Ti-1, 1.5Ti-1) 區間系數在后。

(5) 輸出編碼信息。主要包括兩類：① 提供解碼的信息，閾值、主表和輔表；② 提供掃描的信息，閾值和重要系數序列。

EZW算法對小波系數進行編碼的具體步驟如圖1所示。

圖1 EZW算法小波系數編碼步驟圖

2 基于EZWSP的圖像壓縮算法

2.1 S+P變換

S+P變換是將序列變換和預測算法結合起來，完成整數到整數的變換，其中預測算法主要用來優化序列變換和逆變換的截斷誤差[11]，S變換類似于“haar”小波多分辨率分解[12]，假設整數序列c[n],n=0,1,…,N-1，N為偶數。c[n]可以由兩個序列來表示：

(2)

n=0,1,…,N/2-1

h[n]=c[2n]-c[2n+1]

(3)

n=0,1,…,N/2-1

式中，

為取整運算。序列l[n]和h[n]構成了c[n]的S變換。S變換的逆變換為：

c[2n]=l[n]+h[n]+12

(4)

c[2n+1]=c[2n]-h[n]

(5)

(6)

對于圖像的邊緣，預測方法為：

(7)

預測誤差為：

hd[n]=h[n]-h^[n]+1

/2

(8)

n=0,1,…,N/2-1

逆變換中，可按下式求得：

h[n]=hd[n]+h^[n]+1

/2

(9)

n=N/2-1,N/2-2,…,1,0

式中，運算順序從大到小，恢復序列h[n]后，再作S變換的逆變換，重構序列c[n]。

2.2 基于S+P變換改進的EZW編碼算法

基于S+P變換改進的EZW編碼算法框圖，如圖2所示。

圖2 編碼與解碼框圖

首先，根據原始圖像通過線性預測得到一幅差值圖像[14]，然后對差值圖像作S+P變換，先作行方向的變換，再作列方向的變換，具體方法為：

(1) 將待變換的圖像XM×N，采用回行數據結構排成一維的行向量Yc[X]；對Yc[X]進行一維S+P變換，產生兩個大小為M×N/2的一維子帶信號S0與S1；分別把S0與S1按回形數據結構排列成兩個子圖，大小為M×N/2。

(2) 將一維子帶信號S0與S1，采用回行數據結構排成兩個一維的列向量Yi[S0]與Yi[S1]；分別對Yi[S0]與Yi[S1]進行一維S+P變換，得到大小為(M/2)×(N/2)的4個一維子帶信號S00、S10、S01、與S11；分別把S00、S10、S01、與S11采用回行數據結構排成兩個子圖。

(3) 對低頻子圖重復(1)、(2)操作，迭代到給定的閾值為止，從而獲得圖像的多分辨塔式結構，如圖3所示。

圖3 圖像的多分辨塔式分解

利用S+P變換實現圖像的多分辨塔式分解，數據在大尺度下重建圖像時，需要濾波多次，這樣量化誤差對重建圖像的質量將產生較大影響，且影響的空間范圍比數據在小尺度的情況下要大。為減少量化噪聲，本文采用文獻[15]中針對人眼視覺特性設計的加權量化方案，各級子帶對應加權系數，如表1所示。

最后對經過加權量化處理的S+P變換系數進行EZW編碼，考慮到S+P變換子帶系數的相關性，規定權較大的子帶系數比權較小的子帶系數重要，對重要系數優先編碼，且對重要系數逐次逼近量化，形成嵌入式碼流， 詳細的操作步驟為：① 根據式(1)，計算初始閾值T0；② 根據“Zigzag”掃描順序進行掃描，根據主編碼流程創建主表，根據次編碼流程創建輔表；③ 根據系數的重要程度，排列輔表中分解系數值的順序；④ 將主表和輔表的值送至熵編碼器進行自適應算術編碼輸出；⑤ 判斷閾值精度，達到給定閾值，則停止編碼，否則重復②、③。

表1 各子帶加權系數

3 實驗結果與性能比較

由于小波變換的圖像壓縮技術中，小波基和小波分解級數的選擇對圖像的壓縮效果有很大的影響，且S+P變換要求圖像X是M×N或者M×N×P(M、N、P是圖像矩陣的維數)，其中M和N可以被2∧L(L是分解級數)整除。因此，實驗選用lbM為分解級數，同時采用EZW編碼通過不同的小波基對標準的256 × 256 × 8bit的woman、Lena、和mask圖像進行圖像壓縮和圖像重建，并選用最優壓縮效果的EZW算法與EZWSP算法的編碼效果進行實驗比較。其中，熵編碼采用Huffman編碼，通過給定閾值對實驗結果(即，算法的迭代次數)進行控制[16]。woman、Lena、和mask原圖像分別采用“haar”’、“coif1”、“sym2”以及“bior1.3”小波基進行EZW編碼的壓縮效果曲線，如圖4所示。

(a)woman壓縮結果

(b)Lena壓縮結果

(c)mask壓縮結果

由圖4可見，對于woman圖像，基于“haar”小波基的EZW編碼效果最優，對于Lena、mask圖像，基于“sym2”、“coif1”小波基的EZW編碼效果最優，并且綜合圖4(a)、(b)和(c)可以看出，基于“sym2”和“coif1”小波基的EZW編碼效果基本一致。因此，對于woman、Lena和mask圖像，分別選用基于“haar”、“sym2”和“coif1”小波基的EZW算法與EZWSP算法的編碼效果進行實驗比較。

(1) 主觀評價。鑒于本文算法考慮到人眼視覺特性，并且對參與實驗的EZW編碼算法也進行了加權量化，可在進行客觀評價前，選用主觀評價作為算法性能的度量。針對圖像特征的不同，都選用了最優的迭代次數對圖像進行了重構，最優迭代次數可依據圖8中的迭代次數與峰值信噪曲線選定。在迭代次數為10時，兩種算法對woman圖像的重構圖像，如圖5所示；在迭代次數為12時，兩種算法對Lena圖像的重構圖像，如圖6所示；在迭代次數為15時，兩種算法對mask圖像的重構圖像，如圖7所示。

(a)woman原圖像

(b)EZW(‘haar’)算法重構圖像

(c)EZWSP算法重構圖像

(a)Lena原圖像

(b)EZW(‘sym2’)算法重構圖像

(c)EZWSP算法重構圖像

(a)mask Lena原圖像

(b)EZW(‘cofi1’)算法重構圖像

(c)EZWSP算法重構圖像

綜上，可以很容易看出圖5～7在各自相同迭代次數的情況下，圖(c)總是比圖(b)重構質量高，且不易察覺干擾。

(2) 客觀評價。對標準的256 × 256 × 8bit的woamn、 Lena和mask圖像，分別進行EZW與EZWSP編碼，并記錄相同的迭代次數下，兩種算法重構woman、Lena、和mask圖像的峰值信噪比(psnr)，繪出對應的曲線如圖8所示；采用不同的迭代次數，并記錄下相應的像素深度(bpp)與峰值信噪比(psnr)，繪出對應的曲線如圖9所示。

圖8 迭代次數與峰值信噪比關系曲線

從圖8中可以看出，在相同的迭代次數下，woman、Lena和mask圖像采用EZWSP編碼的峰值信噪比均高于采用EZW編碼的峰值信噪比，這說明在一定的迭代次數下，使用EZWSP編碼，重構的圖像質量更高，EZWSP編碼效率優于EZW編碼。從圖9中可以看出，woman、Lena和mask圖像采用EZWSP編碼的像素深度(bpp)與峰值信噪比(psnr)曲線均在采用EZW編碼的曲線上方，這說明相同的壓縮率下，EZWSP編碼重構的圖像質量更高；或者相同的重構圖像質量下，EZWSP編碼的壓縮率更大。實驗結果表明：不管是在編碼效率、壓縮率還是重構質量方面，本文提出的EZWSP編碼算法均優于EZW編碼算法，因而具有廣闊的應用前景。

圖9 像素深度與峰值信噪比關系曲線

4 結 語

本文把EZW編碼與S+P變換結合起來，提出了一種有效的圖像壓縮算法，該算法首先根據原始圖像通過線性預測得到一幅差值圖像，然后對差值圖像進行S+P變換，且對S+P變換系數進行加權量化， 最后對經過加權量化處理的S+P變換系數進行EZW編碼壓縮。此外，該算法采用回形數據結構把圖像轉化為一個一維的向量，然后進行一維的S+P變換，減少了S+P變換增加的數據量，有效地解決了圖像邊緣輪廓的處理問題。實驗結果與性能比較表明，不論是從主觀評價參數還是客觀評價參數來看，EZWSP編碼算法在編碼效率、壓縮率以及圖像重構效果上均比原算法有較大的改善。

參考文獻(References)：

[1] Shapiro J M. Embedded image coding using zero trees of wavelet coefficients[J]. IEEE Trans Signal Process,1993,41(12) :3445-3462.

[2] 陳 冬,張田文,李 東.位漸進逼近量化的EZW改進算法[J].哈爾濱工業大學學報,2010,42(5):779-783.

[3] 黃 慶.一種改進的嵌入式零樹小波圖像編碼算法[J].通信技術,2013,2(46):29-34.

[4] Naveen C H, Satpute V R., Keskar A G.. An efficient low dynamic range image compression using improved block based EZW [J]. IEEE Asia Pacific Conference on Postgraduate Research in Microelectronics and Electronics,2015,10(1109):63-68.

[5] Michael D, Adams, Andreas A. Reversible EZW-based image compression using best-transform selection and selective partial embedding[J].IEEE Trans on Analog and Digital Processing, 2000,47(10): 1119-1122.

[6] Christophe E, Duhamel P, Mailhes C. Signed binary digit representation to simplify 3D-EZW[J]. IEEE Int. Conf. Acoustics Speech and Signal Processing, 2007, 1:1025-1028.

[7] 詹 旭,杜玲艷,馬 將.基于小波壓縮的彩色圖像半脆弱水印認證[J].實驗室研究與探索,2014,33(8):22-25.

[8] 孫 燕,李曉光,卓 力.一種基于小波壓縮感知的藏族壁畫圖像處理[J].實驗室研究與探索,2016,35(5):138-140.

[9] Tsai J C, Hsieh C H, Hsu T C. A new dynamic finit-state vector quantization algorithm for image compression[J]. IEEE Trans on Image Processing, 2000, 9(11):1825-1836.

[10] 寇蓓蕾.基于小波變換的分類矢量量化圖像壓縮編碼方法研究[D]. 西安：西安電子科技大學, 2001.

[11] Skodras A, Christopoulos C, Ebrahimi T. The JPEG 2000 still image compression standard[J]. IEEE Signal Process, 2001,18(5):36-58.

[12] 米 晨,湯秀芬,魏鳳蘭.基于Haar小波變換的圖像分解與重構[J]. 實驗室研究與探索,2003,22(2):78-81.

[13] Babel M, Deforges O, Ronsin J. Interleaved S+P pyramidal decomposition with refined prediction model[J]. In ICIP, 2007, 2:750-753.

[14] Zhang Li-hong, Hou Xian-tao, Wang Xiao-kai. Super resolution image reconstruction algorithm based on S+P transformation and interpolation[J].IET Conference Publications,2010,10(1049): 331-334.

[15] Desarte P, Macq B, Slock D. Signal-adapted multiresolution transform for image coding[J]. IEEE Trans. on Information Theory, 1992, 38(2): 897-904.

[16] 李秀梅,應廣之,賈中云. EZW算法中小波分解層數及掃描次數對圖像壓縮性能的影響[J].計算機系統應用,2013,22(8):130-135.