圖像變換(非常重要的內(nèi)容)

1、第三章 圖像變換 第三章第三章 圖象變換圖象變換3.1 圖像變換的預(yù)備知識圖像變換的預(yù)備知識 3.2 傅立葉變換傅立葉變換 3.3 頻域變換的一般表達(dá)式頻域變換的一般表達(dá)式 3.4 離散余弦變換離散余弦變換 3.5 離散沃爾什哈達(dá)瑪變換離散沃爾什哈達(dá)瑪變換 3.6 小波變換簡介小波變換簡介 第三章 圖像變換 概述概述一定義： 圖像變換即為達(dá)到圖像處理的某種目的而使用的一種數(shù)學(xué)方法。二圖像變換的目的： 使圖像處理問題簡化； 有利于圖像特征提取； 有助于從概念上增強(qiáng)對圖像信息的理解。 第三章 圖像變換 三圖像變換的要求：圖像函數(shù)變換后處理較變換前更加方便和簡單；圖像函數(shù)變換后不損失原圖像的信息；圖

2、像變換必須是可逆的。 第三章 圖像變換 3 31 1 圖像變換的預(yù)備知識圖像變換的預(yù)備知識一一線性系統(tǒng)線性系統(tǒng)1 系統(tǒng)的定義：接受一個輸入，并產(chǎn)生相應(yīng)輸出的任何實(shí)體。系統(tǒng)的輸入是一個或兩個變量的函數(shù)，輸出是相同變量的另一個函數(shù)。系統(tǒng)x(t)x(t)輸入輸入y(t)y(t)輸出輸出第三章 圖像變換 2 2 線性系統(tǒng)線性系統(tǒng)的定義：的定義：對于某特定系統(tǒng)，有： x1(t) y1(t) x2(t) y2(t)該系統(tǒng)是線性的當(dāng)且僅當(dāng)：x1(t) + x2(t) y1(t) + y2(t) 從而有：a*x1(t) a*y1(t)第三章 圖像變換 3 線性系統(tǒng)線性系統(tǒng)位移不變性位移不變性的定義：的定義：對

3、于某線性系統(tǒng)，有：x(t) y(t)當(dāng)輸入信號沿時間軸平移T，有： x(t - T) y(t - T)則稱該線性系統(tǒng)具有位移不變性第三章 圖像變換 二卷積二卷積 卷積的定義 離散一維卷積 二維卷積的定義 離散二維卷積 相關(guān)的定義第三章 圖像變換 1 卷積的定義 對于一個線性系統(tǒng)的輸入f(t)和輸出h(t)，如果有如下關(guān)系： h(t) = g(t - )f( )d 記為：h = g * f - g(t)稱為沖激響應(yīng)函數(shù)。 h(t)為f(t) 與g(t)的卷積。 上式就是卷積積分的一般表達(dá)式第三章 圖像變換 2 離散一維卷積 h(i) = f(i)*g(i) = f(j)g(i-j) j3 二維卷

4、積的定義 h(x,y) = f*g = f(u,v)g(x u, y v)dudv - 4 離散二維卷積 h(x,y) = f*g = f(m,n)g(x m, y n) m n第三章 圖像變換 三三. . 頻域世界與頻域變換頻域世界與頻域變換圖3-1 任意波形可分解為正弦波的加權(quán)和 (a)(b)(c)(d)第三章 圖像變換 圖3-2 正弦波的振幅A和相位 初相位振幅 A基本 正弦波(A1, 0)角頻率OAAOfOf(a)(b)圖3-3 圖3-1（a）波形的頻域表示(a) 幅頻特性； (b) 相頻特性 第三章 圖像變換 空域和頻域之間的變換可用數(shù)學(xué)公式表示如下： )(),()(ffAff正變換

5、逆變換 為能同時表示信號的振幅和相位，通常采用復(fù)數(shù)表示法，因此式（3-1）可用復(fù)數(shù)表示為 )()(fFff正變換逆變換完成這種變換，一般采用的方法是線性正交變換。 (3-1) (3-1) (3-2) (3-2) 第三章 圖像變換 3.2 3.2 傅傅 立立 葉葉 變變 換換 一一. . 連續(xù)函數(shù)的傅立葉變換連續(xù)函數(shù)的傅立葉變換 若把一個一維輸入信號作一維傅立葉變換，該信號就被變換到頻域上的一個信號，即得到了構(gòu)成該輸入信號的頻譜，頻譜反映了該輸入信號由哪些頻率構(gòu)成。這是一種分析與處理一維信號的重要手段。 當(dāng)一個一維信號f(x)滿足狄里赫萊條件，即f(x) （1） 具有有限個間斷點(diǎn)； （2） 具有

6、有限個極值點(diǎn)； （3） 絕對可積。 第三章 圖像變換 則其傅立葉變換對（傅立葉變換和逆變換）一定存在。在實(shí)際應(yīng)用中，這些條件一般總是可以滿足的。 一維傅立葉變換對的定義為 dueuFxfuFFdxexfuFxfFuxjuxj212)()()()()()(3-3) (3-4) 式中： ，x稱為空域變量，u稱為頻域變量。 1j第三章 圖像變換 以上一維傅立葉變換可以很容易地推廣到二維，如果二維函數(shù)f(x, y)滿足狄里赫萊條件，則它的二維傅立葉變換對為: dudvevuFyxfvuFFdxdyeyxfvuFyxfFvyuxjvyuxj)(21)(2),(),(),(),(),(),( (3-5)

7、(3-6) 式中：x, y為空域變量；u, v為頻域變量。 第三章 圖像變換 二二. . 離散傅立葉變換離散傅立葉變換 要在數(shù)字圖像處理中應(yīng)用傅立葉變換， 還需要解決兩個問題：一是在數(shù)學(xué)中進(jìn)行傅立葉變換的f(x)為連續(xù)（模擬）信號， 而計(jì)算機(jī)處理的是數(shù)字信號（圖像數(shù)據(jù)）；二是數(shù)學(xué)上采用無窮大概念，而計(jì)算機(jī)只能進(jìn)行有限次計(jì)算。通常， 將受這種限制的傅立葉變換稱為離散傅立葉變換（Discrete Fourier Transform，DFT)。 設(shè)f(x)|f(0), f(1), f(2), , f(N-1)為一維信號f(x)的N個抽樣， 其離散傅立葉變換對為 :第三章 圖像變換 NuxjNxNux

