小波變換課件第4章小波變換的實現(xiàn)技術(shù)

1、第4章 小波變換的實現(xiàn)技術(shù)4.1 Mallat算法雙正交小波變換的Mallat算法：設(shè)、為實系數(shù)雙正交小波濾波器。，是小波分析濾波器，是小波綜合濾波器。表示的逆序，即。若輸入信號為，它的低頻部分和高頻部分以此為和，小波分解與重構(gòu)的卷積算法： 先進行輸入信號和分析濾波器的巻積，再隔點采樣，以形成低頻和高頻信號。對于有限的數(shù)據(jù)量，經(jīng)過多次小波變化后數(shù)據(jù)量大減，因此需對輸入數(shù)據(jù)進行處理。4.1.1 邊界延拓方法下面給出幾種經(jīng)驗方法。1. 補零延拓是假定邊界以外的信號全部為零，這種延拓方式的缺點是，如果輸入信號在邊界點的值與零相差很大，則零延拓意味著在邊界處加入了高頻成分，造成很大誤差。實際應(yīng)用中很少

2、采用。2.簡單周期延拓將信號看作一個周期信號,即。簡單周期延拓后的信號變?yōu)檫@種延拓方式的不足之處在于，當信號兩端邊界值相差很大時，延拓后的信號將存在周期性的突變，也就是說簡單周期延拓可在邊界引入大量高頻成分，從而產(chǎn)生較大誤差。3. 周期對稱延拓這種方法是將原信號在邊界上作對稱折疊，一般分二1）當與之做卷積的濾波器為奇數(shù)時，周期延拓信號為2）當與之做卷積的濾波器為偶數(shù)時，周期延拓信號為 4. 光滑常數(shù)延拓在原信號兩端添加與端點數(shù)據(jù)相同的常數(shù)。5. 平滑延拓在原信號兩端用線性外插法補充采樣值，即沿著信號兩端包絡(luò)線的一階導(dǎo)數(shù)方向增加采樣值。l 實際應(yīng)用時，在變換前對輸入信號進行邊界進行延拓，使之變成

3、無限長的信號，變換后，、在盡可能不丟失信息的情況下，適當截取部分變換系數(shù)作為低頻信號和高頻信號，以保證小波分解后的數(shù)據(jù)總量保持不變。見下圖。為實現(xiàn)完全重構(gòu)，先對有限長序列進行延拓，然后再插值和濾波，對濾波后的信號相加，再適當截取，以恢復(fù)原信號。見下圖。4.1.3 用小波處理函數(shù)信號的基本步驟1. 初始化l 對于時間的連續(xù)信號，選擇適當?shù)?，使得大于信號的抽樣頻率(不同的應(yīng)用決定了不同的抽樣率)。l 設(shè)信號在最高初始分辨率級下的光滑逼近為，則有由式（322）, 既可得在實際應(yīng)用中，由原信號確定的的范圍是有限的，譬如信號的持續(xù)時間為，則的范圍為。2. 小波分解應(yīng)用Mallat 算法，得到離散信號的小

4、波變換，相應(yīng)地，得到的分辨率表示：其中， 。具體地,實際應(yīng)用中，可以根據(jù)需要控制分解的級數(shù)，不一定達到級。3. 小波系數(shù)處理針對不同的應(yīng)用目標，對小波系數(shù)進行處理獲得新的小波系數(shù)。譬如，在進行信號的數(shù)據(jù)壓縮時，將絕對值小于某一閾值的系數(shù)置為零，保留剩余的系數(shù)，用于重構(gòu)信號；而在去噪時，將絕對值小于某一閾值的系數(shù)置為零，用于重構(gòu)去噪信號。4. 小波重構(gòu)對處理后的小波系數(shù)，重構(gòu)出分辨率時的離散信號。一般地，是的逼近信號。進而可以得到或的重構(gòu)信號。對于離散信號的小波處理過程為 ，設(shè)（）是一個離散輸入信號，采樣間隔為，其中?？蓪⑴c聯(lián)系起來（是正交尺度函數(shù)），使為的均勻采樣，即。根據(jù)式（322）可得。由

