1、第三章 圖像變換,1,2020年7月28日,數(shù)字圖像處理,第三章 圖像變換(一) 正交變換、傅立葉變換,第三章 圖像變換,2,2020年7月28日,什么是圖像變換?,圖像變換是將圖像從空間域變換到其它域（如頻域）的數(shù)學變換。 簡單的圖像變換通常就是一種二維的正交變換，但要求這種正交變換必須是可逆的，并且正變換和反變換的算法不能太復(fù)雜。 常用的變換：傅立葉變換、離散余弦變換、沃爾什變換和哈達瑪變換、霍特林變換、拉東變換、小波變換等等。,第三章 圖像變換,3,2020年7月28日,一、正交變換,第三章 圖像變換,4,2020年7月28日,連續(xù)函數(shù)集合的正交性,正交函數(shù)集合,當C=1時，稱集合為歸一

2、化正交函數(shù)集合,第三章 圖像變換,5,2020年7月28日,正交函數(shù)集合的完備性,若f(x)是定義在t0和t0+T區(qū)間的實值信號，平方可積?？梢员硎緸椋?對任意小的0，存在充分大的N，,其中,，則稱函數(shù)U集合是完備的。,意味著f(x)可以由無窮級數(shù)來表示,第三章 圖像變換,6,2020年7月28日,離散情況,n個正交向量,當C=1時，稱歸一化正交。即每一個相量為單位相量 。,第三章 圖像變換,7,2020年7月28日,滿足上式的基相量組成矩陣：,則一定滿足：,第三章 圖像變換,8,2020年7月28日,一維正交變換,對于一向量f，用上述正交矩陣進行運算：,g = Af,若要恢復(fù)f，則:,以上過

3、程稱為正交變換。,我們把原為A-1可以用AT來代替的A陣稱為正交矩陣。,第三章 圖像變換,9,2020年7月28日,二維正交變換,NN二維函數(shù)可以類似于一維,正變換核,反變換核,顯然，這兩個變換核應(yīng)該滿足正交性和完備性。,第三章 圖像變換,10,2020年7月28日,二、傅立葉變換,第三章 圖像變換,11,2020年7月28日,傅立葉變換,傅立葉變換域也稱為頻域變換，它把圖像從圖像空間變換到頻率空間。 將原定義在圖像空間的圖像以某種形式轉(zhuǎn)換（正變換）到另外一些空間，并利用在這些空間的特有性質(zhì)方便地進行一定的加工，最后再轉(zhuǎn)換回圖像空間（反變換或逆變換）以得到所需要的效果。,第三章 圖像變換,12

4、,2020年7月28日,1.連續(xù)函數(shù)的傅立葉變換 若把一個一維輸入信號作一維傅立葉變換，該信號就被變換到頻域上的一個信號，即得到了構(gòu)成該輸入信號的頻譜，頻譜反映了該輸入信號由哪些頻率構(gòu)成。 當一個一維信號f(x)滿足狄里赫萊條件，即f(x) （1） 具有有限個間斷點； （2） 具有有限個極值點； （3） 絕對可積。 則其傅立葉變換對（正變換和逆變換）一定存在。,第三章 圖像變換,13,2020年7月28日,一維傅立葉變換的定義,f(x)為連續(xù)可積函數(shù)，其傅立葉變換定義為：,其反變換為：,式中： ，x稱為時域變量，u為頻域變量。通常傅立葉變換為復(fù)數(shù)形式F(u)=R(u)+jI(u),幅度譜： 相

5、位譜：,第三章 圖像變換,14,2020年7月28日,變換分析的直觀說明,把一個信號的波形分解為許多不同頻率正弦波之和。,第三章 圖像變換,15,2020年7月28日,一維傅立葉變換舉例,方波信號：,經(jīng)過傅立葉變換后：,第三章 圖像變換,16,2020年7月28日,一維離散傅立葉變換(DFT),一維離散傅立葉變換公式為：,逆變換為：,數(shù)學上建立傅立葉變換的f(x)是連續(xù)的模擬信號，而計算機處理的是離散的數(shù)字信號，同時數(shù)學上用無窮大概念，而計算機只能進行有限次計算。通常就將這種受限的傅立葉變換稱為離散傅立葉變換（DFT）。,第三章 圖像變換,17,2020年7月28日,由歐拉公式可知 可得 可見

6、，離散序列的傅立葉變換仍然是一個離散的序列，每一個u對應(yīng)的傅立葉變換結(jié)果是所有輸入序列f(x)的加權(quán)和。 每個f(x)都乘以不同頻率的正弦和余弦值。,第三章 圖像變換,18,2020年7月28日,二維離散傅立葉變換,對于二維傅立葉變換，由一維推廣而來，其離散形式為：,逆變換為：,幅譜(頻譜)、相譜：,第三章 圖像變換,19,2020年7月28日,二維傅立葉變換舉例,對于二維方波信號,傅立葉變換為：,幅度：,第三章 圖像變換,20,2020年7月28日,例：函數(shù)在以原點為中心的一個正方形內(nèi)為正值常數(shù)，而在其它地方為零。傅立葉頻譜幅度的灰度圖顯示。,第三章 圖像變換,21,2020年7月28日,二

