圖像檢測(cè)-10頻域變換

1、第十章圖像的頻域變換第十章圖像的頻域變換本章要點(diǎn):二維離散二維離散FourierFourier變換變換快速快速FourierFourier變換（變換（FFTFFT）二維二維FourierFourier變換的應(yīng)用變換的應(yīng)用 人類視覺(jué)所感受到的是在空間域和時(shí)人類視覺(jué)所感受到的是在空間域和時(shí)間域的信號(hào)。間域的信號(hào)。 但是，往往許多問(wèn)題在頻域中討論時(shí)，但是，往往許多問(wèn)題在頻域中討論時(shí)，有其非常方便分析的一面。例如，空有其非常方便分析的一面。例如，空間位置上的變化不改變信號(hào)的頻域特間位置上的變化不改變信號(hào)的頻域特性。性。問(wèn)題的提出：?jiǎn)栴}的提出：10.1 10.1 二維離散二維離散FourierFouri

2、er變換變換 1010)(2),(),(MxNyjNyvMxueyxfvuF正變換：正變換：,)fTfTfxy列行（ （,)fTfTfxy列行（ （注：這里給出的一維正變換的系數(shù)為注：這里給出的一維正變換的系數(shù)為1 1。 二維Fourier變換可以轉(zhuǎn)化為兩次一維Fourier變換。 101022),(MxNyjjMxuNyveeyxf1010)(2),(1),(MuNvjNyvMxuevuFMNyxf反變換：反變換：注：逆變換的系數(shù)不為注：逆變換的系數(shù)不為1 1。),(111vuFfTfTMN列列行行 ),(111vuFfTfTMN行行列列 因?yàn)橐驗(yàn)镕ourier變換是一種正交變換，所以變換是

3、一種正交變換，所以其正、反變換的系數(shù)可以有幾種表示形式。其正、反變換的系數(shù)可以有幾種表示形式。 按照嚴(yán)格意義上的正交變換，正、反變換按照嚴(yán)格意義上的正交變換，正、反變換的系數(shù)相等，為：的系數(shù)相等，為：1MN 按照計(jì)算方便的角度，正、反變換的系數(shù)按照計(jì)算方便的角度，正、反變換的系數(shù)可以按照前面的方式給出，并且正、反變換可以按照前面的方式給出，并且正、反變換的系數(shù)可以互換。的系數(shù)可以互換。FourierFourier變換有兩個(gè)好處：變換有兩個(gè)好處：1 1）可以得出）可以得出信號(hào)在各個(gè)頻率點(diǎn)信號(hào)在各個(gè)頻率點(diǎn)上的強(qiáng)度。上的強(qiáng)度。2 2）可以將卷積運(yùn)算化為乘積運(yùn)算。）可以將卷積運(yùn)算化為乘積運(yùn)算。10.2

4、 10.2 快速快速FourierFourier變換（變換（FFTFFT） 快速Fourier變換的提出，是為了減少計(jì)算量。 基本思想是，找出Fourier變換中的數(shù)據(jù)變化規(guī) 律，按照其規(guī)律整理出適合計(jì)算機(jī)運(yùn)算的邏輯 結(jié)構(gòu)。 N個(gè)點(diǎn)需做N2次復(fù)數(shù)乘法和N(N-1)次復(fù)數(shù)加法。而做一次復(fù)數(shù)乘法需要做四次實(shí)數(shù)相乘和兩次實(shí)數(shù)相加，做一次復(fù)數(shù)加法需要做兩次實(shí)數(shù)相加。 例：N=1024時(shí)，則需要總共1,048,576次復(fù)數(shù)乘，即4,194,304次實(shí)數(shù)乘法。 快速傅里葉變換(FFT，F(xiàn)ast Fourier Transform)算法的本質(zhì):充分利用因子WN的周期性和對(duì)稱性。 對(duì)稱性： 周期性： FFT算

