圖像傅里葉變換（課堂PPT）

1、.1研究生課程研究生課程數(shù)字圖像處理數(shù)字圖像處理和分析和分析Digital Image Processingand Analysis杜紅杜紅E_mail:.2第三章第三章 傅里葉變換傅里葉變換.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17傅里葉變換傅里葉變換.18 為什么要在頻率域研究圖像增強(qiáng)為什么要在頻率域研究圖像增強(qiáng) 可以利用頻率成分和圖像外表之間的對(duì)應(yīng)關(guān)系。一可以利用頻率成分和圖像外表之間的對(duì)應(yīng)關(guān)系。一些在空間域表述困難的增強(qiáng)任務(wù)，在頻率域中變得非些在空間域表述困難的增強(qiáng)任務(wù)，在頻率域中變得非常普通常普通 濾波在頻率域更為直觀，它可以解釋空間域?yàn)V波的濾波在頻

2、率域更為直觀，它可以解釋空間域?yàn)V波的某些性質(zhì)某些性質(zhì) 可以在頻率域指定濾波器，做反變換，然后在空間可以在頻率域指定濾波器，做反變換，然后在空間域使用結(jié)果濾波器作為空間域?yàn)V波器的指導(dǎo)域使用結(jié)果濾波器作為空間域?yàn)V波器的指導(dǎo) 一旦通過頻率域試驗(yàn)選擇了空間濾波，通常實(shí)施都在一旦通過頻率域試驗(yàn)選擇了空間濾波，通常實(shí)施都在空間域進(jìn)行空間域進(jìn)行傅里葉變換傅里葉變換定義定義.19 一維連續(xù)傅里葉變換及反變換一維連續(xù)傅里葉變換及反變換 單變量連續(xù)函數(shù)單變量連續(xù)函數(shù)f(x)的傅里葉變換的傅里葉變換F(u)定義定義為為 給定給定F(u),通過傅里葉反變換可以得到通過傅里葉反變換可以得到f(x) f(x)e j2 u

3、xdxF(u) 1其中，其中，j F(u)ej2 uxduf(x) 傅里葉變換傅里葉變換定義定義.20傅里葉變換傅里葉變換定義定義.21.22.23.24.25.26.27從歐拉公式從歐拉公式 e cos jsin f x cos( 2 ux)/M jsin( 2 ux)/M f x cos2 ux/M jsin2 ux/M 一維離散傅里葉變換及反變換一維離散傅里葉變換及反變換 j M 1x 01MF(u) f x e j( 2 ux)/M M 1x 0M 1x 01M1M傅里葉變換傅里葉變換.28 F u R u I u 2 2 u arctan 傅里葉變換的極坐標(biāo)表示傅里葉變換的極坐標(biāo)表示

4、F u F u e j u 幅度或頻率譜為幅度或頻率譜為12R(u)和和I(u)分別是分別是F(u)的實(shí)部和虛部的實(shí)部和虛部相角或相位譜為相角或相位譜為 I u R u 傅里葉變換傅里葉變換.29P u F u R u I u 傅里葉變換的極坐標(biāo)表示傅里葉變換的極坐標(biāo)表示 功率譜為功率譜為 f(x)的離散表示的離散表示 F(u)的離散表示的離散表示2 2 2f x f x 0 x x x 0,1,2,., M 1F u F u u u 0,1,2,., M 1傅里葉變換傅里葉變換.30傅里葉變換傅里葉變換定義定義.31 F u,v R u,v I u,v 2 2 u,v arctan 二維二維

5、DFT的極坐標(biāo)表示的極坐標(biāo)表示F u,v F u,v e j u,v 幅度或頻率譜為幅度或頻率譜為12R(u,v)和和I(u,v)分別是分別是F(u,v)的實(shí)部和虛部的實(shí)部和虛部相角或相位譜為相角或相位譜為 I u,v R u,v 傅里葉變換傅里葉變換.32P u,v F u,v R u,v I u,v f x, y 1 二維二維DFT的極坐標(biāo)表示的極坐標(biāo)表示 功率譜為功率譜為 用用(-1)x+y乘以乘以f(x,y),將將F(u,v)原點(diǎn)變換到頻原點(diǎn)變換到頻率坐標(biāo)下的率坐標(biāo)下的(M/2，N/2)，它是，它是MN區(qū)域的中心區(qū)域的中心 u=0,1,2,M-1,v=0,1,2,N-12 2 2F u

