數(shù)字圖象處理 4 北京大學(xué)計(jì)算機(jī)研究所

1、數(shù)字圖象處理1第三節(jié) 頻域變換2.3.1 傅立葉變換導(dǎo)言理論基礎(chǔ)、連續(xù)與離散的傅立葉變換2.3.2 二維傅立葉變換特性可分離性、周期與共軛對(duì)稱、平移性、旋轉(zhuǎn)特性、線性與相似性 、均值性、拉普拉斯、卷積與相關(guān)2.3.3 快速傅立葉變換FFT算法、逆向FFT算法、算法實(shí)現(xiàn)2第三節(jié) 頻域變換2.3.1 傅立葉變換導(dǎo)言理論基礎(chǔ)連續(xù)與離散的傅立葉變換32.3.1 傅立葉變換導(dǎo)言:理論基礎(chǔ)理論基礎(chǔ)線性系統(tǒng)卷積與相關(guān)42.3.1 傅立葉變換導(dǎo)言:理論基礎(chǔ)線性系統(tǒng)系統(tǒng)的定義：接受一個(gè)輸入，并產(chǎn)生相應(yīng)輸出的任何實(shí)體。系統(tǒng)的輸入是一個(gè)或兩個(gè)變量的函數(shù)，輸出是相同變量的另一個(gè)函數(shù)。系統(tǒng)x(t)輸入y(t)輸出52.

2、3.1 傅立葉變換導(dǎo)言:理論基礎(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)62.3.1 傅立葉變換導(dǎo)言:理論基礎(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)具有移不變性72.3.1 傅立葉變換導(dǎo)言:理論基礎(chǔ)卷積卷積的定義離散一維卷積二維卷積的定義離散二維卷積相關(guān)的定義8第三節(jié) 頻域變換:理論基礎(chǔ)卷積的定義對(duì)于一個(gè)線性系統(tǒng)的輸

3、入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ù)92.3.1 傅立葉變換導(dǎo)言:理論基礎(chǔ)離散一維卷積 h(i) = f(i)*g(i) = f(j)g(i-j) j二維卷積的定義 h(x,y) = f*g = f(u,v)g(x u, y v)dudv -102.3.1 傅立葉變換導(dǎo)言:理論基礎(chǔ)離散二維卷積 h(x,y) = f*g = f(m,n)g(x m, y n) m n相關(guān)的定義 h(t) = g(t + )f()d 記

4、為：y = g x -112.3.1 傅立葉變換導(dǎo)言:傅立葉變換連續(xù)與離散的傅立葉變換一維連續(xù)傅立葉變換二維連續(xù)傅立葉變換離散傅立葉變換離散傅立葉變換的計(jì)算與顯示122.3.1 傅立葉變換導(dǎo)言:傅立葉變換一維連續(xù)傅立葉變換：定義設(shè) f(x)為實(shí)變量x的連續(xù)函數(shù)， f(x)的傅立葉變換表示為Ff(x),定義為： Ff(x) = F(u) = f(x)exp(-j2ux)dx -其中 j2 = -1132.3.1 傅立葉變換導(dǎo)言:傅立葉變換一維連續(xù)傅立葉逆變換：定義如果給定F(u),f(x)可以由傅立葉逆變換得到： FF(u) = f(x) = F(u)exp(j2ux)du -其中 j2 = -

