數(shù)字圖像頻域變換

數(shù)字圖像頻域變換第一頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換傅立葉變換導(dǎo)言理論基礎(chǔ)、連續(xù)與離散的傅立葉變換二維傅立葉變換特性可分離性、周期與共軛對(duì)稱、平移性、旋轉(zhuǎn)特性、線性與相似性、均值性、拉普拉斯、卷積與相關(guān)快速傅立葉變換FFT算法、逆向FFT算法、算法實(shí)現(xiàn)第二頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換2.2.1傅立葉變換導(dǎo)言理論基礎(chǔ)連續(xù)與離散的傅立葉變換第三頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:理論基礎(chǔ)理論基礎(chǔ)線性系統(tǒng)卷積與相關(guān)第四頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:理論基礎(chǔ)線性系統(tǒng)系統(tǒng)的定義：接受一個(gè)輸入，并產(chǎn)生相應(yīng)輸出的任何實(shí)體。系統(tǒng)的輸入是一個(gè)或兩個(gè)變量的函數(shù)，輸出是相同變量的另一個(gè)函數(shù)。系統(tǒng)x(t)輸入y(t)輸出第五頁，共七十九頁，2022年，8月28日第三節(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)第六頁，共七十九頁，2022年，8月28日第三節(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)具有移不變性第七頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:理論基礎(chǔ)卷積卷積的定義離散一維卷積二維卷積的定義離散二維卷積相關(guān)的定義第八頁，共七十九頁，2022年，8月28日第三節(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ù)第九頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:理論基礎(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

-第十頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:理論基礎(chǔ)離散二維卷積h(x,y)=f*g=

f(m,n)g(x–m,y–n)

mn相關(guān)的定義 h(t)=g(t+)f()d

記為：y=gx

-

第十一頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換連續(xù)與離散的傅立葉變換一維連續(xù)傅立葉變換二維連續(xù)傅立葉變換離散傅立葉變換離散傅立葉變換的計(jì)算與顯示第十二頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換一維連續(xù)傅立葉變換：定義設(shè)f(x)為實(shí)變量x的連續(xù)函數(shù)，f(x)的傅立葉變換表示為F{f(x)},定義為：

F{f(x)}=F(u)=f(x)exp(-j2ux)dx

其中j2=-1 -如果給定F(u),f(x)可以由傅立葉逆變換得到：

F{F(u)}=f(x)=F(u)exp(j2ux)du

第十三頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換一維連續(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)

第十四頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換一維連續(xù)傅立葉變換：幾個(gè)概念（3）

f(x)的傅立葉相位記為：(u)

(u)=tan-1(I(u)/R(u))

（4）

傅立葉變換中的變量u通常稱為頻率變量這個(gè)名稱源于尤拉公式中的指數(shù)項(xiàng)exp[-j2ux]=cos2ux-jsin2ux

如果把傅立葉變換的積分解釋為離散項(xiàng)的和，則易推出F(u)是一組sin和cos函數(shù)項(xiàng)的無限和，其中u的每個(gè)值決定了其相應(yīng)cos,sin函數(shù)對(duì)的頻率。第十五頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換二維連續(xù)傅立葉變換如果f(x,y)連續(xù)可積，并且F(u,v)可積，則存在以下傅立葉變換對(duì)，其中u,v為頻率變量：

F{f(x,y)}=F(u,v)=f(x,y)exp[-j2(ux+vy)]dxdy

-

F{F(u,v)}=f(x,y)=F(u,v)exp[j2(ux+vy)]dudv

-第十六頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換二維連續(xù)傅立葉變換

二維傅立葉模、相位和模平方分別為：

模： |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)

第十七頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換離散傅立葉變換

假設(shè)連續(xù)函數(shù)f(x),通過取N個(gè)x單位的采樣點(diǎn)，被離散化為一個(gè)序列：{f(x0),f(x0+x),f(x0+2x),…,f(x0+[N–1]x)}

無論將x作為離散的或連續(xù)的變量，在子序列中來研究都將是方便的，僅僅依賴于討論的上下文。為作到此要求定義：

f(x)=f(x0+xx)

第十八頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換離散傅立葉變換

其中假設(shè)x現(xiàn)在的離散值是：0,1,2,…,N-1。

{f(x0),f(x0+x),f(x0+2x),...,f(x0+[N–1]x)}

