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

1、第三章第三章 圖像變換圖像變換數(shù)字圖像處理數(shù)字圖像處理傅立葉變換原理傅立葉變換原理第三章第三章 圖像變換圖像變換1.1二維離散傅立葉變換二維離散傅立葉變換(Discrete Fourier Transform：DFT)性質(zhì)性質(zhì)二維離散傅立葉變換特性二維離散傅立葉變換特性 可分離性可分離性 平移性平移性 周期性與共軛對稱周期性與共軛對稱 旋轉(zhuǎn)特性旋轉(zhuǎn)特性 線性與比例性線性與比例性 均值性均值性 卷積與相關(guān)卷積與相關(guān)第三章第三章 圖像變換圖像變換1.1.1可分離性可分離性 二維離散傅立葉變換二維離散傅立葉變換DFTDFT可分離性的基本可分離性的基本思想是：思想是： 二維二維DFTDFT可分離為兩次

2、一維可分離為兩次一維DFTDFT。 應(yīng)用：應(yīng)用： 二維快速傅立葉算法二維快速傅立葉算法FFT FFT ，是通過計算兩，是通過計算兩次一維次一維FFTFFT實現(xiàn)的。實現(xiàn)的。第三章第三章 圖像變換圖像變換1.1.1 可分離性可分離性 可分離性的定義可分離性的定義 1M0 x1N0yMux2 jexpNvy2 jexpy, xfMN1v, uFu=0,1,2,u=0,1,2,M-1M-1；v=0,1,2,.N-1v=0,1,2,.N-1 1M0u1N0vMux2 jexpNvy2 jexpv, uFy, xfx=0,1,2,x=0,1,2,M-1M-1；y=0,1,2,.N-1y=0,1,2,.N-