7、維傅立葉變換的性質(zhì),1.分離性 二維傅立葉變換可由連續(xù)兩次運用一維傅立葉變換來實現(xiàn)。,第三章 圖像變換,22,2020年7月28日,由可分離性可知，一個二維傅立葉變換可分解為兩步進行， 其中每一步都是一個一維傅立葉變換。先對f(x, y)按列進行傅立葉變換得到F(x, v)，再對F(x, v)按行進行傅立葉變換，便可得到f(x, y)的傅立葉變換結(jié)果，如圖所示。 顯然對f(x, y)先按行進行離散傅立葉變換，再按列進行離散傅立葉變換也是可行的。,第三章 圖像變換,23,2020年7月28日,2.平移性,將f(x,y)與一個指數(shù)項相乘就相當于把其變換后的頻域中心移動到新的位置。 F(u,v)與一

8、個指數(shù)項相乘就相當于把其反變換后的空域中心移動到新的位置。 對f(x,y)的平移不影響其傅立葉變換的幅值。,第三章 圖像變換,24,2020年7月28日,3.周期性和共扼對稱性,如果f(x,y)是實函數(shù)，則它的傅立葉變換具有共扼對稱性：,F*(u,v)為F(u,v)的復(fù)共扼。,假定傅立葉變換和反變換均以N為周期。,第三章 圖像變換,25,2020年7月28日,由旋轉(zhuǎn)不變性可知，如果時域中離散函數(shù)旋轉(zhuǎn)0角度，則在變換域中該離散傅立葉變換函數(shù)也將旋轉(zhuǎn)同樣的角度0 。離散傅立葉變換的旋轉(zhuǎn)不變性如圖3-3所示。,圖3-3 離散傅立葉變換的旋轉(zhuǎn)不變性 （a） 原始圖像； （b） 原圖像的傅立葉頻譜； （

9、c） 旋轉(zhuǎn)45后的圖像； （d） 圖像旋轉(zhuǎn)后的傅立葉頻譜,4.旋轉(zhuǎn)性質(zhì),借助極坐標變換 x=rcos， y=rsin， u=w cos， v=w sin，將f(x,y)和F(u,v)轉(zhuǎn)換為f(r,)和F(w,)。,第三章 圖像變換,26,2020年7月28日,傅立葉變換和反變換對加法滿足分配律，但對乘法則不滿足。,5.分配律,6.尺度變換(縮放) 比例性質(zhì),第三章 圖像變換,27,2020年7月28日,將u = v = 0代入正變換式，可以得到：,7.平均值,2個函數(shù)的卷積定義為：,8.卷積,平均值計算,計算步驟: 折疊,位移,相乘,積分（求和）,圖像變換(二) 快速傅立葉變換、離散余弦變換,

10、第三章 圖像變換,29,2020年7月28日,普通傅立葉變換：,完成全部DFT運算的計算量與N2成正比。特別是當N較大時，其運算時間將迅速增長， 以至于無法容忍。 為此，研究離散傅立葉變換的快速算法（Fast Fourier Transform，F(xiàn)FT）非常必要。,研究快速傅立葉變換的必要性,快速離散傅立葉變換 一種稱為逐次加倍法的快速傅立葉變換算法（FFT），它是1965年Cooley和Tukey首先提出的。算法時間復(fù)雜度為Nlog2N。當N很大時計算量可以大大減少。,第三章 圖像變換,31,2020年7月28日,記,稱為旋轉(zhuǎn)因子。則有：,單位圓表示：,快速傅立葉變換,(3-1),第三章 圖

11、像變換,32,2020年7月28日,式中，由Wux構(gòu)成的矩陣稱為W陣或系數(shù)矩陣。,一維離散傅立葉變換（DFT）用矩陣的形式表示為：,第三章 圖像變換,33,2020年7月28日,W的定義表達式W=e-j2N，由歐拉公式知系數(shù)W是以N為周期的。這樣，W陣中很多系數(shù)就是相同的， 且由于W的對稱性，即,因此可進一步減少計算工作量。 例如，對于N=4， W陣為,W4W0，W6W2，W9W1； W3W1，W2W0,第三章 圖像變換,34,2020年7月28日,可見N=4的W陣中只需計算W0和W1兩個系數(shù)即可。說明W陣的系數(shù)有許多計算工作是重復(fù)的，如果把一個離散序列分解成若干短序列，并充分利用旋轉(zhuǎn)因子W的

12、周期性和對稱性來計算離散傅立葉變換，便可以簡化運算過程，這就是FFT的基本思想。 設(shè)N為2的正整數(shù)次冪， 即,如令M為正整數(shù)，且,N=2M,第三章 圖像變換,35,2020年7月28日,將式N=2M代入式（3-1），離散傅立葉變換可改寫成如下形式：,由旋轉(zhuǎn)因子W的定義可知， 因此式(3-2)變?yōu)?現(xiàn)定義,(3-2),(3-3),(3-4),(3-5),第三章 圖像變換,36,2020年7月28日,于是式(3-3)變?yōu)?(3-6),進一步考慮W的對稱性和周期性可知 和， 于是,(3-7),由此，可將一個N點的離散傅立葉變換分解成兩個N2短序列的離散傅立葉變換，即分解為偶數(shù)和奇數(shù)序列的離散傅立葉變

