數(shù)字圖像處理 第三章 圖像變換

1、Slide 1第第3 3章章 圖像變換圖像變換Slide 2內(nèi)容提要l主要介紹圖像處理中常用的二維離散變換的定義、性質(zhì)、實(shí)現(xiàn)方法及應(yīng)用。l經(jīng)典變換離散傅里葉變換（DFT）l離散余弦變換（DCT）l離散沃爾什-哈達(dá)瑪變換（DWT）lK-L變換（KLT）l離散小波變換（DWT）及其應(yīng)用Slide 3知識(shí)要點(diǎn)知識(shí)要點(diǎn) l余弦型變換：余弦型變換：l傅里葉變換和余弦變換。傅里葉變換和余弦變換。l方波型變換：方波型變換：l沃爾什沃爾什- -哈達(dá)瑪變換。哈達(dá)瑪變換。l基于特征向量的變換：基于特征向量的變換：lK-LK-L變換。變換。l從哈爾變換、短時(shí)傅里葉變換到小波變換。從哈爾變換、短時(shí)傅里葉變換到小波變換

2、。l各種變換的定義和有關(guān)快速算法及實(shí)現(xiàn)方法。各種變換的定義和有關(guān)快速算法及實(shí)現(xiàn)方法。Slide 43.1 3.1 二維離散傅里葉變換（二維離散傅里葉變換（DFTDFT）3.1.1 二維連續(xù)傅里葉變換二維連續(xù)傅里葉變換l定義：設(shè) f (x, y) 是獨(dú)立變量x和y 的函數(shù)，且在 上絕對(duì)可積，則定義積分 為二維連續(xù)函數(shù) f (x, y) 的傅里葉變換，并定義 為F (u, v) 的反變換。 f (x, y) 和F (u, v) 為傅里葉變換對(duì)。 |( , )|d df x yx y j2() ( , )( , )ed dux vyf x yF u vu vSlide 5【例【例3.1】求圖3.1所