6、 M / 2, v N / 2 F(u,v)的原點(diǎn)變換的原點(diǎn)變換x y傅里葉變換傅里葉變換.33 f x, y F(0,0)表示表示這說明：假設(shè)這說明：假設(shè)f(x,y)是一幅圖像，在原點(diǎn)的傅是一幅圖像，在原點(diǎn)的傅里葉變換等于圖像的平均灰度級(jí)里葉變換等于圖像的平均灰度級(jí)M 1 N 1x 0 y 01MNF 0,0 傅里葉變換傅里葉變換.34如果f(x,y)是實(shí)函數(shù)，它的傅里葉變換是對(duì)稱的，即Fu,v Fu,v傅里葉變換的頻率譜是對(duì)稱的Fu,v Fu,v傅里葉變換.35.36傅里葉變換.37傅里葉變換.38 二維傅里葉變換的性質(zhì)二維傅里葉變換的性質(zhì)1.2.3.4.5.6.7.8.9.平移性質(zhì)平移性

7、質(zhì)分配律分配律尺度變換（縮放）尺度變換（縮放）旋轉(zhuǎn)性旋轉(zhuǎn)性周期性和共軛對(duì)稱性周期性和共軛對(duì)稱性平均值平均值可分性可分性卷積卷積相關(guān)性相關(guān)性傅里葉變換傅里葉變換.391.傅里葉變換對(duì)的平移性質(zhì)傅里葉變換對(duì)的平移性質(zhì)(1)(2) 公式（公式（1）表明將）表明將f(x,y)與一個(gè)指數(shù)項(xiàng)相乘就相當(dāng)于與一個(gè)指數(shù)項(xiàng)相乘就相當(dāng)于把其變換后的頻域中心移動(dòng)到新的位置把其變換后的頻域中心移動(dòng)到新的位置公式（公式（2）表明將）表明將F(u,v)與一個(gè)指數(shù)項(xiàng)相乘就相當(dāng)于與一個(gè)指數(shù)項(xiàng)相乘就相當(dāng)于把其變換后的空域中心移動(dòng)到新的位置把其變換后的空域中心移動(dòng)到新的位置公式（公式（2）表明對(duì)）表明對(duì)f(x,y)的平移不影響其傅

8、里葉變換的平移不影響其傅里葉變換的幅值的幅值f x,y ej2 u0 x/M v0y/N F u u0,v v0 f x x0,y y0 F u,v e j2 ux0/M vy0/N 以以 表示函數(shù)和其傅里葉變換的對(duì)應(yīng)性表示函數(shù)和其傅里葉變換的對(duì)應(yīng)性傅里葉變換傅里葉變換.40 1 f x,y 1 1.傅里葉變換對(duì)的平移性質(zhì)（續(xù)）傅里葉變換對(duì)的平移性質(zhì)（續(xù)）當(dāng)當(dāng)u0=M/2且且v0=N/2,帶入（帶入（1）和（）和（2），得到），得到ex y ej (x y)j2 u0 x/M v0y/N F u M/2,v N/2 x yu v傅里葉變換傅里葉變換.412.分配律分配律根據(jù)傅里葉變換的定義，可

9、以得到根據(jù)傅里葉變換的定義，可以得到 f1 x, y f2 x, y f1 x, y f2 x, y f1 x, y f2 x, y f1 x, y f2 x, y 上述公式表明：傅里葉變換對(duì)加法滿足分配上述公式表明：傅里葉變換對(duì)加法滿足分配律，但對(duì)乘法則不滿足律，但對(duì)乘法則不滿足傅里葉變換傅里葉變換.423.尺度變換（縮放）尺度變換（縮放）給定給定2個(gè)標(biāo)量個(gè)標(biāo)量a和和b，可以證明對(duì)傅里葉變換下列，可以證明對(duì)傅里葉變換下列2個(gè)公式成立個(gè)公式成立af x, y aF u,v F u /a,v/b 1abf ax,by 傅里葉變換傅里葉變換.434. 旋轉(zhuǎn)性旋轉(zhuǎn)性引入極坐標(biāo)引入極坐標(biāo) x rcos