8、jNxeuFNxfuFFexfuFxfF/2101/210)(1)()()()()(3-7) (3-8) 式中：x，u=0， 1， 2， , N1。 N/1注： 式（3-8）中的系數(shù)1/N也可以放在式（3-7）中， 有時也可在傅立葉正變換和逆變換前分別乘以 ， 這是無關(guān)緊要的， 只要正變換和逆變換前系數(shù)乘積等于1/N即可。 第三章 圖像變換 由歐拉公式可知 sincosjej(3-9) 將式（3-9）代入式（3-7），并利用cos()=cos()，可得 102sin2cos)()(NxNuxjNuxxfuF(3-10) 可見，離散序列的傅立葉變換仍是一個離散的序列，每一個u對應(yīng)的傅立葉變換結(jié)果

9、是所有輸入序列f(x)的加權(quán)和（每一個f(x)都乘以不同頻率的正弦和余弦值），u決定了每個傅立葉變換結(jié)果的頻率。 第三章 圖像變換 通常傅立葉變換為復(fù)數(shù)形式， 即 )()()(ujIuRuF(3-11) 式中，R(u)和I(u)分別是F(u)的實(shí)部和虛部。式(3-11)也可表示成指數(shù)形式： F(u)=|F(u) |ej(u) (3-12) 其中 )()(arctan)()()(| )(|22uRuIuuIuRuF(3-13) (3-14) 第三章 圖像變換 通常稱|F(u) |為f(x)的頻譜或傅立葉幅度譜，(u)為f(x)的相位譜。 頻譜的平方稱為能量譜或功率譜，它表示為 )()(| )(|

10、)(222uIuRuFuE(3-15) 考慮到兩個變量，就很容易將一維離散傅立葉變換推廣到二維。二維離散傅立葉變換對定義為 )(210101)(21010),(1),(),(),(),(),(NvyMuxjNvMuNvyMuxjMxNyevuFMNyxfvuFFeyxfvuFyxfF(3-16) (3-17) 第三章 圖像變換 式中：u, x=0, 1, 2, , M-1；v, y=0, 1, 2, , N-1；x, y為空域變量，u, v為頻域變量。 像一維離散傅立葉變換一樣，系數(shù)1/MN可以在正變換或逆變換中，也可以在正變換和逆變換前分別乘以系數(shù) ，只要兩式系數(shù)的乘積等于1MN即可。 二維

11、離散函數(shù)的傅立葉頻譜、 相位譜和能量譜分別為 MN/1),(),(),(),(),(arctan),(),(),(| ),(|2222vuIvuRvuEvuRvuIvuvuIvuRvuF(3-18) (3-19) (3-20) 式中，R(u, v)和I(u, v)分別是F(u, v)的實(shí)部和虛部。 第三章 圖像變換 三三. . 離散傅立葉變換的性質(zhì)離散傅立葉變換的性質(zhì) 表表3-1 3-1 二維離散傅立葉變換的性質(zhì)二維離散傅立葉變換的性質(zhì) 第三章 圖像變換 第三章 圖像變換 1. 1. 可分離性可分離性 由可分離性可知，一個二維傅立葉變換可分解為兩步進(jìn)行， 其中每一步都是一個一維傅立葉變換。先對

12、f(x, y)按行進(jìn)行傅立葉變換得到F(x, v)，再對F(x, v)按列進(jìn)行傅立葉變換，便可得到f(x, y)的傅立葉變換結(jié)果，如圖3-4所示。顯然對f(x, y)先按列進(jìn)行離散傅立葉變換， 再按行進(jìn)行離散傅立葉變換也是可行的。 圖3-4 用兩次一維DFT計(jì)算二維DFT 第三章 圖像變換 2. 2. 平移性質(zhì)平移性質(zhì) 平移性質(zhì)表明，只要將f(x, y)乘以因子(1)x+y，再進(jìn)行離散傅立葉變換，即可將圖像的頻譜原點(diǎn)（0，0）移動到圖像中心（M2, N2）處。圖3-5是簡單方塊圖像平移的結(jié)果。 (a)原圖像 （b）無平移的傅立葉頻譜；（c）平移后的傅立葉頻譜圖3-5 傅立葉頻譜平移示意圖(a)

13、 (b) (c) 第三章 圖像變換 由旋轉(zhuǎn)不變性可知，如果空域中離散函數(shù)旋轉(zhuǎn)0角度，則在變換域中該離散傅立葉變換函數(shù)也將旋轉(zhuǎn)同樣的角度。離散傅立葉變換的旋轉(zhuǎn)不變性如圖3-6所示。 圖3-6 離散傅立葉變換的旋轉(zhuǎn)不變性（a） 原始圖像； （b） 原始圖像的傅立葉頻譜； （c） 旋轉(zhuǎn)45后的圖像； （d） 圖像旋轉(zhuǎn)后的傅立葉頻譜 (a)(b)(d)(c)3. 3. 旋轉(zhuǎn)不變性旋轉(zhuǎn)不變性第三章 圖像變換 四四. . 快速離散傅立葉變換快速離散傅立葉變換 離散傅立葉變換計(jì)算量非常大，運(yùn)算時間長?？梢宰C明其運(yùn)算次數(shù)正比于N2，特別是當(dāng)N較大時，其運(yùn)算時間將迅速增長， 以至于無法容忍。為此，研究離散傅立葉

14、變換的快速算法（Fast Fourier Transform， FFT）是非常有必要的。 下面介紹一種稱為逐次加倍法的快速傅立葉變換算法（FFT），它是1965年Cooley和Tukey首先提出的。采用該FFT算法，其運(yùn)算次數(shù)正比于NlbN，當(dāng)N很大時計(jì)算量可以大大減少。例如，F(xiàn)FT的運(yùn)算次數(shù)和DFT的運(yùn)算次數(shù)之比，當(dāng)N=1024時，比值為1102.4；當(dāng)N=4096時，比值可達(dá)1341.3。 第三章 圖像變換 由于二維離散傅立葉變換具有可分離性， 即它可由兩次一維離散傅立葉變換計(jì)算得到，因此，僅研究一維離散傅立葉變換的快速算法即可。 先將式（3-7）寫成 10)()(NxuxWxfuF(3-

15、21) 式中，W=e-j2N ，稱為旋轉(zhuǎn)因子。 第三章 圖像變換 這樣，可將式(3-21)所示的一維離散傅立葉變換（DFT）用矩陣的形式表示為 ) 1() 1 ()0() 1() 1 ()0()1()1()1(2)1(1)1(00)1(02010)1(0201100)1(020100NfffWWWWWWWWWWWWWWWNFFFNNNNNNNN式中，由Wux構(gòu)成的矩陣稱為W陣或系數(shù)矩陣。 (3-22) 第三章 圖像變換 觀察DFT的W W陣，并結(jié)合W的定義表達(dá)式W=e-j2N，可以發(fā)現(xiàn)系數(shù)W是以N為周期的。這樣，W陣中很多系數(shù)就是相同的， 不必進(jìn)行多次重復(fù)計(jì)算，且由于W的對稱性，即 xuNxu

16、NxuNNjNWWWWeW22222, 1因此可進(jìn)一步減少計(jì)算工作量。 例如，對于N=4， W陣為 9630642032100000WWWWWWWWWWWWWWWW(3-23) 第三章 圖像變換 由W的周期性得：W4W0，W6W2，W9W1；再由W的對稱性可得： W3W1，W2W0。于是式(3-23)可變?yōu)?1010000010100000WWWWWWWWWWWWWWWW(3-24) 第三章 圖像變換 可見N=4的W陣中只需計(jì)算W0和W1兩個系數(shù)即可。這說明W陣的系數(shù)有許多計(jì)算工作是重復(fù)的，如果把一個離散序列分解成若干短序列， 并充分利用旋轉(zhuǎn)因子W的周期性和對稱性來計(jì)算離散傅立葉變換，便可以簡

