圖像傅里葉變換（基礎(chǔ)課堂）

1、研究生課程數(shù)字圖像處理和分析Digital Image Processingand Analysis杜紅E_mail:1智囊經(jīng)驗(yàn)第三章 傅里葉變換2智囊經(jīng)驗(yàn)3智囊經(jīng)驗(yàn)4智囊經(jīng)驗(yàn)5智囊經(jīng)驗(yàn)6智囊經(jīng)驗(yàn)7智囊經(jīng)驗(yàn)8智囊經(jīng)驗(yàn)9智囊經(jīng)驗(yàn)10智囊經(jīng)驗(yàn)11智囊經(jīng)驗(yàn)12智囊經(jīng)驗(yàn)13智囊經(jīng)驗(yàn)14智囊經(jīng)驗(yàn)15智囊經(jīng)驗(yàn)16智囊經(jīng)驗(yàn)傅里葉變換17智囊經(jīng)驗(yàn)為什么要在頻率域研究圖像增強(qiáng) 可以利用頻率成分和圖像外表之間的對(duì)應(yīng)關(guān)系。一些在空間域表述困難的增強(qiáng)任務(wù)，在頻率域中變得非常普通濾波在頻率域更為直觀，它可以解釋空間域?yàn)V波的某些性質(zhì)可以在頻率域指定濾波器，做反變換，然后在空間域使用結(jié)果濾波器作為空間域?yàn)V波器的指導(dǎo)一旦通過

2、頻率域試驗(yàn)選擇了空間濾波，通常實(shí)施都在空間域進(jìn)行傅里葉變換定義18智囊經(jīng)驗(yàn)一維連續(xù)傅里葉變換及反變換單變量連續(xù)函數(shù)f(x)的傅里葉變換F(u)定義為給定F(u),通過傅里葉反變換可以得到f(x)f(x)ej2uxdxF(u) 1其中，j F(u)ej2uxduf(x)傅里葉變換定義19智囊經(jīng)驗(yàn)傅里葉變換定義20智囊經(jīng)驗(yàn)21智囊經(jīng)驗(yàn)22智囊經(jīng)驗(yàn)23智囊經(jīng)驗(yàn)24智囊經(jīng)驗(yàn)25智囊經(jīng)驗(yàn)26智囊經(jīng)驗(yàn)從歐拉公式 e cos jsin fxcos(2ux)/M jsin(2ux)/M fxcos2ux/M jsin2ux/M一維離散傅里葉變換及反變換jM1x01MF(u) fxe j(2ux)/MM 1x0

3、M 1x01M1M傅里葉變換27智囊經(jīng)驗(yàn) Fu Ru Iu2 2u arctan傅里葉變換的極坐標(biāo)表示Fu Fue ju幅度或頻率譜為12R(u)和I(u)分別是F(u)的實(shí)部和虛部相角或相位譜為 IuRu傅里葉變換28智囊經(jīng)驗(yàn)Pu Fu Ru Iu傅里葉變換的極坐標(biāo)表示功率譜為f(x)的離散表示F(u)的離散表示2 2 2f x f x 0 x xx 0,1,2,., M 1F u F u u u 0,1,2,., M 1傅里葉變換29智囊經(jīng)驗(yàn)傅里葉變換定義30智囊經(jīng)驗(yàn) Fu,v Ru,v Iu,v2 2u,varctan二維DFT的極坐標(biāo)表示Fu,v Fu,ve ju,v幅度或頻率譜為12

4、R(u,v)和I(u,v)分別是F(u,v)的實(shí)部和虛部相角或相位譜為 Iu,vRu,v傅里葉變換31智囊經(jīng)驗(yàn)Pu,v Fu,v Ru,v Iu,vf x, y 1 二維DFT的極坐標(biāo)表示功率譜為用(-1)x+y乘以f(x,y),將F(u,v)原點(diǎn)變換到頻率坐標(biāo)下的(M/2，N/2)，它是MN區(qū)域的中心u=0,1,2,M-1,v=0,1,2,N-12 2 2F u M / 2, v N / 2F(u,v)的原點(diǎn)變換x y傅里葉變換32智囊經(jīng)驗(yàn) f x, yF(0,0)表示這說明：假設(shè)f(x,y)是一幅圖像，在原點(diǎn)的傅里葉變換等于圖像的平均灰度級(jí)M 1 N 1x0 y01MNF0,0傅里葉變換3

