基于Ｇｒ ｂｎｅｒ基的對(duì)稱正交多帶多維濾波器組設(shè)計(jì)

（1.北京理工大學(xué) 信息科學(xué)技術(shù)學(xué)院 自動(dòng)控制系 北京 100081； 2.黃河水利職業(yè)技術(shù)學(xué)院 河南 開封 475004）

摘 要：通過引入計(jì)算代數(shù)中Grbner基技術(shù)和合沖模算法，提出了一種多帶多維濾波器組的多相元矩陣的對(duì)稱正交化設(shè)計(jì)方法，給出了一個(gè)4帶二維對(duì)稱正交濾波器組的設(shè)計(jì)算例；另外，給出了由多維濾波器組構(gòu)造多維小波的多維尺度方程表示形式，并將設(shè)計(jì)得到的4帶二維濾波器組構(gòu)造出一種4帶二維小波。

關(guān)鍵詞：Grbner基； 合沖模； 多帶多維濾波器組； 多維小波

中圖分類號(hào)：TN911文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)05-1713-03

Design symmetric orthogonal multiband multidimensional

filter bank using Grbner basis

LI Xiaoxiong1，2 WU Qinghe1

(1.Dept. of Automatic Control School of Information Science Technology Beijing Institute of Technology Beijing 100081 China; 2.Yellow River Conservancy Technical Institute Kaifeng Henan 475004 China)

Abstract:This paper studied the problem of design multiband multidimensioal filter banks. Using the concept of Grbner basis and the algorithms of syzygy module in computing algebra presented the symmetry orthogonality approach for the polyphase matrix of multiband multidimensional filter banks. Moreover achieved the expression of multiscale function which was used to construct multiwavelets by multidimensional filter banks. Constructed the 4band twodimensional wavelets using 4band twodimensional filter banks.

Key words：Grbner basis; syzygy module; multiband multidimensional filter banks; multiwavelets

近年來，隨著空間圖像、醫(yī)學(xué)圖像、高清晰度電視等多維信號(hào)的應(yīng)用需求日益廣泛和迫切，人們期待多維信號(hào)處理技術(shù)快速發(fā)展和進(jìn)步，多維濾波器組作為多維子帶編碼的關(guān)鍵技術(shù)必須首先發(fā)展。然而，多維濾波器組的設(shè)計(jì)是一個(gè)非常困難的問題，主要是因?yàn)槎S及以上的多維濾波器組待求的參數(shù)太多，一般難以確定。盡管如此，國外學(xué)者還是提出了幾種可行的設(shè)計(jì)方法：用McClellan變換法設(shè)計(jì)^[1]，但是該方法僅限于2通道二維濾波器組的設(shè)計(jì)；用直接優(yōu)化參數(shù)的方法設(shè)計(jì)^[2]，但是該方法會(huì)使目標(biāo)函數(shù)落入局部極小值，難以找到最優(yōu)值；用Caylley變換法進(jìn)行設(shè)計(jì)^[3]，但是該方法設(shè)計(jì)得到的濾波器組只具有正交性，不具有對(duì)稱性；采用格形結(jié)構(gòu)方法設(shè)計(jì)^[4]，但是其設(shè)計(jì)的濾波器組不含完全解。而且在現(xiàn)有的多維濾波器組的設(shè)計(jì)方法中，大多只能設(shè)計(jì)兩個(gè)通道的多維濾波器組，到目前為止，對(duì)于多帶多維濾波器組的設(shè)計(jì)依然沒有行之有效的方法。鑒于此，筆者利用計(jì)算代數(shù)中的Grbner基以及合沖模的概念與算法^[5]，提出了一種設(shè)計(jì)對(duì)稱正交多帶多維濾波器組的方法，該方法設(shè)計(jì)思路清晰明了，不但能設(shè)計(jì)具體的多帶多維濾波器組，而且具有一般性和通用性，設(shè)計(jì)結(jié)果中含有完全（全部）解。

1 多維濾波器組的基本原理