17、化運(yùn)算過程，這就是FFT的基本思想。 設(shè)N為2的正整數(shù)次冪， 即 , 2 , 12nnn如令M為正整數(shù)，且 N=2M (3-25) (3-26) 第三章 圖像變換 將式（3-26）代入式（3-21），離散傅立葉變換可改寫成如下形式： 10)12(2)2(2101202) 12()2()()(MxxuMxuMMxMxuxMWxfWxfWxfuF由旋轉(zhuǎn)因子W的定義可知， 因此式(3-27)變?yōu)?uxMuxMWW22uMuxMMxMxuxMWWxfWxfuF21010) 12()2()( 現(xiàn)定義 1, 1 , 0,) 12()(1, 1 , 0,)2()(1010MxuWxfuFMxuWxfuFMx

18、uxMoMxuxMe(3-27)(3-28)(3-29)(3-30)第三章 圖像變換 于是式于是式(3-28)變?yōu)樽優(yōu)?)()()(2uFWuFuFouMe(3-31) 進(jìn)一步考慮進(jìn)一步考慮W的對稱性和周期性可知的對稱性和周期性可知 和和， 于是于是 uMMuMWWuMMuMWW22)()()(2uFWuFMuFouMe(3-32)由此，可將一個由此，可將一個N點(diǎn)的離散傅立葉變換分解成兩個點(diǎn)的離散傅立葉變換分解成兩個N2短序列短序列的離散傅立葉變換，即分的離散傅立葉變換，即分解為偶數(shù)和奇數(shù)序列的離散傅立葉變解為偶數(shù)和奇數(shù)序列的離散傅立葉變換換Fe(u)和和Fo(u) 。 第三章 圖像變換 在此

19、，以計(jì)算在此，以計(jì)算N=8的的DFT為例，此時為例，此時n=3，M=4。由式。由式(3-31)和式和式(3-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(3-33) 第三章 圖像變換 式（3-33）中，u取07時的F(u)、Fe(u)和Fo(u)的關(guān)系可用圖3-7描述。左方的兩個節(jié)點(diǎn)為輸入節(jié)點(diǎn)，代表輸入數(shù)值；右方兩個節(jié)點(diǎn)為輸

20、出節(jié)點(diǎn)，表示輸入數(shù)值的疊加，運(yùn)算由左向右進(jìn)行。線旁的W18和W18為加權(quán)系數(shù)，定義由F(1)、 F(5)、Fe(1)和Fo(1)所構(gòu)成的結(jié)構(gòu)為蝶形運(yùn)算單元, 其表示的運(yùn)算為 ) 1 () 1 ()5() 1 () 1 () 1 (1818oeoeFWFFFWFF(3-34) 第三章 圖像變換 圖3-7 蝶形運(yùn)算單元 Fe(1)F(1)F(5)Fo(1)18W18W第三章 圖像變換 由于Fe(u)和Fo(u)都是4點(diǎn)的DFT，因此，如果對它們再按照奇偶進(jìn)行分組， 則有 ) 1 () 1 () 3()0()0()2() 1 () 1 () 1 ()0()0()0(28082808eoeeeeoee

21、eeoeeeeoeeeFWFFFWFFFWFFFWFF) 1 () 1 () 3()0()0()2() 1 () 1 () 1 ()0()0()0(28082808oooeooooeooooeooooeoFWFFFWFFFWFFFWFF（3-35a） （3-35b） 第三章 圖像變換 圖3-8 4點(diǎn)DFT分解為2點(diǎn)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)28W08W第三章 圖像變換 圖3-9 8點(diǎn)DFT的

22、蝶形流程圖 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)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)第三章 圖像變換 圖3-10 8點(diǎn)DFT逐級分解框圖 第一級N / 4點(diǎn)DF Tf (0)f (4)N / 4點(diǎn)DF Tf