5、3智囊經(jīng)驗(yàn)如果f(x,y)是實(shí)函數(shù)，它的傅里葉變換是對(duì)稱的，即Fu,v Fu,v傅里葉變換的頻率譜是對(duì)稱的Fu,v Fu,v傅里葉變換34智囊經(jīng)驗(yàn)35智囊經(jīng)驗(yàn)傅里葉變換36智囊經(jīng)驗(yàn)傅里葉變換37智囊經(jīng)驗(yàn)二維傅里葉變換的性質(zhì)1.2.3.4.5.6.7.8.9.平移性質(zhì)分配律尺度變換（縮放）旋轉(zhuǎn)性周期性和共軛對(duì)稱性平均值可分性卷積相關(guān)性傅里葉變換38智囊經(jīng)驗(yàn)1.傅里葉變換對(duì)的平移性質(zhì)(1)(2)公式（1）表明將f(x,y)與一個(gè)指數(shù)項(xiàng)相乘就相當(dāng)于把其變換后的頻域中心移動(dòng)到新的位置公式（2）表明將F(u,v)與一個(gè)指數(shù)項(xiàng)相乘就相當(dāng)于把其變換后的空域中心移動(dòng)到新的位置公式（2）表明對(duì)f(x,y)的平移

6、不影響其傅里葉變換的幅值fx,yej2u0 x/Mv0y/N Fuu0,vv0fxx0,yy0Fu,vej2ux0/Mvy0/N以 表示函數(shù)和其傅里葉變換的對(duì)應(yīng)性傅里葉變換39智囊經(jīng)驗(yàn)1fx,y11.傅里葉變換對(duì)的平移性質(zhì)（續(xù)）當(dāng)u0=M/2且v0=N/2,帶入（1）和（2），得到exyej(xy)j2u0 x/Mv0y/NFuM/2,vN/2xyuv傅里葉變換40智囊經(jīng)驗(yàn)2.分配律根據(jù)傅里葉變換的定義，可以得到f1x, y f2x, y f1x, y f2x, yf1x, y f2x, y f1x, yf2x, y上述公式表明：傅里葉變換對(duì)加法滿足分配律，但對(duì)乘法則不滿足傅里葉變換41智囊經(jīng)

7、驗(yàn)3.尺度變換（縮放）給定2個(gè)標(biāo)量a和b，可以證明對(duì)傅里葉變換下列2個(gè)公式成立af x, y aFu,vFu /a,v/b1abfax,by傅里葉變換42智囊經(jīng)驗(yàn)4.旋轉(zhuǎn)性引入極坐標(biāo) xrcos,yrsin,ucos,vsin將f(x,y)和F(u,v)轉(zhuǎn)換為 fr,和F,。將它們帶入傅里葉變換對(duì)得到fr, 0 F, 0f(x,y)旋轉(zhuǎn)角度0，F(xiàn)(u,v)也將轉(zhuǎn)過相同的角度F(u,v)旋轉(zhuǎn)角度0，f(x,y)也將轉(zhuǎn)過相同的角度傅里葉變換43智囊經(jīng)驗(yàn)5.周期性和共軛對(duì)稱性盡管F(u,v)對(duì)無窮多個(gè)u和v的值重復(fù)出現(xiàn)，但只需根據(jù)在任一個(gè)周期里的N個(gè)值就可以從F(u,v)得到f(x,y)只需一個(gè)周期

8、里的變換就可將F(u,v)在頻域里完全確定同樣的結(jié)論對(duì)f(x,y)在空域也成立Fu,v Fu M,v Fu,v N Fu M,v Nfx, y fx M, y fx, y N fx M, y N上述公式表明傅里葉變換44智囊經(jīng)驗(yàn)Fu,v F u,v5.周期性和共軛對(duì)稱性如果f(x,y)是實(shí)函數(shù)，則它的傅里葉變換具有共軛對(duì)稱性Fu,v Fu,v其中，F(xiàn)*(u,v)為F(u,v)的復(fù)共軛。復(fù)習(xí)：當(dāng)兩個(gè)復(fù)數(shù)實(shí)部相等,虛部互為相反數(shù)時(shí),這兩個(gè)復(fù)數(shù)叫做互為共軛復(fù)數(shù).傅里葉變換45智囊經(jīng)驗(yàn)對(duì)于一維變換F(u)，周期性是指F(u)的周期長(zhǎng)度為M，對(duì)稱性是指頻譜關(guān)于原點(diǎn)對(duì)稱周期性和共軛對(duì)稱性舉例半周期的傅里葉

