离散小波变换.doc

离散小波变换
长期以来,离散小波变换(Discrete Wavelet Transform)在数字信号处理、石油勘探、地震预报、医学断层诊断、编码理论、量子物理及概率论等领域中都得到了广泛的应用。各种快速傅氏变换(FFT)和离散小波变换(DWT)算法不断出现,成为数值代数方面最活跃的一个研究领域,而其意义远远超过了算法研究的范围,进而为诸多科技领域的研究打开了一个崭新的局面。本章分别对FFT和DWT的基本算法作了简单介绍,若需在此方面做进一步研究,可参考文献[2]。
离散小波变换DWT
离散小波变换DWT及其串行算法
先对一维小波变换作一简单介绍。设f(x)为一维输入信号,记,,这里与分别称为定标函数与子波函数,与为二个正交基函数的集合。记P0f=f,在第级上的一维离散小波变换DWT(Discrete Wavelet Transform)通过正交投影Pjf与Qjf将Pj-1f分解为:

其中:, ,这里,{h(n)}与{g(n)}分别为低通与高通权系数,它们由基函数与来确定,p为权系数的长度。为信号的输入数据,N为输入信号的长度,L为所需的级数。由上式可见,每级一维DWT与一维卷积计算很相似。所不同的是:在DWT中,输出数据下标增加1时,权系数在输入数据的对应点下标增加2,这称为“间隔取样”。
一维离散小波变换串行算法
输入:c0=d0(c00, c10,…, cN-10)
h=(h0, h1,…, hL-1)
g=(g0, g1,…, gL-1)
输出:cij , dij (i=0, 1,…, N/2j-1, j≥0)
Begin
(1)j=0, n=N
(2)While (n≥1) do
()for i=0 to n-1 do
()cij+1=0, dij+1=0
()for k=0 to L-1 do

end for
end for
()j=j+1, n=n/2
end while
End
显然,(N*L)。
在实际应用中,pactly Supported Wavelets),这时相应的尺度系数和小波系数都是有限长度的,不失一般性设尺度系数只有有限个非零值:h1,…,hN,N为偶数,同样取小波使其只有有限个非零值:g1,…,gN。为简单起见,设尺度系数与小波函数都是实数。对有限长度的输入数据序列:(其余点的值都看成0),它的离散小波变换为:
其中J为实际中要求分解的步数,最多不超过log2M,其逆变换为
注意到尺度系数和输入系列都是有限长度的序列,上述和实际上都只有有限项。若完全按照上述公式计算,在经过J步分解后,所得到的J+1个序列和的非零项的个数之和一般要大于M,究竟这个项目增加到了多少?下面来分析一下上述计算过程。
j=0时计算过程为

不难看出,的非零值范围为:即有个非零值。的非零值范围相同。继续往下分解时,非零项出现的规律相似。分解多步后非零项的个数可能比输入序列的长度增加较多。例如,若输入序列长度为100,N=4,则有51项非零,有27项非零,有15项非零,有9项非零,有6项非零,有4项非零,有4项非零。这样分解到6步后得到的序列的非零项个数的总和为
116,超过了输