23、(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(2)F(3)F (4)F(5)F(6)F (7)第三章 圖像變換 表表3-2 自然順序與碼位倒序（自然順序與碼位倒序（N=8） 十進(jìn)制數(shù)十進(jìn)制數(shù)二進(jìn)制數(shù)二進(jìn)制數(shù)二進(jìn)制數(shù)的二進(jìn)制數(shù)的碼位倒序碼位倒序碼位倒序后碼位倒序后十進(jìn)制十進(jìn)制0000000010011004201001023011110641000011510110156110011371111117第三章 圖像變換 上述FFT是將f(x)序列按x的奇偶進(jìn)行分組計(jì)

24、算的，稱之為時間抽選FFT。如果將頻域序列的F(u)按u的奇偶進(jìn)行分組計(jì)算， 也可實(shí)現(xiàn)快速傅立葉計(jì)算， 這稱為頻率抽選FFT。 至此，應(yīng)該對傅立葉變換的理論基礎(chǔ)及其實(shí)現(xiàn)方式有所了解。 第三章 圖像變換 3.3 頻域變換的一般表達(dá)式頻域變換的一般表達(dá)式 一一. 可分離變換可分離變換 二維傅立葉變換可用通用的關(guān)系式來表示： 10101010),(),(),(),(),(),(NvMuNyMxvuyxhvuFyxfvuyxgyxfvuF(3-36) (3-37) 式中：x, u=0, 1, 2, , M1；y, v=0, 1, 2, , N1；g(x,y,u,v)和h(x,y,u,v)分別稱為正向變

25、換核和反向變換核。 第三章 圖像變換 如果 g(x, y, u, v)=g1(x, u)g2（y, v） (3-38)h(x, y, u, v)=h1(x, u)h2(y, v)(3-39) 則稱正、反變換核是可分離的。進(jìn)一步，如果g1和g2，h1和h2在函數(shù)形式上一樣，則稱該變換核是對稱的。 二維傅立葉變換對是式（3-36）和式（3-37）的一個特殊情況， 它們的核為 NvyjMuxjNvyMuxjeeevuyxg222),(NvyjMuxjNvyMuxjeNeMeMNvuyxh222111),(第三章 圖像變換 可見，它們都是可分離的和對稱的。 如前所述，二維傅立葉變換可以利用變換核的可分

26、離性， 用兩次一維變換來實(shí)現(xiàn)，即可先對f(x, y)的每一行進(jìn)行一維變換得到F(x, v)，再沿F(x, v)每一列取一維變換得到變換結(jié)果F(u, v)。對于其他的圖像變換，只要其變換核是可分離的，同樣也可用兩次一維變換來實(shí)現(xiàn)。 如果先對f(x, y)的每一列進(jìn)行一維變換得到F(y, u)，再沿F(y, u)每一行取一維變換得到F(u, v)，其最終結(jié)果是一樣的。該結(jié)論對反變換核也適用。 第三章 圖像變換 二二. 圖像變換的矩陣表示圖像變換的矩陣表示 數(shù)字圖像都是實(shí)數(shù)矩陣， 設(shè)f(x, y)為MN的圖像灰度矩陣， 通常為了分析、推導(dǎo)方便，可將可分離變換寫成矩陣的形式： F=PfQF=P-1FQ

27、-1 其中，F(xiàn)、f是二維MN的矩陣；P是MM矩陣；Q是NN矩陣。 1010),(),(),(),(NyMxvyQyxfuxPvuF(3-44) (3-43) (3-42) 式中，u=0, 1, 2, , M1，v=0, 1, 2, , N1。 第三章 圖像變換 對二維離散傅立葉變換，則有 NvyjMuxjevxgvyPeuxguxP/22/21),(),(),(),(3-45) (3-46) 實(shí)踐中，除了DFT變換之外，還采用許多其他的正交變換。例如：離散余弦變換、沃爾什-哈達(dá)瑪變換、K-L變換等，下面將對常用的變換作一簡要介紹。 第三章 圖像變換 3.4 離散余弦變換（離散余弦變換（DCT）

28、 離散余弦變換（Discrete Cosine Transform， DCT）的變換核為余弦函數(shù)。DCT除了具有一般的正交變換性質(zhì)外， 它的變換陣的基向量能很好地描述人類語音信號和圖像信號的相關(guān)特征。因此，在對語音信號、圖像信號的變換中，DCT變換被認(rèn)為是一種準(zhǔn)最佳變換。近年頒布的一系列視頻壓縮編碼的國際標(biāo)準(zhǔn)建議中，都把DCT作為其中的一個基本處理模塊。除此之外， DCT還是一種可分離的變換。 第三章 圖像變換 一一. 一維離散余弦變換一維離散余弦變換 一維DCT的變換核定義為 NuxNuCuxg2) 12(cos2)(),(式中，x, u=0, 1, 2, , N1； 其他1021)(uuC

29、(3-47) (3-48) 一維DCT定義如下： 設(shè)f(x)|x=0, 1, , N-1為離散的信號列。 102) 12(cos)(2)()(NxNuxxfNuCuF(3-49) 式中，u, x=0, 1, 2, , N1。第三章 圖像變換 將變換式展開整理后， 可以寫成矩陣的形式， 即 F=Gf （3-50） 其中 )2/) 12)(1cos()2/3)(1cos()2/) 1cos(/2)2/) 12cos()2/6cos()2/cos(/2)2/) 12cos()2/3cos()2/cos(/2111/1NNNNNNNNNNNNNNNNNNNG(3-51) 第三章 圖像變換 一維DCT的

30、逆變換IDCT定義為 102) 12(cos)()(2)(NuNuxuFuCNxf(3-52) 式中， x, u=0, 1, 2, , N1?？梢娨痪SDCT的逆變換核與正變換核是相同的。 第三章 圖像變換 二二. 二維離散余弦變換二維離散余弦變換 考慮到兩個變量，很容易將一維DCT的定義推廣到二維DCT。其正變換核為 NvyMuxvCuCMNvuyxg2) 12(cos2) 12(cos)()(2),(3-53) 式中，C(u)和C(v)的定義同式（3-48）；x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 二維DCT定義如下：設(shè)f(x, y)為MN的數(shù)字圖像矩

