第二章傅里葉變換

1、數(shù)字圖像處理技術(shù)數(shù)字圖像處理技術(shù)Digital Image Processing Technique吳昊天吳昊天E-mail: 2第二章第二章 圖像變換技術(shù)圖像變換技術(shù)要點：要點：1. 主要介紹圖像處理重要的工具主要介紹圖像處理重要的工具 傅里葉變換傅里葉變換.2. 傅立葉變換在圖象處理中的意義是什么傅立葉變換在圖象處理中的意義是什么?3. 什么是高頻、中頻和低頻成分，它們分別對應(yīng)空間域圖像的哪些部分什么是高頻、中頻和低頻成分，它們分別對應(yīng)空間域圖像的哪些部分?4. 什么是卷積定理，它在圖象處理中的作用是什么什么是卷積定理，它在圖象處理中的作用是什么?5. 傅立葉變換的性質(zhì)。傅立葉變換的性質(zhì)。

2、31822年，傅立葉（年，傅立葉（Fourier）發(fā)表了發(fā)表了“熱傳導(dǎo)解析理論熱傳導(dǎo)解析理論”，提出了傅，提出了傅立葉變換。它本質(zhì)上提出了一種與空間思維不同的頻域思維方法。立葉變換。它本質(zhì)上提出了一種與空間思維不同的頻域思維方法。傅立葉變換是十九世紀數(shù)學(xué)界和工程界最輝煌的成果之一。它一直是傅立葉變換是十九世紀數(shù)學(xué)界和工程界最輝煌的成果之一。它一直是信號處理領(lǐng)域中最完美、應(yīng)用最廣泛、效果最好的一種分析手段。它信號處理領(lǐng)域中最完美、應(yīng)用最廣泛、效果最好的一種分析手段。它也是線性系統(tǒng)分析的有利工具。也是線性系統(tǒng)分析的有利工具。傅立葉變換能使我們從空間域（或時域）與頻率域兩個不同的角度來傅立葉變換能使

3、我們從空間域（或時域）與頻率域兩個不同的角度來看待信號或圖象的問題。有時在時域無法解決的問題，在頻域卻是顯看待信號或圖象的問題。有時在時域無法解決的問題，在頻域卻是顯而易見的。而易見的。 4n傅里葉分析中最重要的結(jié)論就是幾乎傅里葉分析中最重要的結(jié)論就是幾乎“所有所有”的函數(shù)的函數(shù)(信號信號)都可以表都可以表示為示為(分解成分解成)簡單的簡單的(加權(quán)加權(quán))正弦波和余弦波之和。從而提供了一種具正弦波和余弦波之和。從而提供了一種具有物理意義的函數(shù)表達方式。有物理意義的函數(shù)表達方式。設(shè)設(shè): f(x)是以是以T為周期的函數(shù)為周期的函數(shù), 滿足一定的條件滿足一定的條件, 例如絕對可積例如絕對可積, 則有則