10、 ,y rsin ,u cos ,v sin 將將f(x,y)和和F(u,v)轉(zhuǎn)換為轉(zhuǎn)換為 f r, 和和F , 。將它。將它們帶入傅里葉變換對(duì)得到們帶入傅里葉變換對(duì)得到f r, 0 F , 0 f(x,y)旋轉(zhuǎn)角度旋轉(zhuǎn)角度 0，F(xiàn)(u,v)也將轉(zhuǎn)過相同也將轉(zhuǎn)過相同的角度的角度F(u,v)旋轉(zhuǎn)角度旋轉(zhuǎn)角度 0，f(x,y)也將轉(zhuǎn)過相同也將轉(zhuǎn)過相同的角度的角度傅里葉變換傅里葉變換.445.周期性和共軛對(duì)稱性周期性和共軛對(duì)稱性 盡管盡管F(u,v)對(duì)無(wú)窮多個(gè)對(duì)無(wú)窮多個(gè)u和和v的值重復(fù)出現(xiàn)，但只需的值重復(fù)出現(xiàn)，但只需根據(jù)在任一個(gè)周期里的根據(jù)在任一個(gè)周期里的N個(gè)值就可以從個(gè)值就可以從F(u,v)得到得

11、到f(x,y)只需一個(gè)周期里的變換就可將只需一個(gè)周期里的變換就可將F(u,v)在頻域里完全在頻域里完全確定確定同樣的結(jié)論對(duì)同樣的結(jié)論對(duì)f(x,y)在空域也成立在空域也成立F u,v F u M,v F u,v N F u M,v N f x, y f x M, y f x, y N f x M, y N 上述公式表明上述公式表明傅里葉變換傅里葉變換.45F u,v F u, v 5. 周期性和共軛對(duì)稱性周期性和共軛對(duì)稱性如果如果f(x,y)是實(shí)函數(shù)，則它的傅里葉變換具有是實(shí)函數(shù)，則它的傅里葉變換具有共軛對(duì)稱性共軛對(duì)稱性 F u,v F u, v 其中，其中，F(xiàn)*(u,v)為為F(u,v)的復(fù)共

12、軛。的復(fù)共軛。復(fù)習(xí)：當(dāng)兩個(gè)復(fù)數(shù)實(shí)部相等復(fù)習(xí)：當(dāng)兩個(gè)復(fù)數(shù)實(shí)部相等,虛部互為相反數(shù)時(shí)虛部互為相反數(shù)時(shí),這兩個(gè)這兩個(gè)復(fù)數(shù)叫做互為共軛復(fù)數(shù)復(fù)數(shù)叫做互為共軛復(fù)數(shù).傅里葉變換傅里葉變換.46對(duì)于一維變換F(u)，周期性是指F(u)的周期長(zhǎng)度為M，對(duì)稱性是指頻譜關(guān)于原點(diǎn)對(duì)稱周期性和共軛對(duì)稱性舉例周期性和共軛對(duì)稱性舉例半周期的傅里葉頻譜一幅二維圖像的傅里葉頻譜全周期的傅里葉頻譜中心化的傅里葉頻譜.47fx, ye j2vy/ N x 0 y 01 M 1 j2ux/M 1 N1Fx,v x 0e6.F(x,v)是沿著f(x,y)的一行所進(jìn)行的傅里葉變換。當(dāng)x=0,1,M-1，沿著f(x,y)的所有行計(jì)算傅里葉

13、變換。分離性Fu,veM N1 M 1 j2ux/MM傅里葉變換.486.分離性二維傅里葉變換的全過程先通過沿輸入圖像的每一行計(jì)算一維變換再沿中間結(jié)果的每一列計(jì)算一維變換可以改變上述順序，即先列后行上述相似的過程也可以計(jì)算二維傅里葉反變換傅里葉變換.49 fx, yfx, y fx, y7.平均值由二維傅里葉變換的定義而M 1N1x0 y01MNFu,vfx, ye j2ux/M vy/ NM 1N1x0 y01MN所以 F0,0M 1N1x0 y01MN傅里葉變換.50f x, y F 0,0 7.平均值平均值所以所以 上式說明：如果上式說明：如果f(x,y)是一幅圖像，在是一幅圖像，在原點(diǎn)