31、陣，則 NvyMuxvCuCyxfMNvuFMxNy2) 12(cos2) 12(cos)()(),(2),(1010(3-54) 第三章 圖像變換 式中： x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 二維DCT逆變換定義如下： NvyMuxvuFvCuCMNyxfMuNv2) 12(cos2) 12(cos),()()(2),(1010(3-55) 式中：x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 類似一維矩陣形式的DCT，可以寫出二維DCT的矩陣形式如下： F=GfGT (3-56)第三章 圖像變換 同時，由式(3-5

32、5)和式(3-54)可知二維DCT的逆變換核與正變換核相同，且是可分離的，即 NvyvCNMuxuCMvyguxgvuyxg2) 12(cos)(22) 12(cos)(2),(),(),(21(3-57)式中：C(u)和C(v)的定義同式（3-48）； x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 第三章 圖像變換 通常根據(jù)可分離性， 二維DCT可用兩次一維DCT來完成， 其算法流程與DFT類似， 即 ),(),(),(),(),(),(),(vuFvuFvxFFvxFvxFyxfFyxfTTT轉(zhuǎn)置列轉(zhuǎn)置行(3-58) 第三章 圖像變換 三三. 快速離散余弦

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

34、201210121010)(Re2)(Re22) 12(cos)(22) 12(cos)(22) 12(cos)(22) 12(cos022) 12(cos)(22) 12(cos)(2)(式中，Re表示取復(fù)數(shù)的實(shí)部。 第三章 圖像變換 由于 為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)(NxNxujeexf0)()(uFuFeu=0, 1, 2, , N-1u=N, N+1, , 2N-1 (3-6

35、2) 第三章 圖像變換 由式(3-52)可得，DCT的IDCT為 1202)12(21212)12(121)(Re2)0(21)(Re2)0(12) 12(cos)(2)0(1)(NuNuxjNujeeNuNuxjeeNueeeeuFNFNNeuFNFNNuxuFNFNxf（3-63） 由式（3-63）可見，IDCT可由 的2N點(diǎn)的IDFT來實(shí)現(xiàn)。 NujeeuF2)(第三章 圖像變換 最后要注意的是二維DCT的頻譜分布， 其譜域分布與DFT相差一倍，如圖3-11所示。 從圖中可以看出，對于DCT而言，(0, 0)點(diǎn)對應(yīng)于頻譜的低頻成分，(N-1, N-1)點(diǎn)對應(yīng)于高頻成分，而同階的DFT中，

36、 (N2, N2)點(diǎn)對應(yīng)于高頻成分（注： 此頻譜圖中未作頻譜中心平移）。 由于DFT和IDFT已有快速算法FFT和IFFT，因此可用它們實(shí)現(xiàn)快速DCT和IDCT算法FCT及IFCT。不過，由于FFT及IFFT中要涉及到復(fù)數(shù)運(yùn)算， 因此這種FCT及IFCT算法并不是最佳的。 第三章 圖像變換 圖3-11 DFT和DCT的頻譜分布（a）DFT頻譜分布； （b） DCT頻譜分布 第三章 圖像變換 DFT總結(jié)：總結(jié)：1. 空間域空間域 頻率域頻率域2. 變換后在頻率域的處理運(yùn)算簡單（高通，低變換后在頻率域的處理運(yùn)算簡單（高通，低通等。）通等。）3. 變換后有利于對圖像的特征提取。變換后有利于對圖像的特

37、征提取。4. 變換算法是全局處理，即變換算法是全局處理，即F(u,v)是是f(x,y)整體整體運(yùn)算所得運(yùn)算所得5. 圖像顯示常用圖像顯示常用lg(1+|F(u,v)|)顯示其傅立葉譜，顯示其傅立葉譜，目的是更好的顯示高頻，利于對圖像頻譜的視目的是更好的顯示高頻，利于對圖像頻譜的視覺理解覺理解第三章 圖像變換 矩形函數(shù)矩形函數(shù)圖像表示圖像表示傅立葉譜傅立葉譜6. 利用傅立葉變換的性質(zhì)，進(jìn)行平移，利用傅立葉變換的性質(zhì)，進(jìn)行平移，F(xiàn)DFT等。等。第三章 圖像變換 31,.,1 , 0 ),10cos()95. 0(nnnxn考慮信號：xn的DFT頻譜：xn的DCT譜：可以看出，DCT主要能量比DFT

38、更集中在低頻，這樣，就可以舍棄較高序段，實(shí)現(xiàn)信號的壓縮。DCT的能量壓縮特性第三章 圖像變換 例：實(shí)際圖像的DCT變換結(jié)果左圖是一幅原始圖象，右圖是對左圖的離散余弦變換結(jié)果（變換幅值）。右圖左上角對應(yīng)低頻分量，由圖可見，左圖中的大部分能量在低頻部分。第三章 圖像變換 DCT在JEPG中的應(yīng)用DCT的能量集中特性使得其稱為靜止圖像壓縮標(biāo)準(zhǔn)JEPG(Joint Photographic Experts Group)算法的核心。在JEPG算法中，輸入圖像被分為88(或1616)模塊，然后對每一模塊計(jì)算二維DCT，接著對DCT系數(shù)進(jìn)行處理，保留其中的低頻(主要能量部分)，舍棄高頻部分(幅值近似0的部分

39、)。這一過程也就是讓每一模塊的DCT系數(shù)乘以模板：1111100011110000111000001100000010000000000000000000000000000000如左圖所示模板，只保留了64個DCT系數(shù)中的15個，也即舍棄了77%的DCT系數(shù)。第三章 圖像變換 例：DCT壓縮效果保留15個DCT系數(shù)，可以得到壓縮前后的對比：可以看出，雖然舍棄了大部分系數(shù)，但由于保留了主要能量，因此圖像依然保持著相當(dāng)?shù)那逦?。第三?圖像變換 實(shí)現(xiàn)前例的MATLAB程序x2=im2double(x); T=dctmtx(8);B=blkproc(x2,8 8,P1*x*P2,T,T);%計(jì)算各8