5、此可獲得在最高分辨率下的初始系數(shù)序列。然后，利用Mallat算法對該序列進行小波分解、對小波系數(shù)處理以及處理后的系數(shù)進行小波重構(gòu)等。4.1.4 應(yīng)用舉例例4.1對單位區(qū)間上一個連續(xù)信號，將信號離散化為個采樣值，相應(yīng)的逼近信號記為。用Haar小波對信號進行3級小波分解，寫出信號的多分辨表示，并畫出該信號在不同分辨率下的逼近信號、和的圖形。 假設(shè)信號為，它在中的投影記為，則的圖形見圖42a。用Haar小波對信號進行3級小波分解，其多分辨表示為其中、波形如圖42b、c、d所示。圖4-2 一個函數(shù)的多分辨逼近函數(shù) 例4.2 對于例4-2中的信號及逼近信號。若用正交尺度函數(shù)和正交小波函數(shù)進行小波分析解，

6、則可得到：其中，1）用Haar尺度函數(shù)和Haar小波函數(shù)分解信號，令絕對值最小的80%和90%的系數(shù)為0，對信號進行小波壓縮。畫出相應(yīng)的重構(gòu)信號波形，并求出相應(yīng)的相對誤差。2）用Daubechice尺度函數(shù)和Daubechice小波 (如db2)分解信號，令絕對值最小的80%和90%的系數(shù)為0，對信號進行小波壓縮。畫出相應(yīng)的重構(gòu)信號波形，并求出相應(yīng)的相對差。3）比較1）和2）的壓縮效果。4）用FFT在相同條件下壓縮信號，所得的相對誤差如何。求解過程如下：1） 用Haar小波函數(shù)分解信號，令絕對值最小的80%和90%的系數(shù)為0，得到重構(gòu)信號圖形如圖4-3a所示。所得的均方差為0.7991；相對誤

7、差為0.0050。如果令絕對值最小的90%的系數(shù)為0，得到重構(gòu)信號圖形如圖4-3b所示。在這種情況下，得到均方誤差為2.9559，相對誤差為0.0185。圖4-3 用Haar小波壓縮后的重構(gòu)信號2） 用Daubechice小波函數(shù)(如Db2)分解信號，令絕對值最小的80%的系數(shù)為0，得到的重構(gòu)信號波形如圖4-4a所示，得到均方誤差為0.0277，相對誤差為0.00017。如果令絕對值最小的90%的系數(shù)為0，得到重構(gòu)信號圖形如圖4-4b所示，這時得到均方誤差為0.2159，相對誤差為0.0014。圖4-4 用Daubechice小波壓縮后的重構(gòu)信號3） 比較1）和2）的壓縮效果可以看出，對于同一

8、種小波，保留更多的變換后的系數(shù)可以得到更好的重構(gòu)信號。對于相同比例的保留系數(shù)，用Daubechice小波分解信號，再重構(gòu)，得到的效果好于Haar小波。這是因為Daubechice小波的連續(xù)性較好，更適合處理連續(xù)性較好的信號。4) 用FFT對信號進行處理。令絕對值最小的80%的系數(shù)為0，則重構(gòu)信號的圖形如圖4-5a所示。得到均方誤差為0.0025，相對誤差為1.59。圖4-5 用FFT壓縮后的重構(gòu)信號注釋：上兩例是說明用小波處理信號的基本過程和在壓縮中的應(yīng)用，并不是想與FFT比較誰的效果好。實際上，這里采用的信號周期性很好（正弦波的疊加），用傅立葉變換處理更有優(yōu)勢。一般地，小波更適合處理突變信號