5、法的基本思想：避免運(yùn)算中的重復(fù)運(yùn)算，將長(zhǎng)序列的DFT分割為短序列的DFT的線性組合，從而達(dá)到整體降低運(yùn)算量的目的。 效果：使原來(lái)的N點(diǎn)DFT的乘法計(jì)算量從N2次降至為N/2log2N次，如N=1024，則計(jì)算量現(xiàn)在為5120次，僅為原計(jì)算量的4.88% 。nkN2NnkNWW nkNnkNNWW 10.2.1 FFT10.2.1 FFT的推導(dǎo)的推導(dǎo) M0)exp(2NxxNjw令：xNNxwxfF10)()( ：則/2 1/2 12(21)00(2 )(21)NNxxNNxxfx wfxw11200(2 )(21)MMxxNMMNxxMfx wfxw w)()()(oNeFwFF（分成奇數(shù)項(xiàng)和

6、偶數(shù)項(xiàng)之和）（分成奇數(shù)項(xiàng)和偶數(shù)項(xiàng)之和）xMMxNxNxxNwjjjw)exp()exp()exp(2/22222 （又可分成奇數(shù)項(xiàng)和偶數(shù)項(xiàng)之和）（又可分成奇數(shù)項(xiàng)和偶數(shù)項(xiàng)之和）( )eF10(2 )MxMxfxw11200(2(2 )(2(21)LLxxMLLMxxLfx wfxw w)()()()2()2(oMeeFwFF ( )F( )( )eNoFw F=(2 )(2 )( )( )eeeMoFw F=(2 )(2 )( )( )ooeMoFw F= FFT的數(shù)據(jù)變換規(guī)律之一是：1)可以不斷分成奇數(shù)項(xiàng)與偶數(shù)項(xiàng)之加權(quán)和。2)奇數(shù)項(xiàng)、偶數(shù)項(xiàng)可分層分類。)()()(MFwMFMFoMNe)()(

7、oMNeFwF)exp(2NMNMNNMNjwwwwNNwjw)exp()()()(oNeFwFMF 至此，計(jì)算量可減少近一半。1)2exp()2exp()2()(10 jxMMxjWWWxfMFMxMMxMxMxMe其中：其中：10.2.2 FFT10.2.2 FFT的設(shè)計(jì)思想的設(shè)計(jì)思想 首先，將原函數(shù)分為奇數(shù)項(xiàng)和偶數(shù)項(xiàng)，通過(guò)首先，將原函數(shù)分為奇數(shù)項(xiàng)和偶數(shù)項(xiàng)，通過(guò)不斷的一個(gè)奇數(shù)一個(gè)偶數(shù)的相加（減），最不斷的一個(gè)奇數(shù)一個(gè)偶數(shù)的相加（減），最終得到需要的結(jié)果。終得到需要的結(jié)果。 也就是說(shuō)也就是說(shuō)FFTFFT是將復(fù)雜的運(yùn)算變成兩個(gè)數(shù)相是將復(fù)雜的運(yùn)算變成兩個(gè)數(shù)相 加（減）的簡(jiǎn)單運(yùn)算的重復(fù)。加（減）的

8、簡(jiǎn)單運(yùn)算的重復(fù)。10.2.3 FFT10.2.3 FFT算法算法1. 1. 先將數(shù)據(jù)進(jìn)行奇、偶分組先將數(shù)據(jù)進(jìn)行奇、偶分組。01234567, ,ff ffffff89101112131415,ffffffff例：02468101214,ffffffff f f fffff下標(biāo)為2x下標(biāo)為2x+1偶數(shù)部分：偶數(shù)部分：奇數(shù)部分：奇數(shù)部分：00000000，00100010，01000100，01100110，10001000，10101010，11001100，1110111000010001，00110011，01010101，01110111，10011001，101

9、11011，11011101，11111111024681 01 21 4,ffffffff135791 11 31 5,ffffffff下標(biāo)用二進(jìn)制數(shù)表示為：下標(biāo)用二進(jìn)制數(shù)表示為：二進(jìn)制數(shù)為：二進(jìn)制數(shù)為：00000 00 0，0010010 0，01010 00 0，0110110 0，10100 00 0，1011010 0，11110 00 0，1111110 0第一層下標(biāo)為：第一層下標(biāo)為： 0 2 4 6 8 10 12 140 2 4 6 1 3 5 7 /2*2第一層下標(biāo)分組為：第一層下標(biāo)分組為： 0， 4，8，12； 2，6，10，142.對(duì)偶數(shù)部分進(jìn)行分層分組排序移位：移位：0

10、0000 0，001001，01010 0，011011，10100 0，101101，11110 0，111111偶數(shù)組：偶數(shù)組：00000 0，01010 0，10100 0，11110 0奇數(shù)組：奇數(shù)組：001001，011011，101101，111111二進(jìn)制數(shù)為：二進(jìn)制數(shù)為： 00000 00 0， 01010 00 0， 10100 00 0， 11110 00 0第二層下標(biāo)為第二層下標(biāo)為： 0 4 8 120 21 3/4*4第二層下標(biāo)分組為：第二層下標(biāo)分組為： 0， 8； 4，12；移位：移位：0000，0101，1010，1111偶數(shù)組：偶數(shù)組：0000，1010奇數(shù)組：奇

11、數(shù)組：0101，11113. 根據(jù)每層偶數(shù)組的排序方式，獲得奇數(shù)組的排序方式。根據(jù)每層偶數(shù)組的排序方式，獲得奇數(shù)組的排序方式。因?yàn)榕紨?shù)項(xiàng)的系數(shù)為因?yàn)榕紨?shù)項(xiàng)的系數(shù)為f(2x)f(2x)，奇數(shù)項(xiàng)的系數(shù)為，奇數(shù)項(xiàng)的系數(shù)為f(2x+1)f(2x+1)所以由第二層偶數(shù)排序：所以由第二層偶數(shù)排序： 0， 8， 4，12；可以得到第一層偶數(shù)排序?yàn)椋嚎梢缘玫降谝粚优紨?shù)排序?yàn)椋?，8，4，12，2，10，6，14；再根據(jù)第一層的偶數(shù)排序，獲得原始數(shù)據(jù)的排序?yàn)椋涸俑鶕?jù)第一層的偶數(shù)排序，獲得原始數(shù)據(jù)的排序?yàn)椋?，8，4，12，2，10，6，14，1，9，5，13，3，11，7，1519513311715,f fff