3、示函數(shù)的傅里葉變換。 他其, 0,),(YyXxAyxf解：解： j2()j2j2 0 0jj( , )( , )ed dededsin()sin()eeXYux vyuxvyuxvyF u vf x yx yAxyuXvYAXYuXvYsin() sin()( , )uXvYF u vAXYuXvY圖3.1 二維信號(hào)f (x, y) 其幅度譜為其幅度譜為Slide 6二維信號(hào)的頻譜圖（a）信號(hào)的頻譜圖）信號(hào)的頻譜圖 （b）圖（）圖（a）的灰度圖）的灰度圖圖圖3.2 信號(hào)的頻譜圖信號(hào)的頻譜圖 Slide 73.1.2 3.1.2 二維離散傅里葉變換二維離散傅里葉變換l尺寸為MN的離散圖像函數(shù)的

4、DFT 1010)/(2),(1),(MxNyNvyMuxjeyxfMNvuFl反變換可以通過(guò)對(duì)F(u,v) 求IDFT獲得 1010)/(2),(),(MuNvNvyMuxjevuFyxfSlide 8lF(u, v)即為f (x, y)的頻譜，通常是復(fù)數(shù)：( , )( , )j ( , )F u vR u vI u v221/2|( , )| ( , )( , )F u vR u vIu v( , )( , )arctan( , )I u vu vR u v幅度譜幅度譜 相位譜相位譜 Slide 9DFT幅度譜的特點(diǎn)幅度譜的特點(diǎn) l 頻譜的直流成分說(shuō)明在頻譜原點(diǎn)的傅頻譜的直流成分說(shuō)明在頻譜

5、原點(diǎn)的傅里葉變換里葉變換F(0, 0)等于圖像的平均灰度級(jí)。等于圖像的平均灰度級(jí)。l 幅度譜幅度譜|F(u, v)|關(guān)于原點(diǎn)對(duì)稱(chēng)。關(guān)于原點(diǎn)對(duì)稱(chēng)。l 圖像圖像f (x, y)平移后，幅度譜不發(fā)生變化，平移后，幅度譜不發(fā)生變化，僅有相位發(fā)生變化。僅有相位發(fā)生變化。Slide 103.1.3 3.1.3 二維離散傅里葉變換的性質(zhì)二維離散傅里葉變換的性質(zhì)l1 1變換可分離性l二維DFT可以用兩個(gè)可分離的一維DFT之積表示：11j2/j2/0011( , )e( , )eMNux Mvy NxyF u vf x yMN1j2/01( , )eMux MxF x vM式中，式中，1j2/01( , )(

6、, )eNvy NyF x vf x yN結(jié)論：結(jié)論：（1）二維變換可以通過(guò)先進(jìn)行二維變換可以通過(guò)先進(jìn)行行變換行變換再進(jìn)行再進(jìn)行列變換列變換的兩的兩次一維變換來(lái)實(shí)現(xiàn)。（次一維變換來(lái)實(shí)現(xiàn)。（2 2）也可以通過(guò)先求）也可以通過(guò)先求列變換列變換再求再求行變換行變換得到得到二維傅里葉變換。二維傅里葉變換。 Slide 11圖圖3.3 用兩次一維用兩次一維DFT計(jì)算二維計(jì)算二維DFT Slide 122 2周期性、共軛對(duì)稱(chēng)性及頻譜中心化l周期性和共軛對(duì)稱(chēng)性來(lái)了許多方便。l首先來(lái)看一維的情況。l設(shè)有一矩形函數(shù),求出它的傅里葉變換： ,0( )0,AxXf x其他jsin( )euXuXF uAXuXsin

7、( )uXF uAXuXSlide 13在進(jìn)行在進(jìn)行DFT之前用輸入信號(hào)乘以（之前用輸入信號(hào)乘以（-1）x，便可，便可以在一個(gè)周期的變換中求得一個(gè)完整的頻譜。以在一個(gè)周期的變換中求得一個(gè)完整的頻譜。 （a）幅度譜）幅度譜 （b）原點(diǎn)平移后的幅度譜）原點(diǎn)平移后的幅度譜 圖圖3.4 頻譜圖頻譜圖 2211j(/2)j0011(/2)( )e( 1)( )eNNx u NxuxNNxxF uNf xf xNNSlide 14 用(-1)x+y 乘以輸入的圖像函數(shù)，則有：)2/, 2/() 1)(,(NvMuFyxfDFTyxl原點(diǎn)原點(diǎn)F(0,0)被設(shè)置在被設(shè)置在 u = M/2和和v = N/2上。

8、上。l如果是一幅圖像，在原點(diǎn)的傅里葉變換如果是一幅圖像，在原點(diǎn)的傅里葉變換F(0,0)等于圖像的平均灰度級(jí)，也稱(chēng)作頻率等于圖像的平均灰度級(jí)，也稱(chēng)作頻率譜的直流成分。譜的直流成分。 Slide 153離散卷積定理l設(shè)f (x, y)和g(x, y) 是大小分別為AB和CD的兩個(gè)數(shù)組，則它們的離散卷積定義為DFT ( , )* ( , )( , ) ( , )f x yg x yF u v G u vl卷積定理卷積定理1010),(),(),(*),(MmNnnymxgnmfyxgyxfSlide 16【例3.2】用MATLAB實(shí)現(xiàn)圖像的傅里葉變換。l為了增強(qiáng)顯示效果，用對(duì)數(shù)對(duì)頻譜的幅度進(jìn)行壓縮，

9、然為了增強(qiáng)顯示效果，用對(duì)數(shù)對(duì)頻譜的幅度進(jìn)行壓縮，然后將頻譜幅度的對(duì)數(shù)值用在后將頻譜幅度的對(duì)數(shù)值用在010之間的值進(jìn)行顯示。之間的值進(jìn)行顯示。l【解】【解】MATLAB程序如下：程序如下：lI = imread(pout.tif);%讀入圖像讀入圖像limshow(I); %顯示圖像顯示圖像lF1 = fft2(I); %計(jì)算二維傅里葉變換計(jì)算二維傅里葉變換lfigure, imshow(log(abs(F1)+1),0 10); l%顯示對(duì)數(shù)變換后的頻譜圖顯示對(duì)數(shù)變換后的頻譜圖lF2 = fftshift(F1); %將直流分量移到頻譜圖的中心將直流分量移到頻譜圖的中心lfigure, ims

10、how(log(abs(F2)+1),0 10); l%顯示對(duì)數(shù)變換后中心化的頻譜圖顯示對(duì)數(shù)變換后中心化的頻譜圖Slide 17（a）原始圖像）原始圖像 (b) 中心化前的頻譜圖中心化前的頻譜圖 (c) 中心化后的頻譜中心化后的頻譜圖圖3.6 圖像頻譜的中心化圖像頻譜的中心化Slide 18 （a）原始圖像 （b）圖像的頻譜圖 （c）中心化的頻譜圖圖3.7 傅里葉變換Slide 191.4 快速傅里葉變換快速傅里葉變換(FFT) 隨著計(jì)算機(jī)技術(shù)和數(shù)字電路的迅速發(fā)展，在隨著計(jì)算機(jī)技術(shù)和數(shù)字電路的迅速發(fā)展，在信號(hào)處理中使用計(jì)算機(jī)和數(shù)字電路的趨勢(shì)愈信號(hào)處理中使用計(jì)算機(jī)和數(shù)字電路的趨勢(shì)愈加明顯。離散傅

11、里葉變換已成為數(shù)字信號(hào)處加明顯。離散傅里葉變換已成為數(shù)字信號(hào)處理的重要工具。理的重要工具。Slide 20 快速傅里葉變換并不是一種新的變換，它是快速傅里葉變換并不是一種新的變換，它是離散傅里葉變換的一種算法。離散傅里葉變換的一種算法。這種方法是在分析這種方法是在分析離散傅里葉變換中的多余運(yùn)算的基礎(chǔ)上，進(jìn)而消離散傅里葉變換中的多余運(yùn)算的基礎(chǔ)上，進(jìn)而消除這些重復(fù)工作的思想指導(dǎo)下得到的，所以在運(yùn)除這些重復(fù)工作的思想指導(dǎo)下得到的，所以在運(yùn)算中大大節(jié)省了工作量，達(dá)到了快速運(yùn)算的目的。算中大大節(jié)省了工作量，達(dá)到了快速運(yùn)算的目的。Slide 21對(duì)于一個(gè)有限長(zhǎng)序列對(duì)于一個(gè)有限長(zhǎng)序列 ，它的傅里葉變換由下式

12、表示它的傅里葉變換由下式表示 ( )()x nnN01X mx n emNnNjmnN( )( ), ,0120 11(347) 令令 221,jjNNWeWeSlide 22x nNX m WnNmn( )( )101將正變換式（將正變換式（348）展開(kāi)可得到如下算式）展開(kāi)可得到如下算式X mx n WnNmn( )( )01因此，傅里葉變換對(duì)可寫(xiě)成下式因此，傅里葉變換對(duì)可寫(xiě)成下式 (349） (348) Slide 23XxWxWx NWXxWxWx NWXxWxWx NWX NxWxWx NWNNNNNNN( )( )( )()( )( )( )()( )( )( )()()( )( )

13、()()()()()()()()00111011201110110001011011112021211 01 111 (350) Slide 24) 1()2() 1 ()0( )1()2() 1 ()0() 1)(1(1 ) 1(0) 1() 1(22120) 1( 11110) 1(00100NxxxxWWWWWWWWWWWWNXXXXNNNNNNN上面的方程式（350）可以用矩陣來(lái)表示(351) Slide 25從上面的運(yùn)算顯然可以看出，要得到每一個(gè)頻率分從上面的運(yùn)算顯然可以看出，要得到每一個(gè)頻率分量，需進(jìn)行量，需進(jìn)行N次乘法和次乘法和N-1次加法運(yùn)算。要完成整個(gè)次加法運(yùn)算。要完成整個(gè)變

14、換需要變換需要 次乘法和次乘法和N(N-1)次加法運(yùn)算。當(dāng)序列次加法運(yùn)算。當(dāng)序列較長(zhǎng)時(shí)，必然要花費(fèi)大量的時(shí)間。較長(zhǎng)時(shí)，必然要花費(fèi)大量的時(shí)間。 N2觀察上述系數(shù)矩陣，發(fā)現(xiàn)觀察上述系數(shù)矩陣，發(fā)現(xiàn) 是以為是以為N周期的，周期的，即即 Wmn()()mlNnhNm nWW(352) Slide 26jWjWNN434,WWNN 112, 例如，當(dāng)例如，當(dāng)N=8時(shí)，其周期性如圖時(shí)，其周期性如圖36所示。由于所示。由于 所以，當(dāng)所以，當(dāng)N=8時(shí)，時(shí)，可得：可得：WeNjNjN222cossinSlide 276W 5W 7W 4W 0W 3W 1W 2W 圖 36 N=8 時(shí) 的周期性和對(duì)稱(chēng)性的周期性和對(duì)

15、稱(chēng)性 mnWSlide 28可見(jiàn)，離散傅里葉變換中的乘法運(yùn)算有許多重復(fù)可見(jiàn)，離散傅里葉變換中的乘法運(yùn)算有許多重復(fù)內(nèi)容。內(nèi)容。1965年庫(kù)利圖基提出把原始的年庫(kù)利圖基提出把原始的N點(diǎn)序列依點(diǎn)序列依次分解成一系列短序列，然后，求出這些短序列的次分解成一系列短序列，然后，求出這些短序列的離散傅里葉變換，以此來(lái)減少乘法運(yùn)算。離散傅里葉變換，以此來(lái)減少乘法運(yùn)算。Slide 29 快速傅里葉變換簡(jiǎn)稱(chēng)快速傅里葉變換簡(jiǎn)稱(chēng)FFT。算法根據(jù)分解的特點(diǎn)。算法根據(jù)分解的特點(diǎn)一般有兩類(lèi)，一般有兩類(lèi)，一類(lèi)是按時(shí)間分解一類(lèi)是按時(shí)間分解，一，一類(lèi)是按頻率類(lèi)是按頻率分解分解。下面介紹一下的基本形式及運(yùn)算蝶。下面介紹一下的基本形

16、式及運(yùn)算蝶式流程圖。式流程圖。 Slide 301.4. 基數(shù)按時(shí)間分解的算法基數(shù)按時(shí)間分解的算法把把 x(n) 分成偶數(shù)點(diǎn)和奇數(shù)點(diǎn)分成偶數(shù)點(diǎn)和奇數(shù)點(diǎn),即即:這種算法的流程圖如圖這種算法的流程圖如圖37所示：圖所示：圖(a)輸入為順序輸入為順序的，運(yùn)算結(jié)果是亂序的；圖的，運(yùn)算結(jié)果是亂序的；圖(b)輸入為亂序的，運(yùn)算輸入為亂序的，運(yùn)算結(jié)果是順序的。結(jié)果是順序的。x nxnnNxnxnnN1220 121210 121( )(), ,;( )(), , .Slide 31蝶式運(yùn)算流程圖 (按時(shí)間分解) Slide 32蝶式運(yùn)算流程圖 (按時(shí)間分解)Slide 33Slide 341.4. 基數(shù)基數(shù)

17、2按頻率分解的算法按頻率分解的算法 這種分解方法是直接把序列分為前這種分解方法是直接把序列分為前 點(diǎn)和后點(diǎn)和后 點(diǎn)兩個(gè)序列，即點(diǎn)兩個(gè)序列，即 N2N212, 2 , 1 , 0 2)(12, 2 , 1 , 0 )()(21NnNnxnxNnnxnx(355) Slide 35Slide 361.5 用計(jì)算機(jī)實(shí)現(xiàn)快速付傅里葉變換用計(jì)算機(jī)實(shí)現(xiàn)快速付傅里葉變換 利用利用 FFT 蝶式流程圖算法在計(jì)算機(jī)上實(shí)現(xiàn)快速傅蝶式流程圖算法在計(jì)算機(jī)上實(shí)現(xiàn)快速傅里葉變換必須解決如下問(wèn)題：里葉變換必須解決如下問(wèn)題：1）、）、 迭代次數(shù)迭代次數(shù) r 的確定；的確定；2）、對(duì)偶節(jié)點(diǎn)的計(jì)算；）、對(duì)偶節(jié)點(diǎn)的計(jì)算；3）、加權(quán)

18、系數(shù)）、加權(quán)系數(shù) 的計(jì)算；的計(jì)算；4）、重新排序問(wèn)題。）、重新排序問(wèn)題。WNPSlide 37(1) 迭代次數(shù)迭代次數(shù)r的確定的確定 由蝶式流程圖可見(jiàn)，迭代次數(shù)由蝶式流程圖可見(jiàn)，迭代次數(shù) r 與與 N 有關(guān)。值有關(guān)。值可由下式確定可由下式確定 Nr2log(359) 式中式中 N 是變換序列的長(zhǎng)度。對(duì)于前述基數(shù)是變換序列的長(zhǎng)度。對(duì)于前述基數(shù)2的蝶式的蝶式流程圖是流程圖是2的整數(shù)次冪。例如，序列長(zhǎng)度為的整數(shù)次冪。例如，序列長(zhǎng)度為8則要三則要三次迭代，序列長(zhǎng)度為次迭代，序列長(zhǎng)度為16時(shí)就要時(shí)就要4次迭代等等。次迭代等等。Slide 38(2) 對(duì)偶節(jié)點(diǎn)的計(jì)算對(duì)偶節(jié)點(diǎn)的計(jì)算 在流程圖中把標(biāo)有在流程圖

19、中把標(biāo)有 的點(diǎn)稱(chēng)為節(jié)點(diǎn)。其中下標(biāo)的點(diǎn)稱(chēng)為節(jié)點(diǎn)。其中下標(biāo) l為列數(shù)，也就是第幾次迭代，例如，為列數(shù)，也就是第幾次迭代，例如， 則說(shuō)明它則說(shuō)明它是第一次迭代的結(jié)果。是第一次迭代的結(jié)果。 代表流程圖中的行數(shù)，代表流程圖中的行數(shù)，也就是序列的序號(hào)數(shù)。其中每一節(jié)點(diǎn)的值均是用前也就是序列的序號(hào)數(shù)。其中每一節(jié)點(diǎn)的值均是用前一節(jié)點(diǎn)對(duì)計(jì)算得來(lái)的。一節(jié)點(diǎn)對(duì)計(jì)算得來(lái)的。)(kxlx k1( )kSlide 39 在蝶式流程圖中，在蝶式流程圖中，把具有相同來(lái)源的一對(duì)節(jié)把具有相同來(lái)源的一對(duì)節(jié)點(diǎn)叫做對(duì)偶節(jié)點(diǎn)。點(diǎn)叫做對(duì)偶節(jié)點(diǎn)。如如: 和和 就是一就是一對(duì)對(duì)偶節(jié)點(diǎn)，因?yàn)樗鼈兙鶃?lái)源于對(duì)對(duì)偶節(jié)點(diǎn)，因?yàn)樗鼈兙鶃?lái)源于 x(0) 和和

