第8章圖像變換快速傅立葉變換.

1、1 圖像的頻域變換圖像的頻域變換 2 把圖像信號(hào)從空域變換到頻域，從頻域來(lái)分析圖把圖像信號(hào)從空域變換到頻域，從頻域來(lái)分析圖 像信號(hào)的特性。像信號(hào)的特性。 數(shù)字圖像的頻域處理主要應(yīng)用：數(shù)字圖像的頻域處理主要應(yīng)用： 利用某些頻域變換可從圖像中提取圖像的特征；利用某些頻域變換可從圖像中提取圖像的特征； 利用圖像頻域處理可實(shí)現(xiàn)圖像高效壓縮編碼；利用圖像頻域處理可實(shí)現(xiàn)圖像高效壓縮編碼； 減小計(jì)算維數(shù)，使算術(shù)運(yùn)算次數(shù)大大減少，從減小計(jì)算維數(shù)，使算術(shù)運(yùn)算次數(shù)大大減少，從 而提高圖像處理的速度。而提高圖像處理的速度。 頻域變換的理論基礎(chǔ)是頻域變換的理論基礎(chǔ)是“任何波形都可以用單純?nèi)魏尾ㄐ味伎梢杂脝渭?的正弦波

2、的和來(lái)表示的正弦波的和來(lái)表示”。 3 4 一維一維DFTDFT和和IDFTIDFT 1 0 2 1 0 2 1 N u u N x j N x x N u j e )u(F N xf exfuF N j N eWLet 2 u=0,1,2,N-1 x=0,1,2,N-1 1 0 1 0 1 N u ux N N x ux N W)u(F N Wxf 5 二維二維DFTDFT和和IDFTIDFT 1210 1210 1 1 0 1 0 2 1 0 1 0 2 N,., ,y, v M,., ,x ,u e )v ,u(F MN )y, x(f e )y, x(f)v ,u(F M u N n )