14、的傅里葉變換即等于圖像的平均灰度原點(diǎn)的傅里葉變換即等于圖像的平均灰度級(jí)級(jí)傅里葉變換傅里葉變換.51 f m,n h x m, y n 8.卷積理論卷積理論大小為大小為MN的兩個(gè)函數(shù)的兩個(gè)函數(shù)f(x,y)和和h(x,y)的離散的離散卷積卷積1 M 1N 1MN m 0 n 0f x, y 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 傅里葉變換傅里葉變換.52 f m,n h x m, y n f x,y h x,y F u,v H u,v 9.相關(guān)性理論相關(guān)性理論大小為大小為MN的兩個(gè)函數(shù)的兩個(gè)函數(shù)f(x,y)和和

15、h(x,y)的相關(guān)的相關(guān)f*表示表示f的復(fù)共軛。對(duì)于實(shí)函數(shù)，的復(fù)共軛。對(duì)于實(shí)函數(shù)， f*f相關(guān)定理相關(guān)定理1 M 1N 1 *MN m 0 n 0性定義為性定義為f x, y h x, y f x,y h x,y F* u,v H u,v *傅里葉變換傅里葉變換.53f x,y f x,y F u,v R u,v I u,v f x,y F u,v F u,v 自相關(guān)理論自相關(guān)理論2 2 22注：復(fù)數(shù)和它的復(fù)共軛的乘積是復(fù)數(shù)模的平方注：復(fù)數(shù)和它的復(fù)共軛的乘積是復(fù)數(shù)模的平方傅里葉變換傅里葉變換.54 卷積和相關(guān)性理論總結(jié)卷積和相關(guān)性理論總結(jié) 卷積是空間域過濾和頻率域過濾之間的紐帶卷積是空間域過濾

16、和頻率域過濾之間的紐帶相關(guān)的重要應(yīng)用在于匹配：確定是否有感興相關(guān)的重要應(yīng)用在于匹配：確定是否有感興趣的物體區(qū)域趣的物體區(qū)域 f(x,y)是原始圖像是原始圖像h(x,y)作為感興趣的物體或區(qū)域（模板）作為感興趣的物體或區(qū)域（模板）如果匹配，兩個(gè)函數(shù)的相關(guān)值會(huì)在如果匹配，兩個(gè)函數(shù)的相關(guān)值會(huì)在h找到找到f中相應(yīng)點(diǎn)的位置上達(dá)到最大中相應(yīng)點(diǎn)的位置上達(dá)到最大傅里葉變換傅里葉變換.55相關(guān)性匹配舉例圖像f(x,y)模板h(x,y)延拓圖像f(x,y)相關(guān)函數(shù)圖像延拓圖像h(x,y)通過相關(guān)圖像最大值的水平灰度剖面圖.56傅里葉變換傅里葉變換傅里葉變換及其反變換傅里葉變換的性質(zhì)快速傅里葉變換(FFT)只考慮一

17、維的情況，根據(jù)傅里葉變換的分離性可知，二維傅里葉變換可由連續(xù)2次一維傅里葉變換得到.57快速傅里葉變換(FFT)為什么需要快速傅里葉變換？快速傅里葉變換(FFT)則只需要Mlog2M次運(yùn)算 FFT算法與原始變換算法的計(jì)算量之比是log2M/M，如M=1024103,則原始變換算法需要106次計(jì)算，而FFT需要104次計(jì)算，F(xiàn)FT與原始變換算法之比是1：1001 M1M x0Fufxej2ux/Mu 0,1,2,.,M 1 對(duì)u的M個(gè)值中的每一個(gè)都需進(jìn)行M次復(fù)數(shù)乘法(將f(x)與ej2ux/M相乘)和M-1次加法，即復(fù)數(shù)乘法和加法的次數(shù)都正比于M2.58 FFT算法基本思想算法基本思想FFT算法

18、基于一個(gè)叫做逐次加倍的方法。通算法基于一個(gè)叫做逐次加倍的方法。通過推導(dǎo)將原始傅里葉轉(zhuǎn)換成兩個(gè)遞推公式過推導(dǎo)將原始傅里葉轉(zhuǎn)換成兩個(gè)遞推公式M 1x 01MF u 快速傅里葉變換快速傅里葉變換(FFT) 12 Feven u Fodd u W2ukF u 12 Feven u Fodd u W2ukF u K f x e j2 ux /M u 0,1,2,.,M 1.59 FFT算法基本思想算法基本思想其中：其中：M = 2KFeven(u)、Fodd(u)是是K個(gè)點(diǎn)的傅里葉值個(gè)點(diǎn)的傅里葉值u 0,1,2,.,M 1快速傅里葉變換快速傅里葉變換(FFT) 12 Feven u Fodd u W2u