表示相對(duì)與連續(xù)函數(shù)的任意N個(gè)統(tǒng)一的空間采樣第十九頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換離散傅立葉變換

函數(shù)f(x0+xx)的離散傅立葉變換對(duì)有：

N-1

F(u)=1/N

f(x)exp[-j2ux/N]

x=0 u=0,1,2,...N-1

N-1

f(x)=F(u)exp[j2ux/N]

u=0 x=0,1,2,...N-1第二十頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換離散傅立葉變換:二維

M-1N-1F(u,v)=1/MNf(x,y)exp[-j2(ux/M+vy/N)]

x=0y=0

u=0,1,2,…M-1;v=0,1,2,...N-1

M-1N-1

f(x,y)=F(u,v)exp[j2(ux/M+vy/N)]

u=0v=0

x=0,1,2,...N-1;y=0,1,2,...N-1第二十一頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換離散傅立葉變換的計(jì)算與顯示離散傅立葉變換的計(jì)算舉例離散傅立葉變換的顯示第二十二頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換離散傅立葉變換的計(jì)算舉例xf(x0)=f(x0+x)01231234第二十三頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換F(0)=1/4Σf(x)exp[0]=1/4[f(0)+f1(1)+f(2)+f(3)]=1/4(2+3+4+4)=3.25F(1)=1/4Σf(x)exp[-j2πx/4)]=1/4(2e0+3e

–j2π/4+4e

–j2π2/4+4e

–j2π3/4)=1/4(-2+j)F(2)=-1/4(1+j0)F(3)=-1/4(2+j)第二十四頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換

離散傅立葉變換的計(jì)算舉例因?yàn)椋瘮?shù)f(x,y)的傅立葉變換是f(x,y)積分的函數(shù)，因此計(jì)算每一個(gè)傅立葉變換值，原函數(shù)f(x,y)的每一個(gè)點(diǎn)都需要參予第二十五頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換離散傅立葉變換的顯示

通過對(duì)傅立葉變換模，來顯示傅立葉變換圖象。由于模的值域大于顯示的值域，因此要進(jìn)行動(dòng)態(tài)值域的壓縮

D(u,v)=clog(1+|F(u,v)|)

其中：

c=255/k; k=max(log(1+|F(u,v)|))

值域[0,k]的上限（最大值）第二十六頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換離散傅立葉變換的顯示第二十七頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:傅立葉變換離散傅立葉變換的顯示第二十八頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性2.2.2二維傅立葉變換特性可分離性周期與共軛對(duì)稱平移性旋轉(zhuǎn)特性

線性與相似性均值性拉普拉斯卷積與相關(guān)第二十九頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性可分離性二維離散傅立葉變換DFT可分離性的基本思想是：

二維DFT可分離為兩次一維DFT應(yīng)用：

二維快速傅立葉算法FFT，是通過計(jì)算兩次一維FFT實(shí)現(xiàn)的第三十頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性可分離性的定義

M-1N-1F(u,v)=1/MN[f(x,y)e(-j2vy/N)]e(-j2ux/M)

x=0y=0 u=0,1,2,…M-1;v=0,1,2,...N-1

M-1N-1

f(x,y)=[F(u,v)e(j2vy/N)]e(j2ux/M)

u=0v=0

