1、第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換數字圖象處理北京大學計算機研究所 陳曉鷗第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換 傅立葉變換導言理論基礎、連續與離散的傅立葉變換 二維傅立葉變換特性可分離性、周期與共軛對稱、平移性、旋轉特性、線性與相似性 、均值性、拉普拉斯、卷積與相關 快速傅立葉變換FFT算法、逆向FFT算法、算法實現第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換2.2.1 傅立葉變換導言理論基礎連續與離散的傅立葉變換第二章數字圖象處理基礎第二章數字圖象

2、處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:理論基礎 理論基礎線性系統卷積與相關第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:理論基礎 線性系統系統的定義：接受一個輸入，并產生相應輸出的任何實體。系統的輸入是一個或兩個變量的函數，輸出是相同變量的另一個函數。系統x(t)輸入y(t)輸出第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:理論基礎 線性系統線性系統的定義：對于某特定系統，有： x1(t) y1(t) x2(t) y2(t)該系統是線性的當且僅當：x1(t) + x2(t) y1

3、(t) + y2(t) 從而有：a*x1(t) a*y1(t)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:理論基礎 線性系統線性系統移不變性的定義：對于某線性系統，有：x(t) y(t)當輸入信號沿時間軸平移T，有： x(t - T) y(t - T)則稱該線性系統具有移不變性第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:理論基礎 卷積卷積的定義離散一維卷積二維卷積的定義離散二維卷積相關的定義第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:理論基礎卷積

4、的定義 對于一個線性系統的輸入f(t)和輸出h(t)，如果有一個一般表達式，來說明他們的關系，對線性系統的分析，將大有幫助 卷積積分就是這樣的一般表達式 h(t) = g(t - )f( )d 記為：h = g * f - - g(t)稱為沖激響應函數第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:理論基礎離散一維卷積 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 - - 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節

5、頻域變換頻域變換第三節 頻域變換:理論基礎離散二維卷積h(x,y) = f*g = = f(m,n)g(x m, y n)m nm n相關的定義 h(t) = g(t + )f( )d 記為：y = g x - - 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換 連續與離散的傅立葉變換一維連續傅立葉變換二維連續傅立葉變換離散傅立葉變換離散傅立葉變換的計算與顯示第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 一維連續傅立葉變換：定義設 f(x)為實變量x的連續函數， f(x)的傅立葉變換表示為

6、Ff(x),定義為： Ff(x) = F(u) = f(x)exp(-j2 ux)dx 其中 j2 = -1 - - 如果給定F(u),f(x)可以由傅立葉逆變換得到： FF(u) = f(x) = F(u)exp(j2 ux)du 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 一維連續傅立葉變換：幾個概念 假設函數f(x)為實函數。但一個實函數的傅立葉變換可能為復函數：F(u) = R(u) + jI(u)（1） f(x)的傅立葉模記為： |F(u)| |F(u)| = R2(u) + I2(u)1/2（2） f(x)的傅立葉模平方

7、記為： P(u) P(u) = |F(u)|2 = R2(u) + I2(u)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 一維連續傅立葉變換：幾個概念（3） f(x)的傅立葉相位記為： (u) (u) = = tan-1 (I(u) / R(u)（4） 傅立葉變換中的變量u通常稱為頻率變量 這個名稱源于尤拉公式中的指數項 exp-j2 ux = cos2 ux - jsin2 ux 如果把傅立葉變換的積分解釋為離散項的和，則易推出F(u)是一組sin和cos函數項的無限和，其中u的每個值決定了其相應cos, sin函數對的頻率。第二

8、章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 二維連續傅立葉變換 如果f(x,y)連續可積，并且F(u,v)可積，則存在以下傅立葉變換對，其中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 - - 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 二維連續傅立葉變換 二維傅立葉模、相位和模平方分別為： 模： |F(u,v)| = R2(u,v) +

9、 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)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 離散傅立葉變換 假設連續函數f(x),通過取N個x單位的采樣點，被離散化為一個序列： f ( x0) , f ( x0+ x ) , f(x0+2x), ,f(x0+N1 x) 無論將x作為離散的或連續的變量，在子序列中來研究都將是方便的，僅僅依賴于討論的上下文。為作到此要求定義：f(x) = f(x0+ xx)第

