离散小波变换

1、(2.1.2)for k=0 to L-1 do1.离散小波变换长期以来，离散小波变换(Discrete Wavelet Transform)在数字信号处理、石油勘探、地 震预报、医学断层诊断、编码理论、量子物理及概率论等领域中都得到了广泛的应用。各种 快速傅氏变换(FFT)和离散小波变换(DWT)算法不断出现，成为数值代数方面最活跃的一个 研究领域，而其意义远远超过了算法研究的范围，进而为诸多科技领域的研究打开了一个崭新的局面。本章分别对FFT和DWT的基本算法作了简单介绍，若需在此方面做进一步研究, 可参考文献2。1.1离散小波变换DWT1.1.1离散小波变换DWT及其串行算法先对一维小波

2、变换作一简单介绍。设f(x)为一维输入信号，记jk(x) 2 j/2 (2 jx k),jk(x) 2 j/2 (2 jx k)，这里(X)与(X)分别称为定标函数与子波函数， jk(x)与 jk(x)为二个正交基函数的集合。记P0f=f,在第j级上的一维离散小波变换DWT(DiscreteWavelet Tran sform)通过正交投影Pjf与Qjf将Pj-1f分解为:ck jkkPj 1fPjf Qjfdk jkk其中：cknP 1j 1j0h(n)% n，dkP1 j 1 n0g(n)C2kn(j1,2,，L,k 0,1,，N/2J 1),这里，h(n)与g( n)分别为低通与高通权系

3、数，它们由基函数 jk(x)与 jk(x)来确定，p为权系数的长度。C：为信号的输入数据，N为输入信号的长度，L为所需的级数。由上式可见,每级一维DWT与一维卷积计算很相似。 所不同的是：在DWT中，输出数据下标增加1时, 权系数在输入数据的对应点下标增加2,这称为“间隔取样”。算法22.3 一维离散小波变换串行算法 输入：输出:C0=d0(C00, C10,CN-10) h=(h 0, h1,，hL-1) g=(g 0, g1,，gL-1)Cj , dij (i=0, 1,，N/2j-1, j > 0)Begi n(1) j=0, n=N(2) While (n> 1) do(2

4、.1)for i=0 to n-1 do(2.1.1) c+1 =0, d ij+1 =0ciChk k 2i) mod n ,d；d/gkd(k 2i)mod nend for end for (2.2)j=j+1, n=n/2 end whileEnd显然，算法22.3的时间复杂度为O(N*L)。在实际应用中，很多情况下采用紧支集小波(Compactly Supported Wavelets)，这时相应的尺度系数和小波系数都是有限长度的，不失一般性设尺度系数只有有限个非零值：gi,gN。为简单起见，设尺度系数与小波函数都是实数。对有限长度的输入数据序列:C0 xn,n 1,2, ,M (其

5、余点的值都h1,hN, N为偶数，同样取小波使其只有有限个非零值：看成0)，它的离散小波变换为：ckcn hn 2kn ZdkCn gn 2k n Z0,1, ,J 1其中J为实际中要求分解的步数，最多不超过ck hn 2k k Zcn1iog2M，其逆变换为ckhn 2kk ZJ,1注意到尺度系数和输入系列都是有限长度的序列,上述和实际上都只有有限项。若完全按照上述公式计算，在经过J步分解后，所得到的J+1 个序列 dkj, j 0,1, ,J 1 和 C|k 的非零项的个数之和一般要大于 过程。j=0时计算过程为M,究竟这个项目增加到了多少？下面来分析一下上述计算1 M ,ckxnhn 2

6、kn 1Mdkxng n 2kn 1出，ck非零值范围为：kN. M“口口1,1,0,1,即有22M2现的规律相似。M N 12分解多步后非零项的个数可能比输入序列的长度增加较多。个非零值。dk的非零值范围相同。继续往下分解时，非零项出例如，若输入序列长度为100,N=4,则d：有51项非零，di2有27项非零，d3有15项非零，d：有9项非零，d5有6项非零，d6有4项非零，c6有4项非零。这样分解到 6步后得到的序列的非零项个数的总和为1 1 6,超过了输入序列的长度。在数据压缩等应用中，希望总的长度基本 不增加，这样可以提高压缩比、减少存储量并减少实现的难度。可以采用稍微改变计算公式的方

7、法，使输出序列的非零项总和基本上和输入序列的非零项数相等，并且可以完全重构。这种方法也相当于把输入序列进行延长（增加非零项），因而称为延拓法。只需考虑一步分解的情形，下面考虑第一步分解（j=1 ）。将输入序列作延拓，若M为偶0。然后按M + 1为周期延拓。数，直接将其按 M为周期延拓；若 M为奇数，首先令xM 1作了这种延拓后再按前述公式计算，相应的变换矩阵已不再是 矩阵类似于循环矩阵。例如，当H和G,事实上这时的变换M=8,N=4时矩阵H变为:h3h00h3h4h200h40h3hi000h4h20000h3h000h4h20hi 0 0 h3 hih200h4h2当m=7, N=4时矩阵H

8、变为:h3h00h3h4h200h40h3hi000h4h20000h3hi000h4h20h00h3h从上述的矩阵表示可以看出，计算，因而从矩阵中去掉重复的那一行不会减少任何信息量，也就是说，阵进行截短（即去掉一行），使得所得计算结果仍然可以完全恢复原输入信号。 时截短后的矩阵为：两种情况下的矩阵内都有完全相同的行,这说明作了重复这时我们可以对矩当 M=8，N=4h4 h2 0 00h3hi00h4h2000馆h00h4h2hi00h3h200h4当m=7, N=4时截短后的矩阵为:h3h00h4h2000h3hi00h4h2000h3hi00h4h2h00h3这时的矩阵都只有节行。分解过程

9、成为:HC0D1GC0向量Ci和d1都只有 M 个元素。重构过程为:2C0 H * C1 G* D1可以完全重构。矩阵 H , G有等式M行，可以完全恢复原信号。20元素的个数基本上和输入序列的非0元素个数相则完全相同，而且可以完全重构输入信号。其代价是般情况下，按上述方式保留矩阵的H*H + G*G = I这种方法的优点是最后的序列的非同，特别是若输入序列长度为 2的幕，得到的变换系数 Dj中的一些元素已不再是输入序列的离散小波变换系数，对某些应用可能 是不适合的，但在数据压缩等应用领域，这种方法是可行的。Begi n对所有处理器 my_rank(my_rank=0,p-1)同时执行如下的算法：(1) j=0;(2) while (j<r) do(2.1)将数据cn(n 0,1, ,N/2j 1)按块分配给P台处理器(2.2)将处理器i+1中前L-1个数据发送给处理器i(2.3)处理器ii 1 i 1NN负责cn和dn1 (n i,(i1)一万1)的计算p2j 1p2 j 1(2.4)j=j+1 end whileEnd这里每一步分解后数据cn1和dn1已经是按块存储在 P台处理器上，因此算法第一步中的数据分配除了 j=0时