9、，而傅立葉變換更適合處理周期信號。4.2 多孔算法l Mallat算法存在的問題是數(shù)據(jù)逐級減少問題。原因是逐級二抽樣，每經(jīng)過一級小波分解，數(shù)據(jù)減少一半，因此，隨著分辨率減少，低頻分量的數(shù)據(jù)越來越少。l 多孔算法（非抽樣小波變換或平穩(wěn)小波變換）兩通道Mallat算法等價的z變換如圖47表示。記，l 二分樹算法Mallat算法的小波分解迭代過程如圖4-8所示。其中，l z變換的等效易位性質(zhì)：因為左邊 右邊 圖4-9 Mallat 算法的一種等效形式如果不考慮每個分支的最后的抽樣環(huán)節(jié)，則，相當于中各點的小波變換全部計算出來，這叫非抽樣小波變換。如圖4-9所示。表示在濾波器的任意兩點間插入個零所得到的

10、濾波器Z變換，所以，非抽樣小波變換就是把濾波器，個相鄰點之間插入個零再與低頻信號做卷積，故稱多孔算法。是將每兩個點之間插入三個零得到的新濾波器，是將每兩個點之間插入一個零得到的新濾波器，這樣就把每一級的抽取移到了最后，保證了總數(shù)據(jù)不會逐級減少，有效地實現(xiàn)了Mallat算法。由于和是使，中補零 ，增加了空隙，故稱多孔算法。設(shè)原始信號的長度為，記，根據(jù)下面的分解算法： （4-1）計算各抽樣點處的小波變換，（）的偽碼程序：從多孔算法的分解過程（式（4-1）可知，于是，由完全重構(gòu)條件（式（3-34）可得 （4-2）4.3 小波變換的提升實現(xiàn)優(yōu)點（1）可以實現(xiàn)更快速的小波變換算法，一般比Mallat算法

11、快2倍。（2）可以實現(xiàn)完全的同址運算。（3）能很好地克服小波變換的邊界問題。（4）提升算法小波變換的描述簡單，可以避免使用傅里葉變換。（5）在時域或空域直接實現(xiàn)小波構(gòu)造，既工程師可以按著自己的要求來構(gòu)造不同的小波，不再緊緊依賴數(shù)學(xué)家。4.3.0小波變換的提升實現(xiàn)l 回顧 Haar小波變換按著Haar小波濾波器組，兩個數(shù)a,b的平均與細節(jié)分別為于是，的小波變換為。如果，高度相關(guān)，則很小。由恢復(fù)的計算公式如下：對于長度為的信號，將求平均與細節(jié)運算應(yīng)用到每對數(shù)據(jù)，上，記 （1-45）這里是將信號序列的偶序號點和奇序號點相加取平均得平均值；將奇序號點減去偶序號點得到差值。和各有個樣本，看作是信號的概貌

12、和細節(jié)。當遍歷0到之間的所有整數(shù)時，組成序列，可以對進行類似的分解，得到和，它們各有個樣本，組成了序列。這樣的分解可以進行次，最后的概貌信號只有一個點，它是信號的均值或直流分量。最后的概貌信號加上各級細節(jié)信號，正好是個。上述變換正是Haar小波變換。多級Haar小波變換的分解過程和重構(gòu)過程如下圖。圖1-21 多級小波變換過程示意圖l （1.8.2） Haar小波變換的提升實現(xiàn)小波變換的原位實現(xiàn)（in-lplace）-不增加額外空間（1） d=b-a （先將d 存于原來b的位置） （2） s =a+d/2 (s=a+d/2=a+b/2- a/2= (a+b)/2) （再計算s 存于原來a 的位置

