圖像傅里葉變換PPT課件

研究生課程 數(shù)字圖像處理和分析 DigitalImageProcessingandAnalysis 杜紅 E mail duhmail 第三章傅里葉變換 傅里葉變換 為什么要在頻率域研究圖像增強(qiáng) 可以利用頻率成分和圖像外表之間的對應(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 1x 0 1M F u f x ej 2 ux M M 1x 0M 1x 0 1M1M 傅里葉變換 F u R u I u 22 u arctan 傅里葉變換的極坐標(biāo)表示F u F u e j u 幅度或頻率譜為12R u 和I u 分別是F u 的實(shí)部和虛部相角或相位譜為 I u R u 傅里葉變換 P u F u R u I u 傅里葉變換的極坐標(biāo)表示 功率譜為 f x 的離散表示 F u 的離散表示 222 f x f x0 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 22 u v arctan 二維DFT的極坐標(biāo)表示F u v F u v e j u v 幅度或頻率譜為12R 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 它是M N區(qū)域的中心 u 0 1 2 M 1 v 0 1 2 N 1 222 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)的傅里葉變換等于圖像的平均灰度級 M 1N 1x 0y 0 1MN F 0 0 傅里葉變換 如果f x y 是實(shí)函數(shù) 它的傅里葉變換是 對稱的 即 F u v F u v 傅里葉變換的頻率譜是對稱的F u v F u v 傅里葉變換 傅里葉變換 傅里葉變換 二維傅里葉變換的性質(zhì) 1 2 3 4 5 6 7 8 9 平移性質(zhì)分配律尺度變換 縮放 旋轉(zhuǎn)性周期性和共軛對稱性平均值可分性卷積相關(guān)性 傅里葉變換 1 傅里葉變換對的平移性質(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 表明對f x y 的平移不影響其傅里葉變換的幅值 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ù)和其傅里葉變換的對應(yīng)性 傅里葉變換 1 f x y 1 1 傅里葉變換對的平移性質(zhì) 續(xù) 當(dāng)u0 M 2且v0 N 2 帶入 1 和 2 得到 e x y e j x y j2 u0 x 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 上述公式表明 傅里葉變換對加法滿足分配律 但對乘法則不滿足 傅里葉變換 3 尺度變換 縮放 給定2個(gè)標(biāo)量a和b 可以證明對傅里葉變換下列2個(gè)公式成立af x y aF u v F u a v b 1ab 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 將它們帶入傅里葉變換對得到f r 0 F 0 f x y 旋轉(zhuǎn)角度 0 F u v 也將轉(zhuǎn)過相同的角度F u v 旋轉(zhuǎn)角度 0 f x y 也將轉(zhuǎn)過相同的角度 傅里葉變換 5 周期性和共軛對稱性 盡管F u v 對無窮多個(gè)u和v的值重復(fù)出現(xiàn) 但只需根據(jù)在任一個(gè)周期里的N個(gè)值就可以從F u v 得到f x y 只需一個(gè)周期里的變換就可將F u v 在頻域里完全確定同樣的結(jié)論對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 周期性和共軛對稱性如果f x y 是實(shí)函數(shù) 則它的傅里葉變換具有共軛對稱性 F u v F u v 其中 F u v 為F u v 的復(fù)共軛 復(fù)習(xí) 當(dāng)兩個(gè)復(fù)數(shù)實(shí)部相等 虛部互為相反數(shù)時(shí) 這兩個(gè)復(fù)數(shù)叫做互為共軛復(fù)數(shù) 傅里葉變換 對于一維變換F u 周期性是指F u 的周期長 度為M 對稱性是指頻譜關(guān)于原點(diǎn)對稱 周期性和共軛對稱性舉例 半周期的傅里葉頻譜一幅二維圖像的傅里葉頻譜 全周期的傅里葉頻譜中心化的傅里葉頻譜 f x y e j2 vy N x0 y0 1M 1 j2 ux M1N 1 F x v x0e 6 F x v 是沿著f x y 的一行所進(jìn)行的傅里葉變換 當(dāng)x 0 1 M 1 沿著f x y 的所有行計(jì)算傅里葉變換 分離性F u v eMN1M 1 j2 ux MM 傅里葉變換 6 分離性 二維傅里葉變換的全過程 先通過沿輸入圖像的每一行計(jì)算一維變換再沿中間結(jié)果的每一列計(jì)算一維變換可以改變上述順序 即先列后行上述相似的過程也可以計(jì)算二維傅里葉反變換 傅里葉變換 f x y f x y f x y 7 平均值由二維傅里葉變換的定義 而 M 1N 1x 0y 0 1MN F u v f x y e j2 ux M vy N M 1N 1x 0y 0 1MN 所以F 0 0 M 1N 1x 0y 0 1MN 傅里葉變換 f x y F 0 0 7 平均值所以 上式說明 如果f x y 是一幅圖像 在原點(diǎn)的傅里葉變換即等于圖像的平均灰度級 傅里葉變換 f m n h x m y n 8 卷積理論大小為M N的兩個(gè)函數(shù)f x y 和h x y 的離散 卷積 1M 1N 1MNm 0n 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)性理論大小為M N的兩個(gè)函數(shù)f x y 和h x y 的相關(guān) f 表示f的復(fù)共軛 對于實(shí)函數(shù) f f 相關(guān)定理 1M 1N 1 MNm 0n 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)理論2222注 復(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ì)算 FFT與原始變換算法之比是1 100 1M 1Mx 0 F u f x e j2 ux M u 0 1 2 M 1 對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 1x 0 1M F u 快速傅里葉變換 FFT 12 Feven u Fodd u W2uk F u 12 Feven u Fodd u W2uk F u K f x e j2 ux Mu 0 1 2 M 1 FFT算法基本思想 其中 M 2KFeven u Fodd u 是K個(gè)點(diǎn)的傅里葉值 u 0 1 2 M 1 快速傅里葉變換 FFT 12 Feven u Fodd u W2uk F u 12 Feven u Fodd u W2uk F u K FFT公式推導(dǎo)FFT算法基于一個(gè)叫做逐次加倍的方法 為方便起見用下式表達(dá)離散傅立葉變換公式 這里 是一個(gè)常數(shù) 1M 1Mx 0 F u f x e j2 ux M 快速傅里葉變換 FFT M 1x 0 f x WMux 1M WM e j2 M 快速傅里葉變換 FFT 假設(shè)M的形式是M 2nn為正整數(shù) 因此 M可以表示為M 2K將M 2K帶入上式 2K 1x 0 f x W2uxK 12K F u 1 1K 1u 2x 1K 1u 2x 1 2 K 212KKWWxfuF 2KWxf 快速傅里葉變換 FFT 推導(dǎo) 因?yàn)?所以 帶入上式有 WM e j2 M 1 1K 1ux1K 1uxu 2 Kx 0Kx 0 W22Kux e j2 2ux 2K e j2 ux K WKux x0 x0 快速傅里葉變換 FFT 定義兩個(gè)符號 f 2x WKux 1K 1K Feven u f 2x 1 WKux 1K 1K Fodd u u 0 1 2 K 1 Feven u Fodd u W2K 快速傅里葉變換 FFT 得到FFT的第一個(gè)公式 該公式說明F u 可以通過奇部和偶部之和來計(jì)算 u 12 F u WKuej 2 WKu 1 W W2uKej 1 W2uK 1 快速傅里葉變換 FFT 推導(dǎo) WKu 2 u K2K e j2 u K 2K e j2 u 2Ke j WKu K e j2 u K K e j2 u Ke j2 W2uK 1 f 2x W2K x0f 2x 1 W2K f 2x WK f 2x 1 WK u K xW2 Ku K f 2x WK x0 f 2x 1 WKux W2uK 快速傅里葉變換 FFT K 1x 0 K 1x 0 u K x 1K 1 12 K f x W2 Ku K x 12K 12Kx 0 F u K 1K 1 u K 2x 1 K 1 1K 1 u K 2x 2 Kx 0 1 1K 1ux1K 12 Kx 0K 12 Feven u Fodd u W2uK 快速傅里葉變換 FFT 得到FFT的第二個(gè)公式 該公式說明F u K 可以通過奇部和偶部之差來計(jì)算 12 Feven u Fodd u W2uK F u K Feven u Fodd u W2K 快速傅里葉變換 FFT 最后得到FFT的二個(gè)公式 12 Feven u Fodd u W2uK F u K u 12 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 對于任何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