二維Fourier變換及其作用

二維Fourier變換及其作用論文題目：二維Fourier變換及其作用英文名：Thetwo-dimensionalFouriertransformanditseffect指導(dǎo)老師：熊向團姓名：駱盼學(xué)號：201172020223Email：1234567890@【內(nèi)容提要】19世紀(jì)初，傅里葉在向巴黎科學(xué)院呈交的關(guān)于熱傳導(dǎo)的著名論文中提出了傅里葉級數(shù)傅里葉分析方法已經(jīng)廣泛用于物理學(xué)及工程學(xué)科的各個領(lǐng)域。傅立葉變換能將滿足一定條件的某個函數(shù)表示成三角函數(shù)（正弦和/或余弦函數(shù)）或者它們的積分的線性組合。在不同的研究領(lǐng)域，傅立葉變換具有多種不同的變體形式，如連續(xù)傅立葉變換和離散傅立葉變換。最初傅立葉分析是作為熱過程的解析分析的工具被提出的。【關(guān)健詞】傅里葉級數(shù)，二維離散傅立葉變換，快速傅立葉變換AbstractIntheearly19thcentury,Fourier,shallbesubmittedtotheParisacademyofsciencesofheatconductionofthethesisputforwardthefamousFourierseriesFourieranalysismethodhasbeenwidelyusedinvariousfieldsofphysicsandengineeringdisciplines.Fouriertransformcanmeetcertainconditionsisexpressedasafunctionoftrigonometricfunction(sineand/orcosinefunction)oralinearcombinationoftheintegral.Indifferentfieldsofstudy,avariationoftheFouriertransformhasmanydifferentforms,suchascontinuousFouriertransformanddiscreteFouriertransform.InitialFourieranalysisisatoolforasanalyticalanalysisofthermalprocesswasproposed.KeywordsFourierseries,thetwo-dimensionaldiscreteFouriertransform,fastFouriertransform目錄預(yù)備知識：TOC\o"1-5"\h\z三角函數(shù)系的正交性4（函數(shù)展開成）傅里葉級數(shù)4狹里克雷（Dirichlet）收斂定理5引入傅里葉變換的定義7離散的傅立葉變換7一維離散變換7二維離散變換8二維離散傅立葉變換的性質(zhì)8（一）平均值8（二）變換域的周期性8（三）對稱共軛性9（四）平移性9（五）分配性和比例性9（六）可分離性9（七）旋轉(zhuǎn)性質(zhì)10（八）微分性質(zhì)10\o"CurrentDocument"快速傅立葉變換（FFT）11\o"CurrentDocument"離散圖像變換的一般表達(dá)14離散圖像變換的代數(shù)表達(dá)式14離散圖像變換的矩陣表達(dá)式15\o"CurrentDocument"編程實驗17參考文獻(xiàn)20致謝20傅里葉變換(Fouriertransform)傅里葉變換是一種分析信號的方法，它可分析信號的成分，也可用這些成分合成信號。許多波形可作為信號的成分，比如正弦波、方波、鋸齒波等，傅里葉變換用正弦波作為信號的成分。一.預(yù)備知識:1.三角函數(shù)系的正交性三角級數(shù):2兀b+2^(acosnwx+bsinnwx)T二2nnwA=1三角函數(shù)系:1,coswx,sinwx,cos2wx,sin2wx,…,cosnwx,sinnwx,…(線性組合)正交性:TJ2cosnwxdx=0(2)T—2T.2sinnwxdx=0T—2J2cosn^wxsinmwxdx=0(4)T—2T2cosn^wx-cosmwxdx=0m。nT—2T2sinn^x-sinmwxdx=0m。nT—2另易驗證,三角函數(shù)亦中兩相同函數(shù)的乘積在-T,T上的積分不等于零.22J212dx=T?,Tsin2nwxdx=—2J2cos2nwxdx=—t22兀③-22(T=一)w2.(函數(shù)展開成)傅里葉級數(shù)條件：已知f(x)周期為T,在TT.一一.、一T,T上可積，且可展開成逐項可積的三角級數(shù).22f3)=\+E(a2nn=1

cosnwx+bsinnwx)a=—i2fxdx0TT結(jié)論2住wa=—J2f(x)cosnwxdx(n=12.?.)—

2

a=—i2f(x)cosnwxdx(n=0,1,—)nTT—2過程:①i2f(x)dx=i2^0-dx+TT2——22n=12acosnwxdx+iTn—2absinnwxdx正父性一^T2②i2f(x)cosnwxdxT—2=^-oi2cosnwxdx+E2T

