新Ｂｕｒｔ－Ａｄｅｌｓｏｎ雙正交小波的優化設計

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

修回日期：2007-12-25

基金項目：江蘇省高校自然科學基礎研究資助項目（07KJD520005）；常熟理工學院新引進教師科研啟動基金資助項目（ky11520）；常熟理工學院青年教師科研啟動基金資助項目（ky200657）



作者簡介：劉在德(1977-)，男，山東萊蕪人，博士，主要研究方向為圖像處理、小波分析及其應用(lzd.122604@gmail.com)；常晉義(1955-)，男，山西忻州人，教授，主要研究方向為空間決策支持系統、信息系統安全；聶盼紅(1977-)，女，山西翼城人，講師，碩士，主要研究方向為圖像處理.

(常熟理工學院 計算機科學與工程學院 江蘇 常熟 215500)

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

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

中圖分類號：TN911.73

文獻標志碼：A

文章編號：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

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

1預備知識

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

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

對應的小波低通濾波器分別定義為

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

那么雙正交條件（濾波器精確重構條件）可簡化為

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

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

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

2Burt-Adelson小波的參數化構造

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

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

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

其中：a為自由參數；A和B為待求的未知系數。因為余弦函數是偶函數，滿足式(7)(8)的濾波器自然滿足對稱性和濾波器低、高通條件

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

把濾波器式(7)(8)代入精確重構條件式(6)，因為有cos(ξ+π)=-cos ξ，所以有

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

展開式(9)，根據左、右兩邊對應項系數分別相等，可得到

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

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

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ξ。根據式（5），就可得到對應小波高通濾波器G(ξ)和(ξ)的參數表達式，這里不再給出。

3新Burt-Adelson小波的優化選取

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

3.1編碼增益

本文采用Katto等人[10]提供的編碼增益公式來衡量B-A小波的壓縮性能。對于雙正交小波，這是一個很有效的評估準則。給定一個N子帶小波分解系統，假定第n級子帶的等效分解和合成濾波器的系數分別用n(i)和hn(j)，n=1，…，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是等效的采樣率（對于普通的Mallat金字塔結構分解，αn=1/N)。注意：在本文中，編碼增益是自變量為自由參數a的一個函數。

3.2優化的B-A小波

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

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

表1給出了B-A-5/7-L、J-7/5和B-A-7/5-O三個小波的低通濾波器系數，它們全都是有理數。圖2(a)~(d)分別給出了B-A-5/7-L的尺度、小波函數φ(x)和ψ(x)、對偶尺度、小波函數(x)和(x)的曲線圖。

表1三個B-A小波的低通濾波器系數（已規范化）

小波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小波變換的提升實現

提升是實現DWT的一種有效方法。相對于DWT的卷積濾波，提升具有計算步驟少、復雜度低的優點。提升實現對應著把小波的多相矩陣分解為基本矩陣。Daubechies等人[11]給出了一種利用Euclidean算法求得基本矩陣的通用算法。根據此算法，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)

式中各個提升系數分別為

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

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

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

這時，式中各個系數分別為

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

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

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

式中：i0表示輸入信號的初始采樣下標；i1表示輸入信號的末尾采樣下標。反向DWT的提升步驟只是上述步驟的逆過程，不再給出。表2給出了三個B-A小波對應DWT的提升系數，它們同樣全都是有理數。

表2三個B-A小波對應DWT的提升系數

5性能分析

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

5.1計算復雜性比較

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

5.2壓縮性能比較

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

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

6結束語

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

參考文獻：

[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]劉在德，鄭南寧，宋永紅，等.高性能、有理系數9/7雙正交小波濾波器組的設計[J].西安交通大學學報，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雙正交小波的優化設計及其對圖像壓縮性能的分析[J]. 子與信息學報 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].西安交通大學學報，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.