3、 N vy M ux (j N x N y ) N vy M ux (j 6 二維離散傅立葉變換的性質(zhì)二維離散傅立葉變換的性質(zhì) 7 8 二維傅立葉變換特性二維傅立葉變換特性:可分離性可分離性 二維二維DFT可分離為兩次一維可分離為兩次一維DFT f(x,y)F(x,v)F(u,v) 按列進(jìn)行按列進(jìn)行 一維一維DFT 按行進(jìn)行按行進(jìn)行 一維一維DFT 9 可分離性可分離性 先對(duì)行做變換：先對(duì)行做變換： 然后對(duì)列進(jìn)行變換然后對(duì)列進(jìn)行變換： f(x,y) （0,0） （N-1，M-1） x y F(x,v) （0,0） （N-1，M-1） x v F(x,v) （0,0） （N-1，M-1） x v

4、 F(u,v) （0,0） （N-1，M-1） u v 10 )y, x( fFF ee )y, x( f )y, x( fFF ee )y, x( f e )y, x( f)v ,u(F xy N vy j N y N x M ux j yx M ux j N x N y N vy j N x N y ) N vy M ux (j 2 1 0 1 0 2 2 1 0 1 0 2 1 0 1 0 2 可分離性可分離性 先行后列先行后列 先列后行先列后行 11 二維傅立葉變換特性二維傅立葉變換特性:平移性平移性 ) N v , M u(F)(y, x(f N vand M uif )vv ,uu

5、(Fe )y, x(f e )v ,u(F)yy,xx(f )v ,u(F)y, x(f yx ) N yv M xu (j ) N yv M xu (j 22 1 22 00 00 2 2 00 00 00 將圖像的頻譜原點(diǎn)將圖像的頻譜原點(diǎn)(0,0)移動(dòng)到圖像中心（移動(dòng)到圖像中心（M/2,N/2)處處 12 二維傅立葉變換特性二維傅立葉變換特性:平移性平移性 原圖原圖 無(wú)平移的傅立葉頻譜無(wú)平移的傅立葉頻譜 平移后的傅立葉頻譜平移后的傅立葉頻譜 13 二維傅立葉變換特性二維傅立葉變換特性:旋轉(zhuǎn)不變性旋轉(zhuǎn)不變性 在時(shí)域中離散函數(shù)旋轉(zhuǎn)在時(shí)域中離散函數(shù)旋轉(zhuǎn) 0角度，則在變換域內(nèi)角度，則在變換域內(nèi) 離

6、散傅立葉函數(shù)也將旋轉(zhuǎn)同樣的角度。離散傅立葉函數(shù)也將旋轉(zhuǎn)同樣的角度。 ),(F), r(f ),(F), r(f 00 14 二維傅立葉變換特性二維傅立葉變換特性:旋轉(zhuǎn)不變性旋轉(zhuǎn)不變性 15 快速傅立葉變換快速傅立葉變換(FFT) Fast Fourier Transforming 16 有限長(zhǎng)序列通過(guò)離散傅立葉變換有限長(zhǎng)序列通過(guò)離散傅立葉變換(DFT)將其頻域離散將其頻域離散 化成有限長(zhǎng)序列化成有限長(zhǎng)序列.但其計(jì)算量太大但其計(jì)算量太大(與與N2成正比）成正比）,很難很難 實(shí)時(shí)地處理問(wèn)題實(shí)時(shí)地處理問(wèn)題,因此引出了快速傅立葉變換因此引出了快速傅立葉變換(FFT). FFT并不是一種新的變換形式并不

7、是一種新的變換形式,它只是它只是DFT的一種快速的一種快速 算法算法.并且根據(jù)對(duì)序列分解與選取方法的不同而產(chǎn)生并且根據(jù)對(duì)序列分解與選取方法的不同而產(chǎn)生 了了FFT的多種算法的多種算法. FFT在離散傅立葉反變換、線性卷積和線性相關(guān)等方在離散傅立葉反變換、線性卷積和線性相關(guān)等方 面也有重要應(yīng)用面也有重要應(yīng)用. 17 FFT產(chǎn)生故事產(chǎn)生故事 當(dāng)時(shí)當(dāng)時(shí)Garwin在自已的研究中極需要一個(gè)計(jì)算傅立在自已的研究中極需要一個(gè)計(jì)算傅立 葉變換的快速方法。他注意到葉變換的快速方法。他注意到Turkey正在寫有關(guān)傅立正在寫有關(guān)傅立 葉變換的文章，因此詳細(xì)詢問(wèn)了葉變換的文章，因此詳細(xì)詢問(wèn)了Turkey關(guān)于計(jì)算傅立

8、關(guān)于計(jì)算傅立 葉變換的技術(shù)知識(shí)。葉變換的技術(shù)知識(shí)。 Turkey概括地對(duì)概括地對(duì)Garwin介紹了一介紹了一 種方法，它實(shí)質(zhì)上就是后來(lái)的著名的種方法，它實(shí)質(zhì)上就是后來(lái)的著名的Cooley -Turkey 算法。在算法。在Garwin的迫切要求下，的迫切要求下， Cooley很快設(shè)計(jì)出一很快設(shè)計(jì)出一 個(gè)計(jì)算機(jī)程序。個(gè)計(jì)算機(jī)程序。1965年年Cooley -Turkey在在 Mathematic of Computation上發(fā)表了著名的上發(fā)表了著名的“機(jī)器計(jì)機(jī)器計(jì) 算傅立級(jí)數(shù)的一種算法算傅立級(jí)數(shù)的一種算法” ，提出一種快速計(jì)算，提出一種快速計(jì)算DFT的方的方 法和計(jì)算機(jī)程序法和計(jì)算機(jī)程序-揭開(kāi)了

9、揭開(kāi)了FFT發(fā)展史上的第一頁(yè)，促使發(fā)展史上的第一頁(yè)，促使 FFT算法產(chǎn)生原因還有算法產(chǎn)生原因還有1967年至年至1968年間年間FFT的數(shù)字的數(shù)字 硬件制成，電子數(shù)字計(jì)算機(jī)的條件，使硬件制成，電子數(shù)字計(jì)算機(jī)的條件，使DFT的運(yùn)算大大的運(yùn)算大大 簡(jiǎn)化了。簡(jiǎn)化了。 18 1 1 0 1 1 0 111110 111110 010100 Nf f f WWW WWW WWW NF F F N)N()N()N( N N N/j N x ux N x x N u j eW WxfexfuF 2 1 0 1 0 2 旋轉(zhuǎn)因子 矩陣形式的一維矩陣形式的一維DFT: W系數(shù)矩陣系數(shù)矩陣 FFT的推導(dǎo)的推導(dǎo) 1

10、9 xu N xu N xu N N j N xuNxu N N j N WWWW eW WW eW 22 2 2 2 2 1 1 系數(shù)系數(shù)W是以是以N為周期的，所以為周期的，所以W陣中很多系數(shù)是相同的，陣中很多系數(shù)是相同的， 不必進(jìn)行多次重復(fù)計(jì)算，又由于不必進(jìn)行多次重復(fù)計(jì)算，又由于W的對(duì)稱性，可以進(jìn)一步的對(duì)稱性，可以進(jìn)一步 減少計(jì)算工作量。減少計(jì)算工作量。 FFT的推導(dǎo)的推導(dǎo) W4= W6= W9= W3= W2= W0 W2 W1 -W1 - W0 假設(shè)假設(shè)N4，u,x=0,1,2,3 20 W陣的變換如下：陣的變換如下： FFT的推導(dǎo)的推導(dǎo) 1010 0000 1010 0000 WWW

11、W WWWW WWWW WWWW 9630 6420 3210 0000 WWWW WWWW WWWW WWWW 21 FFT的基本思想的基本思想 把一個(gè)把一個(gè)N點(diǎn)的點(diǎn)的DFT分解成兩個(gè)分解成兩個(gè)N/2短序列的短序列的DFT，即，即 分解成偶數(shù)和奇數(shù)序列的分解成偶數(shù)和奇數(shù)序列的DFT Fe(u)和和Fo(u)，并充，并充 分利用旋轉(zhuǎn)因子分利用旋轉(zhuǎn)因子W的周期性和對(duì)稱性來(lái)計(jì)算的周期性和對(duì)稱性來(lái)計(jì)算DFT， 簡(jiǎn)化運(yùn)算過(guò)程。簡(jiǎn)化運(yùn)算過(guò)程。 1 0 1 0 1 2 0 12 1 2 0 2 122 122 2 M x ux M u N M x ux M N x )x(u N N x )x(u N Wx

12、fWWxf WxfW)x(fuF MN ux M u N N xu j N u j N ux j )x(u N j )x(u N ux M M ux i N ux j )x(u N j WWeee)e(W Wee)e( 2 22 2 2 12 2 12 2 2 2 2 2 u(2x) N W 22 )WW,WW( uFWuF)Mu(F uFWuFuF WxfuF WxfuF u M Mu M u M Mu M o u Me o u Me M x ux Mo M x ux Me 22 2 2 1 0 1 0 12 2 對(duì)前對(duì)前M個(gè)個(gè)DFT 對(duì)后對(duì)后M個(gè)個(gè)DFT FFT的推導(dǎo)的推導(dǎo) 23 u M

13、xju M M xM j M u j Mu M j Mu M WeWeeeW 22 2 2 2 2 2 2 2 )( u M xju M M xM j M u j Mu M j Mu M WeWeeeW 2 22 2 )( W5= - w1 N=8, M=4, W=W8，u=0,1,27 W7= - w3 FFT的推導(dǎo)的推導(dǎo) 24 F(1) F(5) Fe(1) Fo(5) W1 W1 )(FW)(F)(F )(FW)(FF oe oe 515 511 1 1 蝶形運(yùn)算單元蝶形運(yùn)算單元 FFT的蝶形算法的蝶形算法 計(jì)算量計(jì)算量? ? 25 f(2) f(1) f(5) f(3) f(7) f(

14、0) f(4) f(6) F(0) F(1) F(2) F(3) F(4) F(5) F(6) F(7) W0 W4 W4 W4 W4 W0 W0 W0 F1(0) F1(1) F1(2) F1(3) F1(4) F1(5) F1(6) F1(7) F2(0) F2(1) F2(2) F2(3) F2(4) F2(5) F2(6) F2(7) W0 W2 W4 W6 W0 W2 W4 W6 W0 W1 W2 W3 W4 W5 W6 W7 8點(diǎn)的點(diǎn)的FFT的完整蝶形計(jì)算圖和逐級(jí)分解圖。的完整蝶形計(jì)算圖和逐級(jí)分解圖。 37261504 WW,WW,WW,WW 奇奇 偶偶 分分 組，組， 輸輸 入入

15、 倒倒 序序 第一級(jí)第一級(jí)第二級(jí)第二級(jí)第三級(jí)第三級(jí) 輸輸 出出 順順 序序 FFT的蝶形算法的蝶形算法 26 )()()()( )()()()( )()()()( )()()()( )()()()( )()( 7531 6240 7351 8240 6420 400 0000 000 1 0 1 0 1 0 1 2 0 2 ffff ffff fWfWfWfW FWfWfWf FWFWFWF FWFF FFT的蝶形算法的蝶形算法 27 )()()()( )()()()( )()()()( )()()()( )()()()( )()()()( )()()()( )()( 7531 6240 75

16、31 6240 7351 6240 6420 404 4 0004 000 1 0 1 4 1 0 1 2 4 2 ffff ffff ffffW ffff fWfWfWfW fWfWfWf FWFWFWF FWFF FFT的蝶形算法的蝶形算法 28 輸入碼位倒置，輸出順序輸入碼位倒置，輸出順序 自然順序自然順序二進(jìn)制表示二進(jìn)制表示碼位倒置碼位倒置碼位倒置順序碼位倒置順序 00000000 10011004 20100102 30111106 41000011 51011013 61100115 71111117 29 時(shí)間抽取時(shí)間抽取FFTFFT（將（將f(x)f(x)序列按序列按x x的奇

17、偶進(jìn)行分組計(jì)算）的奇偶進(jìn)行分組計(jì)算） 對(duì)對(duì) 點(diǎn)的信號(hào)，需次遞推，每次遞推有 點(diǎn)的信號(hào)，需次遞推，每次遞推有 個(gè)蝶形，共有個(gè)蝶形，共有( (2)M2)M( (2 2）loglog2 2個(gè)蝶個(gè)蝶 形，每個(gè)蝶形包括次乘法和兩次加法。總計(jì)算量形，每個(gè)蝶形包括次乘法和兩次加法。總計(jì)算量 (1/2)Nlog(1/2)Nlog2 2N N次次乘法和乘法和NlogNlog2 2N N次次加法。加法。 對(duì)點(diǎn)對(duì)點(diǎn)DFTDFT總計(jì)算量為：總計(jì)算量為： 次乘法和 次乘法和N(N-1)N(N-1)次加法。次加法。 算法復(fù)雜性算法復(fù)雜性 30 FFT與DFT的比較 NN (DFT) log2N (FFT) N/(log2

18、N) 2422.0 864242.7 1024104857610240102.4 40961677721649152341.3 31 FourierFourier變換變換 高頻反映細(xì)節(jié)、低頻反映景物概貌的特性高頻反映細(xì)節(jié)、低頻反映景物概貌的特性 高頻濾波高頻濾波 低頻濾波低頻濾波 圖像壓縮圖像壓縮，將高頻系數(shù)置為將高頻系數(shù)置為0 0 將卷積運(yùn)算轉(zhuǎn)換為點(diǎn)乘運(yùn)算，由此簡(jiǎn)化運(yùn)算，提高將卷積運(yùn)算轉(zhuǎn)換為點(diǎn)乘運(yùn)算，由此簡(jiǎn)化運(yùn)算，提高 計(jì)算速度。計(jì)算速度。 二維二維FourierFourier變換的應(yīng)用變換的應(yīng)用 32 )(SG ),(jif ),(jif g fgf g ),(),(),(FGFg )(

19、1 gg FFFTf 33 離散余弦變換離散余弦變換 DCT 34 FourierFourier變換的一個(gè)最大的問(wèn)題是：它的參變換的一個(gè)最大的問(wèn)題是：它的參 數(shù)都是復(fù)數(shù)，在數(shù)據(jù)的描述上相當(dāng)于實(shí)數(shù)的數(shù)都是復(fù)數(shù)，在數(shù)據(jù)的描述上相當(dāng)于實(shí)數(shù)的 兩倍。兩倍。 為此，我們希望有一種能夠達(dá)到相同功能但為此，我們希望有一種能夠達(dá)到相同功能但 數(shù)據(jù)量又不大的變換。在此期望下，產(chǎn)生了數(shù)據(jù)量又不大的變換。在此期望下，產(chǎn)生了 DCTDCT變換。變換。 問(wèn)題的提出問(wèn)題的提出 35 離散余弦變換（離散余弦變換（Discrete Cosine TransformDiscrete Cosine Transform）的）的 變

20、換核為余弦函數(shù)。變換核為余弦函數(shù)。DCTDCT除了具有一般的正交變換除了具有一般的正交變換 性質(zhì)外，性質(zhì)外， 它的變換陣的基向量能很好地描述人類它的變換陣的基向量能很好地描述人類 語(yǔ)音信號(hào)和圖像信號(hào)的相關(guān)特征。因此，在對(duì)語(yǔ)音語(yǔ)音信號(hào)和圖像信號(hào)的相關(guān)特征。因此，在對(duì)語(yǔ)音 信號(hào)、圖像信號(hào)的變換中，信號(hào)、圖像信號(hào)的變換中，DCTDCT變換被認(rèn)為是一種變換被認(rèn)為是一種 準(zhǔn)最佳變換。近年頒布的一系列視頻壓縮編碼的國(guó)準(zhǔn)最佳變換。近年頒布的一系列視頻壓縮編碼的國(guó) 際標(biāo)準(zhǔn)建議中，都把際標(biāo)準(zhǔn)建議中，都把DCTDCT作為其中的一個(gè)基本處理作為其中的一個(gè)基本處理 模塊。除此之外，模塊。除此之外， DCTDCT還是一

21、種可分離的變換。還是一種可分離的變換。 36 把一幅圖像劃分成一系列的圖像塊，每個(gè)圖像塊把一幅圖像劃分成一系列的圖像塊，每個(gè)圖像塊 包含包含88個(gè)像素。如果原始圖像有個(gè)像素。如果原始圖像有640480個(gè)個(gè) 像素，則圖片將包含像素，則圖片將包含80列列60行的方塊。如果圖像行的方塊。如果圖像 只包含灰度，那么每個(gè)像素用一個(gè)只包含灰度，那么每個(gè)像素用一個(gè)8比特的數(shù)字比特的數(shù)字 表示。因此可以把每個(gè)圖像塊表示成一個(gè)表示。因此可以把每個(gè)圖像塊表示成一個(gè)8行行8列列 的二維數(shù)組。數(shù)組的元素是的二維數(shù)組。數(shù)組的元素是0255的的8比特整數(shù)。比特整數(shù)。 離散余弦變換就是作用在這個(gè)數(shù)組上。離散余弦變換就是作用

22、在這個(gè)數(shù)組上。 37 如果圖像是彩色的，那么每個(gè)像素可以用如果圖像是彩色的，那么每個(gè)像素可以用24比特、比特、 相當(dāng)于三個(gè)相當(dāng)于三個(gè)8位比特的組合來(lái)表示（用位比特的組合來(lái)表示（用RGB或或YIQ 表示，在這里沒(méi)有影響）。因此，可以用三個(gè)表示，在這里沒(méi)有影響）。因此，可以用三個(gè)8行行8 列的二維數(shù)組表示這個(gè)列的二維數(shù)組表示這個(gè)88的像素方塊。每一個(gè)數(shù)的像素方塊。每一個(gè)數(shù) 組表示其中一個(gè)八位比特組合的像素值。離散余弦組表示其中一個(gè)八位比特組合的像素值。離散余弦 變換作用于每個(gè)數(shù)組。變換作用于每個(gè)數(shù)組。 38 簡(jiǎn)單的說(shuō)，是用一個(gè)簡(jiǎn)單的說(shuō)，是用一個(gè)8行行8列的二維數(shù)組產(chǎn)生另一個(gè)同樣列的二維數(shù)組產(chǎn)生另一

23、個(gè)同樣 包含包含8行行8列二維數(shù)組的函數(shù)，也就是說(shuō)，把一個(gè)數(shù)組通列二維數(shù)組的函數(shù)，也就是說(shuō)，把一個(gè)數(shù)組通 過(guò)一個(gè)變換，變成另一個(gè)數(shù)組。過(guò)一個(gè)變換，變成另一個(gè)數(shù)組。 如圖下圖所示，對(duì)每個(gè)圖像塊做離散余弦變換。通過(guò)如圖下圖所示，對(duì)每個(gè)圖像塊做離散余弦變換。通過(guò) DCTDCT變換可以把能量集中在矩陣左上角少數(shù)幾個(gè)系數(shù)上。變換可以把能量集中在矩陣左上角少數(shù)幾個(gè)系數(shù)上。 wf(i,j)經(jīng)DCT變換之后得到F(u,v)，其中F(0,0)是直流系數(shù)， 稱為DC系數(shù)，其他為交流系數(shù)，稱為AC系數(shù)。 39 離散余弦變換的數(shù)組離散余弦變換的數(shù)組 wf(i,j)經(jīng)DCT變換之后得到F(u,v)，其中F(0,0)是直流系數(shù)， 稱為DC系數(shù)，其他為交流系數(shù)，稱為AC系數(shù)。 40 離散余弦變換（離散余弦變換（DCTDCT） 逆變換： 1 0 1 0 22 2 1212 M x