ShannonGabor小波的快速計算

1、Shannon-Gabor小波的快速計算及其在圖像處理中的應(yīng)用1 插值小波基函數(shù)插值小波基函數(shù)應(yīng)是具有插值特性的緊支撐或指數(shù)衰減函數(shù)，如插值樣條小波、Daubechies小波的自相關(guān)函數(shù)等。但插值樣條小波不具備正交性，而Daubechies小波沒有解析表達式，Haar小波同時具有緊支撐性和正交性，但不連續(xù)，F(xiàn)aber-Schauder小波具有插值特性和緊支撐性，但不光滑，而Shannon小波不具備緊支撐性，因此選擇具有近似緊支撐性和插值特性的Shannon-Gabor小波函數(shù)。Shannon-Gabor尺度函數(shù)定義如下：=sin(x/)x/exp(-x222)(1)其中是離散點間距，=r（r是

2、任意參數(shù)）是窗口大小參數(shù)。為取Shannon-Gabor尺度函數(shù)作為基函數(shù)，按多尺度分析理論對函數(shù)f(x)在定義域a,b內(nèi)進行均勻離散，取離散點個數(shù)為2j+1,(jZ)，則變量x的離散點定義為：xi=a+b-a2j.i則基函數(shù)為jix=sin2jb-a(x-xi)2jb-a(x-xi)exp-22j2r2x-xib-a2(2)令j1=b-a2j1，=rj1,則若取具有插值特性的Shannon-Gabor小波作為試函數(shù)，即Wx=Wj1x-xk=sin(x-xkj1)j1(x-xkj1)j1exp-12x-xkj1rj12（3）將x=xkj1 、x=xnj2代入式(3)，可得出Wxnj2-xkj1

3、=sin(xnj2-xkj1)j1(xnj2-xkj1)j1exp-12xnj2-xkj1rj12(4)其中，j1=b-a2j1 ，j2=b-a2j2 ，即 xkj1=b+k. j1 ，xnj2=b+n. j2=b+n.2j1-j2.j1公式（4）可被簡化為Wxnj2-xkj1=sin(n.2j1-j2-k)n.2j1-j2-kexp-12n.2j1-j2-kr2(5)下面分別對Shannon-Gabor小波函數(shù)求一階、二階導(dǎo)數(shù)： Shannon-Gabor小波函數(shù)的一階導(dǎo)數(shù)Wx=exp-12r2x-xkj1j12cosx-xkj1j1x-xkj1-j1x-xkj12sinx-xkj1j1-s

4、inx-xkj1j1r2.j1(6)將x=xnj2 代入公式，可得Wxnj2=exp-12r2n.2j1-j2-k2cos(n.2j1-j2-k)n.2j1-j2-k.j1-sinn.2j1-j2-k.j1.n.2j1-j2-k2-sinn.2j1-j2-kr2.j1(7)當(dāng)n.2j1-j2-k=0 時，Wxnj2=0 Shannon-Gabor小波函數(shù)的二階導(dǎo)數(shù)W''(x)= exp-12r2x-xkj1j12sinx-xkj1j1.1r2.j1.x-xkj1+x-xkj1r4.(j1)3-j1.x-xkj1+2j1.x-xkj13-2r2.(j1)2+2x-xkj12cos

5、x-xkj1j1(8)將x=xnj2代入公式，可得W''(xnj2)=exp-n.2j1-j2-k22r2sinn.2j1-j2-k.j121n.2j1-j2-kr2+n.2j1-j2-kr4-2n.2j1-j2-k+2n.2j1-j2-k3-2cosn.2j1-j2-kj121r2+1n.2j1-j2-k2(9)令 n.2j1-j2-k=t,則W''(xnj2)=exp-t22r2sint.j121t.r2+tr4-2t+2t3-2costj121r2+1t2(10)當(dāng)n.2j1-j2-k=0 時，W''(xnj2)=-23(j1)2-1(j1

6、)2.r22二維偏微分方程插值小波的快速計算方法采用插值小波變換理論計算小波系數(shù)、構(gòu)造插值算子，在提高精度的同時，也帶來了計算量的問題。下面對二維偏微分方程的插值小波算法中的參數(shù)進行優(yōu)化，以實現(xiàn)算法的快速計算。二維偏微分方程的求解首先對所求解區(qū)域進行空間離散，形成關(guān)于時間的常微分方程組，然后再對常微分方程組的數(shù)值進行求解，對空間離散的方法主要包括小波有限元法和小波配置法99-102。小波配置法要求基函數(shù)具有插值特性，在相同計算精度下，計算速度比有限元方法快；且具有自適應(yīng)性，在方程解的奇異點位置自動加密配點，在解平滑處配置點稀疏，可同時滿足計算效率、精度。1996年S.Bertoluzza99選