=^-oi2cosnwxdx+E2T

—2K=1ai2fcosn^xcoskwxdx+bKTK—2T2cosn^xsink^xdxT—2正交性ai2cos2nwxdx=a?—nTn2—2③同②ae一-傅里葉級數(shù)：f(x)?寸+產(chǎn)(acosn^x+bsinn^x)n=1狹里克雷(Dirichlet)收斂定理設(shè)f(x)在-2,-上滿足連續(xù)，或還多有有限個第一類間斷點；分段單調(diào),且單調(diào)區(qū)間的個數(shù)還多只有有限個則f(x)的傅里葉級數(shù)尋+E(acosnwx+bsinnwx)收斂，且其和函數(shù)n=1S(x)=〈12推論：f(S(x)=〈12推論：f(x)1f(x—0)+f(x+0)]2〕f(-1+0)+f(I-0)xe(—TT)(2,2)連續(xù)點xe(—T,T)間斷點(第一類)22x=—T,T221.T=Ew=史=1取[一丸日T墮/3)cos〃"x(〃=o,i,2...)-K卜/(x)sinnx^x(〃=。，璀，…)兀-7t711、aVz,?、f(x)?一^+七(。cosnx+bsmnx)'2?nn=l2.T=2/(/〉0),w=—=-取L/,/]TI丫⑴cos§"*0,1,2,...)"/3)sin竺"x(〃二°，12…)-iIClVs0z〃丸r?〃兀\f(x)??+乙(qcos——x+bsm——X)2"IRIn=l是奇函數(shù)，即f(x)=-/(x)XG/w_2/(x)cosnwxdx(〃=0,1,2,..?)T°b=o(〃=0,l,2,...)naV—^+，qcosnwx2〃n=l余弦(傅里葉)級數(shù)4.f(x)在一二二上是奇函數(shù)，即f(x)=—f⑴居n(〃=0,1,2,.??)4住b=—J2/(x)sinnwxdx(n=0,1,2,???)、〃To'/■(])?#bsinnwx正弦(傅里葉)級數(shù)nn=l例1:得=<x~°展開成傅里葉級數(shù).U0<X<712兀解：T=2nw=———1T在匚兀,丸]上滿中收斂定理的條件，在端點x=±7i處的傅里葉級數(shù)在端三n奇

