第五章-圖像變換

1、第5章 圖像變換o數(shù)字圖像處理方法主要分為兩大類：一類方法是在空間域直接對圖像進(jìn)行處理，稱為空域法；o另一類是變換到變換域?qū)D像進(jìn)行處理，稱為變換域處理法。在變換域處理法中，頻域變換法是運(yùn)用最為廣泛的一種方法。o數(shù)字圖像處理既有廣泛的技術(shù)基礎(chǔ)，也有嚴(yán)密的數(shù)學(xué)理論基礎(chǔ)。數(shù)學(xué)作為圖像變換的工具，發(fā)揮了重要作用。o在數(shù)字圖像處理與分析中，圖像增強(qiáng)、圖像復(fù)原、圖像壓縮編碼、圖像分析等每一種處理手段和方法都要應(yīng)用圖像變換方法。第五章 圖像變換第5章 圖像變換本章內(nèi)容：n圖像變換的作用n傅立葉變換n離散傅立葉變換n傅立葉變換的性質(zhì)n二維傅立葉變換n離散K-L變換n離散余弦變換第5章 圖像變換 一. 圖像變

2、換的作用 圖像變換的定義是將圖像從空域變換到其它域（如頻域）的數(shù)學(xué)變換 圖像變換的作用 我們?nèi)祟愐曈X所感受到的是在空間域和時間域的信號。但是，往往許多問題在頻域中討論時，有其非常方便分析的一面。 1. 方便處理 2. 便于抽取特性第5章 圖像變換常用的變換1. 傅立葉變換Fourier Transform2. 離散余弦變換Discrete Cosine Transform3. 沃爾什哈達(dá)瑪變換Walsh-Hadamard Transform第5章 圖像變換二. 傅立葉變換 傅立葉變換的作用（1）可以得出信號在各個頻率點(diǎn)上的強(qiáng)度。（2）可以將卷積運(yùn)算化為乘積運(yùn)算。（3）傅氏變換和線性系統(tǒng)理論是進(jìn)