40、8模塊的DCTmask=1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; %通過模板中1和0的位置，就可以對DCT系數(shù)進(jìn)行取舍B2=blkproc(B,8 8,P1.*x,mask); %應(yīng)用模板，舍棄大部分DCT低幅系數(shù)I2=blkproc(B2,8 8,P1*x*P2,T,T); %DCT反變換figure;imshow(x2);figure;imshow(I2);第三章 圖像變換 不

41、同模板的壓縮效果111110001111000011100000110000001000000000000000000000000000000011111110111111001111100011110000111000001100000010000000000000001110000011000000100000000000000000000000000000000000000000000000第三章 圖像變換 3.5 離散沃爾什離散沃爾什-哈達(dá)瑪變換（哈達(dá)瑪變換（WHT） 一一. 一維離散沃爾什一維離散沃爾什-哈達(dá)瑪變換哈達(dá)瑪變換 1. 沃爾什函數(shù)沃爾什函數(shù) 沃爾什函數(shù)是1923年由美國數(shù)

42、學(xué)家沃爾什提出的。沃爾什函數(shù)系是一個完備正交函數(shù)系，其值只能取1和1。從排列次序上可將沃爾什函數(shù)分為三種定義方法：一種是按照沃爾什排列來定義（按列率排序）；另一種是按照佩利排列來定義（按自然排序）；第三種是按照哈達(dá)瑪排列來定義。由于哈達(dá)瑪排序的沃爾什函數(shù)是由2n（n=0，1，2，）階哈達(dá)瑪矩陣（Hadamard Matrix）得到的，而哈達(dá)瑪矩陣的最大優(yōu)點(diǎn)在于它具有簡單的遞推關(guān)系， 即高階矩陣可用兩個低階矩陣的克羅內(nèi)克積求得，因此在此只介紹哈達(dá)瑪排列定義的沃爾什變換。(教材：P52，53） 第三章 圖像變換 N=2n(n=0, 1, 2, )階哈達(dá)瑪矩陣每一行的符號變化規(guī)律對應(yīng)于某一個沃爾什函

43、數(shù)的符號變化規(guī)律，即N=2n(n=0, 1, 2, )階哈達(dá)瑪矩陣的每一行對應(yīng)于一個離散沃爾什函數(shù)，哈達(dá)瑪矩陣與沃爾什函數(shù)系不同之處僅僅是行的次序不同。2n階哈達(dá)瑪矩陣有如下形式： 1111 1 21HH111111111111111122224HHHHH(3-64) (3-65) (3-66) 第三章 圖像變換 哈達(dá)瑪矩陣的階數(shù)是按N2n(n0, 1, 2, )規(guī)律排列的，階數(shù)較高的哈達(dá)瑪矩陣，可以利用矩陣的克羅內(nèi)克積運(yùn)算，由低階哈達(dá)瑪矩陣遞推得到，即 2222222222211111NNNNNHHHHHHHHHHHHnnnnnn（3-67） 第三章 圖像變換 矩陣的克羅內(nèi)克積(Kronec

44、ker Product)運(yùn)算用符號記作A B， 其運(yùn)算規(guī)律如下： 設(shè) ,2222111211nnaaaaaaAijiijjbbbabbbbbB212222111211第三章 圖像變換 則 BaBaBaBaBaBaBaBaBaBAmnmmnn212222111211AbAaAbAbAbAbAbAbAbABijiijj212222111211(3-68) (3-69) 第三章 圖像變換 2. 離散沃爾什離散沃爾什-哈達(dá)瑪變換哈達(dá)瑪變換一維離散沃爾什變換定義為 10),()(1)(NxxuWalshxfNuW(3-70) 10),()()(NuxuWalshuWxf一維離散沃爾什逆變換定義為 (3-

45、71) 式中，Walsh(u, x)為沃爾什函數(shù)。若將Walsh(u, x)用哈達(dá)瑪矩陣表示，并將變換表達(dá)式寫成矩陣形式，則式（3-70）和式（3-71）分別為 第三章 圖像變換 ) 1() 1 ()0(1) 1() 1 ()0(NfffHNNWWWN和 ) 1() 1 ()0() 1() 1 ()0(NWWWHNfffN(3-72) (3-73) 式中，HN為N階哈達(dá)瑪矩陣。 第三章 圖像變換 由哈達(dá)瑪矩陣的特點(diǎn)可知，沃爾什-哈達(dá)瑪變換的本質(zhì)上是將離散序列f(x)的各項(xiàng)值的符號按一定規(guī)律改變后，進(jìn)行加減運(yùn)算， 因此，它比采用復(fù)數(shù)運(yùn)算的DFT和采用余弦運(yùn)算的DCT要簡單得多。 第三章 圖像變換

46、 二二. 二維離散沃爾什變換二維離散沃爾什變換 很容易將一維WHT的定義推廣到二維WHT。二維WHT的正變換核和逆變換核分別為 1010),(),(),(1),(NyMxyvWslshxuWalshyxfMNvuW1010),(),(),(),(NvMuyvWslshxuWalshvuWyxf(3-74) 和 (3-75) 式中：x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 第三章 圖像變換 二維離散沃爾什變換的矩陣形式表達(dá)式為： W=H f H 13311331133113311f和 11111111111111112f求這兩個信號的二維WHT。 第三章 圖

47、像變換 根據(jù)題意，式（3-36）中的M=N=4， 其二維WHT變換核為 11111111111111114H第三章 圖像變換 所以 00000000000010021111111111111111133113311331133111111111111111114121W第三章 圖像變換 00000000000000011111111111111111111111111111111111111111111111114122W第三章 圖像變換 再如，圖3-12是一幅數(shù)字圖像及對其進(jìn)行二維WHT變換的結(jié)果。 圖3-12 二維WHT結(jié)果（a）原圖像；（b）WHT結(jié)果 第三章 圖像變換 從以上例子可看出

48、，二維WHT具有能量集中的特性，而且原始數(shù)據(jù)中數(shù)字越是均勻分布，經(jīng)變換后的數(shù)據(jù)越集中于矩陣的邊角上。因此，二維WHT可用于壓縮圖像信息。 第三章 圖像變換 三三. 快速沃爾什變換（快速沃爾什變換（FWHT） 類似于FFT，WHT也有快速算法FWHT， 也可將輸入序列f(x)按奇偶進(jìn)行分組，分別進(jìn)行WHT。FWHT的基本關(guān)系為 )()(21)2()()(21)(uWuWNuWuWuWuWoeoe(3-78) WHT的變換核是可分離和對稱的， 因此二維WHT也可分為兩個一維的WHT分別用FWHT進(jìn)行變換而得到最終結(jié)果，由此便可實(shí)現(xiàn)二維的FWHT。 第三章 圖像變換 綜上所述，WHT是將一個函數(shù)變換

49、成取值為1或1的基本函數(shù)構(gòu)成的級數(shù)，用它來逼近數(shù)字脈沖信號時要比FFT有利。同時， WHT只需要進(jìn)行實(shí)數(shù)運(yùn)算，存儲量比FFT要少得多， 運(yùn)算速度也快得多。因此，WHT在圖像傳輸、 通信技術(shù)和數(shù)據(jù)壓縮中被廣泛使用。 第三章 圖像變換 3.6 小波變換簡介小波變換簡介 一一. 小波變換的理論基礎(chǔ)小波變換的理論基礎(chǔ) 信號分析是為了獲得時間和頻率之間的相互關(guān)系。傅立葉變換提供了有關(guān)頻率域的信息，但有關(guān)時間的局部化信息卻基本丟失。與傅立葉變換不同，小波變換是通過縮放母小波（Mother wavelet）的寬度來獲得信號的頻率特征， 通過平移母小波來獲得信號的時間信息。對母小波的縮放和平移操作是為了計(jì)算小

50、波系數(shù)，這些小波系數(shù)反映了小波和局部信號之間的相關(guān)程度。 第三章 圖像變換 1. 連續(xù)小波變換（連續(xù)小波變換（CWT） 像傅立葉分析一樣，小波分析就是把一個信號分解為將母小波經(jīng)過縮放和平移之后的一系列小波，因此小波是小波變換的基函數(shù)。小波變換可以理解為用經(jīng)過縮放和平移的一系列小波函數(shù)代替傅立葉變換的正弦波和余弦波進(jìn)行傅立葉變換的結(jié)果。 圖3-13表示了正弦波和小波的區(qū)別，由此可以看出，正弦波從負(fù)無窮一直延續(xù)到正無窮，正弦波是平滑而且是可預(yù)測的， 而小波是一類在有限區(qū)間內(nèi)快速衰減到0的函數(shù)，其平均值為0， 小波趨于不規(guī)則、不對稱。 第三章 圖像變換 圖3-13 正弦波和小波（a） 正弦波曲線；

51、(b) 小波曲線 (a)(b)第三章 圖像變換 從小波和正弦波的形狀可以看出，變化劇烈的信號，用不規(guī)則的小波進(jìn)行分析比用平滑的正弦波更好，即用小波更能描述信號的局部特征。 連續(xù)小波變換（Continuous Wavelet Transform， CWT）用下式表示： dttpositionscaletfpositionscaleC),()(),(3-79) 式（3-79）表示小波變換是信號f(x)與被縮放和平移的小波函數(shù)()之積在信號存在的整個期間里求和的結(jié)果。CWT的變換結(jié)果是許多小波系數(shù)C，這些系數(shù)是縮放因子（scale）和平移（positon）的函數(shù)。 第三章 圖像變換 基本小波函數(shù)()