12、fffffffffff4. 進(jìn)行分層的奇、偶項(xiàng)相加。進(jìn)行分層的奇、偶項(xiàng)相加。對(duì)第二層偶數(shù)排序：對(duì)第二層偶數(shù)排序： 0， 8， 4，12；對(duì)上面的結(jié)果再進(jìn)行相加運(yùn)算：對(duì)上面的結(jié)果再進(jìn)行相加運(yùn)算：8020)2()0(fwfFe8020)2() 1 (fwfFe12024)2() 1 (fwfFo12024)2()0(fwfFo)0()0()0()2(04)2()(oeeFwFF) 1 () 1 () 1 ()2(14)2()(oeeFwFF)0()0()2()2(04)2()(oeeFwFF) 1 () 1 () 3()2(14)2()(oeeFwFF10.2.4 FFT

13、10.2.4 FFT算法圖示算法圖示0f8f(0)(3)0(1)(3)1FF(0)(2)(0)(2)01(0)(2)(0)(2)23,FFFF(0)(1)(0)(1)(0)(1)(0)(1)0123(0)(1)(0)(1)(0)(1)(0)(1)4567,FFFFFFFF(4)(3)0(4)(3)1FF4f12f(2)(3)0(2)(3)1FF2f6f10f14f(6)(3)0(6)(3)1FF1f9f(1)(3)0(1)(3)1FF5f13f(5)(3)0(5)(3)1FF3f7f(3)(3)0(3)(3)1FF11f15f(7)(3)0(7)(3)1FF(2)(2)(2)(2)01(2)(

14、2)(2)(2)23,FFFF(1)(2)(1)(2)01(1)(2)(1)(2)23,FFFF(3)(2)(3)(2)01(3)(2)(3)(2)23,FFFF(1)(1)(1)(1)(1)(1)(1)(1)0123(1)(1)(1)(1)(1)(1)(1)(1)4567,FFFFFFFF01234567,F F F F F F F F89101112131415(,)F F FFFFFF10.2.5 FFT10.2.5 FFT計(jì)算例計(jì)算例 設(shè)對(duì)一個(gè)函數(shù)進(jìn)行快速設(shè)對(duì)一個(gè)函數(shù)進(jìn)行快速FourierFourier變換，函數(shù)在變換，函數(shù)在采樣點(diǎn)上的值設(shè)為：采樣點(diǎn)上的值設(shè)為：76543210,fff

15、fffff偶數(shù)項(xiàng)部分：偶數(shù)項(xiàng)部分：76543210,ffffffff0246,ffff下標(biāo)值分別為：下標(biāo)值分別為：000000，010010，100100，110110排序?yàn)椋号判驗(yàn)椋?000, 100,000, 100, 010, 110010, 110奇數(shù)項(xiàng)部分：奇數(shù)項(xiàng)部分：1357,f fff下標(biāo)值分別為：下標(biāo)值分別為：001001，011011，101101，111111排序?yàn)椋号判驗(yàn)椋?001, 101,001, 101, 011, 111011, 111分成偶數(shù)、奇數(shù)為（偶數(shù)在左，奇數(shù)在右）：分成偶數(shù)、奇數(shù)為（偶數(shù)在左，奇數(shù)在右）：6420,ffff7531,ffff40, ff6