x=0,1,2,...N-1;y=0,1,2,...N-1第三十一頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性可分離性成立的推導(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=0

第三十二頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性先對(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）uv第三十三頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性平移性定理平移性的描述函數(shù)自變量的位移的傅立葉變換產(chǎn)生一個(gè)復(fù)系數(shù)F{f(x-a,y-b)}=exp[-j2(au+bv)]F(u,v)第三十四頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性平移性成立的證明用一維函數(shù)為例進(jìn)行證明： 設(shè)位移為a,f(x-a)的傅立葉變換為：F{f(x-a)}=F(u)=f(x-a)exp(-j2ux)dx

-將積分乘以

1=

exp(-j2au)exp(j2au)

且設(shè)：v

=x-a,dv

=dx

第三十五頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性平移性成立的證明F{f(x-a)}=F(u)

=

f(x-a)exp(-j2ux)exp(-j2au)exp(j2au)dx

-

=exp(-j2au)

f(x-a)exp(-j2ux)exp(j2ua)dx

-

第三十六頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性

=exp(-j2au)

f(x-a)exp[-j2u(x-a)]dx

-

=exp(-j2au)f(v)exp[-j2uv]dv

-

=exp(-j2au)F(u)第三十七頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性周期與共軛對(duì)稱周期性的描述：離散傅立葉變換DFT和它的逆變換是以N為周期的對(duì)于一維傅立葉變換有：

F(u)=F(u+N)對(duì)于二維傅立葉變換有：

F(u,v)=F(u+M,v+N)第三十八頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性周期與共軛對(duì)稱共軛對(duì)稱性的描述：傅立葉變換結(jié)果是以原點(diǎn)為中心的共軛對(duì)稱函數(shù)對(duì)于一維傅立葉變換有：

F(u)=F*(-u)對(duì)于二維傅立葉變換有：

F(u,v)=F*(-u,-v)第三十九頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性共軛對(duì)稱性證明以一維傅立葉變換為例證明：F(u)=∫f(x)exp[-j2ux]dx =∫f(x)exp[j2(-u)x]dx =∫f(x)exp[-j2(-u)x]*dx（取共軛復(fù)數(shù)）

=F*(-u)第四十頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性旋轉(zhuǎn)特性旋轉(zhuǎn)特性描述：如果f(x,y)旋轉(zhuǎn)了一個(gè)角度，那么f(x,y)旋轉(zhuǎn)后的圖象的傅立葉變換也旋轉(zhuǎn)了相同的角度。

設(shè)：a(x,y)=xcos()-ysin()

b(x,y)=xsin()+ycos()

F{f(a(x,y),b(x,y))}F(a(u,v),b(u,v))第四十一頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性旋轉(zhuǎn)特性結(jié)論： 對(duì)圖象的旋轉(zhuǎn)變換和傅立葉變換的順序是可交換的

F{R{f(x,y)}}R{F{f(x,y)}}第四十二頁，共七十九頁，2022年，8月28日第三節(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)}

第四十三頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性線性的證明用一維函數(shù)為例進(jìn)行證明：F{f(x)+g(x)}=F(u)=

(f(x)+g(x))exp[-j2ux]dx=(f(x)exp[-j2ux]+g(x)exp[-j2ux])dx=f(x)exp[-j2ux]dx+g(x)exp[-j2ux]dx=F(u)+G(u)第四十四頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性線性與相似性相似性的描述：

af(x,y)aF(u,v)

且有：

f(ax,by)1/|ab|F(u/a,v/b)

第四十五頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性相似性的證明用一維函數(shù)為例進(jìn)行證明：f(ax)1/|a|F(u/a)

F{f(ax)}=F(u)=f(ax)exp[-j2ux]dx將指數(shù)和積分同時(shí)乘以1=a/a并設(shè)：v=ax,dv=

adxF{f(ax)}=f(ax)exp[-j2uxa/a]a/adx =1/a

f(ax)exp[-j2uxa/a]adx =1/a

f(v)exp[-j2v(u/a)]dv=1/|a|F(u/a)第四十六頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性均值性均值性的描述： 離散函數(shù)的均值等于該函數(shù)傅立葉變換在(0,0)點(diǎn)的值M-1N-1

f(x,y)=1/MNf(x,y)e0

x=0y=0 f(x,y)=F(0,0)第四十七頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性拉普拉斯拉普拉斯特性的描述：給出二維拉普拉斯函數(shù)的傅立葉變換表達(dá)式：拉普拉斯函數(shù)：2f(x,y)=2f/x2+2f/y2其傅立葉變換為：

F{2f(x,y)}=-42(u2+v2)F(u,v)這個(gè)定理將在圖象的邊界提取中用到第四十八頁，共七十九頁，2022年，8月28日第三節(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)第四十九頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性卷積定理成立的證明用一維函數(shù)為例進(jìn)行證明：F{f(x)*g(x)}=f(x)*g(x)exp[-j2ux]dx =

[

f(t)g(x-t)dt]exp[-j2ux]dx

對(duì)于上面這個(gè)式子，我們可以看出是一個(gè)兩個(gè)變量t、x的二維積分。交換積分的順序有：第五十頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性

=[f(t)g(x-t)exp[-2jux]dx]dt =f(t)[g(x-t)exp[-2jux]dx]dt

將t視為位移量，由平移定理 G{g(x-t)}=g(x-t)exp[-2jux]dx =exp[-j2tu]G(u)

有：

=

f(t)exp[-2jtu]G(u)dt =G(u)f(t)exp[-2jtu]dt=F(u)G(u)第五十一頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:二維傅立葉變換特性卷積與相關(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)第五十二頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換2.2.3快速傅立葉變換FFT算法逆向FFT算法算法實(shí)現(xiàn)第五十三頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換FFT算法——基本思想

FFT算法基于一個(gè)叫做遞推加倍的方法。為方便起見我們用下式表達(dá)離散傅立葉變換公式

N-1 F(u)=1/N∑f(x)(WN)ux

x=0

這里

WN

=exp(-j2/N)是一個(gè)常數(shù)第五十四頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換FFT算法——基本思想

假設(shè)N為：

N=2n

其中n是一個(gè)正整數(shù)，因此N可表示為：

N=2M

這里M仍然是一個(gè)正整數(shù)。將N=2M代入上式，得到：

第五十五頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換FFT算法——基本思想

2M-1F(u)=1/(2M)∑f(x)(W2M)ux x=0

M-1

M-1

=1/2[1/M∑f(2x)W2Mu(2x)+1/M∑f(2x+1)W2Mu(2x+1)] x=0 x=0第五十六頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換FFT算法——基本思想由于：WN=exp(-j2/N)

W2M2ux

=exp[-j22ux/2M] =exp[-j2ux/M]=WMux所以：

W2M2xu

=Wmxu代入上式有：第五十七頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換

M-1M-11/2[1/M∑f(2x)Wmux+1/M∑f(2x+1)WMux

W2Mu]x=0x=0定義兩個(gè)符號(hào)： M-1Feven(u)=1/M∑f(2x)Wmux偶數(shù)部分

x=0 u=0,1,2,…M-1 M-1Fodd(u)=1/M∑f(2x+1)Wmux奇數(shù)部分 x=0u=0,1,2,…M-1第五十八頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換得出FFT的第一個(gè)遞推公式：

F(u)=1/2(Feven(u)+Fodd(u)W2Mu)該公式說明F(u)可以通過奇部和偶部之和來計(jì)算第五十九頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換另有：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=

-W2Mu第六十頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換因?yàn)椋篧Mu+M=Wmu；