52、的縮放和平移操作含義如下： (1) 縮放。簡單地講， 縮放就是壓縮或伸展基本小波， 縮放系數(shù)越小， 則小波越窄，如圖3-14所示。 圖3-14 小波的縮放操作 OOOf (t)f (t)f (t)tttf (t)(t)；scale1f (t)(2t)；scale0.5f (t)(4t)；scale0.25第三章 圖像變換 (2) 平移。簡單地講，平移就是小波的延遲或超前。在數(shù)學(xué)上， 函數(shù)f(t)延遲k的表達(dá)式為f(t-k)，如圖3-15所示。 圖3-15 小波的平移操作(a) 小波函數(shù)(t)； (b) 位移后的小波函數(shù)(t-k) Ot(t)Ot(t k)(a)(b)第三章 圖像變換 CWT計(jì)算

53、主要有如下五個步驟： 第一步： 取一個小波， 將其與原始信號的開始一節(jié)進(jìn)行比較。 第二步： 計(jì)算數(shù)值C， C表示小波與所取一節(jié)信號的相似程度，計(jì)算結(jié)果取決于所選小波的形狀， 如圖3-16所示。 第三步：向右移動小波，重復(fù)第一步和第二步，直至覆蓋整個信號，如圖3-17所示。 第四步： 伸展小波， 重復(fù)第一步至第三步， 如圖3-18所示。 第三章 圖像變換 圖3-16 計(jì)算系數(shù)值C 原 始 信 號小 波 信 號C 0.0102第三章 圖像變換 圖3-17 計(jì)算平移后系數(shù)值C 原始信號小波信號第三章 圖像變換 圖3-18 計(jì)算尺度后系數(shù)值C 原始信號小波信號C0.2247第三章 圖像變換 第五步：對

