第7章_小波變換和多分辨率處理

1、小波和多分辨率處理 辛明琴Digital Image Processing, 3nd ed.12015/12/22小波變換是基于具有變化的頻率和有限持續(xù)時間的小型波進行的。它是多分辨率理論的分析基礎(chǔ)。本章將從多分辨率的角度解釋小波變換。介紹圖像編碼，噪聲去除和邊緣提取等一些應(yīng)用實例。2小波變換和傅里葉變換的區(qū)別 傅里葉展開函數(shù)是頻率變化及持續(xù)時間無限的正弦波；小波變換的展開函數(shù)是持續(xù)時間有限及頻率變化的小波。3主要內(nèi)容背景多分辨率展開一維小波變換快速小波變換二維小波變換小波包47.1背景Background從數(shù)學(xué)的觀點看，圖像是一個亮度值的二維矩陣，像邊界和對比強烈區(qū)域那樣的突變特性的不同組合

2、會產(chǎn)生統(tǒng)計值的局部變化。如圖7.1所示。圖7.1 一幅自然圖像和它的局部直方圖變化57.1.1 圖像金字塔圖像金字塔圖像金字塔是以多分辨率來解釋圖像的一種有效但概念簡單的結(jié)構(gòu)。圖7.2 (a) 一個金字塔圖像結(jié)構(gòu)67.1.1 圖像金字塔金字塔的底部是待處理圖像的高分辨率表示，而頂部是低分辨率的近似。當向金字塔的上層移動時，尺寸和分辨率就降低。圖7.2 (a) 一個金字塔圖像結(jié)構(gòu)77.1.1 圖像金字塔近似金字塔和預(yù)測殘差金字塔近似金字塔和預(yù)測殘差金字塔 如圖7.2(b) 框圖所表明的，近似值和預(yù)測殘差金字塔都是以一種迭代的方式進行計算。圖7.2 (b) 建立金字塔的方框圖87.1.1 圖像金字

3、塔傳遞由3個連續(xù)步驟組成：1.計算第j級輸入圖像降低的分辨率近似值。通過對輸入進行濾波并以2為因數(shù)進行下采樣實現(xiàn)。圖7.2 (b) 建立金字塔的方框圖97.1.1 圖像金字塔傳遞由3個連續(xù)步驟組成：2.由步驟1產(chǎn)生的降低分辨率近似創(chuàng)建第j級輸入圖像的一個估計。這通過對產(chǎn)生的近似與第j級圖像進行上采樣和濾波來完成。得到的預(yù)測圖像與第j級輸入圖像的維數(shù)相同7.1背景 Background圖7.2 (b) 建立金字塔的方框圖107.1.1 圖像金字塔傳遞由3個連續(xù)步驟組成：3.計算步驟2的預(yù)測圖像和步驟1的輸入之間的差異。把得到的結(jié)果放在預(yù)測殘差金字塔的第j級。圖7.2 (b) 建立金字塔的方框圖1

4、17.1.1 圖像金字塔例7.1 高斯和拉普拉斯金字塔圖7.3 兩種圖像金字塔及直方圖（a）近似金字塔（b）預(yù)測殘差金字塔127.1.2 子帶編碼子帶編碼子帶編碼是另一種與多分辨率分析相關(guān)的重要圖像技術(shù)。在子帶編碼中，一幅圖像被分解成為一系列頻帶受限的分量，稱為子帶。子帶可以重組在一起無失真地重建原始圖像。每個子帶通過對輸入圖像進行帶通濾波而得到。137.1.2 子帶編碼圖7.6(a)顯示了兩段子帶編譯碼系統(tǒng)的基本部分。圖7.6 （a）一維子帶編碼和解碼的兩頻帶濾波器組，（b）頻譜分離特性14目的：選擇濾波器，以便子帶編碼和解碼系統(tǒng)的輸入和輸出是相同的。最終采用了完美重建濾波器。157.1.2

