ShannonGabor小波的快速计算

1、Shannon-Gabor小波的快速计算及其在图像处理中的应用1 插值小波基函数插值小波基函数应是具有插值特性的紧支撑或指数衰减函数，如插值样条小波、Daubechies小波的自相关函数等。但插值样条小波不具备正交性，而Daubechies小波没有解析表达式，Haar小波同时具有紧支撑性和正交性，但不连续，Faber-Schauder小波具有插值特性和紧支撑性，但不光滑，而Shannon小波不具备紧支撑性，因此选择具有近似紧支撑性和插值特性的Shannon-Gabor小波函数。Shannon-Gabor尺度函数定义如下：=sin(x/)x/exp(-x222)(1)其中是离散点间距，=r（r是

2、任意参数）是窗口大小参数。为取Shannon-Gabor尺度函数作为基函数，按多尺度分析理论对函数f(x)在定义域a,b内进行均匀离散，取离散点个数为2j+1,(jZ)，则变量x的离散点定义为：xi=a+b-a2j.i则基函数为jix=sin2jb-a(x-xi)2jb-a(x-xi)exp-22j2r2x-xib-a2(2)令j1=b-a2j1，=rj1,则若取具有插值特性的Shannon-Gabor小波作为试函数，即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小波函数求一阶、二阶导数： Shannon-Gabor小波函数的一阶导数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)当n.2j1-j2-k=0 时，Wxnj2=0 Shannon-Gabor小波函数的二阶导数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)当n.2j1-j2-k=0 时，W''(xnj2)=-23(j1)2-1(j1

6、)2.r22二维偏微分方程插值小波的快速计算方法采用插值小波变换理论计算小波系数、构造插值算子，在提高精度的同时，也带来了计算量的问题。下面对二维偏微分方程的插值小波算法中的参数进行优化，以实现算法的快速计算。二维偏微分方程的求解首先对所求解区域进行空间离散，形成关于时间的常微分方程组，然后再对常微分方程组的数值进行求解，对空间离散的方法主要包括小波有限元法和小波配置法99-102。小波配置法要求基函数具有插值特性，在相同计算精度下，计算速度比有限元方法快；且具有自适应性，在方程解的奇异点位置自动加密配点，在解平滑处配置点稀疏，可同时满足计算效率、精度。1996年S.Bertoluzza99选

7、择Daubechies小波的自相关函数为基函数构造了一种单层小波配置法，该方法虽然对边界条件具有较强的适应性，但在整个求解区间上配置点是均匀选取的，计算量较大。OlegV.Vasilyev100构造的多层小波配置法则避免了上述算法的缺陷，但多层小波配置法中插值基函数的构造复杂，计算量大。文献41利用插值小波理论构造了一种求解偏微分方程的自适应quasi-Shannon小波配置法，该方法充分利用了quasi-Shannon小波的插值特性，相对于文献99的方法，多层插值函数的构造简单且计算量小，但只适用于一维的偏微分方程求解。下面通过构造二维多层自适应插值小波算子、插值小波基函数的选取、插值小波快

8、速计算方法等将自适应小波配置法推广至二维偏微分方程的求解。4.1.1 构造二维多层自适应插值小波算子考虑二维图像函数f(x,y) ，二维小波函数对其进行逼近，配置点选取如图4-1所示。由图4-1可看出，不同层上的配点关系如下： j层每行包含 (2j+1)个元素。 在第j层下标为k的元素是第k+1个配点，所在的行、列坐标为k/(2j+1)，k mod (2j+1)。 j层下标为k的配点，对应到第J层配点的下标为kJ，则kJ=2J-j.2J+1.k2j+1+k mod 2j+1图4-1 不同层（j=0,j=1）上的配点关系3102147358206根据张量积的定义，可得出二维小波函数j,k1,k2

9、1、j,k1,k22、j,k1,k23和二维尺度函数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层的小波函数等于第j+1层的尺度函数，第j层配置点对应的第J层的三个小波点分别为kJ+1、kJ+2j+1+1、kJ+2j+1+1+1。多层小波配置法需要同时考虑不同离散栅格大小下的插值算子，根据插值小波变换理论，函数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)由插值小波变换理论可写出插值小波系数j,k1,k21、j,k1,k22、j,k1,k23 ，小波系数表示经过插值得到的配点函数值与真实值之间的逼近误差。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)为了得到统一的多层插值小波算子，需要将插值小波系数j,k1,k21、j,k1,k22、j,k1,k23表达成J层上所有配置点的权重和，因此定义限制算子为：Rk1, k2 ,m1 ,m2 l,l,j,j=1,xk1l=xm1j且yk2l=ym2j0,其他(4-6)限制算子表示了多层间对应值相等的配点。利用限制算子，将公式（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）得出小波系数表达式：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），用保留的已知点坐标值直接求小波系数，可得以下公式： 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、量矩阵。所以，当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 显然，当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。分析可得小波系数通过C1、C2、C3直接计算的时间复杂度为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)由于在不同时刻配置点的数量和位置均不相同，所以自适应算法中，在不同的时间段，必须重新构造插值算子,因此插值算子的构造速度对整个算法的计算效率有极其重要的影响。本文构造出的插值算子具有显式表达式且在形式上将单层插值小波算子和多层插值小波算子统一起来，同传统方法相比，具有较小的计算量。-快速计算方法-1.Shannon-Gabor小波函数的快速计算 在小波自适应插值算法中，经常需要大量计算公式（4-16）中的Shannon-Gabor小波函数j,k1,k21、j,k1,k22、j,k1,k23，当用j1层上的k点计算j2层上的配点n时，公式如下： Wxnj2-xkj1=sinxnj2-xkj1j1xnj2-xkj1j1exp-12r2xnj2-xkj12j22(4-27)其中,j1=b-a2j1。为了计算方便，将xkj1，xnj2映射到第J层上，对应J层中的编号为xnkJ，xnnJ，则得出以下公式：xnkJ=nkJxnnJ=nnJ nk=2J-j1knn=2J-j2n(4-