20、 x(4) 。 對(duì)對(duì)偶節(jié)點(diǎn)的計(jì)算也就是求出在每次迭代中對(duì)偶節(jié)點(diǎn)偶節(jié)點(diǎn)的計(jì)算也就是求出在每次迭代中對(duì)偶節(jié)點(diǎn)的間隔或者節(jié)距。的間隔或者節(jié)距。x10( )x14( )Slide 40 由流程圖可見(jiàn)，第一次迭代的節(jié)距為由流程圖可見(jiàn)，第一次迭代的節(jié)距為 ，第，第二次迭代的節(jié)距為二次迭代的節(jié)距為 ，第三次迭代的節(jié)距為，第三次迭代的節(jié)距為 等等。由以上分析可得到如下對(duì)偶節(jié)點(diǎn)的等等。由以上分析可得到如下對(duì)偶節(jié)點(diǎn)的計(jì)算方法。計(jì)算方法。4NN2N23Slide 41)(kxl如果某一節(jié)點(diǎn)為如果某一節(jié)點(diǎn)為 ，那么，它的對(duì)偶節(jié)點(diǎn)為，那么，它的對(duì)偶節(jié)點(diǎn)為llNkx2式中式中 l 是表明第幾次迭代的數(shù)字，是表明第幾次迭代

21、的數(shù)字，k 是序列的序是序列的序號(hào)數(shù)，號(hào)數(shù)，N 是序列長(zhǎng)度。是序列長(zhǎng)度。(360) Slide 42例：如果序列長(zhǎng)度例：如果序列長(zhǎng)度N=8，求，求 的對(duì)偶節(jié)點(diǎn)的對(duì)偶節(jié)點(diǎn)。 x21( )可利用式（可利用式（360）計(jì)算，得）計(jì)算，得)3()1 ()1 ()3(281210812222xWxxxxNkxll則則xxW x21841313( )( )( )其正確性不難由流程圖來(lái)驗(yàn)證。其正確性不難由流程圖來(lái)驗(yàn)證。Slide 43（3）加權(quán)系數(shù)）加權(quán)系數(shù) 的計(jì)算的計(jì)算 WNP 的計(jì)算主要是確定的計(jì)算主要是確定 P值。值。P 值可用下述方法值可用下述方法求得求得。 WNP (1)把把k值寫(xiě)成值寫(xiě)成r位的二

22、進(jìn)制數(shù)（位的二進(jìn)制數(shù)（k 是序列的序號(hào)數(shù)，是序列的序號(hào)數(shù)，r 是迭代次數(shù)）；是迭代次數(shù)）；Slide 44 （）把這個(gè)二進(jìn)制數(shù)右移（）把這個(gè)二進(jìn)制數(shù)右移 r-l 位，并把左邊的空位位，并把左邊的空位補(bǔ)零（結(jié)果仍為補(bǔ)零（結(jié)果仍為 r 位）；位）； （）把這個(gè)右移后的二進(jìn)制數(shù)進(jìn)行比特倒轉(zhuǎn)；（）把這個(gè)右移后的二進(jìn)制數(shù)進(jìn)行比特倒轉(zhuǎn)； （）把這比特倒轉(zhuǎn)后的二進(jìn)制數(shù)翻成十進(jìn)制數(shù)就（）把這比特倒轉(zhuǎn)后的二進(jìn)制數(shù)翻成十進(jìn)制數(shù)就得到得到p值。值。Slide 45例：求例：求 的加的加 權(quán)系數(shù)權(quán)系數(shù) 。x22( )WP8 由由 和和 可知可知: :k=2=2，l=2=2，n=8=8， 則則x22( )WP8rNlo

23、glog2283 （）因?yàn)椋ǎ┮驗(yàn)閗=2=2，所以寫(xiě)成二進(jìn)制數(shù)為，所以寫(xiě)成二進(jìn)制數(shù)為010010； （）（）r- -l=3-2=1=3-2=1，把，把010010右移一位得到右移一位得到001001；Slide 46 （）把（）把001001做位序顛倒，即做比特倒轉(zhuǎn)，得到做位序顛倒，即做比特倒轉(zhuǎn)，得到100100； （）把（）把100100譯成十進(jìn)制數(shù)，得到譯成十進(jìn)制數(shù)，得到4 4，所以，所以 P=4=4， 的加權(quán)值為的加權(quán)值為 。W84x22( )Slide 47 結(jié)合對(duì)偶節(jié)點(diǎn)的計(jì)算，可以看出結(jié)合對(duì)偶節(jié)點(diǎn)的計(jì)算，可以看出 具有下述規(guī)具有下述規(guī)律：律：如果某一節(jié)點(diǎn)上的加權(quán)系數(shù)為如果某一節(jié)點(diǎn)上的