nrn偶1A—f⑴g1{—xSinMJ1nn奇項禺n點x=-處收斂于f（-—+0）+f（—-0）=哮=：'而在連續(xù)點x日-三n奇

nrn偶1A—f⑴g1{—xSinMJ1nn奇項禺n計算傅里葉系數(shù)：a=上卜f（x）dx=—fKxdx=：a=L卜f(x)cosnxdx=L卜xcosnxdx分部(cosn—-1)=<n—-——0^=n2—因此f3）的傅里葉級數(shù)展開式為f(x)=a-+#(ancosnwx+bsinnwx)n=1=—+(-—cosx+sinx)-—sin2x+(-^—cos3x+—sin3x)4—232—31?——sin4x+xe(-—,—)4二.引入傅里葉變換的定義一一。）是t的函數(shù)，如果t滿足狄里赫萊條件：具有有限個間斷點；具有有限個極值點；絕對可積。則有下圖①式成立。稱為積分運算弋t）的傅里葉變換，②式的積分運算叫做F「）的傅里葉逆變換。F（-）叫做的像函數(shù)，」（t）叫做F（-）的像原函數(shù)。F（-）是弋t）的像oAt）是F「）的原像。①傅里葉變換OOF（3）=石=fdt——CXD②傅里葉逆變換

中文譯名:Fouriertransform或TransformeedeFourier有多個中文譯名，常見的有“傅里葉變換”、“付立葉變換”、“傅立葉轉(zhuǎn)換”、“傅氏轉(zhuǎn)換”、“傅氏變換”、等等。三.離散的傅立葉變換一維離散變換為：NN式中，1=偵…，網(wǎng)-頃=1二維離散變換為:也-切一1F（W）=旗仇珂冰di-ov-0因為在離散的情況下，皿）和研口）兩者總是存在的，所以和連續(xù)的情況不同，我們不必考慮關(guān)系離散傅立葉變換的存在性。二維離散傅立葉變換的性質(zhì)此處約定離散函數(shù)的大小為NXN.（一）平均值傅開變換域原點的頻譜分量珂叩）是空間域的平均值的N倍，即由右邊（1）式:lJ'.'-1J1.'-11J'.1-1JV-1（二）變換域的周期性設(shè)m,n為整數(shù)，m,n=0,±1,±2,…，將u+mN和v+nN代入右（1）式中，有:土M切川/）,誑-活弋5）.呷［一腿臉+嘩）］上式中，右邊第二個指數(shù)項誑［T5阮c+涉）］為單位值，因此傅立葉變換是周期性的，即：如+祕3+域）=戲"（三）對稱共軛性由離散傅立葉變換定義可方便地證明，傅立葉變換滿足：+?W）=F（-ui）=F*（3）（四）平移性如用E）5g）表示傅立葉變換對，則平移性是指：血）珂［腿吁叫。頊一心頊）川T盤頊*叩）誑［壬零芯|刊叩雨普血'+◎'）］=網(wǎng)叩）|LNJ，因而說明f（x,y）的移動并不影響它的傅立葉變換的幅度。（五）分配性和比例性設(shè)姒"），若恥"和戲"分別是川"就曷）的傅氏變換，則根據(jù)定義可知其分配性，即（線性特性）：F（um）=碩1但*）+占功（u,v）同時，也容易證明其比例性，即：F（（3u加）=（六）可分離性可分離性的主要優(yōu)點是可以通過兩次一維變換來實現(xiàn)一個二維變換（或反變換）。可分為兩步。第一步，先沿y軸對f（x,y）求一維離散傅立葉變換，得中間結(jié)果如G，艮即]其（"）=37捕/聶）岫-膈”）第二步，再沿x軸對F1（x,v）求一維離散傅氏變換，得最后結(jié)果F（u,v），即:（七）旋轉(zhuǎn)性質(zhì)由于在極坐標(biāo)下表示二維函數(shù)圖形的旋轉(zhuǎn)特性非常方便，所以將坐標(biāo)進(jìn)行轉(zhuǎn)換?？臻g域坐標(biāo)變換為：x=^cos6>7=^-sin^，頻率域坐標(biāo)變換為：u=tucos^v=tusin^，"）oS）便是極坐標(biāo)中的傅氏變換對。可以證明二維離散傅氏變換具有如下旋轉(zhuǎn)性質(zhì)：了區(qū)白+務(wù)）。『3渺+榭）（八）微分性質(zhì)傅立葉變換的微分性質(zhì)可表示為：冷15碩附6作為特例，定義拉普拉斯（Laplace）算式為：（在圖像增強中會用到）Art"）=寸六7）=邛工+等袒則由微分性質(zhì)可知laplace算子的傅氏變換為-逐+儼?微5），即：您3?=-0）氣投+"）玳叩）便是在模式識別技術(shù)中經(jīng)常用到的laplace算子。四.快速傅立葉變換（FFT）傅立葉變換除了具有前面介紹過的許多獨特性質(zhì)之外，還有一個突出的優(yōu)點，即它的快速算法（FFT）。FFT的存在使計算機節(jié)省了大量的計算時間。目前，快速傅立葉變換有好幾種，最常用的是由Cooley和Tukey于1965年首先提出來的一種FFT快速算法。利用這種算法在實現(xiàn)f（x）（x=0,1,…，N-1）的離散傅立葉變換時，需要完成的復(fù)數(shù)乘法和加法的次靈敏分別為1/2Nlog2N和Nlog2N。而直接用離散傅立葉變換的原始式（3-25）式計算f（x）的傅立葉變換時，需要進(jìn)行的復(fù)數(shù)乘法和加法次數(shù)分別為N2和N（N-1）^N2（后者稱為直接傅立葉變換（DFT））。通過表3-1比較N取不同的值時N2與Nlog2N的差異，可明顯看出FFT在計算速度上的巨大優(yōu)勢。對于一幅MXN的數(shù)字圖像，如果用DFT法計算其傅立葉變換，需要完成的復(fù)數(shù)乘法次數(shù)復(fù)數(shù)加法次數(shù)分別為M2N2和MN（M-1）（N-1）。對于目前常用的512X512圖像處理系統(tǒng)，用DFT法計算這樣一幅圖像的傅立葉變換，復(fù)數(shù)加法和乘法次數(shù)均將達(dá)到700億次，可以想象其運算量的巨大。因而FFT法的產(chǎn)生可以說是數(shù)字圖像處理領(lǐng)域的一次革命。下面開始討論Cooley和Tukey的逐次加倍法FFT的基本原理，它要求N為2的整數(shù)次幕，即N=2n（n為正整數(shù)）因為二維離散傅立葉變換可通過兩次一維離散傅立葉變換來實現(xiàn)，所以只討論一維FFT即可。由一維離散傅立葉變換的表達(dá)式，]E則（4-15）因為N為偶數(shù)，所以（4-15）式右邊共有偶數(shù)個項目相加，可將其分為兩部分之和，即N/2個偶數(shù)項和N/2個奇數(shù)項之和，則（4-15）式可寫為另1當(dāng)1心）=￡[立冷頃法"+立川"1必5]@=山廠小一1）因為囹另或給所以，有

我們知道F(u)(u=0,1,2,...,N-1)共有N個離散值散值分成兩個式子來表示，則有典f壽如￡」VJ￡(4-16)如果把前N/2個離散值與后N/2個離焉嗆皿+1)唉T5(4-17)Fu+—(將(4-18)這里(4-17)式表示了我們知道F(u)(u=0,1,2,...,N-1)共有N個離散值散值分成兩個式子來表示，則有典f壽如￡」VJ￡(4-16)如果把前N/2個離散值與后N/2個離焉嗆皿+1)唉T5(4-17)Fu+—(將則(4-18)式可簡化為：1項7詔/Q坪伽X+^=l[

k7-焉如g(4-19)則(4-17)式得(4-19)式可寫為汽u)則(4-17)式得(4-19)式可寫為汽u)=![璃&)+踹竭如)]汽n+?)=![跖⑴-畔扁⑴]由(4-20)式、(4-21)式和F林矗方E咐心只..孕(4-21)@=叫2...冷—1)心以…'？』(4-22)(4-22)式可以看出，計算一維離散傅立葉變換，可以分兩步進(jìn)行。第一步，先按定義求出扁⑴和％⑴，按(4-22)式計算出傅立葉變換F(u)的前N/2個點和后N/2個點。按這個方式求出全部N個點的F(u)，需要的復(fù)數(shù)乘法次數(shù)為N(N+1)/2，復(fù)數(shù)加法次數(shù)為N(N/2-1)?？梢运愠觯@種算法的速度約是DFT算法的兩倍。FFT的速度優(yōu)勢并不局限于此。因為N=2n,N是偶數(shù)，當(dāng)nN2時，N/2仍然是偶數(shù)。因