19、kF u 12 Feven u Fodd u W2ukF u K .60 FFT公式推導(dǎo)公式推導(dǎo)FFT算法基于一個(gè)叫做逐次加倍的方法。為算法基于一個(gè)叫做逐次加倍的方法。為方便起見用下式表達(dá)離散傅立葉變換公式方便起見用下式表達(dá)離散傅立葉變換公式這里這里是一個(gè)常數(shù)是一個(gè)常數(shù)1 M 1M x 0F u f x e j2 ux/M快速傅里葉變換快速傅里葉變換(FFT) M 1x 0f x WM ux1MWM e j2 /M.61 快速傅里葉變換快速傅里葉變換(FFT)假設(shè)假設(shè)M的形式是的形式是M 2nn為正整數(shù)。因此，為正整數(shù)。因此，M可以表示為可以表示為M 2K將將M=2K帶入上式帶入上式2K 1x

20、 0f x W2uxK12KF u 1 1 K 1 u 2x 1 K 1 u 2x 1 2 K.62 2 1 2 K K W W x f u F 2 K W x f快速傅里葉變換(FFT)推導(dǎo)：因?yàn)樗詭肷鲜接蠾M ej2/M11 K1 ux 1 K1 ux u 2K x0 K x0 W22 K ux e j2 (2ux)/2K e j2 (ux)/K WK ux.63 x 0 x 0快速傅里葉變換(FFT)定義兩個(gè)符號(hào)f2xWK ux1 K1KFevenuf2x1WK ux1 K1KF odduu0,1,2,.,K1.64Fevenu FodduW2K快速傅里葉變換(FFT)得到FFT的第

21、一個(gè)公式該公式說明F(u)可以通過奇部和偶部之和來(lái)計(jì)算u12Fu.65WK ue j2 WK u1WW2uKe j1 W2uK1快速傅里葉變換(FFT)推導(dǎo)：WK u2uK2K e j2uK/2Kej2u/2KejWK uK e j2 (uK)/K e j2u/Ke j2W2uK1.66 f2xW2K x 0 f2x1W2Kf2xWKf2x1WK uKxW2K uKf2xWK x 0 f2x1WK ux W2uK 快速傅里葉變換(FFT)K1x0K1x0uKx1K1 12 KfxW2K uKx1 2K12K x0FuK1 K1 uK2x1K11 K1 uK2x2K x01 1 K1 ux 1

22、K12K x0 K12FevenuFodduW2uK.67快速傅里葉變換(FFT)得到FFT的第二個(gè)公式該公式說明F(uK)可以通過奇部和偶部之差來(lái)計(jì)算12Fevenu FodduW2uKFu K.68Fevenu FodduW2K快速傅里葉變換(FFT)最后得到FFT的二個(gè)公式12Fevenu FodduW2uKFu Ku12Fu.69分析這些表達(dá)式得到如下一些有趣的特性： 一個(gè)M個(gè)點(diǎn)的變換，能夠通過將原始表達(dá)式分成兩個(gè)部分來(lái)計(jì)算 通過計(jì)算兩個(gè)（M/2）個(gè)點(diǎn)的變換。得Feven(u)和 Fodd(u) 奇部與偶部之和得到F(u)的前(M/2)個(gè)值 奇部與偶部之差得到F(u)的后(M/2)個(gè)值。且不需要額外的變換計(jì)算快速傅里葉變換(FFT).70歸納快速傅立葉變換的思想：（1）通過計(jì)算兩個(gè)單點(diǎn)的DFT，來(lái)計(jì)算兩個(gè)點(diǎn)的DFT，（2）通過計(jì)算兩個(gè)雙點(diǎn)的DFT，來(lái)計(jì)算四個(gè)點(diǎn)的DFT，以此類推（3）對(duì)于任何N=2m的DFT的計(jì)算，通過計(jì)算兩個(gè)N/2點(diǎn)的DFT，來(lái)計(jì)算N個(gè)點(diǎn)的DFT快速傅里葉變換(FFT).71FFT算法基本思想FFT算法舉例：設(shè)：有函數(shù)f(x)，其N = 23 = 8,有：f(0),f(1),f