1.1 定義

在n維多變量系統(tǒng)中，采樣矩陣M的大小為n×n，頻帶寬m=｜det M｜，M的單位平行六面體μp(M)由Mx，x∈(0，1)T上的所有點(diǎn)集構(gòu)成，在μp(M)和μp(MT)上分別用ki和li表示采樣格的平移向量。

定義1^[6] 設(shè)向量P=[p1，p2，…，pn]T，矩陣M=[m1，m2，…1.2 濾波器的指數(shù)和類型

定義2^[6] 如果多項(xiàng)式矩陣A(z)滿足A(z)=±ZnA(z-1)，則稱之為指數(shù)為n的自對(duì)稱矩陣，用ind(A(z))=n表示。

定義3^[6] 如果m帶濾波器組的第k個(gè)子帶濾波器Hk(z)的指數(shù)nk能表示為nk=Mmk+ki的形式，那么稱其為ki型的。設(shè)H表示一個(gè)多相元矩陣，它的Hk，i元可由式（1）獲得

Hk(z)=∑m-1i=0Z kiHk，i(ZM)(1)

1.3 完全重構(gòu)條件和線性相位條件

結(jié)論1^[6] 對(duì)于FIR濾波器組，綜合多相元矩陣G(Z)和分析多相元矩陣H(Z)一定能構(gòu)成一對(duì)完全重構(gòu)對(duì)，當(dāng)且僅當(dāng)det(H(Z))是單項(xiàng)式，即H(z)是單模陣。

結(jié)論2^[6] 多相元矩陣的線性相移條件是

H(ZM)=D#8226;Ωnk#8226;H(Z-M)#8226;W(Z-1)#8226;Δl#8226;W(Z-1)

式中：D=diag[±1，…，±1]，正（負(fù)）號(hào)取決于濾波器組的對(duì)稱（反對(duì)稱）性。

Ωnk=diag[zn0，zn1，…，znm]；W(Z)=diag[1，zk1，…，zkm-1]

Δl=Wd#8226;L#8226;Wd/m，[Wd]ij=e-j2πlTjM-1ki

L=diag[1，e-j2πlT1 M-1kl，…，e-j2πlTm-1M-1kil]

結(jié)論3^[6] 設(shè)det H(Z)=ZP滿足完全重構(gòu)條件(PR)，如果子帶濾波器滿足LP和PR條件，那么下面等式一定成立：

∑m-1i=0ni=2(Mp+∑m-1i=0ki)(2)

結(jié)論4 如果m帶PR濾波器組中的分析濾波器組滿足線性相位條件LP，那么對(duì)稱和反對(duì)稱的濾波器可由下列關(guān)系確定：

a)m為奇數(shù)時(shí)，對(duì)稱濾波器數(shù)比反對(duì)稱濾波器多1個(gè)；

b)m為偶數(shù)時(shí)，對(duì)稱濾波器數(shù)比反對(duì)稱濾波器多0、2或4個(gè)。

2 設(shè)計(jì)多帶多維濾波器組

人類視覺系統(tǒng)對(duì)相位畸變很敏感，而應(yīng)用線性相位濾波器對(duì)圖像進(jìn)行處理時(shí)才能避免相位畸變，具有線性相位的濾波器是對(duì)稱的。除此以外使用對(duì)稱濾波器還可使人們對(duì)有限長的信號(hào)進(jìn)行周期延拓，因此線性相位是濾波器需要具有的重要特征之一。同時(shí)，正交濾波器組由于具有下面兩個(gè)良好的性質(zhì)而備受關(guān)注：a)正交性意味著能保持能量；b)在一定條件下，正交濾波器可用于構(gòu)造正交小波基^[1]。此外，兩帶濾波器組雖然具有低頻能量集中的良好優(yōu)點(diǎn)，但是對(duì)于中—高頻帶含大量信息的信號(hào)而言分析效果不好。由此可見，人們期望所設(shè)計(jì)的濾波器組不但要具有對(duì)稱性，而且也要具有正交性，設(shè)計(jì)具有一定消失矩的對(duì)稱正交多帶多維濾波器組是設(shè)計(jì)的最高境界。