16、2, ff51, ff73, ff0f4f2f6f1f5f3f7f(0)(1)0(0)(1)1FF(2)(1)0(2)(1)1FF(1)(1)0(1)(1)1FF(3)(1)0(3)(1)1FF(0)(2)(0)(2)01(0)(2)(0)(2)23,FFFF(1)(2)(1)(2)01(1)(2)(1)(2)23,FFFF),( ,76543210FFFFFFFF按照前面敘述的按照前面敘述的FFTFFT方法方法, ,第第1 1層層(4(4組組2 2個(gè)點(diǎn)的運(yùn)算個(gè)點(diǎn)的運(yùn)算) )：(0)(1)0002404Ffw fff(0)(1)0102404Ffw fff同理：同理：(2)(1)026Fff(

17、2)(1)126Fff(1)(1)015Fff(1)(1)115Fff(3)(1)037Fff(3)(1)137Fff第第2 2層（層（2 2組組4 4個(gè)點(diǎn)的運(yùn)算）：個(gè)點(diǎn)的運(yùn)算）：(0)(2)(0)(0(2)(1)00400426FFw Fffff1)(0)(2)(0)(1)1(2)(1)1114104426()FFw Fffwff同理：同理：(0)(2)(0)(1)0(2)(1)22420426FFw Fffff(0)(2)(0)(1)1(2)(1)1314104426()FFw Fffwff(1)(2)(1)(1)0(3)(1)00401537FFw Fffff(1)(2)(1)(1)0(

18、3)(1)20401537FFw Fffff(1)(2)(1)(1)1(3)(1)1114115437()FFw Fffwff(1)(2)(1)(1)1(3)(1)1314115437()FFw Fffwff第第3 3層（層（1 1組組8 8個(gè)點(diǎn)的運(yùn)算）：個(gè)點(diǎn)的運(yùn)算）：(0)(2)0(1)(2)008004261357FFw Fffffffff(0)(2)1(1)(2)111118104426815437()()FFw Fffwffwffwff(0)(2)2(1)(2)22282042681537)FFw Fffffw ffff（）（(0)(2)3(1)(2)13133830442681543