5、1142.3.1 傅立葉變換導(dǎo)言:傅立葉變換一維連續(xù)傅立葉變換：幾個(gè)概念 假設(shè)函數(shù)f(x)為實(shí)函數(shù)。但一個(gè)實(shí)函數(shù)的傅立葉變換可能為復(fù)函數(shù)：F(u) = R(u) + jI(u)（1） f(x)的傅立葉模記為： |F(u)| |F(u)| = R2(u) + I2(u)1/2（2） f(x)的傅立葉模平方記為： P(u) P(u) = |F(u)|2 = R2(u) + I2(u)152.3.1 傅立葉變換導(dǎo)言:傅立葉變換一維連續(xù)傅立葉變換：幾個(gè)概念（3） f(x)的傅立葉相位記為： (u) (u) = tan-1 (I(u) / R(u)（4） 傅立葉變換中的變量u通常稱為頻率變量 這個(gè)名稱源

6、于尤拉公式中的指數(shù)項(xiàng) exp-j2ux = cos2ux - jsin2ux 如果把傅立葉變換的積分解釋為離散項(xiàng)的和，則易推出F(u)是一組sin和cos函數(shù)項(xiàng)的無限和，其中u的每個(gè)值決定了其相應(yīng)cos, sin函數(shù)對(duì)的頻率。162.3.1 傅立葉變換導(dǎo)言:傅立葉變換二維連續(xù)傅立葉變換 如果f(x,y)連續(xù)可積，并且F(u,v)可積，則存在以下傅立葉變換對(duì)，其中u,v為頻率變量： Ff(x,y)=F(u,v)=f(x,y)exp-j2(ux+vy)dxdy - FF(u,v)=f(x,y)=F(u,v)expj2(ux+vy)dudv -172.3.1 傅立葉變換導(dǎo)言:傅立葉變換二維連續(xù)傅立葉

7、變換 二維傅立葉模、相位和模平方分別為： 模： |F(u,v)| = R2(u,v) + I2(u,v)1/2 相位： (u,v) = tan-1 (I(u,v) / R(u,v) 模平方：P(u,v) = |F(u,v)|2 = R2(u,v) + I2(u,v)182.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換 假設(shè)連續(xù)函數(shù)f(x),通過取N個(gè)x單位的采樣點(diǎn)，被離散化為一個(gè)序列： f(x0), f(x0+x) , f(x0+2x), ,f(x0+N1 x) 無論將x作為離散的或連續(xù)的變量，在子序列中來研究都將是方便的，僅僅依賴于討論的上下文。為作到此要求定義：f(x) = f(x0+

8、 xx)192.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換 其中假設(shè)x現(xiàn)在的離散值是：0,1,2, ,N-1。 f(x0),f(x0+x),f(x0+2x), . , f(x0+N1x)表示相對(duì)與連續(xù)函數(shù)的任意N個(gè)統(tǒng)一的空間采樣202.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換函數(shù)f(x0+xx)的離散傅立葉變換對(duì)有： N-1F(u) = 1/N f(x)exp-j2ux/N x=0u = 0, 1, 2, .N-1 N-1 逆變換：f(x) = F(u)expj2ux/N u=0 x = 0, 1, 2, .N-1212.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換:二維 M

9、-1 N-1F(u,v) =1/MNf(x,y)exp-j2(ux/M+vy/N) x=0 y=0u = 0, 1, 2, M-1; v = 0, 1, 2, .N-1 M-1 N-1 f(x,y) = F(u,v)expj2(ux/M+vy/N) u=0 v=0 x = 0, 1, 2, .N-1; y = 0, 1, 2, .N-1222.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換的計(jì)算與顯示離散傅立葉變換的計(jì)算舉例離散傅立葉變換的顯示232.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換的計(jì)算舉例xf(x0)=f(x0+x)01231234242.3.1 傅立葉變換導(dǎo)言:傅立葉變

10、換F(0) = 1/4f(x)exp0= 1/4f(0) + f1(1) + f(2) + f(3)= 1/4(2 + 3 + 4 + 4)= 3.25F(1) = 1/4f(x)exp-j2x/4)= 1/4(2e0 + 3e j21/4 + 4e j22/4 + 4e j23/4)= 1/4(-2 + j)F(2) = -1/4(1 + j0)F(3) = -1/4(2 + j)252.3.1 傅立葉變換導(dǎo)言:傅立葉變換 離散傅立葉變換的計(jì)算舉例因?yàn)?，函?shù)f(x,y)的傅立葉變換是f(x,y)積分的函數(shù)因此，計(jì)算每一個(gè)傅立葉變換值，原函數(shù)f(x,y)的每一個(gè)點(diǎn)都需要參與262.3.1 傅立