4、有xTjkkkeaxf2 )(TxTjkkdxexfTa02)(156特別注意特別注意n傅傅氏級數(shù)中基底的物理意義非常明確氏級數(shù)中基底的物理意義非常明確, 每一個基函數(shù)都是一個單頻諧每一個基函數(shù)都是一個單頻諧波波, 而相應(yīng)的系數(shù)而相應(yīng)的系數(shù)(頻譜頻譜)表明了原函數(shù)對這種頻率成份貢獻的大小表明了原函數(shù)對這種頻率成份貢獻的大小(原原函數(shù)在這個諧波上的投影函數(shù)在這個諧波上的投影), 或者說原函數(shù)中某種頻率成分的多少或者說原函數(shù)中某種頻率成分的多少.n從圖像從圖像(信號信號)處理的角度處理的角度, 利用諧波的物理性質(zhì)可以通過對系數(shù)的處理利用諧波的物理性質(zhì)可以通過對系數(shù)的處理達到對圖像的處理達到對圖像的

5、處理, 如增強、壓縮等等如增強、壓縮等等.nf(x)傅傅氏系數(shù)氏系數(shù)ak的計算的計算, 需要用到函數(shù)在整個空間需要用到函數(shù)在整個空間(或時間或時間)上的分布情上的分布情況況.TxTjkkdxexfTa02)(17一維傅里葉變換及反變換一維傅里葉變換及反變換考慮定義在無窮區(qū)間連續(xù)函數(shù)的傅里葉變換公式考慮定義在無窮區(qū)間連續(xù)函數(shù)的傅里葉變換公式(通常函數(shù)要滿足一通常函數(shù)要滿足一定的條件才能保證傅里葉變換的存在性和收斂性定的條件才能保證傅里葉變換的存在性和收斂性):dxexfuFuxj2)()(dueuFxfuxj2)()(8連續(xù)情形的傅里葉變換比較方便用于公式推導(dǎo)和定理證明連續(xù)情形的傅里葉變換比較方

6、便用于公式推導(dǎo)和定理證明, 但在實際但在實際應(yīng)用中應(yīng)用中, 面臨更多也更實際的是離散的情況面臨更多也更實際的是離散的情況. 定義離散情形的傅里葉變換定義離散情形的傅里葉變換(DFT)公式公式: f(x)為離散函數(shù)為離散函數(shù), 其中其中x = 0, 1, , M-1.1, 1 , 0 )(1)(10/2MuexfMuFMxMuxj1, 1 , 0 )()(10/2MxeuFxfMxMuxj離散傅里葉變換和它對應(yīng)的反變換總是存在的離散傅里葉變換和它對應(yīng)的反變換總是存在的, 不必特地關(guān)心分析不必特地關(guān)心分析各項的意義各項的意義.9頻率域的概念頻率域的概念:利用歐拉公式利用歐拉公式: ej = cos

7、 + jsin , 有有101( )( )cos(2/)sin(2/)MxF uf xux Mjux MM其中其中u = 0, 1, 2, , M-1.變量變量u確定了變換的頻率成分確定了變換的頻率成分 u的取值范圍稱為頻率域的取值范圍稱為頻率域(給定一個給定一個u 上述公式可以計算出離散信號中包含了上述公式可以計算出離散信號中包含了“多少多少”這個頻率的諧波這個頻率的諧波).對每一對每一個個u, F(u)稱為變換的頻率分量稱為變換的頻率分量(也叫振幅也叫振幅). F(u)可以看作f(x)在諧波上的投影，即f(x)在頻率為u的諧波上占有的成份。10譜的概念譜的概念:注意到傅里葉變換后的函數(shù)是在

8、復(fù)數(shù)域內(nèi)注意到傅里葉變換后的函數(shù)是在復(fù)數(shù)域內(nèi), 也可以表示為也可以表示為F(u) = R(u) + iI(u)或極坐標的形式或極坐標的形式: F(u) = |F(u)|ej (u).我們把量我們把量|F(u)| = R2(u) + I2(u)1/2稱為傅里葉變換的幅度稱為傅里葉變換的幅度(Magnitude)或者譜或者譜(Spectrum). 這是在圖像處理中要經(jīng)常用到的量這是在圖像處理中要經(jīng)常用到的量. 譜可以表示原函譜可以表示原函數(shù)數(shù)(或圖像或圖像)對某一頻譜分量的貢獻對某一頻譜分量的貢獻.)()(arctan)(uRuIu稱為變換的相角或者相位譜稱為變換的相角或者相位譜, 用來表示原函數(shù)

9、中某一頻譜分量的起用來表示原函數(shù)中某一頻譜分量的起始位置始位置*.另外另外, 一個重要的量是功率譜一個重要的量是功率譜(有時也叫能量譜、譜密度有時也叫能量譜、譜密度)P(u) = |F(u)|2 = R2(u) + I2(u)11例例4.1 兩個簡單一維函數(shù)的傅里葉譜兩個簡單一維函數(shù)的傅里葉譜特征特征: (1) 當曲線下的面積在當曲線下的面積在x域加倍時域加倍時, 頻率譜的高度也加倍頻率譜的高度也加倍;(2) 當函數(shù)的長度加倍時當函數(shù)的長度加倍時, 相同長度區(qū)域內(nèi)的零點數(shù)量也加倍相同長度區(qū)域內(nèi)的零點數(shù)量也加倍. 極限情況極限情況? 12解釋解釋: 圖圖a函數(shù)的傅里葉變換為函數(shù)的傅里葉變換為:1

10、010/2)(1)(KxxuKxMuxjrMAAeMuF)(/2Mjer易見易見, 當當u = 0時時, ru = 1, 故而故而MAKMAuFKx 1)(10若若u 0, 則則ru 1, 對對u = 1, 2, , M-1,uuKKxxrrMArMAuF11 )()(10u利用歐拉公式可知利用歐拉公式可知: r = cos(2 /M) - jsin(2 /M).所以所以, 當當uK是是M的倍數(shù)時的倍數(shù)時, 就有就有ruK = 1(當然這時也有當然這時也有ru2K = 1 ), 從而從而F(u) = 0. 如果圖如果圖a中函數(shù)中函數(shù)f(x)非零點的個數(shù)是非零點的個數(shù)是K時時, F(u) = 0

11、的點數(shù)是的點數(shù)是n個個, 那么那么, 當當f(x)的非零點數(shù)是的非零點數(shù)是2K時時, F(u) = 0的點數(shù)應(yīng)該是的點數(shù)應(yīng)該是2n個個. 13關(guān)于變量的說明關(guān)于變量的說明:書中的記號書中的記號 f(x)(x = 0, 1, , M-1)表示從連續(xù)函數(shù)中取表示從連續(xù)函數(shù)中取M個樣點個樣點, 這些這些點不一定選取為區(qū)間點不一定選取為區(qū)間0, M-1中的整數(shù)點中的整數(shù)點. 通常用通常用x0(任意位置的任意位置的)表示第一表示第一個取樣點個取樣點, x是取樣間隔是取樣間隔. 所以所以, f(x)理解為理解為其中其中: u = 0, 1, , M-1.值得注意的是值得注意的是, 當當M固定時固定時, x

12、和和 u之間有如下的反比關(guān)系之間有如下的反比關(guān)系:)( )(0 xxxfxf其中其中: x = 0, 1, , M-1.同理同理, 變量變量u有相似的解釋有相似的解釋, 但序列通?？偸菑牡蛄型ǔ？偸菑?頻率開始頻率開始. 因此因此, u的取的取值序列為值序列為u = 0, u, 2 u, , (M-1) u. F(u)理解為理解為:)( )(uuFuFxMu114二維二維DFT及反變換及反變換 離散情形離散情形完全類似完全類似.設(shè)設(shè)f(x, y)是一幅尺寸為是一幅尺寸為MN的圖象函數(shù)的圖象函數(shù), 相應(yīng)的相應(yīng)的離散傅里葉變換離散傅里葉變換(DFT)可以表示為可以表示為: dxdyeyxfvuF

13、vyuxj)(2),(),( dudvevuFyxfvyuxj)(2),(),(1010)/(2),(1),(MxNyNvyMuxjeyxfMNvuF傅里葉譜傅里葉譜: |F(u, v)| = R2(u, v) + I2(u, v)1/2二維傅里葉變換本質(zhì)上是一維情形向兩個方向的簡單擴展二維傅里葉變換本質(zhì)上是一維情形向兩個方向的簡單擴展. 1010)/(2),(),(MuNvNvyMuxjevuFyxf15相角相角: (u, v) = arctan(I(u, v)/R(u, v)功率譜功率譜: P(u, v) = |F(u, v)|2 = R2(u, v) + I2(u, v)注意注意:為了把

14、變換后的中心移到圖像的中心為了把變換后的中心移到圖像的中心(M/2, N/2), 通常在變換通常在變換之前都要在函數(shù)上乘以之前都要在函數(shù)上乘以(-1)x+y. 這是由于這是由于傅傅里葉變換的平移性質(zhì)決定的里葉變換的平移性質(zhì)決定的, 以一維為例以一維為例:f(x)ej2 u0 x/M F(u - u0)f(x - x0) F(u)e-j2 x0u/M當當x0 = M/2或或u0 = M/2時時f(x)(-1)x F(u - M/2)f(x - M/2) F(u)(-1)u16對頻譜圖像的認識對頻譜圖像的認識?171010),(1)0 , 0(MxNyyxfMNF易見易見是圖像的平均灰度是圖像的平

15、均灰度. 因為在原點處兩個方向的頻率都為零因為在原點處兩個方向的頻率都為零, 所以所以, 這這個量經(jīng)常被稱為頻譜的直流分量個量經(jīng)常被稱為頻譜的直流分量(DC). DC就是電子工程領(lǐng)域中的直流就是電子工程領(lǐng)域中的直流, 也就是零頻率的電流也就是零頻率的電流.和一維情形和一維情形, 同樣也有同樣也有xMu1yNv118例例4.2 一個簡單函數(shù)的頻譜一個簡單函數(shù)的頻譜(已經(jīng)做過中心化處理已經(jīng)做過中心化處理).圖像是圖像是512 512的黑色背景上疊加一個的黑色背景上疊加一個20 40 象素的白色矩形象素的白色矩形. 頻譜的顯示頻譜的顯示經(jīng)過了對數(shù)變換處理以加強灰度級細節(jié)經(jīng)過了對數(shù)變換處理以加強灰度級

16、細節(jié), 并適當調(diào)整了灰度強度并適當調(diào)整了灰度強度.可以看出可以看出, u方方向譜的零點分隔恰好是向譜的零點分隔恰好是v方向零點分隔的兩倍方向零點分隔的兩倍, 在不同方向上符合了原圖中在不同方向上符合了原圖中1:2的的矩形尺寸比例矩形尺寸比例. 這和一維情形完全類似這和一維情形完全類似.極限情況、能量分布情況極限情況、能量分布情況? 19頻率域濾波頻率域濾波頻率域的基本性質(zhì)頻率域的基本性質(zhì)傅里葉變換每個頻譜分量都要涉及到圖像空間中的每個傅里葉變換每個頻譜分量都要涉及到圖像空間中的每個像像素素, 所以所以一般來說一般來說, 頻譜信息中很難看出空間的信息頻譜信息中很難看出空間的信息。但由于頻率反映的

17、是空間但由于頻率反映的是空間強度的變化率強度的變化率, 如低頻對應(yīng)著圖像變化慢的部分如低頻對應(yīng)著圖像變化慢的部分, 高頻對應(yīng)著圖像變化快高頻對應(yīng)著圖像變化快的部分的部分。所以所以, 在某種意義上兩者之間仍然有不可分割的聯(lián)系在某種意義上兩者之間仍然有不可分割的聯(lián)系, 盡管這些盡管這些聯(lián)系是聯(lián)系是“總體總體”的的.1010)/(2),(1),(MxNyNvyMuxjeyxfMNvuF 1010)/(2),(),(MuNvNvyMuxjevuFyxf(4.2.16)(4.2.17)20例例4.3 一幅圖像和顯示某些重要特征的傅利葉譜一幅圖像和顯示某些重要特征的傅利葉譜集成電路的掃描電子顯微鏡圖像集成

18、電路的掃描電子顯微鏡圖像, 放大放大2500倍倍.注意注意: 45 角的角的兩個強邊緣和熱感應(yīng)兩個強邊緣和熱感應(yīng)不足引起的兩個白色不足引起的兩個白色氧化突起氧化突起.高頻和低頻部分高頻和低頻部分, 能量分布的一般情況能量分布的一般情況.21頻率域濾波基礎(chǔ)頻率域濾波基礎(chǔ) f(x, y) F(u, v)步驟步驟:(1) 用用(-1)x+y乘以輸入圖像乘以輸入圖像, 做頻譜中心化處理做頻譜中心化處理;(2) 計算計算(1)結(jié)果的結(jié)果的DFT, 即即F(u, v);(3) 用濾波器函數(shù)用濾波器函數(shù)H(u, v)乘以乘以F(u, v)(在頻譜域處理圖像在頻譜域處理圖像)濾波器函數(shù)濾波器函數(shù)下面討論下面討

19、論;(4) 計算計算(3)中結(jié)果的反中結(jié)果的反DFT;(5) 得到得到(4)結(jié)果中的實部結(jié)果中的實部;(6) 用用(-1)x+y乘以乘以(5)中的結(jié)果中的結(jié)果濾波和濾波器濾波和濾波器: 濾波顧名思義就是阻止或減少信號或圖像中的某些頻濾波顧名思義就是阻止或減少信號或圖像中的某些頻率成分率成分. 濾波器濾波器(函數(shù)函數(shù))就是能起到這樣作用的函數(shù)就是能起到這樣作用的函數(shù). 一般表達式一般表達式:G(u, v) = H(u, v)F(u, v)濾波后的結(jié)果圖像可以從濾波后的結(jié)果圖像可以從G(u, v)的反傅里葉變換得到的反傅里葉變換得到.g(x, y) = -1G(u, v)22頻域濾波的基本步驟頻域

20、濾波的基本步驟(包括前處理和后處理包括前處理和后處理):陷波濾波器陷波濾波器(Notch Filter): 使得處理后的圖像平均值為零使得處理后的圖像平均值為零, 從而圖從而圖像的整體灰度降低像的整體灰度降低.others 1)2/ , 2/(),( 0),(NMvuvuH23對圖對圖4.4a使用陷波濾波器使用陷波濾波器, 將傅里葉變換的原點設(shè)置為將傅里葉變換的原點設(shè)置為0.24低通濾波器和高通濾波器低通濾波器和高通濾波器25高頻增強濾波高頻增強濾波26空間域濾波器和頻率域濾波器之間的對應(yīng)關(guān)系空間域濾波器和頻率域濾波器之間的對應(yīng)關(guān)系 結(jié)論結(jié)論: 空間域的濾波器空間域的濾波器, 和頻率域的濾波器

21、組成了一組傅里葉變換對和頻率域的濾波器組成了一組傅里葉變換對.也就是說也就是說, 給出在頻率域的濾波器給出在頻率域的濾波器, 通過傅里葉反變換就可以得到在空間通過傅里葉反變換就可以得到在空間域相應(yīng)的濾波器域相應(yīng)的濾波器, 反之亦然反之亦然. 這個最基本的聯(lián)系是由著名的卷積定理建立起來的這個最基本的聯(lián)系是由著名的卷積定理建立起來的. 兩個兩個M N的離散函數(shù)的離散函數(shù)f(x, y)和和h(x, y)的卷積定義為的卷積定義為1010),(),(),(),(MmNnnymxhnmfyxhyxf空間域濾波的本質(zhì)上就是用選好的掩模空間域濾波的本質(zhì)上就是用選好的掩模(mask), 經(jīng)過一定的處理經(jīng)過一定的

22、處理, 與與給定的圖像作卷積給定的圖像作卷積.例如例如: 平滑濾波的掩模平滑濾波的掩模27卷積定理卷積定理F(u, v) f(x, y)的傅里葉變換的傅里葉變換H(u, v) h(x, y)的傅里葉變換的傅里葉變換則有則有f(x, y)*h(x, y) F(u, v)H(u, v)f(x, y)h(x, y) F(u, v)*H(u, v)28卷積定理的證明提示：卷積定理的證明提示： （51） （52） 證明：由定義： )()()()(sGsFtgtfF)()()()(tgtfsGsF1F)()()()()()()()()()()(2)(22)(22sGsFutvduufdvevgdudteu

23、tgufdtdueutguftgtfsujvsjsujutsjstj 令F29定義定義: 在坐標在坐標(x0, y0)處強度為處強度為A的沖激的沖激(脈沖脈沖)函數(shù)函數(shù)A (x x0, y y0)滿足滿足一些結(jié)論：一些結(jié)論：),(),(),(00101000yxAsyyxxAyxsMxNy1。)0 , 0(),(),(1010AsyxAyxsMxNy2。MNeyxMNvuFNvyMuxjMxNy1),(1),()/(21010 3。),(1),(),(1),(*),(1010yxhMNnymxhnmMNyxhyxfMmNn 30這個結(jié)論的指導(dǎo)意義這個結(jié)論的指導(dǎo)意義: 在頻率域選擇濾波器更為直觀

24、在頻率域選擇濾波器更為直觀, 物理意義比較物理意義比較明確明確. 在空間域用較小的模板進行濾波計算則比較經(jīng)濟在空間域用較小的模板進行濾波計算則比較經(jīng)濟. 如果兩個濾波器如果兩個濾波器的大小一樣的大小一樣, 則在頻率域進行濾波計算比較方便則在頻率域進行濾波計算比較方便. 更令人感興趣的是更令人感興趣的是, 在在頻率域找到一個有意義的濾波器頻率域找到一個有意義的濾波器, 然后作傅里葉反變換然后作傅里葉反變換, 并以此為依據(jù)并以此為依據(jù), 盡可能在空間域建造盡可能小的濾波模板盡可能在空間域建造盡可能小的濾波模板.高斯濾波器高斯濾波器以一維為例以一維為例, 設(shè)高斯濾波器設(shè)高斯濾波器(頻率域頻率域)為為

25、H(u) = Ae-u2/2 2, 其中其中: 為高斯為高斯曲線的標準差曲線的標準差. 而相關(guān)的空間濾波器則為而相關(guān)的空間濾波器則為22222)(xAexh注意高斯函數(shù)有兩個重要特性注意高斯函數(shù)有兩個重要特性: 它本身和它的傅里葉變換都是實高斯函數(shù)它本身和它的傅里葉變換都是實高斯函數(shù); 這一對傅利葉變換相互間有某種反比特性這一對傅利葉變換相互間有某種反比特性, 即當即當H(u)有較寬的輪有較寬的輪廓廓(大的大的 值值)時時, h(x)有較窄的輪廓有較窄的輪廓, 反之亦然反之亦然.當接近無限時當接近無限時, H(u)趨于常數(shù)量趨于常數(shù)量, h(x)則趨于沖激函數(shù)則趨于沖激函數(shù).31高斯函數(shù)是低高

26、斯函數(shù)是低通濾波器通濾波器(?), 但也但也可以通過組合構(gòu)造可以通過組合構(gòu)造出更復(fù)雜的濾波器出更復(fù)雜的濾波器, 如高通和帶通等如高通和帶通等. 2222122/2/)(uuBeAeuH22222212222122)(xxBeAexh高頻增強高頻增強空間域空間域頻域濾波器頻域濾波器空間域空間域其中其中:21B，A32在頻率域技術(shù)的發(fā)展過程中在頻率域技術(shù)的發(fā)展過程中, 經(jīng)常被問到的問題就是計算復(fù)雜性經(jīng)常被問到的問題就是計算復(fù)雜性. 為為什么在空間域用小模板就可以做到的事情什么在空間域用小模板就可以做到的事情, 卻要在頻率域里去考慮卻要在頻率域里去考慮? 這個這個問題可以從兩方面來回答問題可以從兩方

27、面來回答:一方面是因為頻率域直觀一方面是因為頻率域直觀, 可以很容易憑經(jīng)驗指定濾波器可以很容易憑經(jīng)驗指定濾波器;另一方面的答案取決于空間模板的大小另一方面的答案取決于空間模板的大小, 并可以用對比計算復(fù)雜性的并可以用對比計算復(fù)雜性的方式來回答方式來回答.一個用于計算復(fù)雜性對比的基準是計算卷積一個用于計算復(fù)雜性對比的基準是計算卷積. 空間域的卷積由公式空間域的卷積由公式(4.2.30)給出給出. 而由卷積定理可知而由卷積定理可知, 對兩個函數(shù)傅里葉變換的乘積做反變換對兩個函數(shù)傅里葉變換的乘積做反變換, 也可以得到同樣的結(jié)果也可以得到同樣的結(jié)果.假定假定: 在同一臺微機上用軟件實現(xiàn)這兩種算法在同一

28、臺微機上用軟件實現(xiàn)這兩種算法(頻率域使用頻率域使用4.6.6節(jié)討節(jié)討論的論的FFT), 會發(fā)現(xiàn)對較小的會發(fā)現(xiàn)對較小的M和和N值值, 頻率域的計算會非?？祛l率域的計算會非常快.頻率域可以看成是一個實驗室頻率域可以看成是一個實驗室, 從中可以利用頻率成分和圖像外觀之從中可以利用頻率成分和圖像外觀之間的對應(yīng)關(guān)系間的對應(yīng)關(guān)系.后面的許多例子將反復(fù)證明后面的許多例子將反復(fù)證明: 一些在空間域中很難表述、甚至不可能一些在空間域中很難表述、甚至不可能的增強任務(wù)的增強任務(wù), 在頻率域會變得非常簡單在頻率域會變得非常簡單.例如周期性背景噪聲例如周期性背景噪聲.33這一節(jié)是本章的重要內(nèi)容之一這一節(jié)是本章的重要內(nèi)容

29、之一. 目的是解決實際計算傅里葉變換時目的是解決實際計算傅里葉變換時出現(xiàn)的問題出現(xiàn)的問題, 包括快速傅里葉變換包括快速傅里葉變換. 假設(shè)假設(shè): f(x, y)是是M N的二維圖像的二維圖像, F(u, v)是其傅里葉變換是其傅里葉變換, 有有1010)/(2),(1),(MxNyNvyMuxjeyxfMNvuF1010)/(2),(),(MuNvNvyMuxjevuFyxf平移性質(zhì)平移性質(zhì)f(x, y)ej2 (u0 x/M+v0y/N) F(u u0, v v0)f(x x0, y y0) F(u, v)e-j2 (x0u/M+x0v/N)二維傅里葉變換的性質(zhì)二維傅里葉變換的性質(zhì)34注意注意

30、: 當當u0 = M/2和和v0 = N/2時時, 有有ej2 (u0 x/M+v0y/N) = ej (x+y) = (-1)x+yf(x, y)(-1)x+y F(u M/2, v N/2)提供了頻譜中心化的方法提供了頻譜中心化的方法.分配性和比例變換性分配性和比例變換性旋轉(zhuǎn)性質(zhì)旋轉(zhuǎn)性質(zhì): 如果引入極坐標如果引入極坐標:x = rcos ,y = rsin ,u = cos , v = sin f(r, + 0) F( , + 0)此式表明當原圖像此式表明當原圖像f(x, y)以某一角度旋轉(zhuǎn)時以某一角度旋轉(zhuǎn)時, 其譜平面也將轉(zhuǎn)過同樣其譜平面也將轉(zhuǎn)過同樣的角度的角度. 注注: 對離散情形對離

31、散情形, 若有若有M = N, 證明易見證明易見. ),(),(),(),(2121yxfbyxfayxbfyxaf)/,/(1),(bvauFabbyaxff(x, y)ej2 (u0 x/M+v0y/N) F(u u0, v v0)352021-11-2935(a)原始圖像 (b) DFT變換 (c) 原始圖像旋轉(zhuǎn)45 (d) 旋轉(zhuǎn)之后DFT變換結(jié)果 36*周期性和對稱性周期性和對稱性直接驗證可知直接驗證可知, 離散傅里葉變換具有周期性離散傅里葉變換具有周期性F(u, v) = F(u+M, v) = F(u, v+N) = F(u+M, v+N)注意注意e-j2 x = 1, 故故e-j

32、2 (u+M)x/M+vy/N) = e-j2 (ux/M+vy/N)同理同理, 反變換也具有周期性反變換也具有周期性f(x, y) = f(x+M, y) = f(x, y+N) = f(x+M, y+N)除此之外除此之外, 還有共軛對稱性還有共軛對稱性F(u, v) = F*(-u, -v)共軛的定義為共軛的定義為: 若一個復(fù)數(shù)若一個復(fù)數(shù)Z = x + i y, 則其共軛為則其共軛為Z* = x - i y, 且且 |Z| = |Z*|.37由傅里葉變換的共軛對稱性質(zhì)可以得到結(jié)論由傅里葉變換的共軛對稱性質(zhì)可以得到結(jié)論: 頻譜是關(guān)于原點對頻譜是關(guān)于原點對稱的稱的.|F(u, v)| = |F

33、(-u, -v)|上述這些性質(zhì)說明在這里給出的離散傅里葉變換是周期函數(shù)上述這些性質(zhì)說明在這里給出的離散傅里葉變換是周期函數(shù), 并并關(guān)于原點對稱關(guān)于原點對稱(經(jīng)過平移即為中心對稱經(jīng)過平移即為中心對稱). 38可分性可分性10/21010/2/2),(1 ),(1),(MxMuxjMxNyNvyjMuxjevxFMNeyxfeMNvuF還可交換順序還可交換順序.因而在實際計算中因而在實際計算中, 可逐列或逐行先計算一維的傅里可逐列或逐行先計算一維的傅里葉變換葉變換, 然后對另外一個方向?qū)嵭杏嬎闳缓髮α硗庖粋€方向?qū)嵭杏嬎?反變換的計算類似。反變換的計算類似。39用前向變換計算傅里葉反變換用前向變換計