W2Mu+M=

-W2Mu得出u+M的DFT為：M-1F(u+M)=1/2[1/M∑f(2x)WM(u+M)x+x=0 M-1 1/M∑f(2x+1)WM(u+M)x

W2Mu+M]

x=0

=1/2(Feven(u)-Fodd(u)W2Mu)

第六十一頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換得出FFT的第二個(gè)遞推公式：

F(u+M)=1/2(Feven(u)-Fodd(u)W2Mu)

該公式說明F(u+M)可以通過F(u)偶部和奇部之差來計(jì)算第六十二頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換得出FFT的兩個(gè)遞推公式：

F(u)=1/2(Feven(u)+Fodd(u)W2Mu)F(u+M)=1/2(Feven(u)-Fodd(u)W2Mu)

第六十三頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換分析這些表達(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)個(gè)值。（4）奇部與偶部之差得到F(u)的后(N/2)個(gè)值。且不需要額外的變換計(jì)算。第六十四頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換歸納快速傅立葉變換的思想：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)的DFT第六十五頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換逆向FFT算法算法思想描述：用正向變換計(jì)算逆向變換

N-1F(u)=1/Nf(x)exp[-j2ux/N]

x=0 u=0,1,2,...N-1

N-1

f(x)=F(u)exp[j2ux/N]

u=0 x=0,1,2,...N-1第六十六頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換逆向FFT算法在離散逆向變換表達(dá)式兩邊同取共軛，并除N

N-11/Nf*(x)=1/NF*(u)exp[-j2ux/N]

u=0 u=0,1,2,...N-1

用正向變換算法計(jì)算，得到1/Nf*(x)，取共軛并乘上N，即得到f(x)

第六十七頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換FFT算法實(shí)現(xiàn)通過一個(gè)實(shí)例來體會(huì)一下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)}

第六十八頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換FFT算法實(shí)現(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)}

第六十九頁，共七十九頁，2022年，8月28日第三節(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)}

第七十頁，共七十九頁，2022年，8月28日第三節(jié)頻域變換:快速傅立葉變換算法實(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