7、擇Daubechies小波的自相關(guān)函數(shù)為基函數(shù)構(gòu)造了一種單層小波配置法，該方法雖然對邊界條件具有較強的適應(yīng)性，但在整個求解區(qū)間上配置點是均勻選取的，計算量較大。OlegV.Vasilyev100構(gòu)造的多層小波配置法則避免了上述算法的缺陷，但多層小波配置法中插值基函數(shù)的構(gòu)造復(fù)雜，計算量大。文獻41利用插值小波理論構(gòu)造了一種求解偏微分方程的自適應(yīng)quasi-Shannon小波配置法，該方法充分利用了quasi-Shannon小波的插值特性，相對于文獻99的方法，多層插值函數(shù)的構(gòu)造簡單且計算量小，但只適用于一維的偏微分方程求解。下面通過構(gòu)造二維多層自適應(yīng)插值小波算子、插值小波基函數(shù)的選取、插值小波快

8、速計算方法等將自適應(yīng)小波配置法推廣至二維偏微分方程的求解。4.1.1 構(gòu)造二維多層自適應(yīng)插值小波算子考慮二維圖像函數(shù)f(x,y) ，二維小波函數(shù)對其進行逼近，配置點選取如圖4-1所示。由圖4-1可看出，不同層上的配點關(guān)系如下： j層每行包含 (2j+1)個元素。 在第j層下標(biāo)為k的元素是第k+1個配點，所在的行、列坐標(biāo)為k/(2j+1)，k mod (2j+1)。 j層下標(biāo)為k的配點，對應(yīng)到第J層配點的下標(biāo)為kJ，則kJ=2J-j.2J+1.k2j+1+k mod 2j+1圖4-1 不同層（j=0,j=1）上的配點關(guān)系3102147358206根據(jù)張量積的定義，可得出二維小波函數(shù)j,k1,k2

9、1、j,k1,k22、j,k1,k23和二維尺度函數(shù)j,k1,k2。j,k1,k2=j,k1(x)j,k2(y)(4-1) j,k1,k21=j+1,2k1+1,2k2(x,y)j,k1,k22=j+1,2k1,2k2+1(x,y)j,k1,k23=j+1,2k1+1,2k2+1(x,y)(4-2)顯見，第j層的小波函數(shù)等于第j+1層的尺度函數(shù)，第j層配置點對應(yīng)的第J層的三個小波點分別為kJ+1、kJ+2j+1+1、kJ+2j+1+1+1。多層小波配置法需要同時考慮不同離散柵格大小下的插值算子，根據(jù)插值小波變換理論，函數(shù)f(x,y)的逼近表達式為fx,y=k1=02j0k2=02j0j0,k1

10、,k2j0,k1,k2 +j=j0k1=02jk2=02jj,k1,k21j,k1,k21+j,k1,k22j,k1,k22+j,k1,k23j,k1,k23(4-3) 其中，j0,k1,k2=f(xk01j0,yk02j0)由插值小波變換理論可寫出插值小波系數(shù)j,k1,k21、j,k1,k22、j,k1,k23 ，小波系數(shù)表示經(jīng)過插值得到的配點函數(shù)值與真實值之間的逼近誤差。j,k1,k21=fxj+1,2k1+1,yj+1,2k2-Ijfxj+1,2k1+1,yj+1,2k2j,k1,k22=fxj+1,2k1,yj+1,2k2+1-Ijfxj+1,2k1,yj+1,2k2+1 j,k1,k