3、1第三章第三章 圖像變換圖像變換1.1.1 可分離性可分離性 可分離性成立的推導(dǎo)可分離性成立的推導(dǎo)先對行（先對行（y y變量）做變換：變量）做變換： 102exp),(1,NyNvyjyxfNvxF然后對列（然后對列（x x變量）進(jìn)行變換：變量）進(jìn)行變換： 1M0 xMux2 jexp)v, x(FM1v, uF第三章第三章 圖像變換圖像變換1.1.1 可分離性可分離性先對行做變換：先對行做變換： 然后對列進(jìn)行變換：然后對列進(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

4、，N-1）uv第三章第三章 圖像變換圖像變換 傅立葉變換對有如下平移性質(zhì)：傅立葉變換對有如下平移性質(zhì)： f(x,y)expj2 (u0 x/M+v0y/N) F(u-u0,v-v0) 和和 f(x-x0,y-y0) F(u,v)exp-j2 (ux0/M+vy0/N) 以上式子表明，以上式子表明，在在頻域中頻域中原點原點平移到平移到(u0 ,v0)時時，其對應(yīng)的其對應(yīng)的f(x,y)要要乘乘上一個正的指數(shù)項：上一個正的指數(shù)項： expj2 (u0 x/M+v0y/N) ； 在空域中圖像原點平移到在空域中圖像原點平移到(x0,y0)時，時，其其對應(yīng)的對應(yīng)的F(u,v)要乘上一個負(fù)的指數(shù)項：要乘上一

5、個負(fù)的指數(shù)項： exp-j2 (ux0/M+vy0/N) 。1.1.2 平移性平移性第三章第三章 圖像變換圖像變換 對于對于M=N，則類似地有：則類似地有： f(x,y)expj2 (u0 x+v0y)/N F(u-u0,v-v0) 和和 f(x-x0,y-y0) F(u,v)exp-j2 (ux0+vy0)/N 在在頻域中頻域中原點原點平移到平移到(u0 ,v0)時時，其對應(yīng)的其對應(yīng)的f(x,y)要要乘乘上一個正的指數(shù)項上一個正的指數(shù)項expj2 (u0 x+v0y)/N； 在空域中圖像原點平移到在空域中圖像原點平移到(x0,y0)時，時，其其對應(yīng)的對應(yīng)的F(u,v)要乘上一個負(fù)的指數(shù)項要乘

6、上一個負(fù)的指數(shù)項exp-j2 (ux0+vy0)/N 。1.1.2 平移性平移性第三章第三章 圖像變換圖像變換3.3.2 平移性平移性 在數(shù)字圖像處理中，常常需要將在數(shù)字圖像處理中，常常需要將F(u,v)的原點的原點移到移到NN頻域的中心（平移前空域、頻域原點均頻域的中心（平移前空域、頻域原點均在左上方），以便能清楚地分析傅立葉譜的情況在左上方），以便能清楚地分析傅立葉譜的情況。要做到此，只需令。要做到此，只需令 u0=v0=N/2則則expj2(u0 x+v0y)/N =所以所以f(x,y)(-1)x+y F(u-N/2,v-N/2) 上式說明：如果需要將圖像傅立葉譜的原點從上式說明：如果需

7、要將圖像傅立葉譜的原點從左上角左上角(0,0)移到中心點移到中心點(N/2,N/2)，只要，只要f(x,y)乘上乘上(-1)x+y因子進(jìn)行傅立葉變換即可實現(xiàn)。因子進(jìn)行傅立葉變換即可實現(xiàn)。)()(22) 1(yxyxNNje第三章第三章 圖像變換圖像變換1.1.2 平移性平移性 平移性告訴我們一個感興趣的事實：當(dāng)空域中平移性告訴我們一個感興趣的事實：當(dāng)空域中f(x,y)產(chǎn)生產(chǎn)生移動移動時，在頻域中只發(fā)生相移，時，在頻域中只發(fā)生相移，并不影響并不影響它的傅立葉變換的幅它的傅立葉變換的幅值值，因為，因為),(),()(200vuFevuFvyuxNj 反之，當(dāng)頻域中反之，當(dāng)頻域中F(u,v)產(chǎn)生產(chǎn)生

8、移動移動時，相應(yīng)的時，相應(yīng)的f(x,y)在空域中也只發(fā)生相移，而在空域中也只發(fā)生相移，而幅幅值不變。值不變。第三章第三章 圖像變換圖像變換1.1.3 周期性和共軛對稱性周期性和共軛對稱性1.1.周期性周期性 離散傅立葉變換離散傅立葉變換DFTDFT和它的逆變換是以和它的逆變換是以N N為周期的。為周期的。對于一維傅立葉變換有：對于一維傅立葉變換有： F(u)=F(uF(u)=F(ukN)kN) k=0,1,2,k=0,1,2,對于二維傅立葉變換有：對于二維傅立葉變換有： F(u,v)=F(uF(u,v)=F(ukNkN,v,vl lN)N) k=0,1,2,k=0,1,2, l=0,1,2,

9、l=0,1,2, 第三章第三章 圖像變換圖像變換1.1.3 周期性和共軛對稱性周期性和共軛對稱性類似有：類似有：f(xkN,ylN)=f(x,y) 即從即從DFT的角度來看，反變換得到的圖像的角度來看，反變換得到的圖像陣列也是二維循環(huán)。陣列也是二維循環(huán)。 第三章第三章 圖像變換圖像變換1.1.3 周期性和共軛對稱性周期性和共軛對稱性2.2.共軛對稱性共軛對稱性 傅立葉變換結(jié)果是以原點為中心的共軛對傅立葉變換結(jié)果是以原點為中心的共軛對稱函數(shù)。稱函數(shù)。對于一維傅立葉變換有：對于一維傅立葉變換有： F(u) = FF(u) = F* *(kN-u)(kN-u) k=0,1,2, k=0,1,2,對于

10、二維傅立葉變換有：對于二維傅立葉變換有： F(u,v) = FF(u,v) = F* *(kN-u ,lN-v)(kN-u ,lN-v) k=0,1,2, k=0,1,2, l=0,1,2, l=0,1,2,第三章第三章 圖像變換圖像變換周期性和共軛對稱性舉例周期性和共軛對稱性舉例1.1.3 周期性和共軛對稱性周期性和共軛對稱性第三章第三章 圖像變換圖像變換3. 二維離散的傅立葉變換結(jié)果中頻率的分布二維離散的傅立葉變換結(jié)果中頻率的分布對應(yīng)低頻成分對應(yīng)低頻成分直流部分直流部分二維二維DFT二維二維IDFT圖像圖像對應(yīng)高頻成分對應(yīng)高頻成分對應(yīng)低頻成分對應(yīng)低頻成分 對應(yīng)高頻成分對應(yīng)高頻成分1 42

11、3直流部分直流部分換位換位3421光學(xué)的二維光學(xué)的二維DFT第三章第三章 圖像變換圖像變換1.1.3 周期性和共軛對稱性周期性和共軛對稱性 存儲存儲DFT結(jié)果的二維數(shù)組中頻率成分的分布，結(jié)果的二維數(shù)組中頻率成分的分布，如上圖所示，即數(shù)組的左上角相當(dāng)于直流部分，左如上圖所示，即數(shù)組的左上角相當(dāng)于直流部分，左上、右上、左下、右下各角的周圍對應(yīng)低頻成分，上、右上、左下、右下各角的周圍對應(yīng)低頻成分，數(shù)組中央部分附近對應(yīng)于高頻成分。為了使直流成數(shù)組中央部分附近對應(yīng)于高頻成分。為了使直流成分出現(xiàn)在數(shù)組中央，在把畫面分成四分的基礎(chǔ)上，分出現(xiàn)在數(shù)組中央，在把畫面分成四分的基礎(chǔ)上，進(jìn)行如圖所示的換位也是可以的。

12、進(jìn)行如圖所示的換位也是可以的。 使中央對直流部分這樣的二維傅立葉變換稱作使中央對直流部分這樣的二維傅立葉變換稱作光學(xué)傅立葉變換光學(xué)傅立葉變換(optical Fourier transform)。第三章第三章 圖像變換圖像變換1.1.4 旋轉(zhuǎn)特性旋轉(zhuǎn)特性 旋轉(zhuǎn)特性描述：旋轉(zhuǎn)特性描述： 如果如果f(x,y)f(x,y)旋轉(zhuǎn)了一個角度旋轉(zhuǎn)了一個角度 ，那么，那么f(x,y)f(x,y)旋旋轉(zhuǎn)后的圖像的傅立葉變換也旋轉(zhuǎn)了相同的角度轉(zhuǎn)后的圖像的傅立葉變換也旋轉(zhuǎn)了相同的角度 。 結(jié)論：結(jié)論： 對圖像的旋轉(zhuǎn)變換和傅立葉變換的順序是可對圖像的旋轉(zhuǎn)變換和傅立葉變換的順序是可交換的。交換的。FRf(x,y) F

13、Rf(x,y) RFf(x,y) RFf(x,y)第三章第三章 圖像變換圖像變換1.1.4 旋轉(zhuǎn)特性旋轉(zhuǎn)特性 反之，如果反之，如果F(u,v)旋轉(zhuǎn)某一角度，則旋轉(zhuǎn)某一角度，則f(x,y)在空間在空間域也旋轉(zhuǎn)同樣的角度。域也旋轉(zhuǎn)同樣的角度。 若引入極坐標(biāo)若引入極坐標(biāo)sincosryrxsincosvu 則則f(x,y)和和F(u,v)分別變?yōu)榉謩e變?yōu)閒(r, )和和F( , )。在極坐。在極坐標(biāo)中存在以下變換對：標(biāo)中存在以下變換對： f(r, + 0) F(, + 0) 這條性質(zhì)以極坐標(biāo)代以這條性質(zhì)以極坐標(biāo)代以x,y,u,v，則可以得到證明。，則可以得到證明。第三章第三章 圖像變換圖像變換1.1

