【正文】 2m的 DFT的計算 ， 通過計算兩個 N/2點的 DFT， 來計算 N個點的 DFT 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 ?逆向 FFT算法 – 算法思想描述：用正向變換計算逆向變換 N1 F(u) = 1/N? f(x)exp[j2?ux/N] x=0 u = 0, 1, 2, ...N1 N1 f(x) = ? F(u)exp[j2?ux/N] u=0 x = 0, 1, 2, ...N1 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 ?逆向 FFT算法 在離散逆向變換表達式兩邊同取共軛，并除 N N1 1/Nf*(x) = 1/N? F*(u) exp[j2?ux/N] u=0 u = 0, 1, 2, ...N1 用正向變換算法計算，得到 1/Nf*(x) ，取共軛并乘上 N，即得到 f(x) 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 ?FFT算法實現(xiàn) 通過一個實例來體會一下 FFT算法： 設：有函數(shù) f(x)，其 N = 23 = 8 有： {f(0), f(1), f(2), f(3), f(4), f(5), f(6), f(7)} 計算： {F(0), F(1), F(2), F(3), F(4), F(5), F(6),F(7)} 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 ?FFT算法實現(xiàn) 首先分成奇偶兩組： 有： { 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) } 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 { f(0), f(4) } { f(2), f(6) } { f(1), f(5) } { f(3), f(7) } {F2(0),F2(4)} {F2(2),F2(6)} {F2(1),F2(5)} {F2(3),F2(7)} {F4(0), F4(4), F4(2), F4(6)} {F4(1), F4(5), F4(3),F4(7)} {F8(0), F8(1), F8(2), F8(3), F8(4), F8(5), F8(6), F8(7)} 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 ? 算法實現(xiàn)的幾個關鍵點 1）地址的排序： ——按位倒序規(guī)則 例如： N = 23 = 8 原地址 原順序 新地址 新順序 000 f(0) 000 f(0) 001 f(1) 100 f(4) 010 f(2) 010 f(2) 011 f(3) 110 f(6) 100 f(4) 001 f(1) 101 f(5) 101 f(5) 110 f(6) 011 f(3) 111 f(7) 111 f(7) 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 ? 算法實現(xiàn)的幾個關鍵點 2）計算順序及地址增量 地址 +1 地址 +2 地址 +4 f(0) F2(0) F4(0) f(4) F2(4) F4(4) f(2) F2(2) F4(2) f(6) F2(6) F4(6) f(1) F4(1) F4(1) f(5) F2(5) F4(5) f(3) F2(3 ) F4(3) f(7) F2(7) F4(7) 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 ? 算法實現(xiàn)的幾個關鍵點 3）復系數(shù)的計算： ——尤拉公式 W2M = exp[j2?/2M] = exp[j?/M] = cos(?/M) + jsin(?/M) 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 SUBROUTINE FFT(F,LN) COMPLEX F(1024),U,W,T,CMPLX PI = N = 2**LN /*要計算 FFT的函數(shù)點數(shù) */ NV2 = N/2 NM1 = N1 J = 1 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 DO 3 I = 1,NM1 IF (I. GE. J) GOTO 1 T = F(J) F(J) = F(I) T = F(I) 1 K = NV2 2 IF (K .GE. J) GOTO 3 K = K/2 GOTO 2 3 J = J + K /*交換輸入函數(shù) F(I)的順序 */ 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 DO 5 L = 1,LN LE = 2**L LE1 = LE /2 /*地址增量計算*/ U = (, ) /*系數(shù)賦初值 */ W = CMPLX(COS(PI/LE1),SIN(PI/LE1)) DO 5 J = 1,LE1 DO 4 I = J, N, LE IP = I +LE1 /*計算地址 */ T= F(IP) * U /*奇部乘系數(shù) */ F(IP) = F(I) T /*后半部分計算 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 第三節(jié) 頻域變換 :快速傅立葉變換 4 F(I) = F(I) + T /*后半部分計算 */ 5 U = U*W /*新遞推系數(shù)計算 */ DO 6 I = 1, N 6 F(I) = F(I) / FLOAT(N) RETURN END 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 第二次作業(yè) FFT算法的實現(xiàn) 1. 將寬為 2n的正方形圖象，用 FFT算法 從空域變 換到頻域； 2. 將頻域圖象以中心為原點的四個象限，做水平和垂直鏡像，使圖象能量中心，對應到幾何中心，并用頻域圖象的模來進行顯示。 3. 將頻域圖象，通過 FFT逆變換到空域，并顯示。 第二章數(shù)字圖象處理基礎 第三節(jié) 頻域變換 請?zhí)釂?