離散小波變換

1、1. 離散小波變換長期以來，離散小波變換(Discrete Wavelet Transform)在數(shù)字信號處理、石油勘探、地震預(yù)報(bào)、醫(yī)學(xué)斷層診斷、編碼理論、量子物理及概率論等領(lǐng)域中都得到了廣泛的應(yīng)用。各種快速傅氏變換(FFT)和離散小波變換(DWT)算法不斷出現(xiàn)，成為數(shù)值代數(shù)方面最活躍的一個(gè)研究領(lǐng)域，而其意義遠(yuǎn)遠(yuǎn)超過了算法研究的范圍，進(jìn)而為諸多科技領(lǐng)域的研究打開了一個(gè)嶄新的局面。本章分別對FFT和DWT的基本算法作了簡單介紹，若需在此方面做進(jìn)一步研究，可參考文獻(xiàn)2。 1.1 離散小波變換DWT1.1.1 離散小波變換DWT及其串行算法先對一維小波變換作一簡單介紹。設(shè)f(x)為一維輸入信號，記，

2、這里與分別稱為定標(biāo)函數(shù)與子波函數(shù)，與為二個(gè)正交基函數(shù)的集合。記P0f=f，在第級上的一維離散小波變換DWT(Discrete Wavelet Transform)通過正交投影Pjf與Qjf將Pj-1f分解為： 其中：， ，這里，h(n)與g(n)分別為低通與高通權(quán)系數(shù)，它們由基函數(shù)與來確定，p為權(quán)系數(shù)的長度。為信號的輸入數(shù)據(jù)，N為輸入信號的長度，L為所需的級數(shù)。由上式可見，每級一維DWT與一維卷積計(jì)算很相似。所不同的是：在DWT中，輸出數(shù)據(jù)下標(biāo)增加1時(shí)，權(quán)系數(shù)在輸入數(shù)據(jù)的對應(yīng)點(diǎn)下標(biāo)增加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()cij+1=0, dij+1=0()for k=0 to L-1 do end forend for(2.2)j=j+1, n=n/2 end whileEnd顯然，算法22.3的時(shí)間復(fù)雜度為O(N*L)。在實(shí)際應(yīng)用中，很多情況下采用緊支集小波（Compactly Supported Wavelets），這時(shí)相應(yīng)的尺度系數(shù)和小波系數(shù)都是有限長度的，不

4、失一般性設(shè)尺度系數(shù)只有有限個(gè)非零值：h1,hN，N為偶數(shù)，同樣取小波使其只有有限個(gè)非零值：g1,gN。為簡單起見，設(shè)尺度系數(shù)與小波函數(shù)都是實(shí)數(shù)。對有限長度的輸入數(shù)據(jù)序列：(其余點(diǎn)的值都看成0)，它的離散小波變換為:其中J為實(shí)際中要求分解的步數(shù)，最多不超過log2M，其逆變換為注意到尺度系數(shù)和輸入系列都是有限長度的序列，上述和實(shí)際上都只有有限項(xiàng)。若完全按照上述公式計(jì)算，在經(jīng)過J步分解后，所得到的J+1個(gè)序列和的非零項(xiàng)的個(gè)數(shù)之和一般要大于M，究竟這個(gè)項(xiàng)目增加到了多少？下面來分析一下上述計(jì)算過程。j=0時(shí)計(jì)算過程為 不難看出，的非零值范圍為：即有個(gè)非零值。的非零值范圍相同。繼續(xù)往下分解時(shí)，非零項(xiàng)出現(xiàn)

5、的規(guī)律相似。分解多步后非零項(xiàng)的個(gè)數(shù)可能比輸入序列的長度增加較多。例如，若輸入序列長度為100，N=4，則有51項(xiàng)非零，有27項(xiàng)非零，有15項(xiàng)非零，有9項(xiàng)非零，有6項(xiàng)非零，有4項(xiàng)非零，有4項(xiàng)非零。這樣分解到6步后得到的序列的非零項(xiàng)個(gè)數(shù)的總和為116，超過了輸入序列的長度。在數(shù)據(jù)壓縮等應(yīng)用中，希望總的長度基本不增加，這樣可以提高壓縮比、減少存儲量并減少實(shí)現(xiàn)的難度?？梢圆捎蒙晕⒏淖冇?jì)算公式的方法，使輸出序列的非零項(xiàng)總和基本上和輸入序列的非零項(xiàng)數(shù)相等，并且可以完全重構(gòu)。這種方法也相當(dāng)于把輸入序列進(jìn)行延長（增加非零項(xiàng)），因而稱為延拓法。只需考慮一步分解的情形，下面考慮第一步分解(j=1)。將輸入序列作延

6、拓，若M為偶數(shù)，直接將其按M為周期延拓；若M為奇數(shù)，首先令。然后按M+1為周期延拓。作了這種延拓后再按前述公式計(jì)算，相應(yīng)的變換矩陣已不再是H和G，事實(shí)上這時(shí)的變換矩陣類似于循環(huán)矩陣。例如，當(dāng)M=8，N=4時(shí)矩陣H變?yōu)椋寒?dāng)M=7，N=4時(shí)矩陣H變?yōu)椋簭纳鲜龅木仃嚤硎究梢钥闯觯瑑煞N情況下的矩陣內(nèi)都有完全相同的行，這說明作了重復(fù)計(jì)算，因而從矩陣中去掉重復(fù)的那一行不會(huì)減少任何信息量，也就是說，這時(shí)我們可以對矩陣進(jìn)行截短（即去掉一行），使得所得計(jì)算結(jié)果仍然可以完全恢復(fù)原輸入信號。當(dāng)M=8，N=4時(shí)截短后的矩陣為：當(dāng)M=7，N=4時(shí)截短后的矩陣為：這時(shí)的矩陣都只有行。分解過程成為：向量C1 和D1都只有個(gè)

7、元素。重構(gòu)過程為：可以完全重構(gòu)。矩陣H，G有等式H*H+G*G=I一般情況下，按上述方式保留矩陣的行，可以完全恢復(fù)原信號。這種方法的優(yōu)點(diǎn)是最后的序列的非0元素的個(gè)數(shù)基本上和輸入序列的非0元素個(gè)數(shù)相同，特別是若輸入序列長度為2的冪，則完全相同，而且可以完全重構(gòu)輸入信號。其代價(jià)是得到的變換系數(shù)Dj中的一些元素已不再是輸入序列的離散小波變換系數(shù)，對某些應(yīng)用可能是不適合的，但在數(shù)據(jù)壓縮等應(yīng)用領(lǐng)域，這種方法是可行的。Begin對所有處理器my_rank(my_rank=0, p-1)同時(shí)執(zhí)行如下的算法:(1)j=0;(2)while (jr) do(2.1)將數(shù)據(jù)按塊分配給p臺處理器(2.2)將處理器i+1中前L-1個(gè)數(shù)據(jù)發(fā)送給處理器i(2.3)處理器i負(fù)責(zé)和的計(jì)算(2.4)j=j+1end whileEnd這里每一步分解后數(shù)據(jù)和已經(jīng)是按塊存儲在P臺處理器上，因此算法第一步中的數(shù)據(jù)分配除了j=0時(shí)需要數(shù)據(jù)傳送外，其余各步不需要數(shù)據(jù)傳送（數(shù)據(jù)已經(jīng)到位）。因此，按