11、23=fxj+1,2k1+1, yj+1,2k2+1-Ijfxj+1,2k1+1,yj+1,2k2+1(4-4) 其中的插值算子定義如下：Ijfxj+1,2k1+1,yj+1,2k2=m1=02jm2=02jfxj,m1,yj,m2.j,m1,m2(xj+1,2k1+1,yj+1,2k2)Ijfxj+1,2k1,yj+1,2k2+1=m1=02jm2=02jfxj,m1,yj,m2.j,m1,m2(xj+1,2k1,yj+1,2k2+1)Ijfxj+1,2k1+1,yj+1,2k2+1=m1=02jm2=02jfxj,m1,yj,m2.j,m1,m2(xj+1,2k1+1,yj+1,2k2+1

12、)(4-5)為了得到統(tǒng)一的多層插值小波算子，需要將插值小波系數(shù)j,k1,k21、j,k1,k22、j,k1,k23表達成J層上所有配置點的權(quán)重和，因此定義限制算子為：Rk1, k2 ,m1 ,m2 l,l,j,j=1,xk1l=xm1j且yk2l=ym2j0,其他(4-6)限制算子表示了多層間對應(yīng)值相等的配點。利用限制算子，將公式（4-4）中的fx2k1+1j+1,y2k2j+1、fx2k1j+1,y2k2+1j+1和fx2k1+1j+1,y2k2+1j+1 映射到第J層上。fx2k1+1j+1,y2k2j+1=n1=02Jn2=02JR2k1+1,2k2,n1,n2j+1,j+1,J,Jf(

13、xn1J,yn2J)fx2k1j+1,y2k2+1j+1=n1=02Jn2=02JR2k1,2k2+1,n1,n2j+1,j+1,J,Jf(xn1J,yn2J)fx2k1+1j+1,y2k2+1j+1=n1=02Jn2=02JR2k1+1,2k2+1,n1,n2j+1,j+1,J,Jf(xn1J,yn2J)(4-7)因此由公式（4-4）得出小波系數(shù)表達式：j,k1,k21= fxj+1,2k1+1,yj+1,2k2-Ijfxj+1,2k1+1,yj+1,2k2=fx2k1+1j+1,y2k2j+1-k01=02j0k02=02j0fxk01j0,yk02j0k01,k02j0+j1=j0j-1

14、k11=02j1-1k12=02j1-1(j1,k11,k121j1,k11,k121+j1,k11,k122j1,k11,k122+j1,k11,k123j1,k11,k123)(4-8)其中，j=j0,j0+1,J-1將公式（4-7）代入到（4-8），用保留的已知點坐標(biāo)值直接求小波系數(shù)，可得以下公式： aj,k1,k21=i1=02Ji2=02JR2k1+1,2k2,i1,i2j+1,j+1,J,Jfxi1J,yi2J-i1=02Ji2=02Jk01=02j0k02=02j0Rk01,k02,i1,i2j0,j0,J,Jfxi1J,yi2Jk01,k02j0x2k1+1j+1，y2k2j+

15、1+j1=j0j-1k11=02j1-1k12=02j1-1i1=02Ji2=02JC1k11,k12,i1,i2j1,j1,J,J2k11+1,2k12j1+1fxi1J,yi2J+C2 k11,k12,i1,i2j1,j1,J,J2k11,2k12+1j1+1fxi1J,yi2J+C3 k11,k12,i1,i2j1,j1,J,J2k11+1,2k12+1j1+1fxi1J,yi2J=i1=02Ji2=02JC1 k1,k2,i1,i2j1,j1,J,Jfxi1J,yi2J (4-9)公式（4-9）中f(xi1J,yi2J)表示第J層的離散點，C1k1,k2,i1,i2j,j,J,J為一常

16、量矩陣。所以，當(dāng)j1>j0時，C1 k1,k2,i1,i2j1,j1,J,J=R2k1+1,2k2,i1,i2j+1,j+1,J,J-k01=02j0k02=02j0Rk01,k02,i1,i2j0,j0,J,Jk01,k02j0x2k1+1j+1，y2k2j+1-j1=j0j-1k11=02j1-1k12=02j1-1C1 k11,k12,i1,i2j1,j1,J,J2k11+1,2k12j1+1x2k1+1j+1，y2k2j+1+C2 k11,k12,i1,i2j1,j1,J,J2k11,2k12+1j1+1+C3 k11,k12,i1,i2j1,j1,J,J2k11+1,2k12+