9、頻譜一幅二維圖像的傅里葉頻譜全周期的傅里葉頻譜中心化的傅里葉頻譜46智囊經(jīng)驗(yàn)fx, 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ì)算傅里葉變換。分離性Fu,veM N1 M 1 j2ux/MM傅里葉變換47智囊經(jīng)驗(yàn)6.分離性二維傅里葉變換的全過程先通過沿輸入圖像的每一行計(jì)算一維變換再沿中間結(jié)果的每一列計(jì)算一維變換可以改變上述順序，即先列后行上述相似的過程也可以計(jì)算二維傅里葉反變換傅里葉變換48智囊經(jīng)驗(yàn) fx, yfx, y fx, y7.平均值由

10、二維傅里葉變換的定義而M 1N1x0 y01MNFu,vfx, ye j2ux/M vy/ NM 1N1x0 y01MN所以 F0,0M 1N1x0 y01MN傅里葉變換49智囊經(jīng)驗(yàn)fx, y F0,07.平均值所以上式說明：如果f(x,y)是一幅圖像，在原點(diǎn)的傅里葉變換即等于圖像的平均灰度級(jí)傅里葉變換50智囊經(jīng)驗(yàn) fm,nhxm, yn8.卷積理論大小為MN的兩個(gè)函數(shù)f(x,y)和h(x,y)的離散卷積1 M1N1MN m0 n0fx, yhx, y卷積定理fx,yhx,yFu,vHu,vfx,yhx,yFu,vHu,v傅里葉變換51智囊經(jīng)驗(yàn) f m,nhxm, ynf x,yhx,yFu,

11、vHu,v9.相關(guān)性理論大小為MN的兩個(gè)函數(shù)f(x,y)和h(x,y)的相關(guān)f*表示f的復(fù)共軛。對(duì)于實(shí)函數(shù)， f*f相關(guān)定理1 M1N1 *MN m0 n0性定義為fx, yhx, yfx,yhx,yF*u,vHu,v*傅里葉變換52智囊經(jīng)驗(yàn)fx,y fx,yFu,v Ru,v Iu,vfx,y Fu,vFu,v自相關(guān)理論2 2 22注：復(fù)數(shù)和它的復(fù)共軛的乘積是復(fù)數(shù)模的平方傅里葉變換53智囊經(jīng)驗(yàn)卷積和相關(guān)性理論總結(jié)卷積是空間域過濾和頻率域過濾之間的紐帶相關(guān)的重要應(yīng)用在于匹配：確定是否有感興趣的物體區(qū)域f(x,y)是原始圖像h(x,y)作為感興趣的物體或區(qū)域（模板）如果匹配，兩個(gè)函數(shù)的相關(guān)值會(huì)在

12、h找到f中相應(yīng)點(diǎn)的位置上達(dá)到最大傅里葉變換54智囊經(jīng)驗(yàn)相關(guān)性匹配舉例圖像f(x,y)模板h(x,y)延拓圖像f(x,y)相關(guān)函數(shù)圖像延拓圖像h(x,y)通過相關(guān)圖像最大值的水平灰度剖面圖55智囊經(jīng)驗(yàn)傅里葉變換傅里葉變換傅里葉變換及其反變換傅里葉變換的性質(zhì)快速傅里葉變換(FFT)只考慮一維的情況，根據(jù)傅里葉變換的分離性可知，二維傅里葉變換可由連續(xù)2次一維傅里葉變換得到56智囊經(jīng)驗(yàn)快速傅里葉變換(FFT)為什么需要快速傅里葉變換？快速傅里葉變換(FFT)則只需要Mlog2M次運(yùn)算 FFT算法與原始變換算法的計(jì)算量之比是log2M/M，如M=1024103,則原始變換算法需要106次計(jì)算，而FFT需

13、要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ù)都正比于M257智囊經(jīng)驗(yàn)FFT算法基本思想FFT算法基于一個(gè)叫做逐次加倍的方法。通過推導(dǎo)將原始傅里葉轉(zhuǎn)換成兩個(gè)遞推公式M 1x01MFu快速傅里葉變換(FFT)12Fevenu FodduW2ukFu12FevenuFodduW2ukFu Kf xe j2ux /M u 0,1,2,.,M 158智囊經(jīng)驗(yàn)FFT算法基本思想其中：M = 2KFeven(u)、Fodd

