混合基于行和7/5提升格式的小波變換算法

蔡昭權(quán)

(惠州學院科研處, 廣東 惠州 516007)

混合基于行和7/5提升格式的小波變換算法

蔡昭權(quán)

(惠州學院科研處, 廣東 惠州 516007)

針對傳統(tǒng)小波變換算法對內(nèi)存需求大和計算復(fù)雜度高的問題，提出了混合基于行和7/5提升格式的小波變換算法。該算法采用基于行的小波變換，減少圖像壓縮的存儲容量，利用BT7/5濾波器實現(xiàn)提升格式以減小計算復(fù)雜度。實驗結(jié)果表明，該算法具有與JPEG2000相近的壓縮效果，比傳統(tǒng)的小波變換算法具有更小的內(nèi)存需求，比其他基于行的提升小波算法具有更低的計算復(fù)雜度。

圖像壓縮；基于行的小波變換；提升格式

由于離散小波變換(簡稱DWT)具有較好的壓縮能力，所以離散小波變換被廣泛地應(yīng)用于圖像壓縮領(lǐng)域[1-3]。在許多實際應(yīng)用如遙感圖像和醫(yī)學圖像處理中，數(shù)據(jù)量相當大以致于對內(nèi)存的需求也相當之巨大，這就導(dǎo)致了傳統(tǒng)小波變換有點力不從心，因此Chrysafis等[4]提出了基于行的小波變換。該變換方法采用逐行方式進行小波變換并輸出小波系數(shù)，即只要緩存讀入滿足一定要求的行數(shù)，就開始進行小波變換，而不是要等待所有的數(shù)據(jù)全部讀入緩存才開始進行小波變換，這種方法可以明顯地減少小波變換所需要的內(nèi)存容量。

自基于行的小波變換提出后，引起了國內(nèi)外針對該算法的各種研究。劉正光等[5]將基于行的小波變換應(yīng)用于圖像壓縮中，采用基于行的小波變換進行編碼，用改進的提升格式代替Mallat算法進行小波變換；張宏偉等[6]提出采用三項加法單元形式的提升格式代替Mallat算法進行小波變換；Ye等[7]提出采用基于行的小波變換來處理JPEG2000中獨立塊編碼問題；Eristi[8]提出了基于行的小波變換的電力容錯診斷系統(tǒng)。

提升格式對于小變換的實現(xiàn)起著重要的作用，楊漢生等[9]提出了一種基于正交多項式的自適應(yīng)提升格式來實現(xiàn)圖像壓縮；Shoba等[10]將基于提升格式實現(xiàn)的小波變換應(yīng)用于衛(wèi)星圖像壓縮中；高東等[11]利用基于提升格式的小波變換提出了一種過程數(shù)據(jù)在線去噪方法。

目前，在大部分基于提升格式的小波變換方法中，都是采用CDF9/7濾波器來實現(xiàn)的。由于基于9/7提升格式的小波變換的輸出系數(shù)是無理數(shù)，而無理數(shù)在計算方面明顯比有理數(shù)更為復(fù)雜。為了降低小波變換的計算復(fù)雜度和減少內(nèi)存需求，同時又能夠保證圖像的壓縮質(zhì)量，本文嘗試采用BT7/5濾波器實現(xiàn)7/5提升格式的小波變換以達到在變換過程減小計算復(fù)雜度的目的。

1 基于行的小波變換

與傳統(tǒng)的小波變換方法不同，基于行的小波變換方法先逐行讀取數(shù)據(jù)到緩存中，然后對行數(shù)據(jù)進行小波變換，當緩存中的行數(shù)達到由濾波器長度規(guī)定的數(shù)量后，才開始對列數(shù)據(jù)進行小波變換，而不是等待所有行的數(shù)據(jù)都讀入到緩存后才對所有行進行小波變換的。在完成行的小波變換后就立刻輸出小波系數(shù)，即逐行變換，逐行輸出，直到所有的小波系數(shù)全部輸出后才結(jié)束[4]。這樣做的優(yōu)勢就在于：不用同時讀入所有的數(shù)據(jù)行，以致于可以在很大程度上減少了內(nèi)存的需求。

基于行的小波變換流程如下[4]：

設(shè)L=2α+φ為反饋分析濾波器的最大長度，L為奇數(shù)或是偶數(shù)由φ=1還是φ=0決定。一般地，以L為奇數(shù)為例(偶數(shù)情況可以類似處理)，設(shè)緩沖區(qū)的容量BFL等于濾波器的長度L。在邊界處理方面，采用左延拓方式[12]。