13、）l 提升算法中的信號分解提升過程分為三步：分裂、預(yù)測和更新?？紤]信號，提升算法分三步完成（1）Split(分裂)將信號簡單地分為兩部分，有多種方法，這里將信號序列按奇、偶分為兩個子集： 只將完整信號序列分成二部分，不做其他處理，故稱懶小波變換。這里Split是分裂算子。這種分解方法可表示為 注釋：將信號分解為成兩個序列的方法有很多，將信號序列按奇、偶分為兩個子集是一種方法；或?qū)⑶耙话牒秃笠话敕殖蓛蓚€子集也是一種方法；或?qū)⑾噜弮蓚€數(shù)之和分給一個子集，而相鄰兩個數(shù)之差分給另一個子集又是一種方法?？傊煌姆至逊椒ǎ喈斢诓捎貌煌男〔ɑ?。實際應(yīng)用中，最常用的是懶小波最為第一級分解。（2）Pre

14、dict(預(yù)測) 若原信號具有局部相關(guān)性，則子集和也具有相關(guān)性。因此，只要知道其中任一個，就可以以合理地精度預(yù)測另一個，通常用偶子集預(yù)測奇子集。在Haar小波變換的情況下，預(yù)測誤差為，特別地，如果原信號是一個常量，則所有預(yù)測誤差均為零。一般情況，定義預(yù)測算子P，且表示用值的某種運算或某種組合來預(yù)測的值。在Haar小波變換的情況下，簡單地選擇偶次項，去減奇次項，得差值。預(yù)測誤差表示信號的細節(jié)信息。這一步驟在提升算法中被成為“對偶提升”。當信號的相關(guān)性較大時，預(yù)測是非常有效的，若信號為常數(shù)時，恒為零。（3）Update（更新） 低頻概貌信號的一個關(guān)鍵性質(zhì)是，它與原信號應(yīng)具有相同的平均值，即，并且不

15、隨變化。這能確保最后的變換系數(shù)是原信號的總平均。Update操作可保證該性質(zhì)成立，既用細節(jié)信息子集來更新偶序號子集，既式中U為更新算子，表示對的某種運算或某種組合。對于Haar小波，可以簡單地用預(yù)測誤差信號更新偶子集信號，既。在提升算法中，更新稱為“原始提升”，故才有“提升算法”一詞。容易驗證，以上三步操作相當于對信號進行一級小波變換，將它分解為低頻信號和細節(jié)信號。一般地，對于提升算法存在分裂算子Split、預(yù)測算子P和更新算子U，使上述所有操作可以實現(xiàn)原位實現(xiàn)，即偶數(shù)位置用平均值重寫，奇數(shù)位置用細節(jié)重寫。偽碼實現(xiàn)：提升方案實現(xiàn)小波分解的最大優(yōu)點在于將小波分解成了幾個簡單的基本步驟，且每個步驟

16、都非常容易找到它的逆變換。l 提升算法中信號的重構(gòu)過程（三個過程）相反地，從低頻信號和細節(jié)信號恢復(fù)原信號的提升算法為(1)反更新給定和，可由下式恢復(fù)出偶序號序列 （2）反預(yù)測用反更新計算出的偶序號序列和給定的細節(jié)，可通過下式預(yù)測出奇序號序列 （3）合并通過反更新和反預(yù)測步驟，分別獲得偶序號序列和奇序號序列，將它們合并即可恢復(fù)原信號。這一步驟稱為 ，記作 逆懶小波變換對于Haar小波，恢復(fù)4.3.1小波分解與重構(gòu)的多相位表示討論有限沖激響應(yīng)的雙正交濾波器的情況。設(shè)、為雙正交小波濾波器組，對應(yīng)二通道Mallat算法的等價Z變換如圖4-7所示。從圖3-2到圖3-3，是將時域表示成z域，圖中與時域中時