14、.5 線性與比例性線性與比例性1.1.線性線性 線性的描述：傅立葉變換是線性系統(tǒng)、函數(shù)線性的描述：傅立葉變換是線性系統(tǒng)、函數(shù)和的傅立葉變換是可分離的。和的傅立葉變換是可分離的。設(shè)：設(shè)：f(x,y)f(x,y)的傅立葉變換為的傅立葉變換為Ff(x,y)Ff(x,y)g(x,y)g(x,y)的傅立葉變換為的傅立葉變換為Fg(x,y) Fg(x,y) 有：有：Ff(x,y)+g(x,y) = Ff(x,y)+Fg(x,y) Ff(x,y)+g(x,y) = Ff(x,y)+Fg(x,y) 第三章第三章 圖像變換圖像變換1.1.5線性與比例性線性與比例性2.2.比例性比例性 比例性的描述：比例性的描述

15、：af(x,y) af(x,y) aF(u,v) aF(u,v)且有：且有： f(ax,by) f(ax,by) 1/|ab|F(u/a,v/b) 1/|ab|F(u/a,v/b) 第三章第三章 圖像變換圖像變換1.1.6 均值性均值性 均值性的描述：均值性的描述： 離散函數(shù)的均值等于該函數(shù)傅立葉變換在離散函數(shù)的均值等于該函數(shù)傅立葉變換在(0,0)(0,0)點的值。點的值。 01M0 x1N0yey, xfMN1y, xf0 , 0Fy, xf第三章第三章 圖像變換圖像變換1.1.7 卷積與相關(guān)卷積與相關(guān) 卷積與相關(guān)卷積與相關(guān): :空域和頻域之間的基本聯(lián)系空域和頻域之間的基本聯(lián)系1.1.卷積卷