對于第一級小波變換，首先圖像數(shù)據(jù)寫入到緩沖區(qū)BF1中，在寫入的同時，也從BF1讀取α+1行數(shù)據(jù)并進行行向小波變換。然后進行左延拓，在左延拓之后，如果BF1寫滿，則對第0行數(shù)據(jù)進行列向濾波，并輸出低通結(jié)果。之后再讀取一行新數(shù)據(jù)，同時對第1行數(shù)據(jù)進行列向濾波，并保存高通結(jié)果。與輸出的低通結(jié)果不同的是，高通結(jié)果是先要暫存在一個同步緩沖區(qū)中，待所有級的小波變換完成之后一起輸出。如此循環(huán)，則交替輸出低通和高通結(jié)果。

對于第二級小波變換，把一級小波變換的低通結(jié)果寫入緩沖區(qū)BF2中，之后與一級小波變換一樣，先從BF2讀取行數(shù)據(jù)進行行向小波變換，再進行列向小波變換。同理，又將交替輸出低通和高通結(jié)果。

對于第N級小波變換，仍然類似地進行。此時可以計算出緩沖區(qū)的容量為

BF=N(2α+1)=NL

(1)

此外，設(shè)同步緩沖區(qū)的小為α(2N-i-1)，其中i=0,1,…,N-1為當前變換層。

綜上所述，完成N級小波變換需要總的緩沖區(qū)容量為

(2)

2 提升格式

提升格式是實現(xiàn)小波變換最有效的方法[13]，設(shè)x[m,n]為一個2維信號源，信號源先進行行向小波變換再進行列向小波變換。一般情況下，提升格式主要包括分裂、預(yù)測和更新三個步驟。

1)分裂。

將信號源x[m,n]分解成奇數(shù)子集xo[m,n]和偶數(shù)子集xe[m,n]，其中xo[m,n]=x[2m+1,n]，xe[m,n]=x[2m,n]。

2)預(yù)測。

用偶數(shù)子集xe[m,n]預(yù)測奇數(shù)子集xo[m,n]，此時設(shè)P(·)為預(yù)測算子，則：

(3)

其中pi為高通濾波系數(shù)，由于預(yù)測而產(chǎn)生的預(yù)測誤差可由下式表示：

d[m,n]=xo[m,n]+P(xe)[m,n]

(4)

3)更新。

通過預(yù)測誤差d[m,n]來校正偶數(shù)子集xe[m,n]，其公式為

c[m,n]=xe[m,n]+U(d)[m,n]

(5)

其中U(·)為更新算子，U(·)可以通過下式計算：

(6)

其中uj為低通濾波系數(shù)。

因此，通過公式(4)和公式(5)，就可以用d[m,n]、c[m,n]和算子P(·)、U(·)表示信號源x[m,n]。

圖1顯示了采用提升格式的小波變換過程。

圖1 采用提升格式的小波變換Fig.1 Wavelet transform using lifting scheme

2 基于行和7/5提升格式的小波變換算法

2.1 7/5提升格式

目前，大部分的小波變換算法都是采用CDF9/7濾波器實現(xiàn)提升格式，然而正如前文所說，CDF9/7的提升格式計算復(fù)雜度高，嚴重影響了計算效率[14]。由于BT7/5濾波器的小波系數(shù)是有理數(shù)，具有更低計算復(fù)雜度和更容易實現(xiàn)的特點，所以本文采用該濾波器代替CDF9/7濾波器實現(xiàn)小波變換算法中的提升格式。

假設(shè)低通分析濾波器用Hn(ξ)表示，低通綜合濾波器用Gn(ξ)表示，具體如下：

(7)

(8)

同理，假設(shè)高通分析濾波器用Hn+1(ξ)表示，高通綜合濾波器用Gn+1(ξ)表示，具體為：

(9)

(10)

令7/5小波基的提升參數(shù)α=t2，β=t3，γ=t4，θ=s3，由于歐幾里德算法具有因式分解的功能，所以利用歐幾里德算法在BT7/5濾波器中可以求出其多相矩陣。根據(jù)BT7/5濾波器的多相矩陣和系數(shù)的歸一化條件可求出如下小波系數(shù)：

H0=(1+2βγ)θ

H1=[(2αβ+1)γ+α(1+βγ)]θ

H2=βγθ

G0=(2αβ+1)/(2θ)

G1=-β(2θ)

G2=αβ(2θ)