19、7()FFw Fffwffwffwff）(0)(2)0(1)(2)408004261357FFw Fffffffff(0)(2)1(1)(2)111518104426815437()()FFw Fffwffwffwff(0)(2)2(1)(2)26282042681537)FFw Fffffwffff（）（(0)(2)3(1)(2)131738304426815437()FFw Fffwffwffwff）對(duì)函數(shù)：對(duì)函數(shù)：76543210,ffffffff按照定義，可得其按照定義，可得其FourierFourier變換為：變換為：708)()(xxwxfF下面，我們以下面，我們以F F3 3為例

20、驗(yàn)證結(jié)果是否正確：為例驗(yàn)證結(jié)果是否正確：(0)(2)3(1)(2)131338304426815437()FFw Fffwffwffwff）75835853813862822840fwfwfwfwfwfwff75816835848538488831816281682284888484080fwwfwwfwwwwffwwfwwwwfwf0 3132 33 34 35 36 37 30818283848586878f wf wf wf wf wf wf wf w73380(3)( )xxFFf x w0 3132 33 34 35 36 37 30818283848586878f wf wf wf

21、 wf wf wf wf w10.3 10.3 二維二維FourierFourier變換的應(yīng)用變換的應(yīng)用 前面已經(jīng)提到了前面已經(jīng)提到了FourierFourier變換有兩個(gè)好處，變換有兩個(gè)好處，即：可以獲得信號(hào)的頻域特性；可以將卷即：可以獲得信號(hào)的頻域特性；可以將卷積運(yùn)算轉(zhuǎn)換為乘積運(yùn)算。積運(yùn)算轉(zhuǎn)換為乘積運(yùn)算。 因此二維因此二維FourierFourier變換的應(yīng)用也是根據(jù)這變換的應(yīng)用也是根據(jù)這兩個(gè)特點(diǎn)來(lái)進(jìn)行的。兩個(gè)特點(diǎn)來(lái)進(jìn)行的。10.3.1 10.3.1 在圖像濾波中的應(yīng)用在圖像濾波中的應(yīng)用 首先，我們來(lái)看首先，我們來(lái)看FourierFourier變換變換后的圖像，后的圖像，中間部分為低頻部分

22、，越靠外邊頻率越高。中間部分為低頻部分，越靠外邊頻率越高。 因此，我們可以在因此，我們可以在FourierFourier變換圖中，選變換圖中，選擇所需要的擇所需要的高頻高頻或是或是低頻低頻濾波。濾波。10.3.2 10.3.2 在圖像壓縮中的應(yīng)用在圖像壓縮中的應(yīng)用 變換系數(shù)剛好表現(xiàn)的是各個(gè)頻率點(diǎn)上的幅變換系數(shù)剛好表現(xiàn)的是各個(gè)頻率點(diǎn)上的幅值。在小波變換沒(méi)有提出時(shí)，用來(lái)進(jìn)行壓值。在小波變換沒(méi)有提出時(shí)，用來(lái)進(jìn)行壓縮編碼?？s編碼。 考慮到高頻反映細(xì)節(jié)、低頻反映景物概貌考慮到高頻反映細(xì)節(jié)、低頻反映景物概貌的特性。往往認(rèn)為可將高頻系數(shù)置為的特性。往往認(rèn)為可將高頻系數(shù)置為0 0，騙騙過(guò)人眼過(guò)人眼。10.3.

23、3 10.3.3 在卷積運(yùn)算中的應(yīng)用在卷積運(yùn)算中的應(yīng)用 從前面的圖像處理算法中知道，如果抽象從前面的圖像處理算法中知道，如果抽象來(lái)看，其實(shí)都可以認(rèn)為是圖像信息經(jīng)過(guò)了來(lái)看，其實(shí)都可以認(rèn)為是圖像信息經(jīng)過(guò)了濾波器的濾波（如：平滑濾波、銳化濾波濾波器的濾波（如：平滑濾波、銳化濾波等等 ）。）。 如果濾波器的結(jié)構(gòu)比較復(fù)雜時(shí)，直接進(jìn)行如果濾波器的結(jié)構(gòu)比較復(fù)雜時(shí)，直接進(jìn)行時(shí)域中的卷積運(yùn)算是不可思議的。時(shí)域中的卷積運(yùn)算是不可思議的。 FourierFourier變換可以卷積運(yùn)算轉(zhuǎn)換為點(diǎn)乘運(yùn)算，變換可以卷積運(yùn)算轉(zhuǎn)換為點(diǎn)乘運(yùn)算，由此簡(jiǎn)化運(yùn)算，提高計(jì)算速度。由此簡(jiǎn)化運(yùn)算，提高計(jì)算速度。 )(SG) j , i (

24、f) j , i (fgfgfg ),(F),(G),(Fg )F(FFTfg1g 10.3.4 10.3.4 在圖像分割中的應(yīng)用在圖像分割中的應(yīng)用相當(dāng)于濾波,選擇不同的頻率段 ),v,u(F0)v,u(F其它其它或或)0 , 0()v,u(rvu2max22 2/N2/Nu2/N2/NvN)vyux(2jexp)v,u(FN1)y, x( f原圖功率譜3D顯示地毯地毯表面皮革表面磨損缺陷皮革表面磨損缺陷原圖功率譜重構(gòu)圖像分割結(jié)果利用頻域?yàn)V波消除圖像規(guī)律性干擾規(guī)則的圖案往往是周期性的，即這種圖案有固定的頻率。經(jīng)過(guò)傅立葉變換轉(zhuǎn)換到頻率域后，原來(lái)在空間域遍布整個(gè)畫(huà)面的干擾圖案就轉(zhuǎn)換成頻率域上少數(shù)的離散點(diǎn)。利用合適的濾波器很容易將這些離散的點(diǎn)去掉，再經(jīng)過(guò)反變換重新回到空間域，就會(huì)發(fā)現(xiàn)原來(lái)的干擾沒(méi)有了。很多軟件都提供了交互式頻域?yàn)V波處理工具專門處理此類問(wèn)題，比如Image Pro Plus，Poliview，名捕，恒銳等。 利用Photoshop處理則必須安裝第三方提供的專用插件。利用頻域?yàn)V波消除圖像規(guī)律性干擾10.4 10.4 離散余弦變換（離散余