此，扁⑴和=的計算仍然可以按同樣方法分解為偶、奇兩個子集，得出如下結(jié)果琮@)=5［琮瑙@)+闞晶a烏浙W)］(4-23)(4-24)跖［瑋迥叫必”圮］(4-23)(4-24)(4-25)F哥瑙(H)=FF哥瑙(H)=F哥哥(u)=(4-26)對比(4-23)式(4-24)與(4-22)式可知，計算璃⑴和%)卜…"N，相當(dāng)于計算N/2個點離散函數(shù)的傅立葉變換。如果按這種方法一直進(jìn)行下去，直到求出兩點離散函數(shù)的傅立葉變換時為止。這就是快速傅立葉變換的原理。圖4-2給出了當(dāng)N=8(N=3)時的快速傅立葉變換的流程圖?？梢宰C明，這種FFT算法所要進(jìn)行的復(fù)數(shù)乘法和加法次數(shù)分別為按'吧"和ns&r從圖4-2可以看出，f(x)的8個樣本值中，f(0)與f(4)、f(2)與f(6)、f(1)與f(5)、f(3)與f(7)兩兩結(jié)合計算兩點變換、場腳、瑋哥、『枷和%，最后結(jié)果f(u)是按自然順序排列的。那么當(dāng)N>8且N=2n時，為使f(u)(u=0,1,2,…，N-1)按自然順序排列。f(x)(x=0,1,2,…，N-1)應(yīng)按怎樣的次序出現(xiàn)來首先完成兩點變換呢？解決這個問題的辦法稱為“比特倒置”整序處理?！氨忍氐怪谩钡脑瓌t是把f(x)的自然順序號0,1,2,…，N-1改寫成二進(jìn)制數(shù)，然后把這些二進(jìn)制數(shù)作比特位倒置，再將倒置后的二進(jìn)制數(shù)寫成對應(yīng)的十進(jìn)制數(shù)，這十進(jìn)制的值就是整序處理后f(x)的輸入序號。表4-1給出了N=8時的整序處理過程。