11、葉變換導(dǎo)言:傅立葉變換離散傅立葉變換的顯示 通過對(duì)傅立葉變換模，來顯示傅立葉變換圖象。由于模的值域大于顯示的值域，因此要進(jìn)行動(dòng)態(tài)值域的壓縮D(u,v) = c log(1 + |F(u,v)|)其中： c = 255 / k; k = max(log(1 + |F(u,v)|)值域0,k的上限（最大值）272.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換的顯示282.3.1 傅立葉變換導(dǎo)言:傅立葉變換離散傅立葉變換的顯示對(duì)稱平移后29第三節(jié) 頻域變換:二維傅立葉變換特性2.3.2 二維傅立葉變換特性可分離性周期與共軛對(duì)稱平移性旋轉(zhuǎn)特性 線性與相似性 均值性 拉普拉斯 卷積與相關(guān)302.3.

12、2 二維傅立葉變換特性:可分離性可分離性二維離散傅立葉變換DFT可分離性的基本思想是： 二維DFT可分離為兩次一維DFT應(yīng)用： 二維快速傅立葉算法FFT ，是通過計(jì)算兩次一維FFT實(shí)現(xiàn)的312.3.2 二維傅立葉變換特性:可分離性可分離性的定義 M-1 N-1 F(u,v)=1/MN f(x,y)e(-j2vy/N) e(-j2ux/M) x=0 y=0u = 0, 1, 2, M-1; v = 0, 1, 2, .N-1 M-1 N-1 f(x,y)= F(u,v)e(j2vy/N) e(j2ux/M) u=0 v=0 x = 0, 1, 2, .N-1; y = 0, 1, 2, .N-1

13、322.3.2 二維傅立葉變換特性:可分離性可分離性成立的推導(dǎo)先對(duì)行（y變量）做變換： N-1F(x,v)=1/Nf(x,y)exp(-j2vy/N) y=0然后對(duì)列（x變量）進(jìn)行變換： M-1F(u,v)=1/MF(x,v)exp(-j2ux/M) x=0332.3.2 二維傅立葉變換特性:可分離性先對(duì)行做變換：然后對(duì)列進(jìn)行變換：f(x,y)（0，0）（N-1，M-1）xyF(x,v)（0，0）（N-1，M-1）xvF(x,v)（0，0）（N-1，M-1）xvF(u,v)（0，0）（N-1，M-1）uv342.3.2 二維傅立葉變換特性:平移性平移性定理平移性的描述函數(shù)自變量的位移的傅立葉變

14、換產(chǎn)生一個(gè)復(fù)系數(shù) Ff(x-a,y-b) = exp-j2(au+bv) F(u,v)352.3.2 二維傅立葉變換特性:平移性平移性成立的證明用一維函數(shù)為例進(jìn)行證明：設(shè)位移為a,f(x-a)的傅立葉變換為： Ff(x-a) = F(u) = f(x-a)exp(-j2ux)dx -將積分乘以 1 = exp(-j2au) exp(j2au) 且設(shè)：v = x-a, dv = dx 362.3.2 二維傅立葉變換特性:平移性平移性成立的證明Ff(x-a) = F(u) = f(x-a)exp(-j2ux) exp(-j2au)exp(j2au) dx - =exp(-j2au) f(x-a)e

15、xp(-j2ux)exp(j2ua)dx - 372.3.2 二維傅立葉變換特性:平移性 = exp(-j2au) f(x-a)exp-j2u(x-a)dx - = exp(-j2au) f(v)exp-j2uvdv - = exp(-j2au)F(u)382.3.2 二維傅立葉變換特性:周期與共軛對(duì)稱周期與共軛對(duì)稱周期性的描述：離散傅立葉變換DFT和它的逆變換是以N為周期的對(duì)于一維傅立葉變換有： F(u) = F(u + N)對(duì)于二維傅立葉變換有： F(u,v) = F(u + M,v+N)392.3.2 二維傅立葉變換特性:周期與共軛對(duì)稱周期與共軛對(duì)稱共軛對(duì)稱性的描述：傅立葉變換結(jié)果是以原

16、點(diǎn)為中心的共軛對(duì)稱函數(shù)對(duì)于一維傅立葉變換有： F(u) = F*(-u)對(duì)于二維傅立葉變換有： F(u,v) = F*(-u ,-v)402.3.2 二維傅立葉變換特性:周期與共軛對(duì)稱共軛對(duì)稱性證明以一維傅立葉變換為例證明：F(u) =f(x)exp-j2uxdx =f(x)expj2(-u)xdx =f(x)exp-j2(-u)x*dx（取共軛復(fù)數(shù)） = F*(-u)412.3.2 二維傅立葉變換特性:旋轉(zhuǎn)特性旋轉(zhuǎn)特性旋轉(zhuǎn)特性描述：如果f(x,y)旋轉(zhuǎn)了一個(gè)角度 ，那么f(x,y)旋轉(zhuǎn)后的圖象的傅立葉變換也旋轉(zhuǎn)了相同的角度 。 設(shè)： a(x,y) = x cos() - y sin() b(

17、x,y) = x sin() + y cos()Ff(a(x,y),b(x,y) F(a(u,v),b(u,v)422.3.2 二維傅立葉變換特性:旋轉(zhuǎn)特性旋轉(zhuǎn)特性結(jié)論： 對(duì)圖像的旋轉(zhuǎn)變換和傅立葉變換的順序是可交換的FRf(x,y) RFf(x,y)432.3.2 二維傅立葉變換特性:線性與相似性線性與相似性線性的描述：傅立葉變換是線性系統(tǒng)、函數(shù)和的傅立葉變換是可分離的設(shè)：f(x,y) 的傅立葉變換為Ff(x,y)g(x,y)的傅立葉變換為Fg(x,y) 有：Ff(x,y)+g(x,y) = Ff(x,y)+Fg(x,y) 442.3.2 二維傅立葉變換特性:線性與相似性線性的證明用一維函數(shù)為

18、例進(jìn)行證明：Ff(x)+g(x) = F(u) = (f(x)+g(x)exp-j2uxdx= (f(x)exp-j2ux + g(x)exp-j2ux) dx= f(x)exp-j2uxdx + g(x)exp-j2uxdx= F(u) + G(u)452.3.2 二維傅立葉變換特性:線性與相似性線性與相似性相似性的描述：a f(x,y) a F(u,v)且有： f(ax,by) 1/|ab|F(u/a,v/b) 462.3.2 二維傅立葉變換特性:線性與相似性相似性的證明用一維函數(shù)為例進(jìn)行證明：f(ax) 1/|a|F(u/a) Ff(ax) = F(u) = f(ax)exp-j2uxd

19、x將指數(shù)和積分同時(shí)乘以 1 = a/a并設(shè)：v = ax, dv = adxFf(ax) = f(ax)exp-j2ux a/a a/a dx =1/a f(ax)exp-j2u xa/a adx =1/a f(v)exp-j2v (u /a) dv =1/|a|F(u/a)472.3.2 二維傅立葉變換特性:均值性均值性均值性的描述： 離散函數(shù)的均值等于該函數(shù)傅立葉變換在(0,0)點(diǎn)的值 M-1N-1 f(x ,y) = 1/MNf(x,y)e0 x=0 y=0f(x ,y) = F(0,0)482.3.2 二維傅立葉變換特性:拉普拉斯拉普拉斯拉普拉斯特性的描述：給出二維拉普拉斯函數(shù)的傅立葉

20、變換表達(dá)式：拉普拉斯函數(shù)：2 f(x,y) = 2f / x2 + 2f / y2其傅立葉變換為： F2 f(x,y) = -42(u2 +v2)F(u,v)這個(gè)定理將在圖象的邊界提取中用到492.3.2 二維傅立葉變換特性:卷積與相關(guān)卷積與相關(guān):空域和頻域之間的基本聯(lián)系卷積定理的描述：空域中的卷積等價(jià)于頻域中的相乘f(x,y)*g(x,y) F(u,v)G(u,v) Ff(x,y)*g(x,y) = F(u,v)G(u,v)同時(shí)有：f(x,y) g(x,y) F(u,v)*G(u,v)502.3.2 二維傅立葉變換特性:卷積與相關(guān)卷積定理成立的證明用一維函數(shù)為例進(jìn)行證明： Ff(x)*g(x

21、) = f(x)*g(x) exp-j2uxdx= f(t)g(x-t)dt exp-j2uxdx 對(duì)于上面這個(gè)式子，我們可以看出是一個(gè)兩個(gè)變量t、x的二維積分。交換積分的順序有：512.3.2 二維傅立葉變換特性:卷積與相關(guān) = f(t)g(x - t) exp-2juxdxdt = f(t) g(x - t) exp-2juxdxdt將 t 視為位移量，由平移定理Gg(x - t) = g(x - t)exp-2juxdx = exp-j2tuG(u) 有： = f(t) exp-2jtuG(u) dt = G(u) f(t) exp-2jtu dt = F(u)G(u)522.3.2 二

22、維傅立葉變換特性:卷積與相關(guān)卷積與相關(guān):空域和頻域之間的基本聯(lián)系相關(guān)定理的描述： 空域中f(x,y)與g(x,y)的相關(guān)等價(jià)于頻域中F(u,v)的共軛與G(u,v) 相乘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)53第三節(jié) 頻域變換:快速傅立葉變換2.3.3 快速傅立葉變換FFT算法思想遞推公式推導(dǎo)逆向FFT算法算法實(shí)現(xiàn)542.3.3 快速傅立葉變換: FFT算法思想FFT算法基本思想 FFT算法基于一個(gè)叫做遞推加倍的方法。通過推導(dǎo)將DFT轉(zhuǎn)換成兩個(gè)遞推公式 N-1F(u)=1/N f(x) exp(-j2ux/N) x

23、=0 F(u) = 1/2(Feven(u)+Fodd(u)W2Mu) F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu) 552.3.3 快速傅立葉變換: FFT算法思想FFT算法基本思想 F(u) = 1/2(Feven(u)+Fodd(u)W2Mu) F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu)其中： N = 2MFeven(u)、Fodd(u) 是1/2N個(gè)點(diǎn)的傅立葉值 562.3.3 快速傅立葉變換:FFT算法思想FFT算法基本思想通過一個(gè)實(shí)例來體會(huì)一下FFT算法：設(shè)：有函數(shù)f(x)，其 N = 23 = 8 有： f(0), f(1), f(2

24、), 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) 572.3.3 快速傅立葉變換: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) 582.3.3 快速傅立葉變換:FFT算法思想 f(0), f(4) f(2), f(6) f(1), f(5) f(3),