17、1j1+1(4-10)其中，j=j0+1,j0+2,J-1 且 k1,k2=0，1，2，2j-1 k1,k2 Zj , i1,i2 ZJ 顯然，當(dāng)j1=j0時，C1 k01,k02,i1,i2j0,j0,J,J=R2k1+1,2k2,i1,i2j0+1,j0+1,J,J-k01=02j0k02=02j0Rk01,k02,i1,i2j0,j0,J,Jk01,k02j0x2k01+1j0+1，y2k02j0+1C2 k01,k02,i1,i2j0,j0,J,J=R2k1,2k2+1,i1,i2j0+1,j0+1,J,J-k01=02j0k02=02j0Rk01,k02,i1,i2j0,j0,J,J

18、k01,k02j0x2k01j0+1，y2k02+1j0+1C3 k01,k02,i1,i2j0,j0,J,J=R2k01+1,2k02+1,i1,i2j0+1,j0+1,J,J-k01=02j0k02=02j0Rk01,k02,i1,i2j0,j0,J,Jk01,k02j0x2k01+1j0+1，y2k02+1j0+1(4-11)由（4-10）和（4-11）可遞歸分別求出aj,k1,k22,aj,k1,k23。分析可得小波系數(shù)通過C1、C2、C3直接計算的時間復(fù)雜度為O(n4.log2n)。公式（4-6）中的第1項k1=02j0k2=02j0j0,k1,k2j0,k1,k2可以記作：k01=

19、02j0k02=02j0fxk01j0,yk02j0k01,k02j0利用限制算子將fxk01j0,yk02j0映射到J層上的所有點處fxk01j0,yk02j0=i1=02Ji2=02JRk01,k02,i1,i2j0,j0,J,Jfxi1J,yi2J(4-12)公式（4-3）中的第1項可記作：k01=02j0k02=02j0fxk01j0,yk02j0k01,k02j0=i1=02Ji2=02Jk01=02j0k02=02j0Rk01,k02,i1,i2j0,j0,J,Jfxi1J,yi2J(4-13)將公式（4-9）代入(4-3)中的第2項，第2項可寫為：i1=02Ji2=02Jj1=j

20、0J-1k1=02j1k2=02j1c1j,k1,k21+c2j,k1,k22+c3j,k1,k23fxi1J,yi2J(4-14) 因此，由公式（4-13）和（4-14）可將公式（4-3）寫為：fJx,y=i1=02Ji2=02Jk01=02j0k02=02j0Rk01,k02,i1,i2j0,j0,J,Jk01,k02j0+j1=j0J-1k1=02jk2=02jc1j,k1,k21+c2j,k1,k22+c3j,k1,k23fxi1J,yi2J=i1=02Ji2=02JIi1,i2x,y fxi1J,yi2J（4-15）因此插值算子Ii1,i2(x,y)可記作：Ii1,i2x,y=k01

21、=02j0k02=02j0Rk01,k02,i1,i2j0,j0,J,Jk01,k02j0x,y+j1=j0J-1k1=02jk2=02jc1j,k1,k21+c2j,k1,k22+c3j,k1,k23(4-16)由于在不同時刻配置點的數(shù)量和位置均不相同，所以自適應(yīng)算法中，在不同的時間段，必須重新構(gòu)造插值算子,因此插值算子的構(gòu)造速度對整個算法的計算效率有極其重要的影響。本文構(gòu)造出的插值算子具有顯式表達式且在形式上將單層插值小波算子和多層插值小波算子統(tǒng)一起來，同傳統(tǒng)方法相比，具有較小的計算量。-快速計算方法-1.Shannon-Gabor小波函數(shù)的快速計算 在小波自適應(yīng)插值算法中，經(jīng)常需要大量計算公式（4-16）中的Shannon-Gabor小波函數(shù)j,k1,k21、j,k1,k22、j,k1,k23，當(dāng)用j1層上的k點計算j2層上的配點n時，公式如下： Wxnj2-xkj1=sinxnj2-xkj1j1xnj2-xkj1j1exp-12r2xnj2-xkj12j22(4-27)其中,j1=b-a2j1。為了計算方便，將xkj1，xnj2映射到第J層上，對應(yīng)J層中的編號為xnkJ，xnnJ，則得出以下公式：xnkJ=nkJxnnJ=nnJ nk=2J-j1knn=2J-j2n(4-