新Ｂｕｒｔ－Ａｄｅｌｓｏｎ雙正交小波的優(yōu)化設(shè)計(jì)

 收稿日期：2007-09-24；

修回日期：2007-12-25

基金項(xiàng)目：江蘇省高校自然科學(xué)基礎(chǔ)研究資助項(xiàng)目（07KJD520005）；常熟理工學(xué)院新引進(jìn)教師科研啟動(dòng)基金資助項(xiàng)目（ky11520）；常熟理工學(xué)院青年教師科研啟動(dòng)基金資助項(xiàng)目（ky200657）



作者簡(jiǎn)介：劉在德(1977-)，男，山東萊蕪人，博士，主要研究方向?yàn)閳D像處理、小波分析及其應(yīng)用(lzd.122604@gmail.com)；常晉義(1955-)，男，山西忻州人，教授，主要研究方向?yàn)榭臻g決策支持系統(tǒng)、信息系統(tǒng)安全；聶盼紅(1977-)，女，山西翼城人，講師，碩士，主要研究方向?yàn)閳D像處理.

(常熟理工學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院 江蘇 常熟 215500)

摘要：根據(jù)小波濾波器的精確重構(gòu)條件，推導(dǎo)出Burt-Adelson雙正交小波濾波器組的參數(shù)表達(dá)式。該表達(dá)式參數(shù)可任意取值，因此能夠隨意構(gòu)造具有不同特征的Burt-Adelson小波。作為構(gòu)造實(shí)例，構(gòu)造出一個(gè)新的有理系數(shù)Burt-Adelson小波，它具有優(yōu)化的編碼增益。實(shí)驗(yàn)表明，其圖像壓縮性能略低于CDF-9/7小波，但優(yōu)于JPEG 2000標(biāo)準(zhǔn)推薦的7/5小波；而且其提升小波變換的計(jì)算效率比CDF-9/7小波高20%以上，也優(yōu)于7/5小波。

關(guān)鍵詞：雙正交小波； 濾波器； 離散小波變換； 提升； 圖像編碼

中圖分類號(hào)：TN911.73

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)010-3078-03

Optimization design of new Burt-Adelson biorthogonal wavelets

LIU Zai-de CHANG Jin-yi NIE Pan-hong

(School of Computer Science Engineering Changshu Institute of Technology Changshu Jiangsu 215500 China)

Abstract:This paper derived the parameter expressions of Burt-Adelson (B-A) biorthogonal wavelet filter bank (FB) family based on the perfect reconstruction condition of FB. By assigning arbitrary real number to this free parameter any B-A wavelet with different features could be constructed with ease. As an instance constructed a new rational-coefficient B-A wavelet with optimum coding gain. Simulations show that the new B-A wavelet enjoys the image compression performance slightly inferior to that of the CDF-9/7 wavelet by Cohen Daubechies and Feauveau; however surpasses the 7/5 wavelet recommended in JPEG 2000 standard. Moreover its corresponding lifting based discrete wavelet transform (DWT) gains an improvement of computational efficiency up to 20% over the CDF-9/7 superior to 7/5 wavelet also.

Key words：biorthogonal wavelet; filter bank; discrete wavelet transform (DWT); lifting; image coding

雙正交小波已被廣泛應(yīng)用于工程和科學(xué)計(jì)算的各個(gè)領(lǐng)域，尤其在數(shù)字圖像編碼領(lǐng)域取得了極大的成功[1，2]。CDF-9/7小波[3]是圖像變換編碼領(lǐng)域中應(yīng)用最為廣泛的小波之一，并在JPEG 2000標(biāo)準(zhǔn)中得到應(yīng)用，但其濾波器系數(shù)是無(wú)理數(shù)，需要用無(wú)限的計(jì)算精度實(shí)現(xiàn)對(duì)應(yīng)的離散小波變換（DWT），這極大地增加了計(jì)算復(fù)雜度。有理系數(shù)雙正交小波計(jì)算復(fù)雜度低、應(yīng)用方便，引起了許多研究者的興趣[4~8]。第一個(gè)Burt-Adelson（B-A）雙正交小波被用于Laplacian金字塔算法，實(shí)現(xiàn)數(shù)字圖像的有損壓縮[9]。該小波有三個(gè)優(yōu)點(diǎn)：對(duì)稱性；系數(shù)為有理數(shù)；分解小波與合成小波近似正交，即小波濾波器為近似正交鏡像濾波器（quadrature mirror filter）。但其編碼性能很低，在圖像編碼的實(shí)際應(yīng)用中效果并不好。JPEG 2000標(biāo)準(zhǔn)Ⅱ中推薦的7/5小波是另一個(gè)廣為采用的B-A小波[2]，它同樣具有有理系數(shù)，壓縮性能也優(yōu)于第一個(gè)B-A小波。此小波的計(jì)算復(fù)雜度低于CDF-9/7小波，但壓縮性能也與之有著較大的差距。因此設(shè)計(jì)高壓縮性能、低計(jì)算復(fù)雜度的有理系數(shù)雙正交小波是圖像變換編碼領(lǐng)域中十分現(xiàn)實(shí)的一個(gè)問題。