34、算傅里葉反變換上式兩邊取復(fù)共軛并除以上式兩邊取復(fù)共軛并除以M, 有有上式的形式和前向變換一樣上式的形式和前向變換一樣, 左邊再取復(fù)共軛并乘以左邊再取復(fù)共軛并乘以M就是對就是對F(u)反反變換的函數(shù)變換的函數(shù). )(1)(10/2MxMuxjexfMuF )()(0/2MxMuxjeuFxf )(*1)(*10/2MxMuxjeuFMxfM主要思路是基于傅里葉變換的共軛性質(zhì)主要思路是基于傅里葉變換的共軛性質(zhì), 利用正變換公式計算反變利用正變換公式計算反變換換. 傅里葉變換傅里葉變換40我們知道我們知道, 傅里葉變換可以簡化一些運算傅里葉變換可以簡化一些運算, 例如例如: 卷積、微分等卷積、微分等

35、. 但由但由于離散傅里葉變換于離散傅里葉變換(反變換反變換)自動將原函數(shù)做了周期化的處理自動將原函數(shù)做了周期化的處理, 因此在利用因此在利用傅里葉變換處理函數(shù)傅里葉變換處理函數(shù)(或圖象或圖象)時時, 一定要注意這種周期化對運算的影響一定要注意這種周期化對運算的影響. 以卷積為例以卷積為例(特別注意在頻譜域濾波就相當于在空間域的卷積特別注意在頻譜域濾波就相當于在空間域的卷積).以一維為例以一維為例: 如果如果f(x)和函數(shù)和函數(shù)h(x)各有各有400個點個點(如圖如圖4.36a和和4.36b), 那么那么, 10)()()()()(Mmmxhmfxhxfxg(4.3.20) 關(guān)于周期性的更多討論

36、關(guān)于周期性的更多討論:l 直接按公式直接按公式(4.6.20)計算計算(注意在定義域外的注意在定義域外的點不參與運算點不參與運算), 它們的卷積函數(shù)它們的卷積函數(shù)g(x)應(yīng)該是應(yīng)該是有有800個點個點, 從從0到到799, 結(jié)果函數(shù)如圖結(jié)果函數(shù)如圖4.36e所示所示(這個是正確的解這個是正確的解).41l 如果把函數(shù)如果把函數(shù)f(x)和和h(x)先作周期化處理先作周期化處理(為為什么什么?)l 然后利用公式然后利用公式(4.3.20)計算計算, 這時它們的卷這時它們的卷積函數(shù)積函數(shù)g(x)只有只有400個點個點, 并且在開頭有數(shù)并且在開頭有數(shù)據(jù)誤差據(jù)誤差, 結(jié)尾處出現(xiàn)數(shù)據(jù)丟失結(jié)尾處出現(xiàn)數(shù)據(jù)丟失

37、42l 利用離散傅里葉變換的性質(zhì)利用離散傅里葉變換的性質(zhì), 兩個函數(shù)的卷積可以由它們傅里葉變換兩個函數(shù)的卷積可以由它們傅里葉變換的乘積做反變換得到的乘積做反變換得到由于傅里葉變由于傅里葉變換換(反變換反變換)附加的附加的周期性周期性(周期的長度周期的長度等于函數(shù)的長度等于函數(shù)的長度), 如果不謹慎處理周如果不謹慎處理周期問題期問題, 會得到和會得到和上面類似的結(jié)果上面類似的結(jié)果.43如何處理周期問題如何處理周期問題? 處理的方法是對要處理的函數(shù)作零延拓處理的方法是對要處理的函數(shù)作零延拓(Padding).假設(shè)函數(shù)假設(shè)函數(shù)f(x)和和h(x)分別有分別有A個點和個點和B個點組成個點組成, 對兩個

38、函數(shù)同時添加零對兩個函數(shù)同時添加零, 使它們具有相同的周使它們具有相同的周期期, 用用P表示表示PxAAxxffe 010 )(PxBBxxhhe 010 )(只要只要P A+B-1, 將將fe(x)和和he(x)作周期化處理作周期化處理, 然后再用然后再用(4.6.20)作卷積作卷積, 就得到圖就得到圖4.37e的結(jié)果的結(jié)果, 這個結(jié)果在這個結(jié)果在0-799的范圍內(nèi)的范圍內(nèi), 和原來的卷積結(jié)果和原來的卷積結(jié)果(圖圖4.36e)是相同的是相同的. 另一方面另一方面, 在作了適當?shù)暮瘮?shù)延拓后在作了適當?shù)暮瘮?shù)延拓后, 我們就可以利用傅我們就可以利用傅里葉變換和反變換來計算相應(yīng)的卷積里葉變換和反變換

