《离散小波变换.doc》由会员分享,可在线阅读,更多相关《离散小波变换.doc(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1. 离散小波变换长期以来,离散小波变换(Discrete Wavelet Transform)在数字信号处理、石油勘探、地震预报、医学断层诊断、编码理论、量子物理及概率论等领域中都得到了广泛的应用。各种快速傅氏变换(FFT)与离散小波变换(DWT)算法不断出现,成为数值代数方面最活跃的一个研究领域,而其意义远远超过了算法研究的范围,进而为诸多科技领域的研究打开了一个崭新的局面。本章分别对FFT与DWT的基本算法作了简单介绍,若需在此方面做进一步研究,可参考文献2。 1.1 离散小波变换DWT1.1.1 离散小波变换DWT及其串行算法先对一维小波变换作一简单介绍。设f(x)为一维输入信号,记,
2、这里与分别称为定标函数与子波函数,与为二个正交基函数的集合。记P0f=f,在第级上的一维离散小波变换DWT(Discrete Wavelet Transform)通过正交投影Pjf与Qjf将Pj-1f分解为:其中:, ,这里,h(n)与g(n)分别为低通与高通权系数,它们由基函数与来确定,p为权系数的长度。为信号的输入数据,N为输入信号的长度,L为所需的级数。由上式可见,每级一维DWT与一维卷积计算很相似。所不同的是:在DWT中,输出数据下标增加1时,权系数在输入数据的对应点下标增加2,这称为“间隔取样”。算法22.3 一维离散小波变换串行算法输入:c0=d0(c00, c10, cN-10)
3、 h=(h0, h1, hL-1) g=(g0, g1, gL-1)输出:cij , dij (i=0, 1, N/2j-1, j0)Begin(1)j=0, n=N(2)While (n1) do(2.1)for i=0 to n-1 do(2.1.1)cij+1=0, dij+1=0(2.1.2)for k=0 to L-1 do end forend for(2.2)j=j+1, n=n/2 end whileEnd显然,算法22.3的时间复杂度为O(N*L)。在实际应用中,很多情况下采用紧支集小波(Compactly Supported Wavelets),这时相应的尺度系数与小波系数
4、都是有限长度的,不失一般性设尺度系数只有有限个非零值:h1,hN,N为偶数,同样取小波使其只有有限个非零值:g1,gN。为简单起见,设尺度系数与小波函数都是实数。对有限长度的输入数据序列:(其余点的值都看成0),它的离散小波变换为:其中J为实际中要求分解的步数,最多不超过log2M,其逆变换为注意到尺度系数与输入系列都是有限长度的序列,上述与实际上都只有有限项。若完全按照上述公式计算,在经过J步分解后,所得到的J+1个序列与的非零项的个数之与一般要大于M,究竟这个项目增加到了多少?下面来分析一下上述计算过程。j=0时计算过程为不难看出,的非零值范围为:即有个非零值。的非零值范围相同。继续往下分
5、解时,非零项出现的规律相似。分解多步后非零项的个数可能比输入序列的长度增加较多。例如,若输入序列长度为100,N=4,则有51项非零,有27项非零,有15项非零,有9项非零,有6项非零,有4项非零,有4项非零。这样分解到6步后得到的序列的非零项个数的总与为116,超过了输入序列的长度。在数据压缩等应用中,希望总的长度基本不增加,这样可以提高压缩比、减少存储量并减少实现的难度。可以采用稍微改变计算公式的方法,使输出序列的非零项总与基本上与输入序列的非零项数相等,并且可以完全重构。这种方法也相当于把输入序列进行延长(增加非零项),因而称为延拓法。只需考虑一步分解的情形,下面考虑第一步分解(j=1)
6、。将输入序列作延拓,若M为偶数,直接将其按M为周期延拓;若M为奇数,首先令。然后按M+1为周期延拓。作了这种延拓后再按前述公式计算,相应的变换矩阵已不再是H与G,事实上这时的变换矩阵类似于循环矩阵。例如,当M=8,N=4时矩阵H变为:当M=7,N=4时矩阵H变为:从上述的矩阵表示可以看出,两种情况下的矩阵内都有完全相同的行,这说明作了重复计算,因而从矩阵中去掉重复的那一行不会减少任何信息量,也就是说,这时我们可以对矩阵进行截短(即去掉一行),使得所得计算结果仍然可以完全恢复原输入信号。当M=8,N=4时截短后的矩阵为:当M=7,N=4时截短后的矩阵为:这时的矩阵都只有行。分解过程成为:向量C1
7、 与D1都只有个元素。重构过程为:可以完全重构。矩阵H,G有等式H*H+G*G=I一般情况下,按上述方式保留矩阵的行,可以完全恢复原信号。这种方法的优点是最后的序列的非0元素的个数基本上与输入序列的非0元素个数相同,特别是若输入序列长度为2的幂,则完全相同,而且可以完全重构输入信号。其代价是得到的变换系数Dj中的一些元素已不再是输入序列的离散小波变换系数,对某些应用可能是不适合的,但在数据压缩等应用领域,这种方法是可行的。Begin对所有处理器my_rank(my_rank=0, p-1)同时执行如下的算法:(1)j=0;(2)while (jr) do(2.1)将数据按块分配给p台处理器(2.2)将处理器i+1中前L-1个数据发送给处理器i(2.3)处理器i负责与的计算(2.4)j=j+1end whileEnd这里每一步分解后数据与已经是按块存储在P台处理器上,因此算法第一步中的数据分配除了j=0时需要数据传送外,其余各步不需要数据传送(数据已经到位)。因此,按LogP模型,算法的总的通信时间为:2(Lmax(o,g)+l),远小于计算时间O(N)。MPI源程序请参见所附光盘。1. Verlag,19822. 陈崚二维正交子波变换的VLSI并行计算电子学报,1995,23(02):95-97 第 5 页
限制150内