1預(yù)備知識(shí)

這里給出本文用到的基本理論，有關(guān)雙正交小波的完整理論可參看文獻(xiàn)[3]。一個(gè)雙正交小波包括兩個(gè)互為對(duì)偶的尺度函數(shù)φ(x)和(x)，它們分別滿足如下的兩尺度方程：

φ(x)=2∑khkφ(2x-k)，(x)=2∑kk(2x-k)(1)

對(duì)應(yīng)的小波低通濾波器分別定義為

H(ξ)=1/2∑khke-jkξ，(ξ)=1/2∑kke-jkξ(2)

那么雙正交條件（濾波器精確重構(gòu)條件）可簡(jiǎn)化為

H(ξ)(ξ)+H(ξ+π)(ξ+π)=1(6)

這里上劃線代表復(fù)變函數(shù)中的共軛算子。滿足式(5)(6)的濾波器集合{H(ξ)，G(ξ);(ξ)，(ξ)}構(gòu)成一個(gè)精確重構(gòu)雙正交小波濾波器組。

消失矩對(duì)于一個(gè)雙正交小波取得好的能量集中能力至關(guān)重要，一方面具有高消失矩的小波用很少的變換系數(shù)即可精確表達(dá)平滑信號(hào)；另一方面過(guò)高的消失矩會(huì)增加濾波器長(zhǎng)度，不利于信號(hào)奇異點(diǎn)附近能量的集中，而且也會(huì)急劇增大計(jì)算復(fù)雜性。因此在構(gòu)造小波時(shí)，一般設(shè)定消失矩為2~6。指定一個(gè)小波濾波器具有N階消失矩的簡(jiǎn)單方法是添加多項(xiàng)式因子cosN(ξ/2)。對(duì)于一個(gè)雙正交小波，如果基本小波濾波器具有偶數(shù)或奇數(shù)階消失矩，那么對(duì)偶小波濾波器同樣具有偶數(shù)或奇數(shù)階消失矩；反之亦然[3]。

2Burt-Adelson小波的參數(shù)化構(gòu)造

B-A小波具有消失矩2，基本低通濾波器H(ξ)和對(duì)偶低通濾波器(ξ)分別有五個(gè)和七個(gè)節(jié)點(diǎn)，定義兩者分別為

H(ξ)=cos2(ξ/2)[a+(1-a)cos ξ](7)

(ξ)=cos2(ξ/2)[A+B cos ξ+(1-A-B)cos2 ξ](8)

其中：a為自由參數(shù)；A和B為待求的未知系數(shù)。因?yàn)橛嘞液瘮?shù)是偶函數(shù)，滿足式(7)(8)的濾波器自然滿足對(duì)稱性和濾波器低、高通條件

H(0)=1=(0)，H(π)=0=(π)

把濾波器式(7)(8)代入精確重構(gòu)條件式(6)，因?yàn)橛歇ヽos(ξ+π)=-cos ξ，所以有

H(cos ξ)(cos ξ)+H(-cos ξ)(-cos ξ)=1(9)

展開式(9)，根據(jù)左、右兩邊對(duì)應(yīng)項(xiàng)系數(shù)分別相等，可得到

A=2/a，B=(-a2+4a-4)/a

將A和B代入式(8)，并把式(7)(8)分別展開化簡(jiǎn)，最后得到

H(ξ)=(1+a)/4+1/4(z+z-1)+(1-a)/8(z2+z-2)(10)

(z)=(a+2)/(4a)+(-a2+7a-2)/(16a)(z+z-1)+(a-2)/

(8a)(z2+z-2)+(a2-3a+2)/(16a)(z3+z-3)(11)

這里z=ejξ。根據(jù)式（5），就可得到對(duì)應(yīng)小波高通濾波器G(ξ)和(ξ)的參數(shù)表達(dá)式，這里不再給出。

3新Burt-Adelson小波的優(yōu)化選取