3、行圖像恢復(fù)和重構(gòu)的重要手段。（4）傅立葉變換能使我們從空間域與頻率域兩個不同的角度來看待圖像的問題，有時在空間域無法解決的問題在頻域卻是顯而易見的。第5章 圖像變換 傅立葉變換的定義o 傅立葉變換dxexfuFuxj2)()(若f(x)為一維連續(xù)實(shí)函數(shù)，則它的傅里葉變換可定義為： 傅立葉逆變換定義如下： dueuFxfuxj2)()(第5章 圖像變換 函數(shù)f(x)和F(u)被稱為傅立葉變換對。即對于任一函數(shù)f(x)，其傅立葉變換F(u)是惟一的； 反之，對于任一函數(shù)F(u)，其傅立葉逆變換f(x)也是惟一的。 第5章 圖像變換傅里葉變換的條件傅里葉變換的條件 傅里葉變換在數(shù)學(xué)上的定義是嚴(yán)密的，

4、它需要滿足如下狄利克萊條件： (1) 具有有限個間斷點(diǎn)； (2) 具有有限個極值點(diǎn)； (3) 絕對可積;第5章 圖像變換F(u)可以表示為如下形式： )()()(ujIuRuF2122)()(| )(|uIuRuF)()(tan(arg)(uRuIu |F(u)|稱為F(u)的模，也稱為函數(shù)f(x)的傅立葉譜，)(u稱為F(u)的相角。 第5章 圖像變換2| )(|)(uFuE)(uE稱為函數(shù)f(x)的能量譜或功率譜。 第5章 圖像變換高斯函數(shù)的定義為： 例例1 1 高斯函數(shù)的傅立葉變換高斯函數(shù)的傅立葉變換 2)(xexf根據(jù)傅立葉變換的定義可得： dxexfuFuxj2)()(dxeeuxj

5、x22dxeuxjx)2(2dxeejuxu2)(2第5章 圖像變換令x+ju=t，上式可以化為： dteeuFtu22)(2ue2xe2ue結(jié)論:與即，高斯函數(shù)的傅立葉變換依然是高斯函數(shù) 為傅立葉變換函數(shù)對。第5章 圖像變換例例2. 2. 矩形函數(shù)矩形函數(shù) 矩形函數(shù)形式如下矩形函數(shù)形式如下: : 2|02|)(TxTxAxf第5章 圖像變換dxexfuFuxj2)()(根據(jù)傅立葉變換的定義，其傅立葉變換如下： 222TTuxjdxAe02)sin(uxjeuTuA第5章 圖像變換可得矩形函數(shù)可得矩形函數(shù)f(x)f(x)的傅立葉頻譜為：的傅立葉頻譜為： |)sin(| )(|uTuTATuF幾

6、何圖形如下頁圖(b)所示 第5章 圖像變換第5章 圖像變換第5章 圖像變換低通高通第5章 圖像變換第5章 圖像變換第5章 圖像變換)(SG),(jif),(jifgfgfg),(),(),(FGFg)(1ggFFFTf復(fù)雜復(fù)雜簡單簡單第5章 圖像變換三. 離散傅立葉變換 離散傅立葉變換的定義 要在數(shù)字圖像處理中應(yīng)用傅立葉變換，要在數(shù)字圖像處理中應(yīng)用傅立葉變換， 還需要解決兩還需要解決兩個問題：一是在數(shù)學(xué)中進(jìn)行傅立葉變換的個問題：一是在數(shù)學(xué)中進(jìn)行傅立葉變換的f f( (x x) )為連續(xù)（模為連續(xù)（模擬）信號，擬）信號， 而計(jì)算機(jī)處理的是數(shù)字信號（圖像數(shù)據(jù)）；二而計(jì)算機(jī)處理的是數(shù)字信號（圖像數(shù)據(jù)

7、）；二是數(shù)學(xué)上采用無窮大概念，而計(jì)算機(jī)只能進(jìn)行有限次計(jì)算。是數(shù)學(xué)上采用無窮大概念，而計(jì)算機(jī)只能進(jìn)行有限次計(jì)算。 通常，通常， 將受這種限制的傅立葉變換稱為離散傅立葉變將受這種限制的傅立葉變換稱為離散傅立葉變換（換（Discrete Fourier TransformDiscrete Fourier Transform，DFT)DFT)。第5章 圖像變換o 離散傅立葉變換 離散傅立葉變換的定義1021, 2 , 1 , 0)()(NxNuxjNuexfuF設(shè)f (x)| f (0), f (1), f (2), f (N-1)為一維信號f (x)的N個抽樣，第5章 圖像變換1021, 2 , 1

8、 , 0)(1)(NuNuxjNxeuFNxf第5章 圖像變換四. 傅立葉變換的性質(zhì) 共軛對稱性 加法定理 位移定理 相似性定理 卷積定理 能量保持定理第5章 圖像變換 共軛對稱性第5章 圖像變換第5章 圖像變換 加法定理第5章 圖像變換時域加法頻域加法第5章 圖像變換 位移定理第5章 圖像變換 相似性定理 結(jié)論：一個“窄”的函數(shù)有一個“寬”的頻譜第5章 圖像變換第5章 圖像變換 旋轉(zhuǎn)不變性旋轉(zhuǎn)不變性 由旋轉(zhuǎn)不變性可知，如果時域中離散函數(shù)旋轉(zhuǎn)角度，則在變換域中該離散傅立葉變換函數(shù)也將旋轉(zhuǎn)同樣的角度。離散傅立葉變換的旋轉(zhuǎn)不變性如圖所示。(a)(b)(d)(c)圖 離散傅立葉變換的旋轉(zhuǎn)不變性（a）

9、 原始圖像； （b） 原始圖像的傅立葉頻譜； （c） 旋轉(zhuǎn)45后的圖像； （d） 圖像旋轉(zhuǎn)后的傅立葉頻譜 第5章 圖像變換卷積定理第5章 圖像變換能量保持定理第5章 圖像變換五. 二維傅立葉變換1. 二維連續(xù)函數(shù)傅立葉變換的定義 dxdyeyxfvuFvyuxj)(2),(),(第5章 圖像變換 dudvevuFyxfvyuxj)(2),(),(第5章 圖像變換2. 二維離散函數(shù)傅立葉變換的定義 根據(jù)一維離散傅立葉變換的定義和二維連續(xù)傅根據(jù)一維離散傅立葉變換的定義和二維連續(xù)傅立葉變換理論，對于一個具有立葉變換理論，對于一個具有M MN N個樣本值的二位個樣本值的二位離散序列離散序列f(xf(x

10、，y)y)，（，（x=0,1,2,3, x=0,1,2,3, ,M-1,M-1；y=0,1,2,3, y=0,1,2,3, ,N-1,N-1）其傅立葉變換為：）其傅立葉變換為： (1) 二維離散傅立葉正變換1, 2 , 1 , 0; 1, 2 , 1 , 0),(),(10)(210NvMueyxfvuFMxNvyMuxjNy第5章 圖像變換(2) 二維離散傅立葉逆變換若已知頻率二維序列F(u，v) （u=0,1,2,3, ,M-1；v=0,1,2,3, ,N-1），則二維離散序列F(u，v)的傅立葉逆變換定義為： 1, 2 , 1 , 01, 2 , 1 , 0),(1),(10)(210N

11、yMxevuFMNyxfNvNvyMuxjMu第5章 圖像變換 x、y和u、v，分別為空間域采樣間隔和頻率域采樣間隔 兩者之間滿足如下關(guān)系： vNyuMx11第5章 圖像變換 式中序列R(u，v) 和I(u，v)分別表示離散序列F(u，v)的實(shí)序列和虛序列。 二維序列f(x，y)的頻譜（傅立葉幅度譜）、相位譜和能量譜（功率譜）分別如下： F(u，v)可以表示為如下形式：),(),(),(vujIvuRvuF2122),(),(| ),(|vuIvuRvuF),(),(tan(arg),(vuRvuIvu2| ),(|),(vuFvuE第5章 圖像變換第5章 圖像變換第5章 圖像變換DFT變換（

12、幅值譜）第5章 圖像變換(1)(1)線性特性線性特性 3. 二維離散傅立葉變換的性質(zhì)),(),(),(),(22112211yxfkDFTyxfkDFTyxfkyxfkDFT),(),(2211vuFkvuFk(1) (1) 比例性質(zhì)比例性質(zhì) = =0),(1),(abbvauFabbyaxfDFT第5章 圖像變換(3)(3)平移性質(zhì)平移性質(zhì) ),(),(00)(200vvuuFeyxfDFTNyvMxuj 二維傅立葉變換的移位特性表明，當(dāng)用 乘以f(x，y)，然后再進(jìn)行乘積的離散傅里葉變換時，可以使頻率域u-v平面坐標(biāo)系的原點(diǎn)從(0，0)平移到(u0，v0)的位置。 )(200NyvMxuj

13、e第5章 圖像變換(4)(4)可分離性可分離性 10)(210),(),(MxNvyMuxjNyeyxfvuF1, 2 , 1 , 01, 2 , 1 , 0),(102210 NvMueeyxfMxNuxjMvyjNy第5章 圖像變換 二維傅立葉變換的可分離特性表明，一個二維傅立葉變換可通過2次一維傅立葉變換來完成，即：第一次先對y進(jìn)行一維傅立葉變換 1, 2 , 1 , 01, 2 , 1 , 0),(),(210NvMxeyxfvxFNvyjNy在此基礎(chǔ)上再對x進(jìn)行一維傅立葉變換1, 2 , 1 , 01, 2 , 1 , 0),(),(210NvMuevxfvuFMuxjMx第5章 圖

14、像變換變量分離步驟如圖所示 ),(),(),(yxfDFTDFTyxfDFTDFTvuFyxxy先按行先按列結(jié)果都一樣第5章 圖像變換 若已知頻率二維序列F(u，v)，則二維可分離性對傅立葉逆變換同樣適應(yīng) 10)(210),(),(MuNvyMuxjNvevuFyxf1, 2 , 1 , 01, 2 , 1 , 0),(102210 NyMxeevuFMuNuxjMvyjNv逆變換的分離性也同樣可以分解為2次一維傅立葉變換 1, 2 , 1 , 01, 2 , 1 , 0),(),(),(1111NyMxvuFDFTDFTvuFDFTDFTyxfuvvu第5章 圖像變換(5)(5)周期性周期性

15、 1,2, 1 ,01,2, 1 ,0),(),(21NvMuNkvMkuFvuF 如果二維離散函數(shù)f(x，y)的傅里葉變換為F(u，v)，則傅立葉變換及其逆變換存在如下周期特性： 第5章 圖像變換(6)(6)共軛對稱性共軛對稱性 1,2,1 ,01,2,1 ,0),(),(*NvMuvuFvuF第5章 圖像變換(7)(7)旋轉(zhuǎn)不變性旋轉(zhuǎn)不變性 圖像f(x，y)可以表示為f(r，)。同樣，空間頻率域的F(u，v)采用極坐標(biāo)可以表示為F(，)。二維離散傅立葉存在如下旋轉(zhuǎn)特性： ),(),(00FrfDFT),(),(00rfFDFT第5章 圖像變換(a)原始圖像(c) 原始圖像旋轉(zhuǎn)45(b) D

16、FT變換(d) 旋轉(zhuǎn)之后DFT變換結(jié)果第5章 圖像變換(8)(8)微分性質(zhì)微分性質(zhì) 1, 2 , 1 , 01, 2 , 1 , 0),()2(),(NvMuvuFujxyxfDFTnnn1, 2 , 1 , 01, 2 , 1 , 0),()2(),(NvMuvuFvjyyxfDFTnnn第5章 圖像變換(9)(9)平均值性質(zhì)平均值性質(zhì) 平均值定義如下平均值定義如下 1010),(1),(MxNyyxfMNyxf 1010),()0,0(MxNyyxfF),(yxfMN)0 , 0(1),(FMNyxf平均值性質(zhì)如下：平均值性質(zhì)如下： 即：即： 結(jié)論：二維離散函數(shù)的平均值等于其傅立葉變換在頻

17、率原點(diǎn)處值的1/MN。 第5章 圖像變換二維傅立葉變換二維傅立葉變換( (幅值及相位幅值及相位) )意義意義 第5章 圖像變換圖像的說明圖像的說明 第5章 圖像變換第5章 圖像變換第5章 圖像變換n由于由于二維二維離散傅立葉變換具有離散傅立葉變換具有可分離性可分離性， 即它即它可由兩次可由兩次一維一維離散傅立葉變換計(jì)算得到，因此，離散傅立葉變換計(jì)算得到，因此，僅研究一維離散傅立葉變換僅研究一維離散傅立葉變換的的快速算法快速算法即可。即可。n先將一維離散傅立葉變換寫成先將一維離散傅立葉變換寫成 10)()(NxuxWxfuF式中，式中，W=e-j2N ，稱為，稱為旋轉(zhuǎn)因子旋轉(zhuǎn)因子。 第5章 圖像

18、變換n這樣，可將上式所示的一維離散傅立葉變換（這樣，可將上式所示的一維離散傅立葉變換（DFTDFT）用矩陣的形式表示為（用矩陣的形式表示為（注意頻域中的坐標(biāo)點(diǎn)注意頻域中的坐標(biāo)點(diǎn)!）) 1() 1 ()0() 1() 1 ()0()1()1()1(2)1(1)1(02)1(21201)1(1211100)1(020100NfffWWWWWWWWWWWWWWWNFFFNNNNNNNN式中，由Wux構(gòu)成的矩陣稱為W陣或系數(shù)矩陣。 第5章 圖像變換 觀察觀察DFTDFT的的W陣，并結(jié)合陣，并結(jié)合W的定義表達(dá)式的定義表達(dá)式W=e-j2N，可以發(fā)現(xiàn)系數(shù)可以發(fā)現(xiàn)系數(shù)W是是以抽樣點(diǎn)數(shù)以抽樣點(diǎn)數(shù)N N為周期為周

19、期的。這樣，的。這樣，W陣中很多系數(shù)就是相同的，陣中很多系數(shù)就是相同的， 不必進(jìn)行多次重復(fù)計(jì)算，不必進(jìn)行多次重復(fù)計(jì)算，且由于且由于W的的對稱性對稱性，即，即xuNxuNxuNNjNWWWWeW22222, 1因此可進(jìn)一步因此可進(jìn)一步減少計(jì)算工作量減少計(jì)算工作量。 5.3.2 FFT算法原理第5章 圖像變換n例如，對于例如，對于N=4，由，由 展開得到展開得到 W陣陣為：為：9630642032100000WWWWWWWWWWWWWWWW10)()(NxuxWxfuFF(0)F(1)F(2)F(3) FFT根據(jù)算法原理可以分為基于時間分解（DIT）和基于頻率分解（DIF）兩類算法，其中的典型代表

20、分別是DIT基2算法和DIF基2算法。以下以DIT基2算法介紹第5章 圖像變換n由由W的的周期性周期性得：得：W4W0，因此推出，因此推出W6W4*W2=W2，同理可得，同理可得W9W1；再由；再由W的的對稱性對稱性可得：可得： W3W1，推出，推出W2W0。于是上式可變?yōu)橛谑巧鲜娇勺優(yōu)?010000010100000WWWWWWWWWWWWWWWW9630642032100000WWWWWWWWWWWWWWWW第5章 圖像變換n可見可見N=4的的W陣中只需計(jì)算陣中只需計(jì)算W0和和W1兩個系數(shù)兩個系數(shù)即可。這說明即可。這說明W陣的系數(shù)有許多計(jì)算工作是重復(fù)陣的系數(shù)有許多計(jì)算工作是重復(fù)的，如果把一

21、個離散序列分解成若干的，如果把一個離散序列分解成若干短序列短序列， 并充分利用并充分利用旋轉(zhuǎn)因子旋轉(zhuǎn)因子W的的周期性周期性和和對稱性對稱性來計(jì)算來計(jì)算離散傅立葉變換，便可以簡化運(yùn)算過程，這就是離散傅立葉變換，便可以簡化運(yùn)算過程，這就是FFT的基本思想的基本思想。n設(shè)抽樣點(diǎn)數(shù)設(shè)抽樣點(diǎn)數(shù)N為為2的正整數(shù)次冪，的正整數(shù)次冪， 即即, 2 , 12nNn如令如令M為正整數(shù)，且為正整數(shù)，且 N=2M，即即N分成分成2個個長度為長度為M的的短序列短序列 。第5章 圖像變換離散傅立葉變換離散傅立葉變換可改寫成可改寫成奇、偶函數(shù)奇、偶函數(shù)之和，如下形式：之和，如下形式： 10)12(2)2(2101202)

