數(shù)字圖像處理傅立葉變換

數(shù)字圖像處理傅立葉變換第1頁，共46頁，2023年，2月20日，星期六3.3.1可分離性?二維離散傅立葉變換DFT可分離性的基本思想是：

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

二維快速傅立葉算法FFT，是通過計(jì)算兩次一維FFT實(shí)現(xiàn)的。第2頁，共46頁，2023年，2月20日，星期六3.3.1可分離性可分離性的定義u=0,1,2,…M-1；v=0,1,2,...N-1x=0,1,2,…M-1；y=0,1,2,...N-1第3頁，共46頁，2023年，2月20日，星期六3.3.1可分離性可分離性成立的推導(dǎo)先對(duì)行（y變量）做變換：然后對(duì)列（x變量）進(jìn)行變換：第4頁，共46頁，2023年，2月20日，星期六3.3.1可分離性先對(duì)行做變換：–然后對(duì)列進(jìn)行變換：f(x,y)（0,0）（M-1，N-1）xyF(x,v)（0,0）（M-1，N-1）xvF(x,v)（0,0）（M-1，N-1）xvF(u,v)（0,0）（M-1，N-1）uv第5頁，共46頁，2023年，2月20日，星期六?

傅立葉變換對(duì)有如下平移性質(zhì)：

f(x,y)exp[j2(u0x/M+v0y/N)]F(u-u0,v-v0)

和f(x-x0,y-y0)F(u,v)exp[-j2(ux0/M+vy0/N)]

以上式子表明，在頻域中原點(diǎn)平移到(u0,v0)時(shí)，其對(duì)應(yīng)的f(x,y)要乘上一個(gè)正的指數(shù)項(xiàng)：

exp[j2(u0x/M+v0y/N)]；在空域中圖像原點(diǎn)平移到(x0,y0)時(shí)，其對(duì)應(yīng)的F(u,v)要乘上一個(gè)負(fù)的指數(shù)項(xiàng)：

exp[-j2(ux0/M+vy0/N)]

。3.3.2平移性第6頁，共46頁，2023年，2月20日，星期六?對(duì)于M=N，則類似地有：

f(x,y)exp[j2(u0x+v0y)/N]F(u-u0,v-v0)

和f(x-x0,y-y0)F(u,v)exp[-j2(ux0+vy0)/N]

在頻域中原點(diǎn)平移到(u0,v0)時(shí)，其對(duì)應(yīng)的f(x,y)要乘上一個(gè)正的指數(shù)項(xiàng)exp[j2(u0x+v0y)/N]；在空域中圖像原點(diǎn)平移到(x0,y0)時(shí)，其對(duì)應(yīng)的F(u,v)要乘上一個(gè)負(fù)的指數(shù)項(xiàng)exp[-j2(ux0+vy0)/N]

。3.3.2平移性第7頁，共46頁，2023年，2月20日，星期六3.3.2平移性

在數(shù)字圖像處理中，常常需要將F(u,v)的原點(diǎn)移到N×N頻域的中心（平移前空域、頻域原點(diǎn)均在左上方），以便能清楚地分析傅立葉譜的情況。要做到此，只需令

u0=v0=N/2則exp[j2π(u0x+v0y)/N]=所以f(x,y)(-1)x+y

F(u-N/2,v-N/2)

上式說明：如果需要將圖像傅立葉譜的原點(diǎn)從左上角(0,0)移到中心點(diǎn)(N/2,N/2)，只要f(x,y)乘上(-1)x+y因子進(jìn)行傅立葉變換即可實(shí)現(xiàn)。第8頁，共46頁，2023年，2月20日，星期六3.3.2平移性

平移性告訴我們一個(gè)感興趣的事實(shí)：當(dāng)空域中f(x,y)產(chǎn)生移動(dòng)時(shí)，在頻域中只發(fā)生相移，并不影響它的傅立葉變換的幅值，因?yàn)?/p>

反之，當(dāng)頻域中F(u,v)產(chǎn)生移動(dòng)時(shí)，相應(yīng)的f(x,y)在空域中也只發(fā)生相移，而幅值不變。第9頁，共46頁，2023年，2月20日，星期六3.3.3周期性和共軛對(duì)稱性1.周期性

離散傅立葉變換DFT和它的逆變換是以N為周期的。對(duì)于一維傅立葉變換有：

F(u)=F(u±kN)k=0,1,2,···對(duì)于二維傅立葉變換有：

F(u,v)=F(u±kN,v±lN)k=0,1,2,···l=0,1,2,···

第10頁，共46頁，2023年，2月20日，星期六3.3.3周期性和共軛對(duì)稱性類似有：f(x±kN,y±lN)=f(x,y)即從DFT的角度來看，反變換得到的圖像陣列也是二維循環(huán)。

第11頁，共46頁，2023年，2月20日，星期六3.3.3周期性和共軛對(duì)稱性2.共軛對(duì)稱性傅立葉變換結(jié)果是以原點(diǎn)為中心的共軛對(duì)稱函數(shù)。對(duì)于一維傅立葉變換有：

F(u)=F*(kN-u)k=0,1,2,···對(duì)于二維傅立葉變換有：

F(u,v)=F*(kN-u,lN-v)k=0,1,2,···l=0,1,2,···第12頁，共46頁，2023年，2月20日，星期六周期性和共軛對(duì)稱性舉例3.3.3周期性和共軛對(duì)稱性第13頁，共46頁，2023年，2月20日，星期六3.二維離散的傅立葉變換結(jié)果中頻率的分布對(duì)應(yīng)低頻成分直流部分二維DFT二維IDFT圖像對(duì)應(yīng)高頻成分對(duì)應(yīng)低頻成分對(duì)應(yīng)高頻成分1423直流部分換位3421光學(xué)的二維DFT第14頁，共46頁，2023年，2月20日，星期六3.3.3