自由參數(shù)a為優(yōu)化選擇最終的小波提供了一個(gè)自由度。為了得到具有高壓縮性能的新B-A小波以用于圖像編碼，需要指定一個(gè)衡量小波壓縮性能的優(yōu)化準(zhǔn)則。

3.1編碼增益

本文采用Katto等人[10]提供的編碼增益公式來(lái)衡量B-A小波的壓縮性能。對(duì)于雙正交小波，這是一個(gè)很有效的評(píng)估準(zhǔn)則。給定一個(gè)N子帶小波分解系統(tǒng)，假定第n級(jí)子帶的等效分解和合成濾波器的系數(shù)分別用n(i)和hn(j)，n=1，…，N表示；再假定輸入信號(hào)可用相關(guān)因子為ρ的一維Markov模型表示，則編碼增益可表示為

CG(ρ)=∏Nn=1(AnBn)-an(12)

這里An=∑i∑jn(i)n(j)ρ｜i-j｜，Bn=∑ihn(i)2；αn是等效的采樣率（對(duì)于普通的Mallat金字塔結(jié)構(gòu)分解，αn=1/N)。注意：在本文中，編碼增益是自變量為自由參數(shù)a的一個(gè)函數(shù)。

3.2優(yōu)化的B-A小波

在實(shí)際應(yīng)用中，B-A小波有兩種使用方法：一種方法是以基本濾波器為分解濾波器，而以對(duì)偶濾波器為合成濾波器；第二種方法正好相反。圖1給出了B-A小波在兩種用法下的編碼增益（單位：dB）——自由參數(shù)a的關(guān)系曲線圖。這里采用五級(jí)小波分解，相關(guān)因子ρ=0.95。

圖中B-A-5/7對(duì)應(yīng)著第一種使用方法，而B-A-7/5對(duì)應(yīng)著第二種使用方法。從圖中可以看出，當(dāng)參數(shù)a∈[1.25，2.25]時(shí)，B-A-5/7具有較高的編碼增益；而當(dāng)參數(shù)a∈[0.8，1.25]時(shí)，B-A-7/5具有較高的編碼增益。對(duì)于B-A-7/5小波，當(dāng)a=7/5=1.4時(shí)，即可得到由Burt和Adelson構(gòu)造的第一個(gè)B-A小波（記為B-A-7/5-O），但它的編碼增益僅僅為8.397 dB；而當(dāng)a=11/10=1.1時(shí)，得到的小波具有較高的編碼增益，其值為9.267 dB，這個(gè)小波就是JPEG 2000標(biāo)準(zhǔn)Ⅱ推薦的7/5小波（記為J-7/5）。對(duì)于B-A-5/7小波，當(dāng)a=7/4=1.75時(shí)，即可得到本文構(gòu)造的新B-A小波，它具有最佳的編碼增益（9.355 dB，比J-7/5高0.088 dB），記為B-A-5/7-L。值得注意的是，當(dāng)a=2時(shí)得到的B-A-5/7小波恰恰就是JPEG 2000標(biāo)準(zhǔn)中采用的5/3小波，它的編碼增益為9.092 dB。

表1給出了B-A-5/7-L、J-7/5和B-A-7/5-O三個(gè)小波的低通濾波器系數(shù)，它們?nèi)际怯欣頂?shù)。圖2(a)~(d)分別給出了B-A-5/7-L的尺度、小波函數(shù)φ(x)和ψ(x)、對(duì)偶尺度、小波函數(shù)(x)和(x)的曲線圖。

表1三個(gè)B-A小波的低通濾波器系數(shù)（已規(guī)范化）

小波a

hkk

0±1±20±1±2±3

B-A-5/7-L7/411/161/4-3/3215/28115/448-1/56-3/448

J-7/511/1021/401/4-1/8031/44449/1 760-9/88-9/1 760

B-A-7/5-O7/53/51/4-1/2017/2873/280-3/56-3/280

4Burt-Adelson小波變換的提升實(shí)現(xiàn)

提升是實(shí)現(xiàn)DWT的一種有效方法。相對(duì)于DWT的卷積濾波，提升具有計(jì)算步驟少、復(fù)雜度低的優(yōu)點(diǎn)。提升實(shí)現(xiàn)對(duì)應(yīng)著把小波的多相矩陣分解為基本矩陣。Daubechies等人[11]給出了一種利用Euclidean算法求得基本矩陣的通用算法。根據(jù)此算法，B-A-5/7小波的多相矩陣可分解為

P(z)=1α(1+z-1)0 11 0β(1+z)1

1γ(1+z-1)0 1K 001/K(13)

式中各個(gè)提升系數(shù)分別為

α=(1-a)/2，β=1/2a，γ=(a2-2a)/4，K=a/2