24、加權(quán)系數(shù)為 ，則其對(duì)偶，則其對(duì)偶節(jié)點(diǎn)的加權(quán)系數(shù)必然是節(jié)點(diǎn)的加權(quán)系數(shù)必然是 ，而且，而且 WNPWNPWNPN2WWNPNPN 2Slide 48所以一對(duì)對(duì)偶節(jié)點(diǎn)可用下式計(jì)算所以一對(duì)對(duì)偶節(jié)點(diǎn)可用下式計(jì)算 llPNllNkxWkxkx2)(11llPNlllNkxWkxNkx2)(211(361) (362) Slide 49（4）重新排序）重新排序 由蝶式流程圖可見(jiàn)，如果序列由蝶式流程圖可見(jiàn)，如果序列 x(n) 是按順序排列是按順序排列的，經(jīng)過(guò)蝶式運(yùn)算后，其變換序列的，經(jīng)過(guò)蝶式運(yùn)算后，其變換序列 X(m) 是非順序是非順序排列的，即亂序的；反之，如果排列的，即亂序的；反之，如果 x(n) 是亂序

25、的，是亂序的，那么，那么，X(m)就是順序的。因此，為了便于輸出使用，就是順序的。因此，為了便于輸出使用，最好加入重新排序程序，以便保證最好加入重新排序程序，以便保證 x(n) 與它的變與它的變換系數(shù)換系數(shù) X(m) 的對(duì)應(yīng)關(guān)系。具體排序方法如下：的對(duì)應(yīng)關(guān)系。具體排序方法如下： Slide 50（）將（）將r位的二進(jìn)制數(shù)比特倒轉(zhuǎn)，即：位的二進(jìn)制數(shù)比特倒轉(zhuǎn)，即： )(1210rrlkkkkx也就是也就是 X mXk kkkrr()()0121)()(0121kkkkxkxrrllx kl( ) （）將最后一次迭代結(jié)果（）將最后一次迭代結(jié)果 中的序號(hào)中的序號(hào)數(shù)數(shù)k寫(xiě)成二進(jìn)制數(shù)，即寫(xiě)成二進(jìn)制數(shù)，即S

26、lide 51（）求出倒置后的二進(jìn)制數(shù)代表的十進(jìn)制數(shù)，（）求出倒置后的二進(jìn)制數(shù)代表的十進(jìn)制數(shù)，就可以得到與就可以得到與 x(k) 相對(duì)應(yīng)的相對(duì)應(yīng)的 X(m) 的序號(hào)數(shù)。的序號(hào)數(shù)。 Slide 52例如：例如： N=8 N=8 的最后迭代結(jié)果：的最后迭代結(jié)果： x x3 3(0) 000(0) 000倒置倒置000000十進(jìn)制（十進(jìn)制（0 0） x x3 3(1) 001(1) 001倒置倒置100100十進(jìn)制（十進(jìn)制（4 4） x x3 3(2) 010(2) 010倒置倒置010010十進(jìn)制（十進(jìn)制（2 2） x x3 3(3) 011(3) 011倒置倒置110110十進(jìn)制（十進(jìn)制（6 6

27、） x x3 3(4) 100(4) 100倒置倒置001001十進(jìn)制（十進(jìn)制（1 1） x x3 3(5) 101(5) 101倒置倒置101101十進(jìn)制（十進(jìn)制（5 5） x x3 3(6) 110(6) 110倒置倒置011011十進(jìn)制（十進(jìn)制（3 3） x x3 3(7) 111(7) 111倒置倒置111111十進(jìn)制（十進(jìn)制（7 7）Slide 5353Matlab實(shí)現(xiàn)Slide 5454Matlab實(shí)現(xiàn) Slide 5555Matlab實(shí)現(xiàn) Slide 563.2 二維離散余弦變換（二維離散余弦變換（DCT） l任何實(shí)對(duì)稱(chēng)函數(shù)的傅里葉變換中只含余弦項(xiàng)，余弦變換是傅里葉變換的特例，余

28、弦變換是簡(jiǎn)化DFT的重要方法。3.2.1 一維離散余弦變換一維離散余弦變換l將一個(gè)信號(hào)通過(guò)對(duì)折延拓成實(shí)偶函數(shù)，然后進(jìn)行傅里葉變換，我們就可用2N點(diǎn)的DFT來(lái)產(chǎn)生N點(diǎn)的DCT。 1以x = -1/2為對(duì)稱(chēng)軸折疊原來(lái)的實(shí)序列f (n) 得：1),1(10),(nNnfNnnfSlide 57-N-10N-1NN+1f (n)圖圖3.8 延拓示意圖延拓示意圖 2以2N為周期將其周期延拓，其中f（0）f（1），f（N1）f（N） 12),12(10),(NnNnNfNnnffc(2N n 1) = fc(n) Slide 583對(duì)0到2N1的2N個(gè)點(diǎn)的離散周期序列 作DFT，得)(kFc1202)(N

29、nnkNcWnf 102)(NnnkNWnf122) 12(NNmmkNWmNf 令i2Nm1，則上式為 )(kFc102)(NnnkNWnf 01)12(2)(NikiNNWif 22kNW102) 12(cos)(NnNknnfSlide 59l 保證變換基的規(guī)范正交性，引入常量，定義：F(k)C(k) N2102) 12(cos)(NnNknnfC(k)= 其中11, 10,21NkkDCT逆變換為 1112(21)( )(0)( )cos2Nunuf nCF uNNNSlide 603.2.2 二維離散余弦變換二維離散余弦變換 l正變換：l逆變換：1100211( , )( ) ( )

30、( , )coscos22MNxyF u vC u C vf x yu xv yMNMN1100211( , )( ) ( ) ( , )cos() cos()22MNuvf x yC u C v F u vu xv yMNMN Slide 613.2.3 二維DCT的應(yīng)用l典型應(yīng)用是對(duì)靜止圖像和運(yùn)動(dòng)圖像進(jìn)行性能優(yōu)良的有損數(shù)據(jù)壓縮。l在靜止圖像編碼標(biāo)準(zhǔn)JPEG、運(yùn)動(dòng)圖像編碼標(biāo)準(zhǔn)MJPEG和MPEG等標(biāo)準(zhǔn)中都使用了88塊的離散余弦變換，并將結(jié)果進(jìn)行量化之后進(jìn)行熵編碼。lDCT具有很強(qiáng)的能量集中在頻譜的低頻部分的特性，而且當(dāng)信號(hào)具有接近馬爾可夫過(guò)程的統(tǒng)計(jì)特性時(shí)，DCT的去相關(guān)性接近于具有最優(yōu)去相關(guān)

31、性的K-L變換的性能。Slide 62【例3.3】應(yīng)用MATLAB實(shí)現(xiàn)圖像的DCT變換。l【解】MATLAB程序如下：lI = imread(saturn.tif); lsubplot(1,2,1), imshow(I);%顯示原圖像lC1 = dct2(I); %對(duì)圖像做DCT變換lC2 = fftshift(F1);l%將直流分量移到頻譜圖的中心lsubplot(1,2,2),imshow(log(abs(C2)+1,0 10); l%顯示DCT變換結(jié)果Slide 63圖3.10 離散余弦變換 （a）原始圖像 （b）DCT系數(shù)Slide 643.3 3.3 二維離散沃爾什二維離散沃爾什-

32、-哈達(dá)瑪變換（哈達(dá)瑪變換（DHTDHT）l前面的變換是余弦型變換，基底函數(shù)選用的是余弦型。l圖像處理中有些變換常常選用方波信號(hào)或者它的變形。l沃爾什（Walsh）變換。l沃爾什函數(shù)是一組矩形波，其取值為1和-1，便于計(jì)算機(jī)運(yùn)算。l函數(shù)有三種排列或編號(hào)方式，以哈達(dá)瑪排列最便于快速計(jì)算。l采用哈達(dá)瑪排列的沃爾什函數(shù)進(jìn)行的變換稱(chēng)為沃爾什-哈達(dá)瑪變換，簡(jiǎn)稱(chēng)WHT或直稱(chēng)哈達(dá)瑪變換。Slide 653.3.1 沃爾什變換l沃爾什函數(shù)系沃爾什函數(shù)系l函數(shù)值僅取函數(shù)值僅取+1和和1兩值的非正弦型的標(biāo)兩值的非正弦型的標(biāo)準(zhǔn)正交完備函數(shù)系。準(zhǔn)正交完備函數(shù)系。l由于二值正交函數(shù)與數(shù)字邏輯中的兩由于二值正交函數(shù)與數(shù)字邏

33、輯中的兩個(gè)狀態(tài)相對(duì)應(yīng)，所以非常便于計(jì)算機(jī)個(gè)狀態(tài)相對(duì)應(yīng)，所以非常便于計(jì)算機(jī)和數(shù)字信號(hào)處理器運(yùn)算。和數(shù)字信號(hào)處理器運(yùn)算。Slide 66圖3.11 沃爾什函數(shù)系的前10個(gè)函數(shù)Slide 67沃爾什函數(shù)有三種排列或編號(hào)方式l列率排列、佩利（列率排列、佩利（Paley）排列和哈達(dá)瑪）排列和哈達(dá)瑪（Hadamard）排列。）排列。l沃爾什變換的排列方式為列率排列。沃爾什變換的排列方式為列率排列。l與正弦波頻率相對(duì)應(yīng)，非正弦波形可用列率與正弦波頻率相對(duì)應(yīng)，非正弦波形可用列率描述。描述。l列率表示某種函數(shù)在單位區(qū)間上函數(shù)值為零列率表示某種函數(shù)在單位區(qū)間上函數(shù)值為零的零點(diǎn)個(gè)數(shù)之半。的零點(diǎn)個(gè)數(shù)之半。Slide

34、68一維沃爾什變換核g(x,u)l設(shè)N = 2n，變換核為11( )( )01( , )( 1)ininbx buig x uN bk(z)代表z的二進(jìn)制表示的第k位值。核是一個(gè)對(duì)稱(chēng)陣列，其行和列是正交的。Slide 69一維沃爾什變換 l正變換：l逆變換：111( )( )001( )( )( 1)iniNnbx buixW uf xN 111( )( )00( )( )( 1)iniNnbx buiuf xW u Slide 70二維沃爾什變換 l正變換：l逆變換：11111( )( )( )( )0001( , )( , )( 1)iniiniNNnb x buby bvixyW u v

35、f x yN 11111( )( )( )( )0001( , )( , )( 1)iniiniNNnbx buby bviuvf x yW u vN Slide 71【例3.5】求圖像 f 的DWT，并反求 f。l【解】W =G f G，采用MATLAB程序求解W。lf = 2 5 5 2; 3 3 3 3; 3 3 3 3; 2 5 5 1;lG = 1 1 1 1; 1 1 -1 -1; 1 -1 -1 1; 1 -1 1 -1;lW = (1/16)*G*f*G2552333333332551fSlide 72l運(yùn)行結(jié)果為lW =l 3.18750.0625 -0.8125 0.062

36、5l 0.0625 -0.0625 0.0625 -0.0625l 0.18750.0625 -0.8125 0.0625l 0.0625 -0.0625 0.0625 -0.0625Slide 73l反求 f 的程序如下：lW = 3.1875 0.0625 -0.8125 0.0625;l 0.0625 -0.0625 0.0625 -0.0625;l 0.1875 0.0625 -0.8125 0.0625;l 0.0625 -0.0625 0.0625 -0.0625lG = 1 1 1 1; 1 1 -1 -1; 1 -1 -1 1; 1 -1 1 -1;lf = G*W*GSlid

37、e 74l運(yùn)行結(jié)果為lf =l 2 5 5 2l 3 3 3 3l 3 3 3 3l 2 5 5 1Slide 753.3.2 3.3.2 哈達(dá)瑪變換哈達(dá)瑪變換l哈達(dá)瑪矩陣：元素僅由1和1組成的正交方陣。l正交方陣：指它的任意兩行（或兩列）都彼此正交，或者說(shuō)它們對(duì)應(yīng)元素之和為零。l哈達(dá)瑪變換要求圖像的大小為N2n 。l一維哈達(dá)瑪變換核為 其中， bk(z) 代表z的二進(jìn)制表示的第k位值。10)()() 1(1),(niiiubxbNuxgSlide 76二維哈達(dá)瑪正、逆變換具有相同形式l正反變換都可通過(guò)兩個(gè)一維變換實(shí)現(xiàn)。l高階哈達(dá)瑪矩陣可以通過(guò)如下方法求得：lN8的哈達(dá)瑪矩陣為 222211N

38、NNNNHHHHNHN5261437011111111111111111111111111111111111111111111111111111111111111112218HSlide 77一維、二維哈達(dá)瑪正、逆變換l一維哈達(dá)瑪正變換 l一維哈達(dá)瑪逆變換l二維哈達(dá)瑪正變換l二維哈達(dá)瑪逆變換10)()(10) 1)(1)(nxubxbniiixfNuH10)()(10) 1)()(nuubxbniiiuHxf1010)()()()(10) 1)(,(1),(NxNyvbybubxbniiiiiyxfNvuH1010)()()()(10) 1)(,(1),(NuNvvbybubxbniiiiiv

39、uHNyxfSlide 783.4 卡胡南卡胡南-列夫變換（列夫變換（K-L變換）變換）lKahunen-Loeve變換是在均方意義下的最佳變換。l優(yōu)點(diǎn)：l能夠完全去除原信號(hào)中的相關(guān)性，因而具有非常重要的理論意義。l缺點(diǎn)：l基函數(shù)取決于待變換圖像的協(xié)方差矩陣，因而基函數(shù)的形式是不定的，且計(jì)算量很大。Slide 79l設(shè)原圖像為X，采用KLT恢復(fù)的圖像 ，則和原圖像X具有最小的均方誤差，即XT minEXXXXT(0,0),(0,1),(0,1),(1,0),( ,1),(1,1)iiiiiiifffNff r Nf NNX對(duì)第i次獲得的圖像fi(x, y)可以用N2維向量Xi表示： 11Mxi

40、iEMmXXSlide 80lCx是一個(gè)N2N2的實(shí)對(duì)稱(chēng)矩陣。令i和ai（i = 1, 2, , N2）分別為Cx的第i個(gè)特征值和特征向量，其特征向量構(gòu)成的矩陣是一個(gè)正交矩陣 TTT1111()()MMxixixiixxiiMMCXmXmX Xm m222222112111222212NNNNN NaaaaaaaaaASlide 81l ATCxA = A1CxA = （3.51）l 為Cx的特征值構(gòu)成的對(duì)角線矩陣。K-L變換選取一個(gè)上述的正交變換A，使得變換后的圖像Y滿足l Y = A(X mx) （3.52）l優(yōu)點(diǎn)：優(yōu)點(diǎn)：能夠完全去除原信號(hào)中的相關(guān)性，因而具有重要的理論意義。 l缺點(diǎn)：缺點(diǎn)

41、：計(jì)算量很大。Slide 823.5 3.5 二維離散小波變換二維離散小波變換l小波分析是小波分析是20世紀(jì)世紀(jì)80年代開(kāi)始逐漸發(fā)展成熟的年代開(kāi)始逐漸發(fā)展成熟的應(yīng)用數(shù)學(xué)的一個(gè)分支。應(yīng)用數(shù)學(xué)的一個(gè)分支。l主要特點(diǎn)：主要特點(diǎn)：l對(duì)時(shí)間（二維信號(hào)為空間）對(duì)時(shí)間（二維信號(hào)為空間）-頻率的雙重分析和多分頻率的雙重分析和多分辨率分析能力。辨率分析能力。l被譽(yù)為被譽(yù)為“數(shù)學(xué)顯微鏡數(shù)學(xué)顯微鏡”，在信號(hào)和圖像處理等，在信號(hào)和圖像處理等領(lǐng)域具有重要的應(yīng)用價(jià)值。領(lǐng)域具有重要的應(yīng)用價(jià)值。Slide 833.5.1 小波分析的思想來(lái)源l哈爾提出了一種正交歸一化函數(shù)系，以其作為哈爾提出了一種正交歸一化函數(shù)系，以其作為正交

42、規(guī)范基的哈爾變換收斂均勻而迅速，在圖正交規(guī)范基的哈爾變換收斂均勻而迅速，在圖像信息壓縮和特征編碼等方面獲得應(yīng)用。像信息壓縮和特征編碼等方面獲得應(yīng)用。l哈爾變換特點(diǎn)：哈爾變換特點(diǎn)：l（1）具有尺度和位移兩個(gè)特性；）具有尺度和位移兩個(gè)特性；l（2）變換范圍窄；）變換范圍窄；l（3）變換特性與圖像邊界的特性十分接近。）變換特性與圖像邊界的特性十分接近。Slide 84圖3.12 Haar函數(shù)系的前幾個(gè)函數(shù)波形函數(shù)系的前幾個(gè)函數(shù)波形Slide 85窗口傅里葉變換（WFT） l信號(hào)f (x)的窗口傅里葉變換定義為j* 1WFT ( ,)( )()ed2xfRbf x WxbxlWFT的重構(gòu)公式為2j 1

43、( )WFT ( ,)()ed d2xfRf xbW xbbl常見(jiàn)的窗函數(shù)具有相對(duì)短的時(shí)間窗寬，例如可選為高斯函數(shù)，所以WFT也稱(chēng)為短時(shí)傅里葉變換（ STFT）。Slide 86WFT的不足的不足l窗口傅里葉變換是一種大小及形狀均固定的時(shí)頻化分析。l實(shí)際信號(hào)進(jìn)行時(shí)間和頻率分析時(shí)，分辨率往往是相對(duì)的，即反映信號(hào)高頻成分需要較高的時(shí)間分辨率，因此窗函數(shù)寬度應(yīng)該窄一些，而反映低頻成分則需要較高的頻率分辨率，窗函數(shù)寬度應(yīng)該寬一些。l窗口傅里葉變換不能滿足上述要求。Slide 873.5.2 連續(xù)小波變換l小波變換的窗口具有大?。娣e）固定但形狀可改變的特點(diǎn)，能滿足上述時(shí)-頻局部化分析的要求。l按如下方

44、式生成的函數(shù)族為連續(xù)小波（分析小波）：12,( )a bxbxaal (x)稱(chēng)為基本小波或母波la稱(chēng)為伸縮因子，b為平移因子。母波可由平移與尺度變換構(gòu)造小波基函數(shù)。 Slide 88圖3.13 小波函數(shù)的平移與擴(kuò)展Slide 89信號(hào)的連續(xù)小波變換 l正變換：l反變換：1*2, ( , ),( )( )dfa bRxbWa bfxaf xxa ,2 1d( )( , )( )dfa baf xWa bxbCaSlide 903.5.3 一維離散小波變換l把連續(xù)小波變換離散化更有利于實(shí)際應(yīng)用。l對(duì)a和b按如下規(guī)律取樣：l其中 ； ； ，得離散小波：mmanbbaa000,10aZnm,)()(0020,nbxaaxmmnm)(),()()(,xxfdxxxfWnmnmnmnmnmnmnmnmnmfWkf,)(Rb 0 離散小波變換和逆變換為 Slide