39、來計算相應(yīng)的卷積(或者相應(yīng)的濾波或者相應(yīng)的濾波)了了. 4445在頻率域計算卷積的正確步驟在頻率域計算卷積的正確步驟(1) 對兩個函數(shù)作零延拓至適當?shù)拈L度對兩個函數(shù)作零延拓至適當?shù)拈L度;(2) 做兩個序列的傅里葉變換做兩個序列的傅里葉變換(長度和延拓后的一致長度和延拓后的一致);(3) 將兩個序列的傅里葉變換相乘將兩個序列的傅里葉變換相乘;(4) 計算乘積的傅里葉反變換計算乘積的傅里葉反變換.二維圖像濾波問題二維圖像濾波問題同樣的道理同樣的道理, 在處理二維圖像在處理二維圖像, 例如濾波等時例如濾波等時, 也應(yīng)遵循同樣的理念也應(yīng)遵循同樣的理念.假設(shè)假設(shè)f(x, y)和和h(x, y)是兩幅圖像

40、是兩幅圖像(可把可把h(x, y)看成是空間濾波器看成是空間濾波器), 大小分別大小分別為為A B和和C D, 選選: P A+C-1, Q B+D-1.延拓函數(shù)延拓函數(shù)f(x, y)和和h(x, y).QxBPxAByAxyxfyxfeor 00 and 10 ),(),(QxDPxCDyCxyxhyxheor 00 and 10 ),(),(46在頻譜域作卷積的正確步驟和一維類似在頻譜域作卷積的正確步驟和一維類似. 圖圖4.38給出了幾種濾波方式給出了幾種濾波方式的結(jié)果的結(jié)果, 這里這里h(x, y)是濾波器是濾波器H(u, v)的傅里葉反變換的傅里葉反變換. 4.38a是圖像未作延是圖像

41、未作延拓就實行傅里葉變換拓就實行傅里葉變換, 4.38b是正確的函數(shù)延拓是正確的函數(shù)延拓, 4.38c是延拓后的圖像正是延拓后的圖像正確濾波的結(jié)果確濾波的結(jié)果.注意在這個過程中注意在這個過程中用到了頻率域濾波函數(shù)用到了頻率域濾波函數(shù)的傅里葉反變換的傅里葉反變換, 對反對反變換作零延拓變換作零延拓, 然后再然后再進行正變換進行正變換.同樣要注意同樣要注意反變換的實部和虛部反變換的實部和虛部, 不能在傅里葉計算的中不能在傅里葉計算的中間過程中忽略虛部間過程中忽略虛部, 而而且延拓要同時包括實部且延拓要同時包括實部和虛部和虛部.47在空間域延拓低通濾波器在空間域延拓低通濾波器濾波結(jié)果濾波結(jié)果48眾所

42、周知，兩個二維函數(shù)眾所周知，兩個二維函數(shù)f(x, y)和和h(x, y)的卷積定義為的卷積定義為:1010),(),(),(),(MmNnnymxhnmfyxhyxf它們之間的傅里葉變換有如下關(guān)系它們之間的傅里葉變換有如下關(guān)系f(x, y)*h(x, y) F(u, v)H(u, v)f(x, y)h(x, y) F(u, v)*H(u, v)兩個二維函數(shù)兩個二維函數(shù)f(x, y)和和h(x, y)的相關(guān)函數(shù)定義為的相關(guān)函數(shù)定義為:(沒有鏡像變換沒有鏡像變換)其中其中: f*表示表示f的復(fù)共軛的復(fù)共軛. 注意相關(guān)函數(shù)和卷積有非常類似的結(jié)構(gòu)注意相關(guān)函數(shù)和卷積有非常類似的結(jié)構(gòu), 因此因此f(x,

43、y) h(x, y) F*(u, v)H(u, v)f*(x, y)h(x, y) F(u, v) H(u, v)1010),(),(*),(),(),(MmNnnymxhnmfyxhyxfyxg卷積和相關(guān)性理論卷積和相關(guān)性理論(引入一個新的概念引入一個新的概念, 相關(guān)性相關(guān)性)49相關(guān)的重要應(yīng)用是匹配相關(guān)的重要應(yīng)用是匹配.假設(shè)假設(shè)f(x, y)是一幅包含物體是一幅包含物體或者區(qū)域的圖像或者區(qū)域的圖像, 如果想知道中如果想知道中是否包含有感興趣的物體或區(qū)是否包含有感興趣的物體或區(qū)域域, 就讓就讓h(x, y)作為那個區(qū)域或作為那個區(qū)域或物體物體(模板模板), 然后求兩者的相關(guān)然后求兩者的相關(guān)函

44、數(shù)函數(shù).如果存在匹配如果存在匹配(即即f中有感中有感興趣的物體或區(qū)域興趣的物體或區(qū)域), 則相關(guān)函則相關(guān)函數(shù)會在數(shù)會在h和和f對應(yīng)的位置達到最對應(yīng)的位置達到最大值大值.卷積和相關(guān)性理論卷積和相關(guān)性理論50二維傅里葉變換的一些基本性質(zhì)二維傅里葉變換的一些基本性質(zhì)51二維傅里葉變換的一些基本性質(zhì)二維傅里葉變換的一些基本性質(zhì)52532021-11-2953快速傅立葉變換快速傅立葉變換(FFT)n離散傅立葉變換已成為數(shù)字信號處理的重要工具離散傅立葉變換已成為數(shù)字信號處理的重要工具，然而，然而，它的計算量大，運算時間長它的計算量大，運算時間長，在某種程，在某種程度上卻限制了它的使用范圍。度上卻限制了它的

45、使用范圍。n快速算法快速算法大大提高了運算速度大大提高了運算速度，在某些應(yīng)用場合，在某些應(yīng)用場合已已能作實時處理能作實時處理，并且應(yīng)用在控制系統(tǒng)中，并且應(yīng)用在控制系統(tǒng)中n快速傅立葉變換快速傅立葉變換不是一種新的變換不是一種新的變換，它是離散傅，它是離散傅立葉變換的一種算法，它是在分析離散傅立葉變立葉變換的一種算法，它是在分析離散傅立葉變換中的換中的多余運算的基礎(chǔ)多余運算的基礎(chǔ)上，進而消除這些重復(fù)工上，進而消除這些重復(fù)工作的思想指導(dǎo)下得到的作的思想指導(dǎo)下得到的542021-11-2954其原理：其原理：對于一個有限長序列對于一個有限長序列f(x)(0 x N-1)，它的傅立葉變換由下它的傅立葉變

46、換由下式表示：式表示：令令NjNjeWeW212傅立葉變換對可寫為：傅立葉變換對可寫為：(1)(2) 10101NuxuNxxuWuFNxfWxfuF1, 1 , 0/2exp)()(10NxNuxjxfuFNx55將正變換將正變換(1)展開得到：展開得到：矩矩陣陣表表示示為：為：) 1)(1(1 ) 1(0) 1() 1(22120) 1( 11110) 1(00100) 1() 1 ()0() 1() 1() 1 ()0()2() 1() 1 ()0() 1 () 1() 1 ()0()0(NNNNNNNWNfWfWfNFWNfWfWfFWNfWfWfFWNfWfWfF) 1() 1 ()

47、 0() 1() 1 () 0() 1)(1(1 ) 1(0) 1() 1( 11110) 1(00100NfffWWWWWWWWWNFFFNNNNNN從上式可以看出，要得到每一個頻率分量，需進行從上式可以看出，要得到每一個頻率分量，需進行N次乘法和次乘法和N-1次加次加法運算。要完成整個變換需要法運算。要完成整個變換需要N2次乘法和次乘法和N(N-1)次加法運算。當序列次加法運算。當序列較長時，必然要花費大量的時間較長時，必然要花費大量的時間562021-11-2956觀察上面的系數(shù)矩陣，發(fā)現(xiàn)觀察上面的系數(shù)矩陣，發(fā)現(xiàn)Wmn是以是以N為周期的，即為周期的，即mnhNnlNmWW)(當當N=8時

48、，其周期性如圖所示，由于時，其周期性如圖所示，由于NjNeWNj2sin2cos2所以當所以當N=8時，可得：時，可得：jWjWWWNNNN434211W0W1W2W3W4W5W6W7)1)(1(1)1(0)1()1(11110)1(00100NNNNNNWWWWWWWWW572021-11-2957可見，離散傅立葉變換中的乘法運算有許多重復(fù)內(nèi)容?？梢姡x散傅立葉變換中的乘法運算有許多重復(fù)內(nèi)容。1965年年庫利庫利-圖基提出原始的圖基提出原始的N點序列依次分解成一系列短序列，然后，點序列依次分解成一系列短序列，然后，求出這些短序列的離散傅立葉變換，以此來減少乘法運算，例求出這些短序列的離散傅立

49、葉變換，以此來減少乘法運算，例如，設(shè)：如，設(shè)：由此，離散傅立葉變換可寫成下面的形式：由此，離散傅立葉變換可寫成下面的形式：12/, 1 , 0) 12()(12/, 1 , 0)2()(21NxxfxfNxxfxf12/0)12(12/0)2(12/0212/0110) 12()2()()()()(NxuxNNxuxNNxxuNNxxuNNxxuNWxfWxfWxfWxfWxfuF582021-11-2958因為：因為：22kNkNWW所以：所以：F1(u)和和F2(u)分別是分別是f1(x)和和f2(x)的的N/2點點的傅立葉變換的傅立葉變換 )()() 12()2() 12()2()(21

50、12/02/12/02/12/02/12/02/uFWuFWxfWWxfWWxfWxfuFuNNxxuNuNNxxuNNxuNxuNNxxuN由于由于F1(u)和和F2(u)均是以均是以N/2為周期，所以為周期，所以 )()2/()()2/(2211uFNuFuFNuF這說明當這說明當mN/2時，上式也是成立的，因此下式成立：時，上式也是成立的，因此下式成立：1, 1 , 0)()()(21NuuFWuFuFuN592021-11-2959由上面的分析可見，一個由上面的分析可見，一個N點的離散傅立葉變換可由兩個點的離散傅立葉變換可由兩個N/2點的傅立葉變換得到。點的傅立葉變換得到。離散傅立葉變

51、換的計算時間主要由乘法決定，分解后所需的乘法次數(shù)離散傅立葉變換的計算時間主要由乘法決定，分解后所需的乘法次數(shù)大為減少。第一項為大為減少。第一項為(N/2)2次，第二項為次，第二項為(N/2)2N次，總共為次，總共為2(N/2)2N次運算即可完成，而原來需要次運算即可完成，而原來需要N2次運算，可見分解后的次運算，可見分解后的乘法計算次數(shù)減少了近一半。乘法計算次數(shù)減少了近一半。當當N為為2的整數(shù)冪時，則上式中的的整數(shù)冪時，則上式中的F1(u)和和F2(u)還可以再分成兩個更短還可以再分成兩個更短的序列，因此計算時間會更短。的序列，因此計算時間會更短。由此可見，利用由此可見，利用WNm的周期性和分解運算，從而減少乘法運算次數(shù)是的周期性和分解運算，從而減少乘法運算次數(shù)是實現(xiàn)快速運算的關(guān)鍵實現(xiàn)快速運算的關(guān)鍵602021-11-2960實例實例61快速傅里葉變換快速傅里葉變換一直是重要的研究課題一直是重要的研究課題.先看看直接利用定義公式計算傅里葉變換