5、 子帶編碼7.1.2 子帶編碼 一維濾波器也可用于圖像處理的二維可分離濾波器。如圖7.7所示?？煞蛛x濾波器首先應(yīng)用于某一維(如垂直向)，再應(yīng)用于另一維(如水平向)。167.1.2 子帶編碼例7.2 圖7.1中花瓶的4頻段子帶編碼 圖7.9顯示圖7.1中花瓶的512512圖像基于圖7.6濾波器的4頻段分離（a）近似子帶（b）水平細節(jié)子帶（c）垂直細節(jié)子帶（d）對角線細節(jié)子帶177.1.3 哈爾變換哈爾變換(Haar)是與多分辨率分析有關(guān)的圖像處理手段之一。哈爾變換可以用下述矩陣形式表達：T=HFHT 其中，F(xiàn)是一個NN圖像矩陣，H是NN變換矩陣，T是NN變換的結(jié)果。(7.1.15)187.1.3

6、 哈爾變換哈爾變換的變換矩陣H包含哈爾基函數(shù)hk(z)，它們定義在連續(xù)閉區(qū)間z0,1，k=0,1,2,N-1，這里N=2n。為生成H矩陣，定義整數(shù)k，即k=2p+q-1(這里0pn-1, p=0時，q=0或1，p0時， 0q2p)。 可得哈爾基函數(shù)為： 1 , 0 1)()(000zNzhzh(7.1.16)197.1.3 哈爾變換且 1 , 0 , 02/)/25 . 0( 22/ )5 . 0()/21( 21)()(22zotherwiseqzq-qzq-Nzhzhpppppppqk(7.1.17) NN哈爾變換矩陣的第i行包含了元素hi(z)，其中z=0/N，1/N，2/N，(N-1)

7、/N。207.1.3 哈爾變換例如，N=4時，k，q和p值如下：2200002211121111 41 4H(7.1.19) 44哈爾變換矩陣H4217.1.3 哈爾變換22哈爾變換矩陣H41111 21 2H(7.1.18) 它的基函數(shù)僅定義了2抽頭完美重建濾波器組的分析濾波器h0(n)和h1(n)。227.1.3 哈爾變換例7.3 離散小波變換的哈爾函數(shù) （a）用H2哈爾基函數(shù)的離散小波變換 （b）（d）由（a）得到的幾種不同 的近似（64*64,128*128,256*256）237.2 多分辨率展開在多分辨率分析( MRA )中，尺度函數(shù)尺度函數(shù)被用于建立某一函數(shù)或圖像的一系列近似值，

8、相鄰兩近似值之間的近似度相差2倍。被稱為小波小波的附加函數(shù)用于對相鄰近似值之間的差異進行編碼。247.2.1 級數(shù)展開 信號或函數(shù)常?？梢员缓芎玫胤纸鉃橐幌盗姓归_函數(shù)的線性組合(7.2.1)(7.2.2)(7.2.3) 展開集合的閉合跨度，表示為：)(anSpxVkkkkkxxf)()(xxfxxfxkkkd)()()(),(*257.2.1 級數(shù)展開 由于展開集合的正交性，該計算可以是3種可能形式中的一種。 情況1：如果該展開函數(shù)構(gòu)成了V的一個正交基，即：(7.2.4)(7.2.5) 基與它的對偶相等。即：kjkjxxjkkj 1 0)(),()()(xxkk)(),(xfxkk267.2.

9、1 級數(shù)展開 情況2：如果該展開函數(shù)本身不正交，而是V的正交基，則：(7.2.6)(7.2.7)kjxxkj 0)(),(kjkjxxjkkj 1 0)(),( 基函數(shù)及其對偶稱為雙正交。使用式(7.2.3)計算 ，有：k277.2.1 級數(shù)展開)()(),(1)(xxfxAxfkkk222|)(|)(),(|)(|xfBxfxxfAkk 情況3：如果展開集合對V來說不是函數(shù)基，但支持式(7.2.1)中定義的展開，那么它是一個跨度集合，對于任一f (x)V有一個以上k集合。展開函數(shù)及其對偶稱為超完備或冗余。它們組成了一個框架，其中：(7.2.8)(7.2.9) 對于某些A0，B=j0 (7.3

10、.6)(7.3.7)477.3.2 離散小波變換例7.8計算一維離散小波變換考慮四點的離散函數(shù)： f(0)=1，f(1)=4，f(2)=-3和f(3) = 0。因為M=4，J=2且由于j0=0，對x=0，1，2，3，j=0，k=0，或者對于j= 1，k=0求和。將使用哈爾尺度和小波函數(shù)，并假定f(x)的4個采樣值分布在基函數(shù)的支撐區(qū)上，基函數(shù)的寬度為1。將4個采樣點代入式(7.3.5)，可得： 1 10131411 21)()(21)0 , 0(0, 030 xxfWx487.3.2 離散小波變換例7.8計算一維離散小波變換這里采用的是哈爾尺度函數(shù)對于j=0且k=0的均勻空間采樣。該值對應(yīng)于7

11、. 1.3節(jié)的哈爾變換矩陣H4的第一行。繼續(xù)使用式(7.3.6)和相似間隔的采樣點j,k (x)(它對應(yīng)于H4的第2,3,4行)，可得：4)1(0) 1(31411 21)0 , 0(W25 . 10003)2(421 21)0 , 1 (W25 . 1)2(0230401 21) 1 , 1 (W497.3.2 離散小波變換例7.8計算一維離散小波變換式(7.3.7)允許從變換中恢復(fù)出原始函數(shù)。重復(fù)求和，可得：)() 1 , 1 ()()0 , 1 ()()0 , 0()()0 , 0(21)(1 , 10 , 10 , 00 , 0 xWxWxWxWxf1025 . 1)2(25 . 11

12、411 21)0(f x=0，1，2，3。如果x=0 與正變換情況一樣，尺度和小波函數(shù)的均勻空間采樣也用于反變換的計算。507.3.3 連續(xù)小波變換連續(xù)小波變換(CWT)是離散小波變換的自然延伸，將一個連續(xù)函數(shù)變換成兩個連續(xù)變量(變換和尺度)的高冗余度函數(shù)。變換結(jié)果在時頻分析上很容易解釋并有很大價值。連續(xù)的平方可積函數(shù)f(x)的連續(xù)小波變換與實數(shù)值的小波(x)的關(guān)系如下：xxxfsWsd)()(),(,)(1)(,0,sxsxkjs(7.3.8)(7.3.9)517.3.3 連續(xù)小波變換s和分別稱為尺度參數(shù)尺度參數(shù)和平移參數(shù)平移參數(shù)。給定W(s，) ，可以通過反連續(xù)小波變換求得f(x)： 02

13、,dd)(),(1)(ssxsWCxfsuuuCd| )(|2(7.3.10)(7.3.11)527.3.3 連續(xù)小波變換例7.9 一維連續(xù)小波變換墨西哥草帽小波：22241)1 (32)(xexx(7.3.12)537.3.3 連續(xù)小波變換例7.9 一維連續(xù)小波變換（a）小波函數(shù)（b）尺度化小波和傅里葉頻譜關(guān)系（c）CWT一部分（d）小波函數(shù)灰度圖)()()(80, 610, 1xxxf547.4 快速小波變換快速小波變換(FWT)是一種實現(xiàn)離散小波變換(DWT)的高效計算，該變換找到了相鄰尺度DWT系數(shù)間的關(guān)系。它也稱為Mallat人字形算法。nnxnhx)2(2)()( 用2j對x進行尺

14、度化，用k對它進行平移，令m=2k+n，得：mjnjjmxkmhnkxnhkx)2(2)2()2(2(2)()2(1(7.4.1)(7.4.2)557.4 快速小波變換mjjmxkmhkx)2(2)2()2(1(7.4.3)567.4 快速小波變換mmjWkmhkjW), 1()2(),(), 1()2(),(mjWkmhkjWm第7章 小波變換和多分辨率處理(7.4.7)(7.4.8)(7.4.9)0,2| ), 1()(),(kknnjWnhkjW(7.4.10)0,2| ), 1()(),(kknnjWnhkjW7.4 快速小波變換圖7.17 一個FWT分析濾波器族 注意圖7.17中的濾

15、波器族可以迭代產(chǎn)生多階結(jié)構(gòu)，用于計算兩個以上連續(xù)尺度的DWT系數(shù)。587.4 快速小波變換圖7.18 （a）一個兩階或兩尺度FWT分析濾波器族，（b）它的頻率分離特性 例如，圖7.18(a)顯示了一個用于計算變換的兩個最高尺度系數(shù)的二階濾波器族。注意，最高的尺度系數(shù)假定是函數(shù)自身的采樣值。597.4 快速小波變換例7.10 計算一維小波變換 離散函數(shù)f(n)=1,4,-3,0；otherwisennh 0 1 , 0 21)(otherwisennnh 0 1 210 21)(1 , 01 , 00,20,2| ) 12(21)2(21| )()2(| )()(| ), 2()(), 1 (k

16、lkkknkknkxkxlxlkhnfnhnWnhkW(7.4.13)(7.4.14)607.4 快速小波變換例7.10 計算一維小波變換圖7.19 使用哈爾尺度和小波向量計算序列1,4，-3,0的二尺堵快速小波變換617.4 快速小波變換從DWT/FWT的近似值和細節(jié)系數(shù)重建f(x)也存在一種高效的反變換，稱為快速小波反變換(FWT-1)。它使用正變換中所用的尺度和小波向量以及第j級近似值和細節(jié)系數(shù)來生成第j+1級近似值系數(shù)。注意到圖7.17中FWT分析部分和圖7.4(a)中兩頻段子帶分析部分的相似性，可以立即得出要求的FWT-1的綜合濾波器族。627.4 快速小波變換圖7.20 FWT-1

17、 的綜合濾波器族 圖7.20中的FWT-1的濾波器族執(zhí)行下述計算：0upup| ),()(),()(), 1(kkjWkhkjWkhkjW(7.4.15)637.4 快速小波變換1FWT 與FWT-1正變換類似，反變換濾波器族可以如圖7.21所示進行迭代，為了計算FWT-1重建的最后兩個尺度描繪了兩尺度結(jié)構(gòu)。該系數(shù)合并過程可以擴展到任意數(shù)目的尺度，從而保證函數(shù)f(x)的完美重建。 圖7.21 一個兩級或二尺度FWT-1綜合濾波器組647.4 快速小波變換例7.11 計算一維快速小波反變換圖7.22 用哈爾尺度和小波向量計算序列 的兩尺度快速小波反變換1,4, 1.5 2, 1.5 265FWT

18、和FFT之間的區(qū)別(1)計算上的復(fù)雜性計算上的復(fù)雜性：包括在長度為M=2J的序列的FWT計算中的數(shù)學(xué)運算次數(shù)是O(M)階。也就是說，浮點乘法和加法(使用濾波器族)的次數(shù)與序列的長度存在線性關(guān)系。這與FFT算法比較是有利的，F(xiàn)FT需要O(MLogM)階。66FWT和FFT之間的區(qū)別(2)變換的基函數(shù)：變換的基函數(shù)：傅里葉的基函數(shù)(即正弦函數(shù))保證了FFT的存在，而FWT的存在取決于使用的小波尺度函數(shù)是否可用，以及尺度函數(shù)和相應(yīng)的小波的正交性(或雙正交性)。因此，式(7.3.12)的墨西哥草帽小波不能用于計算FWT，因為它沒有相應(yīng)的尺度函數(shù)。換句話說，不能為墨西哥草帽小波建立一個像圖7.15中那樣

19、的濾波器族；它不滿足FWT方法的基本假設(shè)。67FWT和FFT之間的區(qū)別(3)不可分割的關(guān)系：不可分割的關(guān)系：如果試圖同時在時域和頻域內(nèi)對函數(shù)進行分析，就會遇到如下問題：如果想要關(guān)于時域的有價值信息，就要忍受頻域的含糊，反之亦然。這是海森伯(Heisenberg)測不準原理在信息處理中的應(yīng)用。為了用圖示說明該原理，函數(shù)表達中用到的每個基函數(shù)都被概要地看成是時間頻率平面的一個塊。該塊也稱為海森伯單元或海森伯盒，顯示了基函數(shù)能量的集中區(qū)域。塊不重疊是正交基函數(shù)的特點。687.4 快速小波變換圖7.23 時間一頻率片 （a）傳統(tǒng)時域（b）FFT與FWT相關(guān)的基函數(shù)（c）中等高度矩形的水平條帶表示FWT

20、尺度697.5 二維小波變換 , x yxy一維變換很容易像圖像那樣擴展到二維函數(shù)。乘積產(chǎn)生可分離的尺度函數(shù)：)()(),(yxyxH(7.5.1)(7.5.2)()(),(yxyxV)()(),(yxyxD 可分離的“方向敏感的”小波，沿著不同方向的圖像強度或灰度的變化：(7.5.3)(7.5.4)707.5 二維小波變換 給定可分離的二維尺度和小波函數(shù)，一維DWT到二維的擴展很簡單。首先定義一個尺度和平移基函數(shù)：)2 ,2(2),(2/,nymxyxjjjnmj(7.5.5)(7.5.6),),2 ,2(2),(2/,DVHinymxyxjjijinmj717.5 二維小波變換則尺寸為MN

21、的函數(shù)f(x,y)的離散小波變換是：1010.,0),(),(1),(0MxNynmjyxyxfMNnmjW(7.5.7)(7.5.8),),(),(1),(1010,DVHiyxyxfMNnmjWMxNyinmji 727.5 二維小波變換f(x,y)可通過離散反小波變換得到：(7.5.9) DVHijjm ninmjim nnmjyxnmjWMNyxnmjWMNyxf,0,00),(),(1),(),(1),( 類似一維離散小波變換，二維DWT可以用數(shù)字濾波器和抽樣來實現(xiàn)。737.5 二維小波變換圖7.24 二維快速小波變換（a）分析濾波器族747.5 二維小波變換圖7.24 二維快速小波

22、變換（b）分解結(jié)果757.5 二維小波變換圖7.24 二維快速小波變換（c）綜合濾波器族767.5 二維小波變換77圖7.25 計算二維三尺度FWT（a)原圖像 (b)一尺度FWT(c)二尺度FWT (d)三尺度FWT例7.12 計算二維快速小波變換7.5 二維小波變換圖7.26 四階對稱小波。（a）-（b）分解濾波器，（c）-（d）重建濾波器，（e）一維小波，（f）一維尺度函數(shù)，（g）三個二維小波之一，78 例7.12 計算二維快速小波變換7.5 二維小波變換小波在圖像處理中的用途，如在傅里葉域那樣，基本方法是：計算一幅圖像的二維小波變換修改變換計算反變換797.5 二維小波變換例7.13

23、基于小波的邊緣檢測圖7.27 改進的邊緣檢測DWT。（a）（c）選擇的 刪去系數(shù)的兩尺度分解，（b）（d）相應(yīng)的重建807.5 二維小波變換通常基于小波的對圖像去噪聲(即消除噪聲部分)的過程如下所示：1.為分解，選擇一個小波(如哈爾對稱小波)和級別數(shù)或尺度P。然后，計算噪聲圖像的FWT。2.門限化細節(jié)系數(shù)。即從尺度J-1到J-P選擇和應(yīng)用一個門限處理細節(jié)系數(shù)。這可以由硬門限實現(xiàn)，即元素絕對值比門限值低則置零，或由軟門限實現(xiàn)，即元素絕時值比門限值低則置為零，并且標定非零的系數(shù)接近零。軟門限去除了硬門限所固有的不連續(xù)性(在門限處)。3.基于原始的近似系數(shù)，在J-P級執(zhí)行小波重建，并對J-1到J-P

24、級改進細節(jié)系數(shù)。817.5 二維小波變換例7.14 基于小波的噪聲去除圖7.28 對噪聲去除改進DWT。（a）人體頭部的 帶 噪 聲 的M R I 圖 像 ，（b），（c）和（e）門限化細節(jié)系數(shù)后的各 種 重 建 ，（d）和（f）在（c）和（e）重建時移去的信息827.6 小波包快速小波變換將一個函數(shù)分解為一系列與對數(shù)相關(guān)的頻段。即低頻被組成窄頻段，高頻被組成寬頻段。它規(guī)定了通常所說的恒定Q濾波器，如果想要較大地控制時頻平面的一部分(即高頻較相似的頻段)，F(xiàn)WT必須由更靈活的分解稱為小波包的產(chǎn)生。過程的代價是FWT計算復(fù)雜性的增加，從O(M)到O(MlogM)。837.6 小波包 圖7.29(

25、a)的兩尺度濾波器族的圖示分解是一個二叉樹。圖7.29(b)詳細敘述了樹的結(jié)構(gòu)并將合適的FWT尺度和小波系數(shù)連接到它的節(jié)點。根節(jié)點被賦予最高的尺度近似系數(shù)，它是函數(shù)自身的取樣，但葉子繼承變換的近似和細節(jié)系數(shù)的輸出。847.6 小波包 這些概念進一步說明于圖7.30，其中，描繪了一個三尺度FWT分析族、分析樹和相應(yīng)的頻譜。857.6 小波包11JJJWVV122JJJJWWVV1233JJJJJWWWVV 分析樹提供了表示多尺度小波變換的緊湊和有益的方法。它們比相對應(yīng)的濾波器和基于子取樣的方框圖容易畫并占有較少的空間，使它相對容易定位有效的分解。 例如，圖7.30(b)的三尺度分析樹提供了下列三

26、種展開選擇：867.6 小波包 分析樹還是表示小波包的有效機理，它們比在細節(jié)是迭代濾波器的傳統(tǒng)小波變換更簡單。 這樣，圖7.30(b)的三尺度FWT分析樹變成圖7.31的三尺度小波包樹。877.6 小波包 圖7.31中的三尺度小波包樹幾乎是三尺度FWT樹的有效分解(和相關(guān)的時間-頻率片)數(shù)目的三倍。回顧在正常的FWT中，進行分離、濾波，并且單獨對低通波段進行抽樣。這將在頻率波段間生成一個固定的對數(shù)函數(shù)關(guān)系。因此，當圖7.30(a)中的三尺度FWT分析樹提供三種可能的分解的時候見式(7.6.1)到式(7.6.3) 圖7.29的小波包樹支持26種不同的分解。例如，VJ及函數(shù)f(n)可以進行如下擴展

27、：DDJDAJADJAAJDJAJJJJWWWWWWWVV, 1, 1, 1, 1, 2, 233887.6 小波包它們的頻譜如圖7.30( b)中所示，或者：ADJAAJDJJJWWWVV, 1, 1, 11 它們的頻譜在圖7.31中進行了描述。注意，最后的頻譜和圖7.30的完全包頻譜或圖7.28(c)的三尺度FWT頻譜之間的區(qū)別。一般來說，P尺度、一維小波包變換(和P+1層分析樹相關(guān))支持惟一的分解，這里D(1)=1。1)() 1(2PDPD897.6 小波包90圖7.32 三尺度完全小波包分析樹的 （a）濾波器組（b）頻譜分離特性7.6 小波包圖7.33 式 中分解的頻譜圖7.34 一個二維FWT的第一次分解（a）頻譜，（b）子空間分析樹11,1,1,jjjDjAAjADVVWWW917.6 小波包 圖7.35顯示了一個三尺度、二維小波包分析樹的一部分。像圖7.31中它對應(yīng)的一維部分一樣、傳統(tǒng)FWT細節(jié)節(jié)點下一代的每一個節(jié)點的第一