16、積 卷積定理的描述：卷積定理的描述：空域中的卷積等價于頻域中的相乘空域中的卷積等價于頻域中的相乘f(x,y)f(x,y)* *g(x,y) g(x,y) F(u,v)G(u,v) F(u,v)G(u,v) Ff(x,y) Ff(x,y)* *g(x,y) = F(u,v)G(u,v)g(x,y) = F(u,v)G(u,v)同時有：同時有：f(x,y) g(x,y) f(x,y) g(x,y) F(u,v) F(u,v)* *G(u,v)G(u,v)第三章第三章 圖像變換圖像變換1.1.7 卷積與相關(guān)卷積與相關(guān)2. 相關(guān)相關(guān) 相關(guān)定理的描述：相關(guān)定理的描述： 空域中空域中f(x,y)f(x,y

17、)與與g(x,y)g(x,y)的相關(guān)等價于頻域的相關(guān)等價于頻域中中F(u,v)F(u,v)的共軛與的共軛與G(u,v) G(u,v) 相乘相乘 f(x,y)f(x,y)g(x,y) g(x,y) F F* *(u,v)G(u,v)(u,v)G(u,v)同時有：同時有：f f* *(x,y)g(x,y) (x,y)g(x,y) F(u,v) F(u,v)G(u,v)G(u,v)第三章第三章 圖像變換圖像變換1.2 快速傅立葉變換快速傅立葉變換 FFT FFT算法基于一個叫做算法基于一個叫做遞推加倍遞推加倍的方法，通的方法，通過推導(dǎo)將過推導(dǎo)將DFTDFT轉(zhuǎn)換成兩個遞推公式。為方便起見轉(zhuǎn)換成兩個遞推