22、12()2()()(MxxuMxuMMxMxuxMWxfWxfWxfuF由旋轉(zhuǎn)因子W的定義可知， 因此上式變?yōu)?uxMuxMWW22uMuxMMxMxuxMWWxfWxfuF21010) 12()2()( 現(xiàn)定義 1, 1 , 0,) 12()(1, 1 , 0,)2()(1010MxuWxfuFMxuWxfuFMxuxMoMxuxMe第5章 圖像變換于是上式（即上半截短序列，u=0M）變?yōu)?)()()(2uFWuFuFouMe 進(jìn)一步考慮W的對稱性和周期性可知 和， 于是，下半截短序列(u=0M)為uMMuMWWuMMuMWW22)()()()()(2)(2uFWuFMuFWMuFMuFou

23、MeoMuMe由此，可將一個N點(diǎn)的離散傅立葉變換分解成兩個N2短序列的離散傅立葉變換，即分解為偶數(shù)和奇數(shù)序列的離散傅立葉變換Fe(u)和Fo(u) 。 第5章 圖像變換 在此，以計(jì)算抽樣點(diǎn)N=8（=23=2*4）的DFT為例，此時n=3，M=4(折半)。由式(7-31)和式(7-32)可得 )3()3()7()2()2()6()1()1()5()0()0()4()3()3()3()2()2()2()1()1()1()0()0()0(3828180838281808oeoeoeoeoeoeoeoeFWFFFWFFFWFFFWFFFWFFFWFFFWFFFWFF(7-33) 下半截F(u+M)上半

24、截F(u)第5章 圖像變換 式（式（7-33）中，）中，u取取07時的時的F(u)、Fe(u)和和Fo(u)的關(guān)系可用的關(guān)系可用圖圖7-7描述描述(F(0)-F(4); F(1)-F(5); F(2)-F(6); F(3)-F(7)。左方的兩。左方的兩個節(jié)點(diǎn)為輸入節(jié)點(diǎn)，代表輸入數(shù)值；右方兩個節(jié)點(diǎn)為輸出節(jié)點(diǎn)，個節(jié)點(diǎn)為輸入節(jié)點(diǎn)，代表輸入數(shù)值；右方兩個節(jié)點(diǎn)為輸出節(jié)點(diǎn)，表示輸入數(shù)值的疊加，運(yùn)算由左向右進(jìn)行。線旁的表示輸入數(shù)值的疊加，運(yùn)算由左向右進(jìn)行。線旁的W18和和W18為加權(quán)系數(shù)，定義由為加權(quán)系數(shù)，定義由F(1)、 F(5)、Fe(1)和和Fo(1)所構(gòu)成的結(jié)構(gòu)為所構(gòu)成的結(jié)構(gòu)為蝶形運(yùn)算單元蝶形運(yùn)算單

25、元, 其表示的運(yùn)算為其表示的運(yùn)算為 ) 1 () 1 ()5() 1 () 1 () 1 (1818oeoeFWFFFWFF(7-34) 第5章 圖像變換圖圖7-7 蝶形運(yùn)算單元蝶形運(yùn)算單元 （F(1)-F(5)）Fe(1)F(1)F(5)Fo(1)18W18W) 1 () 1 () 5() 1 () 1 () 1 (1818oeoeFWFFFWFF第5章 圖像變換由于由于Fe(u)和和Fo(u)都是都是4點(diǎn)的點(diǎn)的DFT，因此，如果對它們，因此，如果對它們再按照奇再按照奇偶偶進(jìn)行分組進(jìn)行分組(即即M=2，計(jì)算，計(jì)算F(u)及及F(u+M)， 則有則有 ) 1 () 1 () 3()0()0()

26、2() 1 () 1 () 1 ()0()0()0(28082808eoeeeeoeeeeoeeeeoeeeFWFFFWFFFWFFFWFF) 1 () 1 () 3()0()0()2() 1 () 1 () 1 ()0()0()0(28082808oooeooooeooooeooooeoFWFFFWFFFWFFFWFF（7-35a） （7-35b） )3()3()7()2()2()6()1()1()5()0()0()4()3()3()3()2()2()2()1()1()1()0()0()0(3828180838281808oeoeoeoeoeoeoeoeFWFFFWFFFWFFFWFFFWF

27、FFWFFFWFFFWFFM=4M=2第5章 圖像變換圖7-8 4點(diǎn)DFT分解為2點(diǎn)（M=2）DFT的蝶形流程圖 Fee(0)Feo(1)08W28WFee(1)Feo(0)Fe(0)Fe(1)Fe(2)Fe(3)28W08WFoe(0)Foo(1)08W28WFoe(1)Foo(0)Fo(0)Fo(1)Fo(2)Fo(3)28W08WM=2第5章 圖像變換圖5-8 8點(diǎn)DFT的蝶形流程圖（與編程循環(huán)關(guān)系） Fee(0)Feo(1)08W28WFee(1)Feo(0)Fe(0)Fe(1)Fe(2)Fe(3)28W08WFoe(0)Foo(1)08W28WFoe(1)Foo(0)Fo(0)Fo(

28、1)Fo(2)Fo(3)28W08Wf (0)f (4)08W08Wf (2)f (6)08W08Wf (1)f (5)08W08Wf (3)f (7)08W08W08W18W28W38W08W18W28W38WF(0)F(1)F(2)F(3)F(4)F(5)F(6)F(7)循環(huán)外層循環(huán)中層循環(huán)內(nèi)層第5章 圖像變換圖5-7 8點(diǎn)DFT逐級分解框圖 第一級N / 4點(diǎn)DF Tf (0)f (4)N / 4點(diǎn)DF Tf (2)f (6)N / 2點(diǎn)DF TN / 4點(diǎn)DF Tf (1)f (5)N / 4點(diǎn)DF Tf (3)f (7)N / 2點(diǎn)DF T第二級N 點(diǎn)DFT第三級F(0)F(1)F(

29、2)F(3)F (4)F(5)F(6)F (7)第5章 圖像變換第5章 圖像變換表表7-2 自然順序與自然順序與碼位倒序碼位倒序（N=8） 第5章 圖像變換第5章 圖像變換第5章 圖像變換第5章 圖像變換第5章 圖像變換MXXEmMiix1TxxMiTiiMiTxxTxxxmmXXMmXmXEMmXmXEC1)(1)(11第5章 圖像變換222222212222111211.NNNNNNeeeeeeeeeA第5章 圖像變換第5章 圖像變換第5章 圖像變換第5章 圖像變換21Nnkkn第5章 圖像變換第5章 圖像變換六. 離散余弦變換第5章 圖像變換第5章 圖像變換第5章 圖像變換n一維一維DC

30、T的的變換核定變換核定義為義為NuxNuCuxg2) 12(cos2)(),(式中，式中，x, u=0, 1, 2, , N1； 其他1021)(uuC第5章 圖像變換 一維DCT定義如下： 設(shè)f(x)|x=0, 1, , N-1為離散的信號列。 102) 12(cos)(2)()(NxNuxxfNuCuF式中，u, x=0, 1, 2, , N1。將變換式展開整理后， 可以寫成矩陣的形式， 即 F=Gf 其中 F=F(0),F(1),F(2),F(N-1)T f=f(0),f(1),f(2), f(N-1)T第5章 圖像變換)2/) 12)(1cos()2/3)(1cos()2/) 1cos