25、 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) 592.3.3 快速傅立葉變換: FFT算法思想分析這些表達(dá)式得到如下一些有趣的特性：（1）一個(gè)N個(gè)點(diǎn)的變換，能夠通過將原始 表達(dá) 式分成兩個(gè)部分來計(jì)算（2）通過計(jì)算兩個(gè)（N/2）個(gè)點(diǎn)的變換。得到 Feven(u)和 Fodd(u)（3）奇部與偶部之和得到F(u)的前(N/2

26、)個(gè)值。（4）奇部與偶部之差得到F(u)的后(N/2)個(gè)值。 且不需要額外的變換計(jì)算。602.3.3 快速傅立葉變換: 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)的DFT612.3.3 快速傅立葉變換:遞推公式推導(dǎo)遞推公式推導(dǎo) FFT算法基于一個(gè)叫做遞推加倍的方法。為方便起見我們用下式表達(dá)離散傅立葉變換公式 N-1F(u)=1/N f(x) exp(-j2ux/N) x=0 N-1F(u)=1/N f(x)(

27、WN)ux x=0 這里 WN = exp(-j2/N) 是一個(gè)常數(shù)622.3.3 快速傅立葉變換:遞推公式推導(dǎo)遞推公式推導(dǎo) 假設(shè)N為： N = 2n 其中n是一個(gè)正整數(shù)，因此N可表示為：N = 2M 這里M仍然是一個(gè)正整數(shù)。將N = 2M代入上式，得到： 632.3.3 快速傅立葉變換:遞推公式推導(dǎo)遞推公式推導(dǎo) 2M-1 F(u)=1/(2M)f(x)(W2M)ux x=0 M-1 M-1 =1/2 1/Mf(2x)W2Mu(2x)+1/Mf(2x+1)W2Mu(2x+1) x=0 x=0642.3.3 快速傅立葉變換:遞推公式推導(dǎo)遞推公式推導(dǎo)由于： WN = exp(-j2/N) W2M2