而對(duì)于B-A-7/5小波，其多相矩陣可分解為

P(z)=1 0α(1+z)11β(1+z-1)0 11 0γ(1+z)1K001/K(14)

這時(shí)，式中各個(gè)系數(shù)分別為

α=(a-1)/2，β=-1/2a，γ=(2a-a2)/4，K=1/a

假定用x=xn和y=yn，n∈

瘙 綄 分別表示輸入和輸出信號(hào)，根據(jù)式(13)，得到B-A-5/7小波前向DWT的提升步驟為

式中：i0表示輸入信號(hào)的初始采樣下標(biāo)；i1表示輸入信號(hào)的末尾采樣下標(biāo)。反向DWT的提升步驟只是上述步驟的逆過(guò)程，不再給出。表2給出了三個(gè)B-A小波對(duì)應(yīng)DWT的提升系數(shù)，它們同樣全都是有理數(shù)。

表2三個(gè)B-A小波對(duì)應(yīng)DWT的提升系數(shù)

5性能分析

CDF-9/7小波是圖像變換編碼領(lǐng)域中應(yīng)用最為廣泛的小波之一，本文用它作為比較參照小波來(lái)分析B-A-5/7-L小波的圖像編碼性能。同時(shí)把B-A-5/7-L小波與J-7/5和B-A-7/5-O小波作比較，以驗(yàn)證新小波是否比兩者有著較大的性能改善。

5.1計(jì)算復(fù)雜性比較

首先分析四個(gè)小波變換的計(jì)算復(fù)雜性，比較單位是采用提升計(jì)算一對(duì)相鄰的圖像像素（x2n，x2n+1）所需要的加操作和乘操作的數(shù)量。表3給出了四個(gè)小波變換的計(jì)算因?yàn)榧硬僮鞯臅r(shí)間開銷與乘操作相比微不足道，所以四個(gè)小波變換的計(jì)算復(fù)雜性主要取決于乘操作。單純看表3的數(shù)據(jù)，三個(gè)B-A小波的計(jì)算復(fù)雜性相同，需花費(fèi)五次乘操作，而CDF-9/7需花費(fèi)六次乘操作；B-A小波的計(jì)算效率比CDF-9/7可提高20%。事實(shí)上B-A-5/7-L的計(jì)算復(fù)雜性可進(jìn)一步降低，其提升系數(shù)除β外（β也是簡(jiǎn)單的有理數(shù)，遠(yuǎn)非CDF-9/7復(fù)雜的無(wú)理提升系數(shù)可比），其余都是二進(jìn)制分?jǐn)?shù)，乘操作可用簡(jiǎn)單的移位—加操作實(shí)現(xiàn)[12，13]。因此B-A-5/7-L的計(jì)算效率要高于J-7/5和B-A-7/5-O，較之CDF-9/7，計(jì)算效率的提高肯定超過(guò)20%。

5.2壓縮性能比較

為了得到公平的比較結(jié)果，除了小波類型不同以外，其他測(cè)試條件完全相同：對(duì)稱擴(kuò)展圖像邊界，然后作五級(jí)提升小波變換，得到六層金字塔結(jié)構(gòu)的子帶系數(shù)；量化后采用嵌入式編碼方法SPIHT（set partitioning in hierarchical trees）[14]編碼量化系數(shù)。限于篇幅 這里僅以256級(jí)（8bpp）灰度圖像Lena和Barbara為代表，給出了它們的測(cè)試結(jié)果。選用它們的原因主要是兩者分別是平滑和紋理圖像的典型代表。表4給出了B-A-5/7-L小波在五種典型壓縮比下重構(gòu)圖像的峰值信噪比（PSNR）值（單位：dB）。對(duì)于其他三個(gè)小波，表中給出的是它們相對(duì)于B-A-5/7-L小波的PSNR差值。

從表中可以看出 B-A-7/5-O的壓縮性能最低而沒有討論的必要；CDF-9/7小波的壓縮性能最優(yōu)，但這是以高計(jì)算復(fù)雜性為代價(jià)的；B-A-5/7-L的壓縮性能次之，對(duì)于Lena重構(gòu)圖像，其PSNR值比CDF-9/7小波低0.3~0.5 dB，而對(duì)于Barbara圖像，當(dāng)壓縮比很低時(shí)，兩者的PSNR差值達(dá)到了0.921 dB，不過(guò)這沒有太大的意義。因?yàn)榫幋a的目的是為了對(duì)圖像進(jìn)行高效率的壓縮，實(shí)際應(yīng)用中一般不取如此低的壓縮比；隨著壓縮比的增大，兩者的PSNR差值逐漸縮小，大致在0.08~0.20 dB。J-7/5的計(jì)算效率可比CDF-9/7提高20%，JPEG 2000標(biāo)準(zhǔn)Ⅱ推薦它用在編碼速度遠(yuǎn)比編碼質(zhì)量重要的場(chǎng)合，但對(duì)于兩幀位圖，B-A-5/7-L都取得了比它好的編碼效果，性能改善在0.02~0.11 dB，而且更有意義的是B-A-5/7-L的計(jì)算效率要高于J-7/5。因此，對(duì)于實(shí)現(xiàn)圖像的高質(zhì)量快速壓縮，B-A-5/7-L是一個(gè)更好的選擇。