2.2 算法描述

基于行和7/5提升格式的小波變換算法就是結(jié)合基于行的小波變換思想，采用7/5提升格式實現(xiàn)小波變換。使用三項加法單元實現(xiàn)7/5提升格式，具體如下：

Routput=R1+c(R0+R2)

(11)

其中R0、R1和R2為輸入緩沖區(qū)，Routput為輸出緩沖區(qū)，c為乘法算子。

綜上所述，算法的偽碼如下：

∥R0、R1、R2代表輸入緩沖區(qū)；R3、R4、R5和R6為輸出緩沖區(qū)；R7和R8為同步緩沖區(qū)；p1、u1、p2和u2為三項加法單元的系數(shù)，分別對應(yīng)BT7/5濾波器中的α、β、γ、θ，L為濾波器的長度。OH表示高通輸出，OL表示低通輸出。

讀取第i行圖像數(shù)據(jù);

while (i不是最后一行) {

if (L為奇數(shù))

{

R0=i/L;

R2=i/L;

R3=R1+p1(R0+R2);

R4=R5+u1(R1+R3);

R8=R6+p2(R5+R4);

OH=R8;

OL=R7+u2(R6+R8);

}

else

{

R0=i/L;

R1=i/L;

R5=R2+p1(R0+R1);

R6=R3+u1(R2+R5);

R7=R4+p2(R3+R6);

OH=R7;

OL=R8+u2(R4+R7);

}

讀取第i行圖像數(shù)據(jù);

}

3 實驗結(jié)果與分析

我們采用Visual C++編程軟件在Windows 7操作系統(tǒng)環(huán)境下對本文算法(簡稱7/5LWT)進行了實現(xiàn)，硬件環(huán)境為Inter Core2 Quad CPU 2.83 Hz，內(nèi)存為4.00 GB。為了證明本文算法的優(yōu)勢，本文算法也與目前比較流行的圖像壓縮算法Improved SPIHT[15]、Line-based BCWT和JPEG2000等進行了比較[7,14]。

3.1 壓縮效果比較

我們對512×512的8 bpp(bits per pixel)的Lena圖像進行圖像壓縮，測試了PSNR和MSE性能。所有比較的算法在編碼量化方式上，使用嵌入零樹編碼。圖2顯示了PSNR的測試結(jié)果，圖3顯示了MSE的測試結(jié)果。

從圖2中可以看出，在PSNR方面，7/5LWT算法稍微優(yōu)于Improved SPIHT和Line-based BCWT算法，基本上與JPEG2000接近。圖3中的實驗數(shù)據(jù)也得到了類似的結(jié)果，這說明無論是在PSNR方面，還是在MSE方面，7/5LWT算法都能取得較好的壓縮效果。由于Improved SPIHT和Line-based BCWT算法都是采用的CDF9/7提升格式，所以我們可以推測出一個這樣的結(jié)論：基于7/5提升格式的小波變換在性能上并不會比基于CDF9/7提升格式的小波變換差，甚至會稍好一些。

圖2 不同比特率下PSNR性能Fig.2 Performance PSNR under different bit rate

圖3 不同比特率下MSE性能Fig.3 Performance MSE under different bit rate

3.2 計算復(fù)雜度比較

為了進一步說明本文算法的優(yōu)勢，在相同緩沖區(qū)容量的條件下，我們對這4個算法在計算量方面進行了實驗對比，一般地，算法的計算復(fù)雜度通過執(zhí)行時間體現(xiàn)，圖4顯示了這4個算法的執(zhí)行時間。從圖4可以看出，7/5LWT算法的執(zhí)行時間比JPEG2000要少一半以上。即使與Improved SPIHT和Line-based BCWT算法相比，7/5LWT算法的執(zhí)行時間也它們要低一些，這也與前文的分析結(jié)果是一致的。

圖4 不同比特率下的計算量Fig.4 Computation under different bit rate

4 結(jié) 論

為了找出一種既對內(nèi)存需求少，又能保證圖像壓縮質(zhì)量的小波變換算法，采用基于行的小波變換技術(shù)，結(jié)合BT7/5濾波器的提升方案，提出了一種混合基于行和7/5提升格式的小波變換算法。該算法采用基于行的小波變換降低內(nèi)存需求，采用7/5提升格式提高計算速度。實驗結(jié)果表明：通過與目前比較流行的圖像壓縮算法Improved SPIHT、 Line-based BCWT 和JPEG2000等的比較，本文算法具有更好的壓縮性能和更少的計算復(fù)雜度。該算法能夠較好地應(yīng)用于存儲容量有限的領(lǐng)域，如視頻監(jiān)控等。