28、ux = exp-j22ux/2M = exp-j2ux/M = WMux所以： W2M2xu = WMxu代入上式有：F(u)= M-1 M-1 =1/2 1/M f(2x)W2Mu(2x) + 1/Mf(2x+1)W2Mu(2x+1) x=0 x=0652.3.3 快速傅立葉變換:遞推公式推導(dǎo) M-1 M-1 1/21/Mf(2x)WMux + 1/Mf(2x+1)WMux W2Mu x=0 x=0定義兩個(gè)符號(hào)： M-1 Feven(u) = 1/Mf(2x)WMux 偶數(shù)部分 x=0u = 0,1,2,M-1 M-1 Fodd (u) = 1/Mf(2x+1)WMux 奇數(shù)部分 x=0

29、u = 0,1,2,M-1662.3.3 快速傅立葉變換:遞推公式推導(dǎo)得出FFT 的第一個(gè)遞推公式： F(u)=1/2 ( Feven(u)+Fodd(u)W2Mu )該公式說明F(u)可以通過奇部和偶部之和來計(jì)算672.3.3 快速傅立葉變換:遞推公式推導(dǎo)另有：WMu+M = exp-2j(u+M)/M = exp-2ju/M exp-2j = WMuej(-2) = WMu(-1)(-2) = WMu且：W2Mu+M = exp-2j(u+M)/2M = exp-2ju/2M ej(-1) = W2Mu (-1)(-1) = -W2Mu最后有：WMu+M = WMu ； W2Mu+M =