54、于所有縮放，重復(fù)第一步至第四步。 小波的縮放因子與信號頻率之間的關(guān)系是：縮放因子scale越小，表示小波越窄，度量的是信號的細(xì)節(jié)變化，表示信號頻率越高；縮放因子scale越大， 表示小波越寬，度量的是信號的粗糙程度，表示信號頻率越低。 第三章 圖像變換 2. 離散小波變換（離散小波變換（DWT） 在每個可能的縮放因子和平移參數(shù)下計(jì)算小波系數(shù)，其計(jì)算量相當(dāng)大， 將產(chǎn)生驚人的數(shù)據(jù)量，而且有許多數(shù)據(jù)是無用的。如果縮放因子和平移參數(shù)都選擇為2j（j0且為整數(shù)）的倍數(shù)， 即只選擇部分縮放因子和平移參數(shù)來進(jìn)行計(jì)算， 就會使分析的數(shù)據(jù)量大大減少。使用這樣的縮放因子和平移參數(shù)的小波變換稱為雙尺度小波變換（Dy

55、adic Wavelet Transform），它是離散小波變換（Discrete Wavelet Transform， DWT）的一種形式。通常離散小波變換就是指雙尺度小波變換。 第三章 圖像變換 執(zhí)行離散小波變換的有效方法是使用濾波器， 該方法是Mallat于1988年提出的，稱為Mallat算法。這種方法實(shí)際上是一種信號分解的方法， 在數(shù)字信號處理中常稱為雙通道子帶編碼。 用濾波器執(zhí)行離散小波變換的概念如圖3-19所示。S表示原始的輸入信號， 通過兩個互補(bǔ)的濾波器組， 其中一個濾波器為低 通 濾 波 器 ， 通 過 該 濾 波 器 可 得 到 信 號 的 近 似 值 A （Approxi

56、mations），另一個為高通濾波器， 通過該濾波器可得到信號的細(xì)節(jié)值D（Detail）。 第三章 圖像變換 圖3-19 小波分解示意圖SAD濾波器組低通高通第三章 圖像變換 在小波分析中，近似值是大的縮放因子計(jì)算的系數(shù)，表示信號的低頻分量，而細(xì)節(jié)值是小的縮放因子計(jì)算的系數(shù)，表示信號的高頻分量。實(shí)際應(yīng)用中，信號的低頻分量往往是最重要的，而高頻分量只起一個修飾的作用。如同一個人的聲音一樣， 把高頻分量去掉后，聽起來聲音會發(fā)生改變，但還能聽出說的是什么內(nèi)容，但如果把低頻分量刪除后，就會什么內(nèi)容也聽不出來了。 第三章 圖像變換 3. 小波重構(gòu)小波重構(gòu) 將信號的小波分解的分量進(jìn)行處理后，一般還要根據(jù)需

57、要把信號恢復(fù)出來，也就是利用信號的小波分解的系數(shù)還原出原始信號，這一過程稱為小波重構(gòu)（Wavelet Reconstruction）或叫做小波合成（Wavelet Synthesis）。這一合成過程的數(shù)學(xué)運(yùn)算叫做逆離散小波變換（Inverse Discrete Wavelet Transform， IDWT）。 第三章 圖像變換 重構(gòu)近似信號與細(xì)節(jié)信號重構(gòu)近似信號與細(xì)節(jié)信號 由小波分解的近似系數(shù)和細(xì)節(jié)系數(shù)可以重構(gòu)出原始信號。同樣，可由近似系數(shù)和細(xì)節(jié)系數(shù)分別重構(gòu)出信號的近似值或細(xì)節(jié)值，這時只要近似系數(shù)或細(xì)節(jié)系數(shù)置為零即可。 第三章 圖像變換 圖3-23 重構(gòu)近似和細(xì)節(jié)信號示意（a） 重構(gòu)近似信號

58、； (b) 重構(gòu)細(xì)節(jié)信號 A1HL1000個樣點(diǎn)0約500個0cA1約500個近似分量(a)D1HL1000個樣點(diǎn)(b)約500個0約500個近似分量0cD1第三章 圖像變換 二二. 離散小波變換在圖像處理中的應(yīng)用簡介離散小波變換在圖像處理中的應(yīng)用簡介 1. 用小波變換進(jìn)行圖像分解用小波變換進(jìn)行圖像分解 使用小波變換完成圖像分解的方法很多，例如，均勻分解（Uniform decomposition）、非均勻分解（Non-uniform decomposition）、八帶分解（Octave-band decomposition）、小波包分解（Wavelet-packer decomposition）等。其中八帶分解是使用最廣的一種分解方法，這種分解方法把低頻部分分解成比較窄的頻帶，而對每一級分解得到的高頻部分不再進(jìn)一步進(jìn)行分解。圖3-28為八帶分解示意圖， 用于分解的原始圖像采用Matlab提供的預(yù)存圖像文件woman2.mat，小波基函數(shù)為“haar”小波。圖3-28（c）是用Matlab的小波工具箱編程進(jìn)行分解得到的圖像。 第三章 圖像變換 圖3-28 八帶分解示意圖(a) 一次二維DWT； (b) 兩次二維DWT； (c) Woman二級分解圖 A(近似值)H(垂直細(xì)節(jié))V(垂直