周期性和共軛對(duì)稱性

存儲(chǔ)DFT結(jié)果的二維數(shù)組中頻率成分的分布，如上圖所示，即數(shù)組的左上角相當(dāng)于直流部分，左上、右上、左下、右下各角的周圍對(duì)應(yīng)低頻成分，數(shù)組中央部分附近對(duì)應(yīng)于高頻成分。為了使直流成分出現(xiàn)在數(shù)組中央，在把畫面分成四分的基礎(chǔ)上，進(jìn)行如圖所示的換位也是可以的。使中央對(duì)直流部分這樣的二維傅立葉變換稱作光學(xué)傅立葉變換(opticalFouriertransform)。第15頁，共46頁，2023年，2月20日，星期六3.3.4旋轉(zhuǎn)特性旋轉(zhuǎn)特性描述：

如果f(x,y)旋轉(zhuǎn)了一個(gè)角度，那么f(x,y)旋轉(zhuǎn)后的圖像的傅立葉變換也旋轉(zhuǎn)了相同的角度。

?結(jié)論： 對(duì)圖像的旋轉(zhuǎn)變換和傅立葉變換的順序是可交換的。

F{R{f(x,y)}}R{F{f(x,y)}}第16頁，共46頁，2023年，2月20日，星期六3.3.4旋轉(zhuǎn)特性反之，如果F(u,v)旋轉(zhuǎn)某一角度，則f(x,y)在空間域也旋轉(zhuǎn)同樣的角度。若引入極坐標(biāo)

則f(x,y)和F(u,v)分別變?yōu)閒(r,)和F(ω

,φ

)。在極坐標(biāo)中存在以下變換對(duì)：

f(r,+0)F(ω,φ+0)

這條性質(zhì)以極坐標(biāo)代以x,y,u,v，則可以得到證明。第17頁，共46頁，2023年，2月20日，星期六3.3.5線性與比例性1.線性?線性的描述：傅立葉變換是線性系統(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)}第18頁，共46頁，2023年，2月20日，星期六3.3.5線性與比例性2.比例性?比例性的描述： af(x,y)aF(u,v)

且有：

f(ax,by)1/|ab|F(u/a,v/b)第19頁，共46頁，2023年，2月20日，星期六3.3.6均值性均值性的描述：

離散函數(shù)的均值等于該函數(shù)傅立葉變換在(0,0)點(diǎn)的值。

第20頁，共46頁，2023年，2月20日，星期六3.3.7卷積與相關(guān)卷積與相關(guān):空域和頻域之間的基本聯(lián)系1.卷積?卷積定理的描述：空域中的卷積等價(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)第21頁，共46頁，2023年，2月20日，星期六3.3.7卷積與相關(guān)2.相關(guā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)第22頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換FFT算法基于一個(gè)叫做遞推加倍的方法，通過推導(dǎo)將DFT轉(zhuǎn)換成兩個(gè)遞推公式。為方便起見我們用下式表達(dá)離散傅立葉變換公式：

1.FFT算法——基本思想

這里

WN

=exp(-j2/N)

是一個(gè)常數(shù)第23頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換遞推公式推導(dǎo)假設(shè)N為： N=2n

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

N=2M這里M仍然是一個(gè)正整數(shù)。將N=2M代入前一頁的式子，得到： 第24頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換所以：由于：WN=exp(-j2/N)代入前頁式子有：第25頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換定義兩個(gè)符號(hào)：偶數(shù)部分u=0,1,2,…M-1奇數(shù)部分u=0,1,2,…M-1第26頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換得出FFT的第一個(gè)遞推公式：

該公式說明F(u)可以通過偶部和奇部之和來計(jì)算。第27頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換另有：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第28頁，共46頁，2023年，2月20日，星期六得出u+M的DFT:第29頁，共46頁，2023年，2月20日，星期六得出FFT的第二個(gè)遞推公式：3.4快速傅立葉變換該公式說明F(u+M)可以通過F(u)偶部和奇部之差來計(jì)算。F(u+M)=1/2(Feven(u)-Fodd(u)W2Mu)第30頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換得出FFT的兩個(gè)遞推公式：

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

第31頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換分析這些表達(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ì)算。第32頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換歸納快速傅立葉變換的思想：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=2n的DFT的計(jì)算，通過計(jì)算兩個(gè)N/2點(diǎn)的DFT，來計(jì)算N個(gè)點(diǎn)的DFT。第33頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換2.逆向FFT算法算法思想描述：用正向變換計(jì)算逆向變換。u=0,1,2,...N-1

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

第34頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換在離散逆向變換表達(dá)式兩邊同取共軛，并除Nu=0,1,2,...N-1

可以看出，上式的右端在形式上就是傅立葉正變換。因此，只要將F*(u)輸入，用正向變換算法計(jì)算，得到1/Nf*(x)，取共軛并乘上N，即得到f(x)。

第35頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換3.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)}

第36頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換首先分成奇偶兩組，有：{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)}

第37頁，共46頁，2023年，2月20日，星期六

{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(2),F4(4),F4(6)}{F4(1),F4(3),F4(5),F4(7)}

{F8(0),F8(1),F8(2),F8(3),F8(4),F8(5),F8(6),F8(7)}

第38頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換算法實(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)第39頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換2）計(jì)算順序及地址增量地址+1 地址+2 地址+4f(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)

第40頁，共46頁，2023年，2月20日，星期六3.4快速傅立葉變換3）復(fù)系數(shù)的計(jì)算：——尤拉公式

W2M

=exp[-j2/2M] =exp[-j/M] =cos(/M)-jsin(/M)F(u)=1/2(Feven(u)+Fodd(u)W2Mu)F(u+M)=1/2(