30、-W2Mu682.3.3 快速傅立葉變換:遞推公式推導(dǎo)因?yàn)椋篧Mu+M = WMu ； W2Mu+M = -W2Mu得出u+M 的DFT為： M-1F(u+M) = 1/2 1/Mf(2x)WM(u+M)x + x=0 M-1 1/Mf(2x+1)WM(u+M)x W2Mu+M x=0 = 1/2 ( Feven(u)- Fodd(u)W2Mu ) 692.3.3 快速傅立葉變換:遞推公式推導(dǎo)得出FFT的第二個(gè)遞推公式： F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu) 該公式說明F(u+M)可以通過F(u)偶部和奇部之差來計(jì)算702.3.3 快速傅立葉變換:遞推公式推導(dǎo)得出

31、FFT的兩個(gè)遞推公式： F(u) = 1/2(Feven(u)+Fodd(u)W2Mu) F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu) 712.3.3 快速傅立葉變換: 逆向FFT算法逆向FFT算法算法思想描述：用正向變換計(jì)算逆向變換 N-1F(u) = 1/N f(x)exp-j2ux/N x=0u = 0, 1, 2, .N-1 N-1 f(x) = F(u)expj2ux/N u=0 x = 0, 1, 2, .N-1722.3.3 快速傅立葉變換:逆向FFT算法逆向FFT算法 在離散逆向變換表達(dá)式兩邊同取共軛，并除N N-11/Nf*(x) = 1/N F*(u)

32、 exp-j2ux/N u=0u = 0, 1, 2, .N-1 用正向變換算法計(jì)算，得到1/Nf*(x) ，取共軛并乘上N，即得到f(x)732.3.3 快速傅立葉變換:FFT算法實(shí)現(xiàn)FFT算法實(shí)現(xiàn)幾個(gè)關(guān)鍵點(diǎ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)742.3.3 快速傅立