表4-1N=8時的“比特倒置”整序過程自然順序二進(jìn)制碼比特倒置整序后的順序0000000010011004201001023011110641000011510110156110011371111117現(xiàn)在考慮離散傅立葉反變換的快速算法。根據(jù)離散傅立葉反變換的表達(dá)式心a-f)(X=0,1,2,■■■,?/-1)兩邊取正軛，且乘以1/N，則有N3=叩,時璀-1)此式形式上與(4-15)式相同，應(yīng)用上面所討論的FFT的方法可求出F*(u)的傅立葉變換而廣⑴，由此式可得出f(x)。五?離散圖像變換的一般表達(dá)式1.離散圖像變換的代數(shù)表達(dá)式對二維離散函數(shù)川/Xr=虬…女-1；F=嘰…0-1)變換對的代數(shù)表達(dá)式，一般可寫為W")=zz六印)散匚虬")"3@=叫2???州-擇=嘰那??&-1)(4-27)NW)=戒"，兒口)2j4)u4)NW)=戒"，兒口)2j4)u4)3=偵"、蹌-揄=叫古??0-1)(4-28)其中稱削砌『口)為正變換核，稱心心0為反變換核。如果削砌『見=京")京CaB則稱變換核亦心0是可分離的。同樣，如果頃,虬皿）=妃匚必則稱反變換核是可分離的。變換核可分離的離散圖像變換可表示為x-m0=偵&…,M-擇=嘰&…&-1)(4-29)Hw'）=￡￡M.路乂3。'）熾饑。'）很1…向”口口3=叫2…,M-1；『=虬上…0-1）（4-30）如前面介紹的離散傅立葉變換，其正反變換核都是可分離的。由前面可知，二維離散傅立葉變換可以用兩次一維變換來實現(xiàn)。這個性質(zhì)對變換核（或反變換核）可分離的變換（或反變換）都適用。2.離散圖像變換的矩陣表達(dá)式在二維離散傅立葉變換表示式中，如果令則二維離散傅立葉變換用矩陣式表示，為■叫U）即?汽叫）珥1）…叫N-l)-…汽1,77-1)???:破1嘰噬-㈱■吼-啰T噸-噬心X汽M_頃）汽M-IQI-__啰T)喔心）…琳擴■沖）沖）如1)/(H)…加0-1)X:.-畔一-嘴T-哆g_f(M-1,0)/(A/-1,1)???■『…心（4-31）或簡單地表示為F叫盛T（4-32）上式兩邊左乘矩陣"片并右乘矩陣附#，則有(4-33)這就是離散傅立葉反變換的矩陣表示形式。通過（4-33）式可以看出■<-衩■1…咐S-??????一呢-峪七對比矩陣％與吃'，貿(mào)那與附孑可以看出<=^，所以矩陣吃和貿(mào)網(wǎng)是酉矩陣，而對應(yīng)的變換即離散傅立葉變換是一種酉變換。一般的，如果一個變換（及反變換）的變換核是可分離的，都可寫成如下矩陣形式。T=AfB對六登）皿=叫..算-成=偵..』-1），矩陣a為MXM方陣，矩陣B為NXN方陣。如果一個變換的變換核不可分離，則此變換的矩陣表示形式為T=Aff=A~1T其中：A和必】均為MXM方陣。變換核不可分離的變換，則無法通過兩次一維變換來實現(xiàn)二維變換。六■編程實驗根據(jù)二維離散傅立葉變換公式計算傅立葉譜，并顯示相應(yīng)的傅立葉譜圖像。實驗環(huán)境硬件：一般PC機操作系統(tǒng)：WindowsXP編程平臺：MATLAB或高級語言算法描述及實驗步驟Code：X=zeros(30,30);%本來這里用圖片的，圖片都太大了，所以創(chuàng)建一個小的。forI=14:16forJ=13:17X(I,J)=255;endendX=mat2gray(X);subplot(1,2,1);imshow(X);title原圖；b=size(X);M=1/b(1)*b(2);Y=zeros(b);for(u=1:b(1))for(v=1:b(2))for(x=1:b(1))for(y=1:b(2))Y(u,v)=(X(x,y)*exp(-j*2*pi*(u*x/b(1)+v*y/b(2))))+Y(u,v);end;end;Y(u,v)=M*Y(u,v);end;end;for(u=1:b(1))for(v=1:b(2))Y(u,v)=sqrt(real(Y(u,v))*real(Y(u,v))+i