[1] 柳薇, 陳冬麗. 基于多小波變換的圖像編碼算法研究[J]. 中山大學學報( 自然科學版), 2011, 50(5): 50-53.

[2] 郭昌. 小波變換與HMT 模型的圖像插值算法[J]. 中山大學學報( 自然科學版), 2012, 51(3): 55-59.

[3] VENKATESHWAR R M. BHAGYA R V. Image resolution enhancement technique using lifting wavelet and discrete wavelet transforms[C]∥ Proceeding of the 3rd International Conference on Innovations in Computer Science and Engineering, 2015, 413: 235-239.

[4] CHRYSAFIS C, ORTEGA A. Line-based, reduced memory, wavelet image compression [J]. IEEE Transactions on Image Processing, 2000, 9(3): 378-389.

[5] 劉正光, 申旭剛. 基于行的小波變換及其在圖像壓縮中的應(yīng)用[J]. 中國圖像圖形學報, 2004, 9(3): 370-374.

[6] 張宏偉, 劉正光, 陳紅新. 應(yīng)用提升格式實現(xiàn)的基于行小波變換的圖像壓縮算法[J]. 計算機應(yīng)用, 2005, 25(7): 1626-1628.

[7] YE L, GUO J, NUTTER B, et al. Low-memory-usage image coding with line-based wavelet transform [J]. Optical Engineering, 2011, 50(2): 1-11.

[8] ERISTI H. Fault diagnosis system for series compensated transmission line based on wavelet transform and adaptive neuro-fuzzy inference system [J]. Measurement, 2013, 46(1): 393-401.

[9] 楊漢生, 孔鯤鵬, 許磊. 基于正交多項式的自適應(yīng)提升格式[J]. 南京理工大學學報(自然科學版),2009, 33(3): 307-311.

[10] SHOBA P, MARIA L L, MOHAN V, et al. Landsat image compression using lifting scheme [C]∥ Proceeding of International Conference on Communications and Signal Processing (ICCSP). Tamilnadu Melmaruvathur, India, 2014: 1963-1968.

[11] 高東, 張貝克, 吳重光. 基于提升格式的過程數(shù)據(jù)在線去噪方法及其應(yīng)用[J]. 計算機應(yīng)用研究,2008, 25(10): 3198-3200.

[12] ZHANG L, QIU B. Edge-preserving image compression using adaptive lifting wavelet transform [J]. International Journal of Electronic, 2015, 102(7): 1190-1203.

[13] GUO F, LIU X, ZHAO C. The image enhancement technology based on lifting wavelet [J]. Applied Mechanics and Materials, 2014, 513/514/515/516/517: 3261-3264.

[14] ZENG W, DALY S, LEI S. An overview of the visual optimization tools in JPEG 2000 [J]. Signal Processing: Image Communication, 2002, 17(1): 85-104.

[15] 丁曉峰, 何凱霖. 基于改進提升小波變換 SPIHT 的圖像壓縮算法[J]. 計算機測量與控制, 2014, 22(11): 3670-3672.

Hybrid line-based 7/5 lifting scheme wavelet transform algorithm

CAI Zhaoquan

(Scientific Research Office, Huizhou University, Huizhou 516007, China)

In view of the problem of big memory requirement and high computational complexity in the traditional wavelet transform algorithm, a hybrid line-based 7/5 lifting scheme wavelet transform algorithm is proposed. In the proposed algorithm, the line-based wavelet transform is used to reduce requirement of buffer in image compression, and the lifting scheme which is implemented by BT7/5 filter is used to reduce computation complex. The experimental results show that the proposed algorithm has similar the quality of compression with JPEG2000 and requires smaller memory than the traditional wavelet transform algorithm. Meanwhile, the proposed algorithm has lower computational complexity than the lines-based wavelet algorithm variant.

image compression; line-based wavelet transforms; lifting scheme

10.13471/j.cnki.acta.snus.2016.05.010

2016-01-08

國家自然科學基金資助項目(61170193, 61370185)； 廣東省自然科學基金資助項目(S2013010013432)； 廣東省自然科學基金重點資助項目(S2012020011081)

蔡昭權(quán)(1970年生), 男；研究方向: 圖像處理，模式識別;E-mail:cai@hzu.edu.cn

TN919.81

A

0529-6579(2016)05-0052-05