設(shè)計(jì)具有N正則階的對(duì)稱正交多帶多維濾波器組的多相位矩陣的算法可以描述如下：

a)構(gòu)造多相位矩陣H(z1，…，zn)的第一行，即H0(z1，…，zn)的m個(gè)相元H00(z1，…，zn)，…，H0(m-1)(z1，…，zn)。構(gòu)造濾波器組的多相位矩陣H(z)的第一行非常重要，是設(shè)計(jì)可以順利進(jìn)行的前提。問題的關(guān)鍵在于如何假設(shè)H0(z1，…，zn)的各個(gè)相元的表示形式，對(duì)此不同維數(shù)的濾波器組可以選擇不同的設(shè)計(jì)方法。對(duì)于二維濾波器可以采用下列的方法，而對(duì)于三維以上的濾波器可以采用McClellan變換法設(shè)計(jì)。

b)利用計(jì)算代數(shù)中的合沖模算法（定理3）計(jì)算F=(H0，0(z1，…，zn)，…，H0，m-1(z1，…，zn))的合沖模syz(F)=〈r1(z1，zn)，…，rm(z1，zn)〉。

c)對(duì)合沖模syz(F)=〈r1(z1，zn)，…，rm(z1，zn)〉實(shí)行對(duì)稱正交化，即根據(jù)所求得的合沖模的具體形式假設(shè)Hi(z1，…，zn)，i=1，…，m-1的多相元Hi 0(z1，…，z2)，…，Hi(m-1)(z1，…，z2)的表達(dá)式形式；然后再根據(jù)Hi(z1，…，zn)，i=1，…，m-1的對(duì)稱性和正交性建立一個(gè)以其系數(shù)為未知數(shù)的高階多元多項(xiàng)式非線性方程組；最后調(diào)用Maple軟件中的Grbner基算法獲得其Grbner基。它是一種三角型的非線性方程組，已完全實(shí)現(xiàn)了未知數(shù)的解耦，通過遞推的方法可依次求解出Hi0(z1，…，z2)，…，Hi(m-1)(z1，…，z2)的全部參數(shù)。

d)驗(yàn)證多維濾波器組是否滿足正交性條件H(z1，…，zn)#8226;HT(z-11，…，z-1n)=Im和對(duì)稱性條件Hi(z1，…，zn)=±zp11…zpnnHi(z-11，…，z-1n)；i=0，…，m-1。

為簡單起見，下面以具有2正則階的4帶二維濾波器組的構(gòu)造為例說明上述算法的有效性，更一般的具有N正則階的對(duì)稱正交m帶n維濾波器組的設(shè)計(jì)步驟與其基本相同。

1)構(gòu)造濾波器組的多相元矩陣H(z)的第一行

設(shè)采樣矩陣M=2 00 2，那么平移向量分別為k0=00，k1=10，k2=01，k3=11。由于m=｜det M｜=4是偶數(shù)，那么對(duì)稱和反對(duì)稱的濾波器數(shù)相等。設(shè)第一個(gè)濾波器H0(z)為

H0(z1，z2)=[1 z1 z21 z32]×a00 a01 a02 a03a10 a11 a12 a13a20 a21 a22 a23a30 a31 a32 a33×1z2z22z32

根據(jù)多相元矩陣表示式（1）有

H0(z1，z2)=H00(z21，z22)+z1H01(z21，z22)+z2H02(z21，z22)+

z1z2H03(z21，z22) 

令A(yù)(z1，z2)=[H0(z1，z2)+H0(z1，-z2)]/2

B(z1，z2)=[H0(z1，z2)-H0(z1，-z2)]/2

可推出：

H00(zM)=[A(z1，z2)+A(z1，-z2)]/2

H01(zM)=[A(z1，z2)+A(-z1，z2)]/(2z1)