31、(/2)2/) 12cos()2/6cos()2/cos(/2)2/) 12cos()2/3cos()2/cos(/2111/1NNNNNNNNNNNNNNNNNNNG 一維DCT的逆變換IDCT定義為 102) 12(cos)()(2)(NuNuxuFuCNxf 式中， x, u=0, 1, 2, , N1?？梢娨痪SDCT的逆變換核與正變換核是相同的。 第5章 圖像變換NvyMuxvCuCMNvuyxg2) 12(cos2) 12(cos)()(2),( 考慮到兩個變量，很容易將一維DCT的定義推廣到二維DCT。其正變換核為 式中，C(u)和C(v)的定義同前式；x, u=0, 1, 2,

32、, M1； y, v=0, 1, 2, , N1。 二維DCT定義如下：設(shè)f(x, y)為MN的數(shù)字圖像矩陣，則 NvyMuxvCuCyxfMNvuFMxNy2) 12(cos2) 12(cos)()(),(2),(1010第5章 圖像變換式中： x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 二維DCT逆變換定義如下： NvyMuxvuFvCuCMNyxfMuNv2) 12 (cos2) 12 (cos),()()(2),(1010式中：x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 類似一維矩陣形式的DCT，可以寫出二維DCT

33、的矩陣形式如下：F=GfGT第5章 圖像變換 同時，由前面式可知二維DCT的逆變換核與正變換核相同，且是可分離的，即 NvyvCNMuxuCMvyguxgvuyxg2) 12(cos)(22) 12(cos)(2),(),(),(21式中：C(u)和C(v)的定義同前式； x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 第5章 圖像變換 通常根據(jù)可分離性， 二維DCT可用兩次一維DCT來完成， 其算法流程與DFT類似， 即 ),(),(),(),(),(),(),(vuFvuFvxFFvxFvxFyxfFyxfTTT轉(zhuǎn)置列轉(zhuǎn)置行第5章 圖像變換5.5.3 快速離

34、散余弦變換快速離散余弦變換 離散余弦變換的計(jì)算量相當(dāng)大，離散余弦變換的計(jì)算量相當(dāng)大， 在實(shí)用中非常不方便，在實(shí)用中非常不方便， 也需要研究相應(yīng)的快速算法。目前已有多種快速也需要研究相應(yīng)的快速算法。目前已有多種快速DCT（FCT），）， 在此介紹一種由在此介紹一種由FFT的思路發(fā)展起來的的思路發(fā)展起來的FCT。 首先，將首先，將f(x)延拓為延拓為 0)()(xfxfex=0, 1, 2, , N-1x=N， N+1, , 2N-1 按照一維按照一維DCT的定義，的定義，fe(x)的的DCT為為10)(1)0(NxexfNF第5章 圖像變換NxujNxeNujNuxjNxeNxeNNxeNxeN

35、NxNxNxexfeNexfNNuxxfNNuxxfNNuxxfNNuxNNuxxfNNuxxfNuF2212022)12(1201201210121010)(Re2)(Re22) 12(cos)(22) 12(cos)(22) 12(cos)(22) 12(cos022) 12(cos)(22) 12(cos)(2)(第5章 圖像變換 由于 為fe(x)的2N點(diǎn)DFT。因此，在作DCT時，可把長度為N的f(x)的長度延拓為2N點(diǎn)的序列fe(x)，然后對fe(x)作DFT，最后取DFT的實(shí)部便可得到DCT的結(jié)果。 同理對于離散余弦逆變換IDCT，可首先將F(u)延拓為12022)(NxNxuj

36、eexf0)()(uFuFeu=0, 1, 2, , N-1u=N, N+1, , 2N-1 第5章 圖像變換由前式可得，DCT的IDCT為1202)12(21212)12(121)(Re2)0(21)(Re2)0(12) 12(cos)(2)0(1)(NuNuxjNujeeNuNuxjeeNueeeeuFNFNNeuFNFNNuxuFNFNxf第5章 圖像變換 最后要注意的是二維DCT的頻譜分布， 其譜域分布與DFT相差一倍，如圖5-10所示。 從圖中可以看出，對于DCT而言，(0, 0)點(diǎn)對應(yīng)于頻譜的低頻成分，(N-1, N-1)點(diǎn)對應(yīng)于高頻成分，而同階的DFT中， (N2, N2)點(diǎn)對應(yīng)

37、于高頻成分（注： 此頻譜圖中未作頻譜中心平移）。 由于DFT和IDFT已有快速算法FFT和IFFT，因此可用它們實(shí)現(xiàn)快速DCT和IDCT算法FCT及IFCT。不過，由于FFT及IFFT中要涉及到復(fù)數(shù)運(yùn)算， 因此這種FCT及IFCT算法并不是最佳的。 第5章 圖像變換圖5-10 DFT和DCT的頻譜分布（a）DFT頻譜分布； （b） DCT頻譜分布 低頻高頻低頻高頻第5章 圖像變換返回第5章 圖像變換返回第5章 圖像變換另一幅圖像效果壓縮率為：1.7：1壓縮率為：2.24：1壓縮率為：3.3：1第5章 圖像變換 返回壓縮率為：8.1：1壓縮率為：10.77：1壓縮率為：16.1：1第5章 圖像變

38、換返回第5章 圖像變換第5章 圖像變換1, 3 , 2 , 1 , 0) 1)(1)(10)()(101NuxfNuFNxubxbniini第5章 圖像變換101)()() 1(1),(niiniubxbNuxg第5章 圖像變換1, 3 , 2 , 1 , 0) 1)(1)(10)()(101NxuFNxfNxubxbniini第5章 圖像變換第5章 圖像變換111111111111111111111111111111111111111111111111111111111111111181G第5章 圖像變換1, 3 ,2, 1; 1, 3 ,2, 1 ,0),(),(),(1010 NvMuv

39、yuxgyxfvuFMxNy10)()()()(101101) 1(1),(NuubxbubxbnjjnjniiniMNvyuxg第5章 圖像變換),(),() 1(1) 1(1) 1(1),(2110)()(10)()(10)()()()(101101101101vyguxgNMMNvyuxgNuubxbNuubxbNuubxbubxbnjjnjniininjjnjniini第5章 圖像變換1, 3 , 2 , 1; 1, 3 , 2 , 1 , 0),(),(),(1010NyMxvyuxhvuFyxfMuNv10)()()()(101101) 1(1),(Nuubxbubxbnjjnjn

40、iiniMNvyuxg第5章 圖像變換212111FGGNffGGMNF第5章 圖像變換第5章 圖像變換第5章 圖像變換 哈達(dá)瑪變換與沃爾什變換十分類似，是一種特殊排序的沃爾什變換，一是一個僅包含+1和-1兩個矩陣元素的方陣，不同的行或不同的列之間都彼此正交，不同之處在于僅僅是行的次序不同。 哈達(dá)瑪?shù)淖儞Q的最大優(yōu)點(diǎn)在于它的變換核矩陣具有簡單的遞推關(guān)系，即高階陣可以通過低階陣求出。基于這個原因，許多人更愿意應(yīng)用哈達(dá)瑪變換。第5章 圖像變換 設(shè)f(x)表示N點(diǎn)的一維離散序列，則一維哈達(dá)瑪變換如下：10)()(1010) 1)(1),()()(NxubxbNxniiixfNuxgxfuFu=0,1,2,3,N-1第5章 圖像變換其中，g(x，u)是一維哈達(dá)瑪變換的核，定義如下： 10)()()1(1),