6結(jié)束語(yǔ)

針對(duì)CDF-9/7小波的系數(shù)是無(wú)理數(shù)、不利于工程實(shí)際應(yīng)用的缺點(diǎn)，本文給出了一種構(gòu)造Burt-Adelson（B-A）雙正交小波類的簡(jiǎn)便方法，導(dǎo)出了對(duì)應(yīng)小波濾波器組的參數(shù)表達(dá)式。通過(guò)調(diào)整該參數(shù)，構(gòu)造了具有最佳編碼增益的有理系數(shù)B-A小波B-A-5/7-L。實(shí)驗(yàn)表明，其圖像壓縮性能略低于CDF-9/7小波，但優(yōu)于JPEG 2000標(biāo)準(zhǔn)Ⅱ推薦的7/5小波；而且其提升小波變換的計(jì)算效率比CDF-9/7提高20%以上，也優(yōu)于7/5小波。因此B-A-5/7-L可以作為JPEG 2000標(biāo)準(zhǔn)的新候選小波。

參考文獻(xiàn)：

[1]ISO/IEC 15444-1 Information technology-JPEG 2000 image coding system: core coding system[S].2nd ed. Geneva: ISO/IEC 2004.

[2]ISO/IEC 15444-2 Information technology-JPEG 2000 image coding system: extensions[S]. Geneva: ISO/IEC 2004.

[3]COHEN A DAUBECHIES I FEAUVEAU J C. Biorthogonal bases of compactly supported wavelets[J].Communication on Pure Applied Mathematics 1992，45(5):485-560.

[4]TAY D B H. Rationalizing the coefficients of popular biorthogonal wavelet filters[J].IEEE Trans on Circuits System Video Technology 2000，10(6):998-1005.

[5]劉在德，鄭南寧，宋永紅，等.高性能、有理系數(shù)9/7雙正交小波濾波器組的設(shè)計(jì)[J].西安交通大學(xué)學(xué)報(bào)，2005，39(8):848-851.

[6]LIU Zai-de ZHENG Nan-ning. Parametrization construction of biorthogonal wavelet filter banks for image coding [J].Signal，-Image and Video Processing 2007，1(1): 63-76.

[7]LIU Zai-de ZHENG Nan-ning LIU Yue-hu et al. Optimization design of biorthogonal wavelets for embedded image coding [J]. IEICE Trans on Information and System，2007，E90-D(2):569-578.

[8]劉在德 鄭南寧 劉躍虎，等. 17/11雙正交小波的優(yōu)化設(shè)計(jì)及其對(duì)圖像壓縮性能的分析[J]. 子與信息學(xué)報(bào) 2007，29(6):1403-1407.

[9]BURT P J ADELSON E H. The Laplacian pyramid as a compact-image code[J].IEEE Trans on Communication 1983，31(4):532-540.

[10]KATTO J YASUDA Y. Performance evaluation of subband coding and optimization[C]//Proc of SPIE Vol 1605 Symposium on Visual Comm and Image Proc. Boston:[s.n.] 1991:95-106.

[11]DAUBECHIES I SWELDENS W. Factoring wavelet transforms into lifting steps[J]. J Fourier Analysis and Applications，1998，4(3):247-269.

[12]劉在德，鄭南寧，劉躍虎，等.JPEG 2000中9/7離散小波變換二進(jìn)制系數(shù)實(shí)現(xiàn)[J].西安交通大學(xué)學(xué)報(bào)，2003，37(12):1211-1215.

[13]LIU Zai-de ZHENG Nan-ning. Parametrization construction of integer wavelet transforms for embedded image coding[J].International Journal of Computer Mathematics，2007，84(9):1339-1352.

[14]SAID A PEARLMAN W A. A new fast efficient image codec based on set partitioning in hierarchical trees[J].IEEE Trans on Circuits System Video Technology 1996，6(3):243-250.