圖像傅里葉變換.ppt

《圖像傅里葉變換.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《圖像傅里葉變換.ppt（75頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

研究生課程,數(shù)字圖像處理和分析,Digital Image Processing and Analysis,杜紅,E_mail:duhmail@,第三章 傅里葉變換,傅里葉變換,?,為什么要在頻率域研究圖像增強(qiáng) ? 可以利用頻率成分和圖像外表之間的對(duì)應(yīng)關(guān)系。一 些在空間域表述困難的增強(qiáng)任務(wù)，在頻率域中變得非 常普通,?,濾波在頻率域更為直觀，它可以解釋空間域?yàn)V波的,某些性質(zhì),?,可以在頻率域指定濾波器，做反變換，然后在空間,域使用結(jié)果濾波器作為空間域?yàn)V波器的指導(dǎo) ?一旦通過頻率域試驗(yàn)選擇了空間濾波，通常實(shí)施都在 空間域進(jìn)行,傅里葉變換定義,,,,?,?,?,一維連續(xù)傅里葉變換及反變換,?,單變量連續(xù)函數(shù)f(x)的傅里葉變換F(u)定義為,?,給定F(u),通過傅里葉反變換可以得到f(x),? ??,f(x)e?j2?uxdx,F(u)? ? 1,其中，j ?,? ??,F(u)ej2?uxdu,f(x)?,傅里葉變換定義,傅里葉變換定義,,,,從歐拉公式 e ?cos? ? jsin?,?,? f?x??cos(?2?ux)/M ? jsin(?2?ux)/M?,? f?x??cos2?ux/M ? jsin2?ux/M?,?,一維離散傅里葉變換及反變換,?,j?,M?1 x?0,1 M,F(u) ?,f?x?e j(?2?ux)/M,? ?,M ?1 x?0 M ?1 x?0,1 M 1 M,傅里葉變換,,,,,,? ?,F?u? ? R?u? ?I?u?,2 2,??u?? arctan?,?,? ?,傅里葉變換的極坐標(biāo)表示 F?u?? F?u?e? j??u?,幅度或頻率譜為 1 2 R(u)和I(u)分別是F(u)的實(shí)部和虛部 相角或相位譜為 ? I?u?? ?R?u???,傅里葉變換,,,P?u?? F?u? ?R?u? ?I?u?,?,傅里葉變換的極坐標(biāo)表示,?,功率譜為,?,f(x)的離散表示,?,F(u)的離散表示,2 2 2,f ?x? ? f ?x 0 ? x? x?,x ? 0,1,2,., M ?1,F ?u ? ? F ?u? u ?,u ? 0,1,2,., M ?1,傅里葉變換,傅里葉變換定義,,,,,,? ?,F?u,v? ? R?u,v? ?I?u,v?,2 2,??u,v??arctan?,?,? ?,二維DFT的極坐標(biāo)表示 F?u,v?? F?u,v?e? j??u,v?,幅度或頻率譜為 1 2 R(u,v)和I(u,v)分別是F(u,v)的實(shí)部和虛部 相角或相位譜為 ? I?u,v?? ?R?u,v???,傅里葉變換,,,P?u,v?? F?u,v? ?R?u,v? ?I?u,v?,??f ?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-1,2 2 2,F ?u ? M / 2, v ? N / 2?,F(u,v)的原點(diǎn)變換 x ? y,傅里葉變換,,?? f ?x, y?,?,F(0,0)表示,這說明：假設(shè)f(x,y)是一幅圖像，在原點(diǎn)的傅 里葉變換等于圖像的平均灰度級(jí),M ?1 N ?1 x?0 y?0,1 MN,F?0,0??,傅里葉變換,,,,,?,如果f(x,y)是實(shí)函數(shù)，它的傅里葉變換是,對(duì)稱的，即,?,F?u,v?? F??u,?v?,傅里葉變換的頻率譜是對(duì)稱的 F?u,v? ? F??u,?v?,傅里葉變換,傅里葉變換,傅里葉變換,?,二維傅里葉變換的性質(zhì),1. 2. 3. 4. 5. 6. 7. 8. 9.,平移性質(zhì) 分配律 尺度變換（縮放） 旋轉(zhuǎn)性 周期性和共軛對(duì)稱性 平均值 可分性 卷積 相關(guā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)的平移不影響其傅里葉變換 的幅值,f?x,y?ej2??u0x/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)性,傅里葉變換,???1?,f?x,y???1?,1.,傅里葉變換對(duì)的平移性質(zhì)（續(xù)） 當(dāng)u0=M/2且v0=N/2,,帶入（1）和（2），得到,e,x?y,?e,j?(x?y),j2??u0x/M?v0y/N?,?F?u?M/2,v?N/2?,x?y,u?v,傅里葉變換,2.,分配律 根據(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ì)乘法則不滿足,傅里葉變換,,,,3.,尺度變換（縮放） 給定2個(gè)標(biāo)量a和b，可以證明對(duì)傅里葉變換下列 2個(gè)公式成立 af ?x, y?? aF?u,v?,F?u /a,v/b?,1 ab,f?ax,by??,傅里葉變換,4.,? ?,旋轉(zhuǎn)性 引入極坐標(biāo) x?rcos?,y?rsin?,u??cos?,v??sin? 將f(x,y)和F(u,v)轉(zhuǎn)換為 f?r,??和F??,??。將它 們帶入傅里葉變換對(duì)得到 f?r,? ??0?? F??,? ??0?,f(x,y)旋轉(zhuǎn)角度?0，F(xiàn)(u,v)也將轉(zhuǎn)過相同 的角度 F(u,v)旋轉(zhuǎn)角度?0，f(x,y)也將轉(zhuǎn)過相同 的角度,傅里葉變換,5.,周期性和共軛對(duì)稱性,? ? ?,盡管F(u,v)對(duì)無窮多個(gè)u和v的值重復(fù)出現(xiàn)，但只需 根據(jù)在任一個(gè)周期里的N個(gè)值就可以從F(u,v)得到 f(x,y) 只需一個(gè)周期里的變換就可將F(u,v)在頻域里完全 確定 同樣的結(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? 上述公式表明,傅里葉變換,,,,,F?u,v?? F ??u,?v?,5. ?,周期性和共軛對(duì)稱性 如果f(x,y)是實(shí)函數(shù)，則它的傅里葉變換具有 共軛對(duì)稱性 ? F?u,v? ? F??u,?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ù).,傅里葉變換,,?,對(duì)于一維變換F(u)，周期性是指F(u)的周期長(zhǎng),度為M，對(duì)稱性是指頻譜關(guān)于原點(diǎn)對(duì)稱,周期性和共軛對(duì)稱性舉例,半周期的傅里葉頻譜 一幅二維圖像的傅里葉頻譜,全周期的傅里葉頻譜 中心化的傅里葉頻譜,,,,,f?x, y?e? j2?vy/ N,? ? x 0,? ? y 0,1 M ?1 ? j2?ux/M 1 N?1,F?x,v?,? ? x 0e,6.,F(x,v)是沿著f(x,y)的一行所進(jìn)行的傅里葉變 換。當(dāng)x=0,1,…,M-1，沿著f(x,y)的所有行計(jì) 算傅里葉變換。,分離性 F?u,v?? ?,e M N 1 M ?1 ? j2?ux/M M,傅里葉變換,,6.,分離性——二維傅里葉變換的全過程,? ? ? ?,先通過沿輸入圖像的每一行計(jì)算一維變換 再沿中間結(jié)果的每一列計(jì)算一維變換 可以改變上述順序，即先列后行 上述相似的過程也可以計(jì)算二維傅里葉反變換,傅里葉變換,,,,??,?? f?x, y?,f?x, y??,?? f?x, y?,7.,平均值 由二維傅里葉變換的定義,而,M ?1N?1 x?0 y?0,1 MN,F?u,v??,f?x, y?e? j2??ux/M ?vy/ N?,M ?1N?1 x?0 y?0,1 MN,所以 F?0,0??,?,M ?1N?1 x?0 y?0,1 MN,傅里葉變換,f?x, y?? F?0,0?,7.,平均值 所以 ? 上式說明：如果f(x,y)是一幅圖像，在 原點(diǎn)的傅里葉變換即等于圖像的平均灰度 級(jí),傅里葉變換,,,?? f?m,n?h?x?m, y?n?,8.,卷積理論 大小為MN的兩個(gè)函數(shù)f(x,y)和h(x,y)的離散,卷積,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? f?x,y?h?x,y??F?u,v??H?u,v?,傅里葉變換,,,?? f ?m,n?h?x?m, y?n?,f ?x,y?h?x,y??F?u,v??H?u,v?,9.,相關(guān)性理論 大小為MN的兩個(gè)函數(shù)f(x,y)和h(x,y)的相關(guān),f*表示f的復(fù)共軛。對(duì)于實(shí)函數(shù)， f*＝f,相關(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? *,傅里葉變換,,,,,f?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)理論 2 2 2 2 注：復(fù)數(shù)和它的復(fù)共軛的乘積是復(fù)數(shù)模的平方,傅里葉變換,?,卷積和相關(guān)性理論總結(jié),? ?,卷積是空間域過濾和頻率域過濾之間的紐帶 相關(guān)的重要應(yīng)用在于匹配：確定是否有感興,趣的物體區(qū)域,? ? ?,f(x,y)是原始圖像 h(x,y)作為感興趣的物體或區(qū)域（模板） 如果匹配，兩個(gè)函數(shù)的相關(guān)值會(huì)在h找到f,中相應(yīng)點(diǎn)的位置上達(dá)到最大,傅里葉變換,,,,相關(guān)性匹配舉例,圖像f(x,y),模板h(x,y),延拓圖像f(x,y) 相關(guān)函數(shù)圖像,延拓圖像h(x,y) 通過相關(guān)圖像最大 值的水平灰度剖面圖,傅里葉變換,?,傅里葉變換,? ? ?,傅里葉變換及其反變換 傅里葉變換的性質(zhì) 快速傅里葉變換(FFT),?,只考慮一維的情況，根據(jù)傅里葉變,換的分離性可知，二維傅里葉變換可 由連續(xù)2次一維傅里葉變換得到,,?,快速傅里葉變換(FFT),?,為什么需要快速傅里葉變換？,?,快速傅里葉變換(FFT)則只需要Mlog2M次運(yùn)算,? FFT算法與原始變換算法的計(jì)算量之比是log2M/M，如 M=1024≈103,則原始變換算法需要106次計(jì)算，而FFT需 要104次計(jì)算，F(xiàn)FT與原始變換算法之比是1：100,1 M?1 M x?0,F?u??,f?x?e?j2?ux/M,u ? 0,1,2,.,M ?1,? 對(duì)u的M個(gè)值中的每一個(gè)都需進(jìn)行M次復(fù)數(shù)乘法(將f(x) 與e?j2?ux/M相乘)和M-1次加法，即復(fù)數(shù)乘法和加法的次 數(shù)都正比于M2,,,,,,?,?,FFT算法基本思想 FFT算法基于一個(gè)叫做逐次加倍的方法。通 過推導(dǎo)將原始傅里葉轉(zhuǎn)換成兩個(gè)遞推公式,M ?1 x?0,1 M,F?u??,快速傅里葉變換(FFT),?,1 2,?Feven?u?? Fodd?u?W2uk,F?u??,?,1 2,?Feven?u??Fodd?u?W2uk,F?u ? K??,f ?x?e? j2?ux /M u ? 0,1,2,.,M ?1,?,FFT算法基本思想,其中：M = 2K Feven(u)、Fodd(u)是K個(gè)點(diǎn)的傅里葉值,u ? 0,1,2,.,M ?1,快速傅里葉變換(FFT),?,1 2,?Feven?u?? Fodd?u?W2uk,F?u??,?,1 2,?Feven?u??Fodd?u?W2uk,F?u ? K??,,,?,?,?,FFT公式推導(dǎo) FFT算法基于一個(gè)叫做逐次加倍的方法。為 方便起見用下式表達(dá)離散傅立葉變換公式,這里,是一個(gè)常數(shù),1 M?1 M x?0,F?u??,f?x?e?j2?ux/M,快速傅里葉變換(FFT),?,M ?1 x?0,f?x?WM ux,1 M,WM ? e? j2? /M,,,,?,快速傅里葉變換(FFT) 假設(shè)M的形式是 M ?2n n為正整數(shù)。因此，M可以表示為 M?2K 將M=2K帶入上式,2K ?1 x?0,f ?x?W2uxK,1 2K,F?u??,1? 1 K?1 u?2x? 1 K?1 u?2x?1?? 2?K,,,? ? ? ? ? ? ? ? ? ? 2 1 2 K K W W x f u F,? ? ? 2 K W x f,快速傅里葉變換(FFT),推導(dǎo)：因?yàn)?所以,帶入上式有,WM ?e?j2?/M,1?1 K?1 ux 1 K?1 ux u ? 2?K x?0 K x?0 ?,W22 K ux ? e? j2? (2ux)/2K ? e? j2? (ux)/K ?WK ux,,,? ? x 0,? ? x 0,快速傅里葉變換(FFT) 定義兩個(gè)符號(hào),f?2x?WK ux,1 K?1 K,Feven?u??,f?2x?1?WK ux,1 K?1 K,F odd?u??,u?0,1,2,.,K?1,,?Feven?u?? Fodd?u?W2K,快速傅里葉變換(FFT) 得到FFT的第一個(gè)公式,該公式說明F(u)可以通過奇部和偶部之和 來計(jì)算,?,u,1 2,F?u??,?WK ue j???2? ?WK u??1?,W,?W2uKe j???1? ?W2uK??1?,快速傅里葉變換(FFT),推導(dǎo)：,?WK u,??2?,u?K 2K,? e,? j2??u?K?/2K,?e?j2?u/2Ke?j?,WK u?K ? e? j2? (u?K)/K ? e? j2?u/Ke? j2?,??W2uK,??1?,,,,,,,,,,,,?,? ? ? f?2x?W2K,? ? x 0 f?2x?1?W2K,?,?,?,f?2x?WK,?,f?2x?1?WK ?u?K?xW2?K u?K??,f?2x?WK ?,? ? ? x 0,? ?,?,?,f?2x?1?WK ux ?W2uK ?,快速傅里葉變換(FFT),? ?,?,?,K?1 x?0,K?1 x?0,?u?K?x,1 K,1 ? 1 2 ??K,f?x?W2?K u?K?x,1 2K?1 2K x?0,F?u?K??,?,1 K?1 ?u?K??2x?1??,K,1?1 K?1 ?u?K??2x? 2?K x?0,? ?,1? 1 K?1 ux 1 K?1 2?K x?0 K,?,1 2,?Feven?u??Fodd?u?W2uK,?,,快速傅里葉變換(FFT) 得到FFT的第二個(gè)公式,該公式說明F(u＋K)可以通過奇部和偶部之 差來計(jì)算,?,1 2,?Feven?u?? Fodd?u?W2uK,F?u ? K??,,,?Feven?u?? Fodd?u?W2K,快速傅里葉變換(FFT),?,最后得到FFT的二個(gè)公式,?,1 2,?Feven?u?? Fodd?u?W2uK,F?u ? K??,?,u,1 2,F?u??,?,分析這些表達(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),?,歸納快速傅立葉變換的思想：,（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),?,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),?,FFT算法舉例,首先分成奇偶兩組： 有：{ f(0), f(2), f(4), f(6) } { f(1), f(3), f(5), f(7) } 為了利用遞推特性，再分成兩組： 有： { f(0), f(4) }， { f(2), f(6) } { f(1), f(5) }， { f(3), f(7) },快速傅里葉變換(FFT),快速傅里葉變換(FFT),?,FFT算法實(shí)現(xiàn),?,對(duì)輸入數(shù)據(jù)的排序可根據(jù)一個(gè)簡(jiǎn)單的位對(duì)換,規(guī)則進(jìn)行 ?如用x表示f(x)的1個(gè)自變量值，那么它排序后對(duì)應(yīng) 的值可通過把x表示成二進(jìn)制數(shù)并對(duì)換各位得到 ? 例如N=23,f(6)排序后為f(3),因?yàn)?＝1102而0112 ＝3,?,把輸入數(shù)據(jù)進(jìn)行了重新排序，則輸出結(jié)果是,正確的次序。反之不把輸入數(shù)據(jù)進(jìn)行排序，則 輸出結(jié)果需要重新排序才能得到正確的次序,?,FFT算法實(shí)現(xiàn) 地址的排序：——按位倒序規(guī)則 例如：N = 23 = 8,原地址 000 001 010 011 100 101 110 111,原順序 f(0) f(1) f(2) f(3) f(4) f(5) f(6) f(7),新地址 000 100 010 110 001 101 011 111,新順序 f(0) f(4) f(2) f(6) f(1) f(5) f(3) f(7),快速傅里葉變換(FFT),,?,FFT算法實(shí)現(xiàn)——幾個(gè)關(guān)鍵點(diǎn),2）計(jì)算順序及地址增量：2n,n = 0,1,2…,地址+1 f(0) f(4) f(2) f(6) f(1) f(5) f(3) f(7),地址+2 F2(0) F2(4) F2(2) F2(6) F4(1) F2(5) F2(3) F2(7),地址+4 F4(0) F4(4) F4(2) F4(6) F4(1) F4(5) F4(3) F4(7),快速傅里葉變換(FFT),