17、序反轉(zhuǎn)相對應(yīng)。l 兩通道分析濾波器和綜合濾波器在理想重構(gòu)條件下，、的約束條件設(shè)是一個信號序列， z變換為。當是一個有限序列時，稱是一個Laurent多項式（將實數(shù)下的泰勒公式推廣到復(fù)數(shù)）。 設(shè)小波濾波器的Z變換為。可推出。同理，。另外，由于與的巻積的Z變換等于它們Z變換的乘積，既于是，圖3-2的濾波器組的等價的Z變換形式如圖3-3。令，則根據(jù)二元下采樣的定義，有從而（和表示了二元下采樣） （圖3-3）的結(jié)果又，故（反映了兩個元素之間插入一個零）類似地，有因此，之前第1個求和項應(yīng)等于1，是確保的一個條件；必須消除由引起的混疊，既第2個求和項應(yīng)消除。于是，濾波器組對任何輸入信號實現(xiàn)精確重構(gòu)，下式是

18、二通道濾波器組完全重構(gòu)條件，既PR (Perfect Reconstruction)條件。 （3-34）l PR條件的矩陣形式：當矩陣的行列式時，綜合濾波器、完全由分析濾波器、確定。于是，所以， （3-35）將式（3-35）代入式（3-34），并注意到，可得 （3-36）表明，當時，完全重構(gòu)條件等價于重構(gòu)條件式（3-35）和式（3-36）同時成立。l 有限長度濾波器的完全重構(gòu)條件：對于有限長濾波器，根據(jù)定義，是Z的Laurent多項式，而由式（3-35）知，也是Z的Laurent多項式，因此，必是一個單項式。又因為，故是一個奇數(shù)次的單項式，既代入式（3-35），整理得， （3-37）¨

19、; 一種取法是，于是式（3-37）變?yōu)椋?（3-38）¨ 另一種取法是，于是式（3-37）變?yōu)椋?（3-39）按式（3-38），有限長度濾波器的完全重構(gòu)條件為 （3-40） l 多相表示的基本思想：¨ 一個多相表示的例子對于多項式 =取M=2，可寫成=用替換，得這就是多項式的兩相表示。¨ 設(shè)濾波器，將其分裂成的偶次冪和奇次冪二部分： 定義，和則 ， （4-4）從而有 （4-3）其中，包含了的所有偶系數(shù)，而包含了的所有奇系數(shù)。更進一步，任一給定整數(shù)，可將分解成模不同余數(shù)次冪的部分。即： +可簡潔地寫為：-第一類多相表示；式中，是第一類多相表示的元素，對于因果序列，求

20、和下限可從0開始。定義和的多相位矩陣為 （4-7）于是，類似地，和的多相位矩陣為 （4-8）同理， 因此，小波重構(gòu)的完全條件式（3-34）可以寫成 （4-9）其中，表示矩陣的轉(zhuǎn)置矩陣，為單位陣。l 小波分解與重構(gòu)的多相位表示解釋圖4-11和圖3-3的等價性。設(shè)輸入序列的Z變換為,則流程圖(圖4-12)的作用相當于對進行懶小波變換 , 即抽取的偶序列和奇序列,Z變換分別為設(shè)這兩個Z變換經(jīng)作用后的低頻和高頻部分分別為和，則=可以驗證與圖3-3的結(jié)果一樣。也可作此驗證。4.3.2 Laurent多項式的Euclidean算法l 由于、都是有限長的小波濾波器，所以和的行列式和都是Laurent多項式。

21、由式知，及其倒數(shù)都是Laurent多項式，故為Z的單項式。設(shè)=1，我們根據(jù)小波分解和重構(gòu)的多相位表示，通過對多相位矩陣進行因子分解，給出小波變換的實現(xiàn)算法。l 有限沖激響應(yīng)濾波器FIR可以描述為一系數(shù)集，范圍為。FIR濾波器的Z變換是一個Laurent多項式，既于是，的次數(shù)為因此，濾波器的長度等于其相應(yīng)Laurent多項式的次數(shù)加1。l 兩個Laurent多項式的帶余數(shù)除法對于任何兩個Laurent多項式和，其中，一定存在Laurent多項式的（商）和（余數(shù)），使成立。其中，或。兩個Laurent多項式的商和余數(shù)不是唯一的。例如，對于，則對于以下幾種情況：1），。2），3），都滿足，且。l E