14、(u)是K個(gè)點(diǎn)的傅里葉值u 0,1,2,.,M 1快速傅里葉變換(FFT)12Fevenu FodduW2ukFu12FevenuFodduW2ukFu K59智囊經(jīng)驗(yàn)FFT公式推導(dǎo)FFT算法基于一個(gè)叫做逐次加倍的方法。為方便起見用下式表達(dá)離散傅立葉變換公式這里是一個(gè)常數(shù)1 M1M x0Fufxej2ux/M快速傅里葉變換(FFT)M 1x0fxWM ux1MWM e j2 /M60智囊經(jīng)驗(yàn)快速傅里葉變換(FFT)假設(shè)M的形式是M 2nn為正整數(shù)。因此，M可以表示為M2K將M=2K帶入上式2K 1x0f xW2uxK12KFu1 1 K1 u2x 1 K1 u2x12K61智囊經(jīng)驗(yàn) 2 1 2

15、 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 ux62智囊經(jīng)驗(yàn) x 0 x 0快速傅里葉變換(FFT)定義兩個(gè)符號(hào)f2xWK ux1 K1KFevenuf2x1WK ux1 K1KF odduu0,1,2,.,K163智囊經(jīng)驗(yàn)Fevenu FodduW2K快速傅里葉變換(FFT)得到FFT的第一個(gè)公式該公式說明F(u)可以通過奇部和偶部之和來計(jì)算u12Fu64智囊經(jīng)驗(yàn)WK ue j2 WK

16、u1WW2uKe j1 W2uK1快速傅里葉變換(FFT)推導(dǎo)：WK u2uK2K e j2uK/2Kej2u/2KejWK uK e j2 (uK)/K e j2u/Ke j2W2uK165智囊經(jīng)驗(yàn) 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 K12K x0 K12FevenuFodduW2uK66智囊經(jīng)驗(yàn)快速傅里葉變換(FFT)

17、得到FFT的第二個(gè)公式該公式說明F(uK)可以通過奇部和偶部之差來計(jì)算12Fevenu FodduW2uKFu K67智囊經(jīng)驗(yàn)Fevenu FodduW2K快速傅里葉變換(FFT)最后得到FFT的二個(gè)公式12Fevenu FodduW2uKFu Ku12Fu68智囊經(jīng)驗(yàn)分析這些表達(dá)式得到如下一些有趣的特性： 一個(gè)M個(gè)點(diǎn)的變換，能夠通過將原始表達(dá)式分成兩個(gè)部分來計(jì)算 通過計(jì)算兩個(gè)（M/2）個(gè)點(diǎn)的變換。得Feven(u)和 Fodd(u) 奇部與偶部之和得到F(u)的前(M/2)個(gè)值 奇部與偶部之差得到F(u)的后(M/2)個(gè)值。且不需要額外的變換計(jì)算快速傅里葉變換(FFT)69智囊經(jīng)驗(yàn)歸納快速傅

18、立葉變換的思想：（1）通過計(jì)算兩個(gè)單點(diǎn)的DFT，來計(jì)算兩個(gè)點(diǎn)的DFT，（2）通過計(jì)算兩個(gè)雙點(diǎn)的DFT，來計(jì)算四個(gè)點(diǎn)的DFT，以此類推（3）對(duì)于任何N=2m的DFT的計(jì)算，通過計(jì)算兩個(gè)N/2點(diǎn)的DFT，來計(jì)算N個(gè)點(diǎn)的DFT快速傅里葉變換(FFT)70智囊經(jīng)驗(yàn)FFT算法基本思想FFT算法舉例：設(shè)：有函數(shù)f(x)，其N = 23 = 8,有：f(0),f(1),f(2),f(3),f(4),f(5),f(6),f(7)計(jì)算：F(0),F(1),F(2),F(3),F(4),F(5),F(6),F(7)快速傅里葉變換(FFT)71智囊經(jīng)驗(yàn)FFT算法舉例首先分成奇偶兩組：有： f(0), f(2), f(4), f(6) f(1), f(3), f(5), f(7) 為了利用遞推特性，再分成兩組：有