10、二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 離散傅立葉變換 其中假設x現在的離散值是：0,1,2, ,N-1。 f(x0),f(x0+x),f(x0+2x), . , f(x0+N1x)表示相對與連續函數的任意N個統一的空間采樣第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 離散傅立葉變換函數f(x0+xx)的離散傅立葉變換對有： N-1F(u) = 1/N f(x)exp-j2 ux/N x=0u = 0, 1, 2, .N-1 N-1 f(x) = F(u)expj2 ux

11、/N u=0 x = 0, 1, 2, .N-1第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 離散傅立葉變換:二維 M-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-1第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三

12、節 頻域變換:傅立葉變換 離散傅立葉變換的計算與顯示離散傅立葉變換的計算舉例離散傅立葉變換的顯示第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 離散傅立葉變換的計算舉例xf(x0)=f(x0+x)01231234第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換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

13、 j2/4 + 4e j22/4 + 4e j23/4)= 1/4(-2 + j)F(2) = -1/4(1 + j0)F(3) = -1/4(2 + j)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 離散傅立葉變換的計算舉例因為，函數f(x,y)的傅立葉變換是f(x,y)積分的函數，因此計算每一個傅立葉變換值，原函數f(x,y)的每一個點都需要參予第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 離散傅立葉變換的顯示 通過對傅立葉變換模，來顯示傅立葉變換圖象。由于模的值域大于顯