H02(zM)=[B(z1，z2)+B(-z1，z2)]/(2z2)

H03(zM)=[B(z1，z2)-B(-z1，z2)]/(2z1z2)

用z1代替z1、z2代替z2代入上式可分別得到

H00(z1，z2)，H01(z1，z2)，H02(z1，z2)，H03(z1，z2)的表達(dá)式。

(1)利用對(duì)稱性條件H0(z1，z2)=z31z32H0(z-11，z-12)有

a30=a03 a31=a02 a32=a01 a33=a00

a20=a13 a21=a12 a22=a11 a23=a10

(2)利用正交性條件有

H00(z1，z2)H00(z-11，z-12)+H01(z1，z2)H01(z-11，z-12)+

H02(z1，z2)H02(z-11，z-12)+H03(z1，z2)H03(z-11，z-12)=1

(3)利用H0(z1，z2)在(-1，-1)有L階消失矩條件

nH0(z1，z2)/(zi1zn-i2)｜(-1，-1)=0；n=0，1，…，L-1；i=0，1，…，n

根據(jù)上述三個(gè)條件可以建立一個(gè)以H0(z1，z2)的參數(shù)為未知數(shù)高階多元多項(xiàng)式非線性方程組，調(diào)用Maple軟件中的Grbner基算法子程序可獲得其Grbner基。它是一種三角型方程組，采用遞推的方法可以很快求出H0(z1，z2)的參數(shù)分別為

a12=a11=1/4，a13=a10=a00=a01=a02=a03=-1/4

那么，H0（z1，z2）的相元分別為

H00(z1，z2)=-1/4-z1/4-z2/4+z1z2/4

H01(z1，z2)=-1/4-z1/4+z2/4-z1z2/4

H02(z1，z2)=-1/4+z1/4-z2/4-z1z2/4

H03(z1，z2)=1/4-z1/4-z2/4-z1z2/4

2)根據(jù)定理3可計(jì)算出F=(H0，0(z)，…，H0，m-1(z))的合沖模為

r1=[3/4-z1/4-z2/4+z1z2/4，-1/4-z1/4-z2/4+z1z2/4，

-1/4-z1/4-z2/4+z1z2/4，1/4+z1/4+z2/4-z1z2/4]

r2=[-1/4-z1/4+z2/4-z1z2/4，3/4-z1/4+z2/4-z1z2/4，

-1/4-z1/4+z2/4-z1z2/4，1/4+z1/4-z2/4+z1z2/4]

r3=[-1/4+z1/4-z2/4-z1z2/4，-1/4+z1/4-z2/4-z1z2/4，

3/4+z1/4-z2/4-z1z2/4，1/4-z1/4+z2/4+z1z2/4]

r4=[1/4-z1/4-z2/4-z1z2/4，1/4-z1/4-z2/4-z1z2/4，

1/4-z1/4-z2/4-z1z2/4，3/4+z1/4+z2/4+z1z2/4]

3)對(duì)合沖模進(jìn)行對(duì)稱正交化

對(duì)合沖模進(jìn)行對(duì)稱正交化的目的是設(shè)計(jì)濾波器組的多相元矩陣的其他幾行，而多相元矩陣的各個(gè)相元的表達(dá)式形式的確定必須以合沖模的表示形式為依據(jù)，這就是計(jì)算合沖模的價(jià)值所在，是整個(gè)設(shè)計(jì)過程中關(guān)鍵的一步。

（1）構(gòu)造濾波器組的多相元矩陣H(z)的第二行

根據(jù)合沖模的形式和H1(z1，z2)的對(duì)稱性，可以假設(shè)H1(z1，z2)的各個(gè)相元分別為

H10(z1，z2)=b00+b13z1+b02z2+b11z1z2

H11(z1，z2)=b10+b03z1+b12z2+b01z1z2

H12(z1，z2)=b01+b12z1+b03z2+b10z1z2

H13(z1，z2)=b11+b02z1+b13z2+b00z1z2

