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

陳軼鳴， 夏景明， 陳愛(ài)月， 唐玲玲

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

0 引 言

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

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

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

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

T0=2lbMax{ci,j}

(1)

式中：{ci,j}是L級(jí)小波變換的變換系數(shù)；ci,j是ci,j的絕對(duì)值。

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

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

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

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

EZW算法對(duì)小波系數(shù)進(jìn)行編碼的具體步驟如圖1所示。

圖1 EZW算法小波系數(shù)編碼步驟圖

2 基于EZWSP的圖像壓縮算法

2.1 S+P變換

S+P變換是將序列變換和預(yù)測(cè)算法結(jié)合起來(lái)，完成整數(shù)到整數(shù)的變換，其中預(yù)測(cè)算法主要用來(lái)優(yōu)化序列變換和逆變換的截?cái)嗾`差[11]，S變換類似于“haar”小波多分辨率分解[12]，假設(shè)整數(shù)序列c[n],n=0,1,…,N-1，N為偶數(shù)。c[n]可以由兩個(gè)序列來(lái)表示：

(2)

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

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

(3)

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

式中，

為取整運(yùn)算。序列l(wèi)[n]和h[n]構(gòu)成了c[n]的S變換。S變換的逆變換為：

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

(4)

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

(5)

(6)

對(duì)于圖像的邊緣，預(yù)測(cè)方法為：

(7)

預(yù)測(cè)誤差為：

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

式中，運(yùn)算順序從大到小，恢復(fù)序列h[n]后，再作S變換的逆變換，重構(gòu)序列c[n]。

2.2 基于S+P變換改進(jìn)的EZW編碼算法

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

圖2 編碼與解碼框圖

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

(1) 將待變換的圖像XM×N，采用回行數(shù)據(jù)結(jié)構(gòu)排成一維的行向量Yc[X]；對(duì)Yc[X]進(jìn)行一維S+P變換，產(chǎn)生兩個(gè)大小為M×N/2的一維子帶信號(hào)S0與S1；分別把S0與S1按回形數(shù)據(jù)結(jié)構(gòu)排列成兩個(gè)子圖，大小為M×N/2。

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

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

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

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

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

表1 各子帶加權(quán)系數(shù)

3 實(shí)驗(yàn)結(jié)果與性能比較

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

(a)woman壓縮結(jié)果

(b)Lena壓縮結(jié)果

(c)mask壓縮結(jié)果

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

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

(a)woman原圖像

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

(c)EZWSP算法重構(gòu)圖像

(a)Lena原圖像

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

(c)EZWSP算法重構(gòu)圖像

(a)mask Lena原圖像

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

(c)EZWSP算法重構(gòu)圖像

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

(2) 客觀評(píng)價(jià)。對(duì)標(biāo)準(zhǔn)的256 × 256 × 8bit的woamn、 Lena和mask圖像，分別進(jìn)行EZW與EZWSP編碼，并記錄相同的迭代次數(shù)下，兩種算法重構(gòu)woman、Lena、和mask圖像的峰值信噪比(psnr)，繪出對(duì)應(yīng)的曲線如圖8所示；采用不同的迭代次數(shù)，并記錄下相應(yīng)的像素深度(bpp)與峰值信噪比(psnr)，繪出對(duì)應(yīng)的曲線如圖9所示。

圖8 迭代次數(shù)與峰值信噪比關(guān)系曲線

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

圖9 像素深度與峰值信噪比關(guān)系曲線

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)(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] 陳 冬,張?zhí)镂?李 東.位漸進(jìn)逼近量化的EZW改進(jìn)算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2010,42(5):779-783.

[3] 黃 慶.一種改進(jìn)的嵌入式零樹(shù)小波圖像編碼算法[J].通信技術(shù),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] 詹 旭,杜玲艷,馬 將.基于小波壓縮的彩色圖像半脆弱水印認(rèn)證[J].實(shí)驗(yàn)室研究與探索,2014,33(8):22-25.

[8] 孫 燕,李曉光,卓 力.一種基于小波壓縮感知的藏族壁畫圖像處理[J].實(shí)驗(yàn)室研究與探索,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]. 西安：西安電子科技大學(xué), 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小波變換的圖像分解與重構(gòu)[J]. 實(shí)驗(yàn)室研究與探索,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] 李秀梅,應(yīng)廣之,賈中云. EZW算法中小波分解層數(shù)及掃描次數(shù)對(duì)圖像壓縮性能的影響[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2013,22(8):130-135.