14、示的值域，因此要進行動態值域的壓縮D(u,v) = c log(1 + |F(u,v)|)其中： c = 255 / k; k = max(log(1 + |F(u,v)|)值域0,k的上限（最大值）第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 離散傅立葉變換的顯示第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:傅立葉變換 離散傅立葉變換的顯示第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性2.2.2 二維傅立葉變換特性 可分

15、離性 周期與共軛對稱 平移性 旋轉特性 線性與相似性 均值性 拉普拉斯 卷積與相關第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 可分離性二維離散傅立葉變換DFT可分離性的基本思想是： 二維DFT可分離為兩次一維DFT應用： 二維快速傅立葉算法FFT ，是通過計算兩次一維FFT實現的第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 可分離性的定義 M-1 N-1 F(u,v)=1/MN f(x,y)e(-j2vy/N) e(-j2ux/M) x=0 y=0u = 0

16、, 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第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 可分離性成立的推導先對行（y變量）做變換： N-1F(x,v)=1/Nf(x,y)exp(-j2vy/N) y=0然后對列（x變量）進行變換： M-1F(u,v)=1/MF(x,v)exp(-j2ux/M) x=0第二章數字圖象處理基礎第二章數字圖象處

17、理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性先對行做變換：然后對列進行變換：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）uv第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 平移性定理平移性的描述函數自變量的位移的傅立葉變換產生一個復系數 Ff(x-a,y-b) = exp-j2(au+bv)F(u,v)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域

18、變換第三節 頻域變換:二維傅立葉變換特性 平移性成立的證明用一維函數為例進行證明：設位移為a,f(x-a)的傅立葉變換為： Ff(x-a) = F(u) = f(x-a)exp(-j2ux)dx -將積分乘以 1 1 = exp(-j2au) exp(j2au) 且設：v = x-a, dv = dx 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 平移性成立的證明Ff(x-a) = F(u) = f(x-a)exp(-j2 ux)exp(-j2 au)exp(j2 au)dx - - =exp(-j2 au) f(x-a)ex

19、p(-j2 ux)exp(j2 ua)dx - - 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 = exp(-j2 au) f(x-a)exp-j2 u(x-a)dx - - = exp(-j2 au) f(v)exp-j2 uvdv - - = exp(-j2 au)F(u)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 周期與共軛對稱周期性的描述：離散傅立葉變換DFT和它的逆變換是以N為周期的對于一維傅立葉變換有： F(u) = F(u + N)對于二維傅

20、立葉變換有： F(u,v) = F(u + M,v+N)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 周期與共軛對稱共軛對稱性的描述：傅立葉變換結果是以原點為中心的共軛對稱函數對于一維傅立葉變換有： F(u) = F*(-u)對于二維傅立葉變換有： F(u,v) = F*(-u ,-v)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 共軛對稱性證明以一維傅立葉變換為例證明：F(u) =f(x)exp-j2 uxdx =f(x)expj2 (-u)xdx =f(x

21、)exp-j2 (-u)x*dx（取共軛復數） = F*(-u)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 旋轉特性旋轉特性描述：如果f(x,y)旋轉了一個角度 ，那么f(x,y)旋轉后的圖象的傅立葉變換也旋轉了相同的角度 。 設： a(x,y) = x cos( ) - y sin( ) b(x,y) = x sin( ) + y cos( )Ff(a(x,y),b(x,y) F(a(u,v),b(u,v)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 旋轉

22、特性結論： 對圖象的旋轉變換和傅立葉變換的順序是可交換的FRf(x,y) RFf(x,y)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 線性與相似性線性的描述：傅立葉變換是線性系統、函數和的傅立葉變換是可分離的設：f(x,y) 的傅立葉變換為Ff(x,y)g(x,y)的傅立葉變換為Fg(x,y) 有：Ff(x,y)+g(x,y) = Ff(x,y)+Fg(x,y) 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 線性的證明用一維函數為例進行證明：Ff(x)+g(

23、x) = F(u) = (f(x)+g(x)exp-j2 uxdx= (f(x)exp-j2 ux + g(x)exp-j2 ux) dx= f(x)exp-j2 uxdx + g(x)exp-j2 uxdx= F(u) + G(u)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 線性與相似性相似性的描述：a f(x,y) a F(u,v)且有： f(ax,by) 1/|ab|F(u/a,v/b) 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 相似性的證明用一維

24、函數為例進行證明：f(ax) 1/|a|F(u/a) Ff(ax) = F(u) = f(ax)exp-j2uxdx將指數和積分同時乘以 1 = a/a并設：v = ax, dv = adxFf(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)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 均值性均值性的描述： 離散函數的均值等于該函數傅立葉變換在(0,0)點的值 M-1N-1

25、f(x ,y) = 1/MNf(x,y)e0 x=0 y=0f(x ,y) = F(0,0)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 拉普拉斯拉普拉斯特性的描述：給出二維拉普拉斯函數的傅立葉變換表達式：拉普拉斯函數：2 f(x,y) = 2f / x2 + 2f / y2其傅立葉變換為： F2 f(x,y) = -42(u2 +v2)F(u,v)這個定理將在圖象的邊界提取中用到第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 卷積與相關:空域和頻域之間的基本聯

26、系卷積定理的描述：空域中的卷積等價于頻域中的相乘f(x,y)*g(x,y) F(u,v)G(u,v) Ff(x,y)*g(x,y) = F(u,v)G(u,v)同時有：f(x,y) g(x,y) F(u,v)*G(u,v)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 卷積定理成立的證明用一維函數為例進行證明： Ff(x)*g(x) = f(x)*g(x) exp-j2 uxdx= f(t)g(x-t)dt exp-j2uxdx 對于上面這個式子，我們可以看出是一個兩個變量t、x的二維積分。交換積分的順序有：第二章數字圖象處理基

27、礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 = f(t)g(x - t) exp-2juxdxdt = f(t) g(x - t) exp-2juxdxdt將 t 視為位移量，由平移定理Gg(x - t) = g(x - t)exp-2juxdx = exp-j2 tuG(u) 有： = f(t) exp-2j tuG(u) dt = G(u) f(t) exp-2jtu dt = F(u)G(u)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:二維傅立葉變換特性 卷積與相關:空域和頻域之間的基本聯

28、系相關定理的描述： 空域中f(x,y)與g(x,y)的相關等價于頻域中F(u,v)的共軛與G(u,v) 相乘f(x,y)g(x,y) F*(u,v)G(u,v)同時有：f*(x,y) g(x,y) F(u,v)G(u,v)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換2.2.3 快速傅立葉變換FFT算法逆向FFT算法算法實現第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換 FFT算法基本思想 FFT算法基于一個叫做遞推加倍的方法。為方便起見我們用下式表達離散傅立葉變換公式

29、N-1F(u)=1/Nf(x)(WN)ux x=0 這里 WN = exp(-j2 /N) 是一個常數第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換 FFT算法基本思想 假設N為： N = 2n 其中n是一個正整數，因此N可表示為：N = 2M 這里M仍然是一個正整數。將N = 2M代入上式，得到： 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換 FFT算法基本思想 2M-1 F(u)=1/(2M)f(x)(W2M)ux x=0 M-1 M-1 =1/2 1/Mf(2x)

30、W2Mu(2x)+1/Mf(2x+1)W2Mu(2x+1) x=0 x=0第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換 FFT算法基本思想由于： WN = exp(-j2/N) W2M2ux = exp-j22ux/2M = exp-j2ux/M = WMux所以： W2M2xu = Wmxu代入上式有：第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換 M-1 M-1 1/21/Mf(2x)Wmux + 1/Mf(2x+1)WMux W2Mu x=0 x=0定義兩個符號：

31、 M-1 Feven(u) = 1/Mf(2x)Wmux 偶數部分 x=0u = 0,1,2,M-1 M-1 Fodd (u) = 1/Mf(2x+1)Wmux 奇數部分 x=0 u = 0,1,2,M-1第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換得出FFT 的第一個遞推公式： F(u)=1/2 ( Feven(u)+Fodd(u)W2Mu )該公式說明F(u)可以通過奇部和偶部之和來計算第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換另有：WMu+M = exp-2j

32、(u+M)/M = exp-2ju/Mexp-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 = -W2Mu第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換因為：WMu+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

33、 1/Mf(2x+1)WM(u+M)x W2Mu+M x=0 = 1/2 ( Feven(u)- Fodd(u)W2Mu ) 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換得出FFT的第二個遞推公式： F(u+M)= 1/2(Feven(u)-Fodd(u)W2Mu) 該公式說明F(u+M)可以通過F(u)偶部和奇部之差來計算第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換得出FFT的兩個遞推公式： F(u) = 1/2(Feven(u)+Fodd(u)W2Mu) F(u+

34、M)= 1/2(Feven(u)-Fodd(u)W2Mu) 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換分析這些表達式得到如下一些有趣的特性：（1）一個N個點的變換，能夠通過將原始 表達 式分成兩個部分來計算（2）通過計算兩個（N/2）個點的變換。得到 Feven(u)和 Fodd(u)（3）奇部與偶部之和得到F(u)的前(N/2)個值。（4）奇部與偶部之差得到F(u)的后(N/2)個值。 且不需要額外的變換計算。第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換歸納快速傅

35、立葉變換的思想：1）通過計算兩個單點的DFT，來計算兩個點的DFT，2）通過計算兩個雙點的DFT，來計算四個點的DFT，以此類推3）對于任何N=2m的DFT的計算，通過計算兩個N/2點的DFT，來計算N個點的DFT第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換 逆向FFT算法算法思想描述：用正向變換計算逆向變換 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-1第二章數字圖象處理基礎第二章數字

36、圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換 逆向FFT算法 在離散逆向變換表達式兩邊同取共軛，并除N N-11/Nf*(x) = 1/N F*(u) exp-j2ux/N u=0u = 0, 1, 2, .N-1 用正向變換算法計算，得到1/Nf*(x) ，取共軛并乘上N，即得到f(x)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換 FFT算法實現通過一個實例來體會一下FFT算法：設：有函數f(x)，其 N = 23 = 8 有： f(0), f(1), f(2), f(3), f(4), f(5)

37、, f(6), f(7) 計算： F(0), F(1), F(2), F(3), F(4), F(5), F(6),F(7) 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換 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) 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立

38、葉變換 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) 第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換第三節 頻域變換:快速傅立葉變換 算法實現的幾個關鍵點1）地址的排序：按位倒序規則例如：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)第二章數字圖象處理基礎第二章數字圖象處理基礎 第三節第三節 頻域變換頻域變換