根據(jù)正交性有

H10(z1，z2)H10(z-11，z-12)+H11(z1，z2)H11(z-11，z-12)+

H12(z1，z2)H12(z-11，z-12)+H13(z1，z2)H13(z-11，z-12)=1

H00(z1，z2)H10(z-11，z-12)+H01(z1，z2)H11(z-11，z-12)+

H02(z1，z2)H12(z-11，z-12)+H03(z1，z2)H13(z-11，z-12)=0

抽取上述兩個(gè)方程的各項(xiàng)系數(shù)，可以得到以H1(z1，z2)的系數(shù)為未知數(shù)的一組高階多元多項(xiàng)式非線性方程組；調(diào)用Maple軟件中的Grbner基算法子程序，可獲得其Grbner基，它是一種三角型方程組，采用遞推的方法可以很快求出H0(z1，z2)的參數(shù)分別為

b00=b01=b10=b12=-1/4 b02=b03=b11=b13=1/4

因此有

H10(z1，z2)=-1/4+z1/4+z2/4+z1z2/4

H11(z1，z2)=-1/4+z1/4-z2/4-z1z2/4

H12(z1，z2)=-1/4-z1/4+z2/4-z1z2/4

H13(z1，z2)=1/4+z1/4+z2/4-z1z2/4

（2）同理可構(gòu)造得到矩陣H(z)的第三、四行的各個(gè)相元分別為

H20(z1，z2)=-7/8-z1/8+z2/8-7z1z2/8

H21(z1，z2)=-7/8-z1/8-z2/8+7z1z2/8

H22(z1，z2)=-7/8+z1/8+z2/8+7z1z2/8

H23(z1，z2)=7/8-z1/8+z2/8+7z1z2/8

H30(z1，z2)=-1/8+7z1/8-7z2/8-z1z2/8

H31(z1，z2)=-1/8+7z1/8+7z2/8+z1z2/8

H32(z1，z2)=-1/8-7z1/8-7z2/8+z1z2/8

H33(z1，z2)=1/8+7z1/8-7z2/8+z1z2/8

4)驗(yàn)證正交性和對(duì)稱性

驗(yàn)證可知濾波器滿足H(z1，z2)×HT(z-11，z-12)=I4和Hi(z1，z2)=±z31z32Hi(z-11，z-12)；i=0，1，2，3的條件，故所設(shè)計(jì)的濾波器組既滿足正交性，也滿足對(duì)稱性，還具有一定消失矩，是具有一定消失矩的正交對(duì)稱多帶多維濾波器組，是一種非常理想的濾波器組。

3 構(gòu)造多維小波

小波分析是信號(hào)處理和圖像處理非常重要的數(shù)學(xué)工具，其發(fā)展前景廣闊。在用小波對(duì)圖像進(jìn)行處理時(shí)，必須對(duì)圖像進(jìn)行分解和重構(gòu)，所采用的小波大多是張量積小波。它由一維小波通過張量積生成，但張量積小波通常不具有對(duì)稱性，而利用不對(duì)稱的小波對(duì)圖像進(jìn)行處理會(huì)在圖像重構(gòu)時(shí)產(chǎn)生相位失真，相位失真必然產(chǎn)生圖像邊緣失真。因此構(gòu)造一個(gè)具有對(duì)稱性和正交性的純多維小波是多維信號(hào)處理和空間圖像、醫(yī)學(xué)圖像處理中的一個(gè)關(guān)鍵問題。

由小波分析的多分辨分析可知，利用Mallat算法對(duì)圖像進(jìn)行分解和重構(gòu)時(shí)不涉及到小波的具體形式，只需要知道低通濾波器和相應(yīng)的高通濾波器即可。這是因?yàn)橛傻屯V波器采用迭代的方法就可構(gòu)造出小波分析中的尺度函數(shù)，而由高通濾波器可構(gòu)造出對(duì)應(yīng)的小波函數(shù)，這是Daubechies小波構(gòu)造的主要思想。與之雷同，多維小波的構(gòu)造依賴于多維濾波器組，只要多維濾波器組已經(jīng)有效設(shè)計(jì)出來了，那么進(jìn)一步采用多維迭代的方法就能由多維低通濾波器組構(gòu)造多維尺度函數(shù)，由多維高通濾波器組構(gòu)造出對(duì)應(yīng)的多維小波函數(shù)。由多維濾波器組構(gòu)造多維小波的尺度方程為

