【正文】 ? F*(u,v)G(u,v) 同時(shí)有： f*(x,y) g(x,y) ? F(u,v)?G(u,v) 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 快速傅立葉變換 – FFT算法 – 逆向 FFT算法 – 算法實(shí)現(xiàn) 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 ? FFT算法 ——基本思想 FFT算法基于一個(gè)叫做 遞推加倍 的方法 。 系統(tǒng)的輸入是一個(gè)或兩個(gè)變量的函數(shù)，輸出 是相同變量的另一個(gè)函數(shù)。得到 Feven(u)和 Fodd(u) （ 3）奇部與偶部之和得到 F(u)的前 (N/2)個(gè)值。 設(shè)： a(x,y) = x cos(?) y sin(?) b(x,y) = x sin(?) + y cos(?) F{f(a(x,y),b(x,y))} ? F(a(u,v),b(u,v)) 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :二維傅立葉變換特性 ? 旋轉(zhuǎn)特性 – 結(jié)論： 對(duì)圖象的旋轉(zhuǎn)變換和傅立葉變換的順序是可交換的 F{R{f(x,y)}} ? R{F{f(x,y)}} 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :二維傅立葉變換特性 ? 線性與相似性 – 線性的描述：傅立葉變換是線性系統(tǒng)、函數(shù)和的傅立葉變換是可分離的 設(shè)： f(x,y) 的傅立葉變換為 F{f(x,y)} g(x,y)的傅立葉變換為 F{g(x,y)} 有： F{f(x,y)+g(x,y)} = F{f(x,y)}+F{g(x,y)} 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :二維傅立葉變換特性 ? 線性的證明 用一維函數(shù)為例進(jìn)行證明： F{f(x)+g(x)} = F(u) = ? (f(x)+g(x))exp[j2?ux]dx = ? (f(x)exp[j2?ux] + g(x)exp[j2?ux]) dx = ?f(x)exp[j2?ux]dx + ?g(x)exp[j2?ux]dx = F(u) + G(u) 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :二維傅立葉變換特性 ? 線性與相似性 – 相似性的描述： a f(x,y) ? a F(u,v) 且有： f(ax,by) ? 1/|ab|F(u/a,v/b) 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :二維傅立葉變換特性 ? 相似性的證明 用一維函數(shù)為例進(jìn)行證明： f(ax)? 1/|a|F(u/a) F{f(ax)} = F(u) = ?f(ax)exp[j2?ux]dx 將指數(shù)和積分同時(shí)乘以 1 = a/a 并設(shè)： v = ax, dv = adx F{f(ax)} = ? f(ax)exp[j2?ux a/a] a/a dx =1/a ? f(ax)exp[j2?u xa/a] adx =1/a ? f(v)exp[j2?v (u /a)] dv =1/|a|F(u/a) 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :二維傅立葉變換特性 ? 均值性 – 均值性的描述： 離散函數(shù)的均值等于該函數(shù)傅立葉變換在 (0,0)點(diǎn)的值 M1N1 ?f(x ,y) = 1/MN??f(x,y)e0 x=0 y=0 ?f(x ,y) = F(0,0) 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :二維傅立葉變換特性 ? 拉普拉斯 – 拉普拉斯特性的描述： 給出二維拉普拉斯函數(shù)的傅立葉變換表達(dá)式： 拉普拉斯函數(shù)： ?2 f(x,y) = ?2f / ?x2 + ?2f / ?y2 其傅立葉變換為： F{?2 f(x,y)} = 4?2(u2 +v2)F(u,v) 這個(gè)定理將在圖象的邊界提取中用到 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :二維傅立葉變換特性 ? 卷積與相關(guān) :空域和頻域之間的基本聯(lián)系 – 卷積定理的描述： 空域中的卷積等價(jià)于頻域中的相乘 f(x,y)*g(x,y) ? F(u,v)G(u,v) F{f(x,y)*g(x,y)} = F(u,v)G(u,v) 同時(shí)有： f(x,y) g(x,y) ? F(u,v)*G(u,v) 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :二維傅立葉變換特性 ? 卷積定理成立的證明 用一維函數(shù)為例進(jìn)行證明： F{f(x)*g(x)} = ? f(x)*g(x) exp[j2?ux]dx = ? [? f(t)g(xt)dt] exp[j2?ux]dx 對(duì)于上面這個(gè)式子 ， 我們可以看出是一個(gè)兩個(gè)變量 t、 x的二維積分 。 系統(tǒng) x(t)輸入 y(t)輸出 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :理論基礎(chǔ) ?線性系統(tǒng) – 線性系統(tǒng) 的定義： 對(duì)于某特定系統(tǒng)，有： x1(t) y1(t) x2(t) y2(t) 該系統(tǒng)是線性的當(dāng)且僅當(dāng)： x1(t) + x2(t) y1(t) + y2(t) 從而有： a*x1(t) a*y1(t) 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :理論基礎(chǔ) ?線性系統(tǒng) – 線性系統(tǒng) 移不變性 的定義： 對(duì)于某線性系統(tǒng) ， 有： x(t) y(t) 當(dāng)輸入信號(hào)沿時(shí)間軸平移 T， 有： x(t T) y(t T) 則稱該線性系統(tǒng)具有移不變性 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :理論基礎(chǔ) ?卷積 – 卷積的定義 – 離散一維卷積 – 二維卷積的定義 – 離散二維卷積 – 相關(guān)的定義 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :理論基礎(chǔ) – 卷積 的定義 ?對(duì)于一個(gè)線性系統(tǒng)的輸入 f(t)和輸出 h(t)，如果有一個(gè)一般表達(dá)式，來說明他們的關(guān)系，對(duì)線性系統(tǒng)的分析，將大有幫助 ?卷積積分就是這樣的一般表達(dá)式 ? h(t) = ? g(t ?)f(?)d? 記為： h = g * f ? g(t)稱為 沖激響應(yīng)函數(shù) 第二章數(shù)字圖象處理基礎(chǔ) 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :理論基礎(chǔ) – 離散一維卷積 h(i) = f(i)*g(i) = ? f(j)g(ij) j – 二維卷積的定義 ? h(x,y) = f*g = ? ? f(u,v)g(x – u, y – v)dudv