18、公式。為方便起見我們用下式表達(dá)離散傅立葉變換公式：我們用下式表達(dá)離散傅立葉變換公式： 1.FFT1.FFT算法算法基本思想基本思想 這里這里 W WN N = exp(-j2= exp(-j2 /N)/N) 是一個常數(shù)是一個常數(shù) 1N0 xuxNWxfN1uF 1N0 x)N/ux2 jexp()x( fN1uF第三章第三章 圖像變換圖像變換1.2快速傅立葉變換快速傅立葉變換遞推公式推導(dǎo)遞推公式推導(dǎo) 假設(shè)假設(shè)N N為：為： N = 2N = 2n n 其中其中n n是一個正整數(shù)，因此是一個正整數(shù)，因此N N可表示為：可表示為：N = 2MN = 2M 這里這里M M仍然是一個正整數(shù)。將仍然是一

19、個正整數(shù)。將N = 2MN = 2M代入前一頁的代入前一頁的式子，得到：式子，得到： 1M20 xuxM2WxfM21uF1M0 x1x2uM21M0 xx2uM2w1x2fM1wx2fM121第三章第三章 圖像變換圖像變換1.2 快速傅立葉變換快速傅立葉變換所以：所以：由于：由于： W WN N = exp(-j2= exp(-j2 /N)/N) uxMux2M2WMux2 jexpM2ux22 jexpW 代入前頁式子有：代入前頁式子有：xuMxu2M2WW 第三章第三章 圖像變換圖像變換1.2 快速傅立葉變換快速傅立葉變換定義兩個符號：定義兩個符號： uM2uxM1M0 xuxM1M0

20、xWW1x2fM1Wx2fM121)u(F uxM1M0 xevenWx2fM1uF 偶數(shù)部分偶數(shù)部分u=0,1,2,u=0,1,2,M-1M-1 uxM1M0 xoddW1x2fM1uF 奇數(shù)部分奇數(shù)部分u=0,1,2,u=0,1,2,M-1M-11012210221212121)(MxxuMMxxuMwxfMwxfMuFxuMxu2M2WW 第三章第三章 圖像變換圖像變換1.2 快速傅立葉變換快速傅立葉變換得出得出FFT FFT 的第一個遞推公式：的第一個遞推公式：該公式說明該公式說明F(u)F(u)可以通過偶部和奇部之和來計算?？梢酝ㄟ^偶部和奇部之和來計算。 uM2oddevenWuFu

21、F21uF 第三章第三章 圖像變換圖像變換1.2 快速傅立葉變換快速傅立葉變換另有：另有：W WM Mu+M u+M = = expexp-2j-2j (u+M)/M(u+M)/M= exp-2j= exp-2j u/Mexp-2ju/Mexp-2j = = W WM Mu ue ej j (-2) (-2) = = W WM Mu u(-1)(-1)(-2) (-2) = = W WM Mu u且：且： W W2M2Mu+M u+M = = expexp-2j-2j (u+M)/2M(u+M)/2M = = exp-2jexp-2j u/2M u/2M e ej j (-1)(-1) = =

22、 W W2M2Mu u (-1)(-1)(-1) (-1) = -= -W W2M2Mu u最后有：最后有：W WM Mu+M u+M = = W WM Mu u ； W W2M2Mu+M u+M = = - -W W2M2Mu u第三章第三章 圖像變換圖像變換uModdevenMxMxuMuxMuxMMxMxMuMxMuMxMuMMxMxxMuMxMuMMxxMuMWuFuFWWxfMWxfMWWxfMWxfMWxfMWxfMWxfMMuF2101021010210101222212022112121211212121121212121)()()()()()()()()()()()()()(

23、)()(得出得出u+M的的DFT:uMMuMuMMuMxuMxuMWWWWWW2222 1M20 xuxM2WxfM21uF1M0 x1x2uM21M0 xx2uM2w1x2fM1wx2fM121第三章第三章 圖像變換圖像變換得出得出FFTFFT的第二個遞推公式：的第二個遞推公式： 1.2 快速傅立葉變換快速傅立葉變換該公式說明該公式說明F(u+M)F(u+M)可以通過可以通過F(u)F(u)偶部和奇部之差偶部和奇部之差來計算。來計算。F(u+M)= 1/2(FF(u+M)= 1/2(Feveneven(u)-F(u)-Foddodd(u)W(u)W2M2Mu u) )第三章第三章 圖像變換圖

24、像變換1.2 快速傅立葉變換快速傅立葉變換得出得出FFTFFT的兩個遞推公式：的兩個遞推公式： F(u) = 1/2(FF(u) = 1/2(Feveneven(u)(u)+ +F Foddodd(u)W(u)W2M2Mu u) ) F(u+M)= 1/2(F F(u+M)= 1/2(Feveneven(u)(u)- -F Foddodd(u)W(u)W2M2Mu u) ) uxM1M0 xevenWx2fM1uF uxM1M0 xoddW1x2fM1uF 第三章第三章 圖像變換圖像變換1.2 快速傅立葉變換快速傅立葉變換分析這些表達(dá)式得到如下一些有趣的特性：分析這些表達(dá)式得到如下一些有趣的特

25、性：（1 1）一個）一個N N個點的變換，能夠通過將原始表達(dá)個點的變換，能夠通過將原始表達(dá) 式分成兩個部分來計算。式分成兩個部分來計算。（2 2）通過計算兩個（）通過計算兩個（N/2N/2）個點的變換。得到）個點的變換。得到 F Feveneven(u)(u)和和 F Foddodd(u)(u)。（3 3）偶部與奇部之和得到）偶部與奇部之和得到F(u)F(u)的前的前(N/2)(N/2)個值。個值。（4 4）偶部與奇部之差得到）偶部與奇部之差得到F(u)F(u)的后的后(N/2)(N/2)個值。個值。 且不需要額外的變換計算。且不需要額外的變換計算。第三章第三章 圖像變換圖像變換1.2快速傅立

26、葉變換快速傅立葉變換歸納快速傅立葉變換的思想：歸納快速傅立葉變換的思想：1 1）通過計算兩個單點的）通過計算兩個單點的DFTDFT，來計算兩個點的，來計算兩個點的DFTDFT。2 2）通過計算兩個雙點的）通過計算兩個雙點的DFTDFT，來計算四個點的，來計算四個點的DFTDFT，以此類推。，以此類推。3 3）對于任何）對于任何N=2N=2n n的的DFTDFT的計算，的計算，通過計算兩個通過計算兩個N/2N/2點的點的DFTDFT，來計算，來計算N N個點的個點的DFTDFT。第三章第三章 圖像變換圖像變換1.2 快速傅立葉變換快速傅立葉變換2.逆向逆向FFT算法算法 算法思想描述：用正向變換

27、計算逆向算法思想描述：用正向變換計算逆向變換。變換。 NuxjxfNuFNx2exp110u = 0,1,2,.N-1u = 0,1,2,.N-1 NuxjuFxfNu2exp10 x = 0,1,2,.N-1x = 0,1,2,.N-1第三章第三章 圖像變換圖像變換1.2 快速傅立葉變換快速傅立葉變換 在離散逆向變換表達(dá)式兩邊同取共軛，并除在離散逆向變換表達(dá)式兩邊同取共軛，并除N N Nux2 jexpuFN1xfN11N0uu = 0,1,2,.N-1u = 0,1,2,.N-1 可以看出，上式的右端在形式上就是傅立葉正可以看出，上式的右端在形式上就是傅立葉正變換。因此，只要將變換。因此，

28、只要將F*(u)輸入，用正向變換算法輸入，用正向變換算法計算，得到計算，得到1/Nf*(x) ，取共軛并乘上取共軛并乘上N，即得到，即得到f(x) 。 NuxjxfNuFNx2exp110 NuxjuFxfNu2exp10第三章第三章 圖像變換圖像變換1.2 快速傅立葉變換快速傅立葉變換3. FFTFFT算法實現(xiàn)舉例算法實現(xiàn)舉例通過一個實例來體會一下通過一個實例來體會一下FFTFFT算法：算法：設(shè)：有函數(shù)設(shè)：有函數(shù)f(x)f(x)，其，其 N = 2N = 23 3 = 8 = 8，有：有： f(0), f(1), f(2), f(3), f(4), f(5), f(0), f(1), f(2

29、), f(3), f(4), f(5), f(6), f(7)f(6), f(7) 計算：計算： F(0), F(1), F(2), F(3), F(4), F(5), F(0), F(1), F(2), F(3), F(4), F(5), F(6),F(7)F(6),F(7) 第三章第三章 圖像變換圖像變換1.2 快速傅立葉變換快速傅立葉變換首先分成奇偶兩組，有：首先分成奇偶兩組，有： f(0), f(2), f(4), f(6) f(0), f(2), f(4), f(6) f(1), f(3), f(5), f(7) f(1), f(3), f(5), f(7) 為了利用遞推特性，再分成

30、兩組，有：為了利用遞推特性，再分成兩組，有： f(0), f(4) f(0), f(4) ， f(2), f(6) f(2), f(6) f(1), f(5) f(1), f(5) ， f(3), f(7) f(3), f(7) 第三章第三章 圖像變換圖像變換 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

31、), F8(4), F8(5), F8(6), F8(7) 第三章第三章 圖像變換圖像變換1.2 快速傅立葉變換快速傅立葉變換 算法實現(xiàn)的幾個關(guān)鍵點算法實現(xiàn)的幾個關(guān)鍵點1 1）地址的排序：）地址的排序：按位倒序規(guī)則按位倒序規(guī)則例如：例如：N = 2N = 23 3 = 8= 8原地址原地址 原順序原順序 新地址新地址 新順序新順序 000000 f(0) f(0) 000 000 f(0) f(0) 001 001 f(1) f(1) 100 100 f(4) f(4) 010 010 f(2) f(2) 010 010 f(2) f(2) 011 011 f(3) f(3) 110 110 f(6) f(6) 100 100 f(4) f(4) 001 001 f(1) f(1) 101 101 f(5) f(5) 101 101 f(5) f(5) 110 110 f(6) f(6) 011 011 f(3) f(3) 111 111 f(7) f(7) 111 111 f(7) f(7)第三章第三章 圖像變換圖像變換1.2 快速傅立葉變換快速傅立葉變換2 2）計算順序及地址增量）計算順序及