13、換Fe(u)和Fo(u) 。,第三章 圖像變換,37,2020年7月28日,在此，以計算N=8的DFT為例，此時n=3，M=4。由式(3-6)和式(3-7)可得,(3-8 ),第三章 圖像變換,38,2020年7月28日,式（3-8）中，u取07時的F(u)、Fe(u)和Fo(u)的關(guān)系可用圖3.1描述。左方的兩個節(jié)點為輸入節(jié)點，代表輸入數(shù)值；右方兩個節(jié)點為輸出節(jié)點，表示輸入數(shù)值的疊加，運算由左向右進行。線旁的W18和W18為加權(quán)系數(shù)，定義由F(1)、 F(5)、Fe(1)和Fo(1)所構(gòu)成的結(jié)構(gòu)為蝶形運算單元, 其表示的運算為,(3-9 ),圖3.1 蝶形運算單元,第三章 圖像變換,39,2

14、020年7月28日,由于Fe(u)和Fo(u)都是4點的DFT，因此，如果對它們再按照奇偶進行分組， 則有,第三章 圖像變換,40,2020年7月28日,圖3.2 4點DFT分解為2點DFT的蝶形流程圖,第三章 圖像變換,41,2020年7月28日,二維快速傅立葉變換的Matlab實現(xiàn),簡單圖像及其傅立葉變換 Eg3.4 d=zeros(32,32); d(13:20,13:20)=1; figure(1); imshow(d,notruesize); D=fft2(d); figure(2); imshow(abs(D),-1 5,notruesize);,第三章 圖像變換,42,2020年

15、7月28日,第三章 圖像變換,43,2020年7月28日,二維快速傅立葉變換的Matlab實現(xiàn),eg3.3 figure(1); load imdemos saturn2; imshow(saturn2); figure(2); S=fftshift(fft2(saturn2); imshow(log(abs(S),);,第三章 圖像變換,44,2020年7月28日,頻域變換的一般表達式,1、可分離變換 二維傅立葉變換可用通用的關(guān)系式來表示：,(3-10),(3-11),式中：x, u=0, 1, 2, , M1；y, v=0, 1, 2, , N1；g(x,y,u,v)和h(x,y,u,v)

16、分別稱為正向變換核和反向變換核。,第三章 圖像變換,45,2020年7月28日,如果,g(x, y, u, v)=g1(x, u)g2（y, v） (3-12) h(x, y, u, v)=h1(x, u)h2(y, v)(3-13),則稱正、反變換核是可分離的。如果g1和g2，h1和h2在函數(shù)形式上一樣，則稱該變換核是對稱的。 二維傅立葉變換對是一個特殊情況， 它們的核為,可分離 對稱,第三章 圖像變換,46,2020年7月28日,對于圖像變換，只要其變換核是可分離的，就可用兩次一維變換來實現(xiàn)。 如果先對f(x, y)的每一列進行一維變換得到F(y, u)，再沿F(y, u)每一行取一維變換

17、得到F(u, v)，和先對f(x, y)的每一行進行一維變換得到F(x, v)，再沿F(x, v)每一列取一維變換得到F(u, v)其最終結(jié)果是一樣的。 該結(jié)論對反變換核也適用。,第三章 圖像變換,47,2020年7月28日,3.4 離散余弦變換,第三章 圖像變換,48,2020年7月28日,3.4.1 一維離散余弦變換 一維DCT的變換核定義為,式中，x, u=0, 1, 2, , N1；,(3-47),(3-48),一維DCT定義如下： 設(shè)f(x)|x=0, 1, , N-1為離散的信號列。,(3-49),式中，u, x=0, 1, 2, , N1。,第三章 圖像變換,49,2020年7月

18、28日,將變換式展開整理后， 可以寫成矩陣的形式， 即,F=Gf,（3-50）,其中,(3-51),第三章 圖像變換,50,2020年7月28日,一維DCT的逆變換IDCT定義為,(3-52),式中， x, u=0, 1, 2, , N1。可見一維DCT的逆變換核與正變換核是相同的。,第三章 圖像變換,51,2020年7月28日,3.4.2 二維離散余弦變換 將一維DCT的定義推廣到二維DCT。其正變換核為,(3-53),式中，C(u)和C(v)的定義同式（3-48）；x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。,第三章 圖像變換,52,2020年7月28日,3.4.2 二維離散余弦變換,二維DCT定義如下：設(shè)f(x, y)為MN的數(shù)字圖像矩陣，則,(3-54),式中： x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。,第三章 圖像變換,53,2020年7月28日,二維DCT逆變換定義如下：,(3-55),式中：x, u=0, 1, 2, , M1； y, v=0, 1, 2, , N1。 類似一維矩陣形式的DCT，可以寫出二維DCT的矩陣形式如下： F=GfGT (3-56),第三章 圖像變換,54,2020年7月28日,同時，由式(3-55)和式(3-54)