22、uclidean算法如下：利用帶余數(shù)除法，可以給出Laurent多項式的Euclidean算法。對于任何兩個Laurent多項式和，其中，且。設(shè)=，=，從開始進行如下的遞歸運算：其中，%是表示取“余數(shù)”運算。則，且是一個Laurent多項式，下標是使的最小數(shù)，“”表示取最大公因子。假設(shè)，則存在m使得=0，因此，算法在步驟結(jié)束，其中，。若記，其中，“/“表示取商運算，則有=這等價于=顯然，同時整除和。如果是一個單項式，則和是互為素數(shù)的。 例4.3 ，則由第一步帶余除法，可得下一步帶余數(shù)除法，給出所以，和是互為素數(shù)的，且輾轉(zhuǎn)除法的步數(shù)為。4.3.3 多相位矩陣的因子分解下面的定理奠定了小波提升實現(xiàn)

23、的基礎(chǔ)。l 定理 4.1 若的行列式等于1，既，則總存在Laurent多項式和及非零常數(shù)，使得 （4-10）其中，=0.定理證明略。主要介紹提升因子和的計算方法。首先，對和應(yīng)用Euclidean算法，可得到記注意到=則由式（4-10）可得，其中。若記=，則=于是，有=所以，于是，有l(wèi) 算法4.1 有限沖激響應(yīng)濾波器FIR多相位矩陣的提升分解算法第1步 ，使用Euclidean算法得到第2步，計算第3步，計算例4.4 Haar小波濾波器的多相位矩陣分解。由=，可得，所以，Haar小波濾波器的多相位矩陣為，且=1令，由，得，因故，故=其中，。得： =所以， =0故 4.3.4 提升算法由（4-10

24、）及式（4-9）可推出， （4-11） (4-12)根據(jù)式（4-12）修改圖4-11中小波分解部分，可得到基于提升的正向小波變換的流程圖（4-13）.類似地，利用式（4-10）修改圖4-11中小波重構(gòu)部分，可得到基于提升的逆向小波變換的流程圖（4-14）l 提升算法的實現(xiàn)1. 時提升算法的實現(xiàn)設(shè)是長度為為偶數(shù)N的一個輸入信號，和表示它們的偶序列和奇序列信號。記若，分別表示序列，（）的Z變換，且則 用序列卷積可表示為其中，。l 算法4.2 正向小波變換的提升實現(xiàn)算法設(shè)預(yù)測步驟由奇序列預(yù)測偶序列開始。步驟1 懶小波變換 ，步驟2 提升與對偶提升¨ For i=to m，步驟3比例變換&#

25、168; For to N/2-1最后得到的和分別為小波分解的低頻分量和高頻分量。其中，。在算法4.2中，懶小波變換對應(yīng)原信號的分裂；提升公式的意義在于用奇序列預(yù)測偶序列，而對偶提升公式的含義是用偶序列的預(yù)測誤差更新。通過若干次預(yù)測和更新過程，經(jīng)過比例變換，最后實現(xiàn)了信號的一級小波變換。 只要對正向小波變換按相反的次序進行操作，并改變正負號，立即得到逆變換。l 算法4.2*逆向小波變換的提升實現(xiàn)算法步驟1. 比例變換For l=0 to N/2-1步驟2 提升與對偶提升For i=m to 1，步驟3 逆懶小波變換，算法分析表明，當輸入數(shù)據(jù)量很大時，提升算法比Mallat算法的設(shè)計量減少一半。2. 時提升算法的實現(xiàn)當時，式（410），即變?yōu)槠渲?，記，于是，可表示為其中，從而，設(shè)是長度為的一個輸入信號，和表示它的偶序列和奇序列信號。若分別表示序列的Z變換，而記則由，則 （415）l 算法4.3正向小波變換的提升算法（預(yù)測步驟由偶序列預(yù)測奇序列開始）步