(x1，…，xn)=∑i1，…，in(2x1-i1，…，2xn-in)H0(i1，…，in)

ψj(x1，…，xn)=∑i1，…，in(2x1-i1，…，2xn-in)Hj(i1，…，in)；j=1，…，m-1



利用前面所設(shè)計(jì)得到的濾波器組就可以構(gòu)造一個(gè)4帶二維的對(duì)稱正交二維小波。采用迭代方法可繪制出其尺度函數(shù)和小波函數(shù)的波形圖如圖1和2所示。

4 結(jié)束語

多帶多維濾波器組是多維信號(hào)處理的關(guān)鍵技術(shù)和困難問題，尤其是正交對(duì)稱多帶多維濾波器組的設(shè)計(jì)目前還是一個(gè)未解的難題。本文應(yīng)用計(jì)算代數(shù)中的Grbner基技術(shù)構(gòu)造了多帶多維濾波器組的多相元矩陣的第一行，并利用合沖模概念和算法找到了其他各行的具體表示形式，在此基礎(chǔ)上應(yīng)用濾波器組的正交性和對(duì)稱性依次建立了以濾波器的系數(shù)為未知數(shù)的高階多元多項(xiàng)式非線性方程組。調(diào)用Maple軟件中的Grbner基算法獲得其Grbner基，采用遞推的方法依次求解出濾波器組的全部參數(shù)，從而設(shè)計(jì)了一種圖像處理中所需要的正交對(duì)稱的多帶多維濾波器組，給出了一個(gè)具體的4帶二維濾波器組的設(shè)計(jì)算例。在此基礎(chǔ)上闡述了多維濾波器組與多維小波之間的密切關(guān)系，給出了采用多維濾波器組構(gòu)造多維小波的尺度方程的具體表示形式，并應(yīng)用二維迭代方法繪制出4帶二維濾波器組所構(gòu)造的二維尺度函數(shù)和二維小波函數(shù)的波形圖。

參考文獻(xiàn)：

［1］SHAPIRO J M. Adaptive multidimensional perfect reconstruction filter banks using McClellan transformations[C]//Proc ofIEEE International Symposium on Circuits and Systems. 1992:939-942.

[2]ZHOU Jianping DO M N KOVACEVIC J. Multidimensional orthogonal filter bank characterization and design using the cayley transform[J]. IEEE Trans on Image Processing 2005，14(6):760-769.

[3]NGUYEN T ORAINTARA T. Multidimensional filter banks design by direct optimization[C]//Proc ofIEEE International Symposium on Circuits and Systems. 2005:1090-1093.

[4]MURAMATSU S YAMADA A KIYA H A. Design method of multidimensional linearphase paraunitary filter banks with a lattice structure[C]//Proc of IEEE Conference on Speech and Image Technologies for Computing and Telecommunications. 1997:69-72.

[5]BUCHBERGER B. Grbner bases and systems theory[J]. Multidimensional Systems and Signal Processing 2001，12(3/4): 223-251.

[6]CHAROENLARPNOPPARUT C. Grbner basis in multidimensional system and signal processing[D]. University Park PA: the Pennsylvania State University 2000.

[7]BASU S. On multidimensional linear phase perfect reconstruction filter bank[C]//Proc of IEEE International Conference on Circuits and Systems. 1994:145-148.

[8]ADAMS W W LOUSTAUNAU P. An introduction to Grbner bases: volume 3 of graduate studies in mathematics[M].[S.l.]:American Mathematic Society 1994.