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

1、1 圖像的頻域變換圖像的頻域變換 2 把圖像信號從空域變換到頻域，從頻域來分析圖把圖像信號從空域變換到頻域，從頻域來分析圖 像信號的特性。像信號的特性。 數(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、的和來表示的正弦波的和來表示”。 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 可分離性可分離性 先對行做變換：先對行做變換： 然后對列進(jìn)行變換然后對列進(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)移動到圖像中心（移動到圖像中心（M/2,N/2)處處 12 二維傅立葉變換特性二維傅立葉變換特性:平移性平移性 原圖原圖 無平移的傅立葉頻譜無平移的傅立葉頻譜 平移后的傅立葉頻譜平移后的傅立葉頻譜 13 二維傅立葉變換特性二維傅立葉變換特性:旋轉(zhuǎn)不變性旋轉(zhuǎn)不變性 在時域中離散函數(shù)旋轉(zhuǎn)在時域中離散函數(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 有限長序列通過離散傅立葉變換有限長序列通過離散傅立葉變換(DFT)將其頻域離散將其頻域離散 化成有限長序列化成有限長序列.但其計(jì)算量太大但其計(jì)算量太大(與與N2成正比）成正比）,很難很難 實(shí)時地處理問題實(shí)時地處理問題,因此引出了快速傅立葉變換因此引出了快速傅立葉變換(FFT). FFT并不是一種新的變換形式并不

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

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

9、揭開了FFT發(fā)展史上的第一頁，促使發(fā)展史上的第一頁，促使 FFT算法產(chǎn)生原因還有算法產(chǎn)生原因還有1967年至年至1968年間年間FFT的數(shù)字的數(shù)字 硬件制成，電子數(shù)字計(jì)算機(jī)的條件，使硬件制成，電子數(shù)字計(jì)算機(jī)的條件，使DFT的運(yùn)算大大的運(yù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的對稱性，可以進(jìn)一步的對稱性，可以進(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的基本思想的基本思想 把一個把一個N點(diǎn)的點(diǎn)的DFT分解成兩個分解成兩個N/2短序列的短序列的DFT，即，即 分解成偶數(shù)和奇數(shù)序列的分解成偶數(shù)和奇數(shù)序列的DFT Fe(u)和和Fo(u)，并充，并充 分利用旋轉(zhuǎn)因子分利用旋轉(zhuǎn)因子W的周期性和對稱性來計(jì)算的周期性和對稱性來計(jì)算DFT， 簡化運(yùn)算過程。簡化運(yùn)算過程。 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 對前對前M個個DFT 對后對后M個個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ì)算圖和逐級分解圖。 37261504 WW,WW,WW,WW 奇奇 偶偶 分分 組，組， 輸輸 入入

15、 倒倒 序序 第一級第一級第二級第二級第三級第三級 輸輸 出出 順順 序序 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 時間抽取時間抽取FFTFFT（將（將f(x)f(x)序列按序列按x x的奇

17、偶進(jìn)行分組計(jì)算）的奇偶進(jìn)行分組計(jì)算） 對對 點(diǎn)的信號，需次遞推，每次遞推有 點(diǎn)的信號，需次遞推，每次遞推有 個蝶形，共有個蝶形，共有( (2)M2)M( (2 2）loglog2 2個蝶個蝶 形，每個蝶形包括次乘法和兩次加法?？傆?jì)算量形，每個蝶形包括次乘法和兩次加法。總計(jì)算量 (1/2)Nlog(1/2)Nlog2 2N N次次乘法和乘法和NlogNlog2 2N N次次加法。加法。 對點(diǎn)對點(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)算，由此簡化運(yùn)算，提高將卷積運(yùn)算轉(zhuǎn)換為點(diǎn)乘運(yù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變換的一個最大的問題是：它的參變換的一個最大的問題是：它的參 數(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變換。變換。 問題的提出問題的提出 35 離散余弦變換（離散余弦變換（Discrete Cosine TransformDiscrete Cosine Transform）的）的 變

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

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

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

23、個同樣 包含包含8行行8列二維數(shù)組的函數(shù)，也就是說，把一個數(shù)組通列二維數(shù)組的函數(shù)，也就是說，把一個數(shù)組通 過一個變換，變成另一個數(shù)組。過一個變換，變成另一個數(shù)組。 如圖下圖所示，對每個圖像塊做離散余弦變換。通過如圖下圖所示，對每個圖像塊做離散余弦變換。通過 DCTDCT變換可以把能量集中在矩陣左上角少數(shù)幾個系數(shù)上。變換可以把能量集中在矩陣左上角少數(shù)幾個系數(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