第7章-頻域處理幻燈片.ppt

1、多媒體通信,北京科技大學(xué) 楊 揚(yáng),第7章 頻域處理,頻域世界與頻域變換 傅立葉變換 頻域變換的一般表達(dá)式 離散余弦變換 離散沃爾什哈達(dá)瑪變換 小波變換簡介,1、頻域世界與頻域變換,頻域變換的理論基礎(chǔ)是： “任意波形都可以用單純的正弦波的和來表示” 因此圖像的頻域變換為： （1）將圖像看成是線性疊加系統(tǒng) ； （2）圖像在空域上相關(guān)性很強(qiáng)； （3）圖像變換是將圖像從空域變換到其它域如頻域的數(shù)學(xué)變換。 常用的變換有：傅立葉變換、離散余弦變換、小波變換、離散K-L變換,1、頻域世界與頻域變換,正弦波的振幅A和相位,1、頻域世界與頻域變換,時(shí)域和頻域之間的變換可用數(shù)學(xué)公式表示如下：,為能同時(shí)表示信號的振

2、幅和相位，通常采用復(fù)數(shù)表示法，因此上式可用復(fù)數(shù)表示為,完成這種變換，一般采用的方法是線性正交變換。,2、傅立葉變換,傅立葉變換是一種常用的正交變換，它的理論完善,應(yīng)用程序多。 在圖像處理應(yīng)用領(lǐng)域，傅立葉變換起著非常重要的作用，可用它完成圖像分析、圖像增強(qiáng)以及圖像壓縮等工作。 當(dāng)一個(gè)一維信號f(x)滿足狄里赫萊條件，即f(x) （1） 具有有限個(gè)間斷點(diǎn)； （2） 具有有限個(gè)極值點(diǎn)； （3） 絕對可積。 則其傅立葉變換對（傅立葉變換和逆變換）一定存在。,2.1 連續(xù)函數(shù)的傅立葉變換,一維傅立葉變換對的定義為：,式中： ，x稱為時(shí)域變量，u稱為頻域變量。,2.1 連續(xù)函數(shù)的傅立葉變換,以上一維傅立葉

3、變換可以很容易地推廣到二維，如果二維函數(shù)f(x, y)滿足狄里赫萊條件，則它的二維傅立葉變換對為,式中：x, y為時(shí)域變量；u, v為頻域變量。,2.1 連續(xù)函數(shù)的傅立葉變換,若把一個(gè)一維輸入信號作一維傅立葉變換，該信號就被變換到頻域上的一個(gè)信號，即得到了構(gòu)成該輸入信號的頻譜，頻譜反映了該輸入信號由哪些頻率構(gòu)成。 一維傅立葉變換對的定義為：,式中： ，x稱為時(shí)域變量，u稱為頻域變量。,2.2 離散傅立葉變換,設(shè)f(x)|f(0), f(1), f(2), , f(N-1)為一維信號f(x)的N個(gè)抽樣， 其離散傅立葉變換（Discrete Fourier Transform，DFT)對為： 式中

4、：x，u=0，1，2，N1。,2.3 離散傅立葉變換的性質(zhì),2.3 離散傅立葉變換的性質(zhì),2.3 離散傅立葉變換的性質(zhì)-平移性質(zhì),由可分離性可知，一個(gè)二維傅立葉變換可分解為兩步進(jìn)行， 其中每一步都是一個(gè)一維傅立葉變換。先對f(x, y)按行進(jìn)行傅立葉變換得到F(x, v)，再對F(x, v)按列進(jìn)行傅立葉變換，便可得到f(x, y)的傅立葉變換結(jié)果，如下圖所示。顯然對f(x, y)先按列進(jìn)行離散傅立葉變換， 再按行進(jìn)行離散傅立葉變換也是可行的。,用兩次一維DFT計(jì)算二維DFT,2.3 離散傅立葉變換的性質(zhì)-可分離性,平移性質(zhì)表明，只要將f(x, y)乘以因子(1)x+y，再進(jìn)行離散傅立葉變換，

5、即可將圖像的頻譜原點(diǎn)（0，0）移動到圖像中心（M/2, N/2）處。下圖是簡單方塊圖像平移的結(jié)果。,傅立葉頻譜平移示意圖 (a)原圖像； (b)無平移的傅立葉頻譜； (c)平移后的傅立葉頻譜,2.3 離散傅立葉變換的性質(zhì)-旋轉(zhuǎn)不變性,由旋轉(zhuǎn)不變性可知，如果時(shí)域中離散函數(shù)旋轉(zhuǎn)0角度，則在變換域中該離散傅立葉變換函數(shù)也將旋轉(zhuǎn)同樣的角度。離散傅立葉變換的旋轉(zhuǎn)不變性如右圖所示。,離散傅立葉變換的旋轉(zhuǎn)不變性 （a） 原始圖像； （b） 原始圖像的傅立葉頻譜； （c） 旋轉(zhuǎn)45后的圖像； （d） 圖像旋轉(zhuǎn)后的傅立葉頻譜,2.4 快速離散傅立葉變換,離散傅立葉變換計(jì)算量非常大，運(yùn)算時(shí)間長?？梢宰C明其運(yùn)算次數(shù)

6、正比于N2，特別是當(dāng)N較大時(shí)，其運(yùn)算時(shí)間將迅速增長，以至于無法容忍。為此，研究離散傅立葉變換的快速算法(Fast Fourier Transform，F(xiàn)FT)是非常有必要的。,2.4 快速離散傅立葉變換,一維離散傅立葉變換的快速算法如下式： 式中，W=e-j2/N ，稱為旋轉(zhuǎn)因子。,2.4 快速離散傅立葉變換,前面所示的一維離散傅立葉變換（DFT）用矩陣的形式表示為： 式中，由Wux構(gòu)成的矩陣稱為W陣或系數(shù)矩陣。,2.4 快速離散傅立葉變換,從上式中的W陣，并結(jié)合W的定義，可以發(fā)現(xiàn)W是以N為周期的。這樣，W陣中很多系數(shù)就是相同的，不必進(jìn)行多次重復(fù)計(jì)算。同時(shí)從下面關(guān)系可以看出W的對稱性： 對于N

7、=4，W陣為：,2.4 快速離散傅立葉變換,由W的周期性得：W4W0，W6W2，W9W1；再由W的對稱性可得： W3W1，W2W0。于是上式可變?yōu)椋?2.4 快速離散傅立葉變換,可見N=4的W陣中只需計(jì)算W0和W1兩個(gè)系數(shù)即可。這說明W陣的系數(shù)有許多計(jì)算工作是重復(fù)的，如果把一個(gè)離散序列分解成若干短序列， 并充分利用旋轉(zhuǎn)因子W的周期性和對稱性來計(jì)算離散傅立葉變換，便可以簡化運(yùn)算過程，這就是FFT的基本思想。 設(shè)N為2的正整數(shù)次冪， 即：,如令M為正整數(shù)，且,N=2M,2.4 快速離散傅立葉變換,將上式代入F(u)式，離散傅立葉變換可改寫成如下形式：,由旋轉(zhuǎn)因子W的定義可知 因此上式變?yōu)椋?現(xiàn)定義

8、：,則可得：,2.4 快速離散傅立葉變換,進(jìn)一步考慮W的對稱性和周期性可知 和， 于是：,由此，可將一個(gè)N點(diǎn)的離散傅立葉變換分解成兩個(gè)N2短序列的離散傅立葉變換，即分解為偶數(shù)和奇數(shù)序列的離散傅立葉變換Fe(u)和Fo(u) 。,2.4 快速離散傅立葉變換,在此，以計(jì)算N=8的DFT為例，此時(shí)n=3，M=4。,2.4 快速離散傅立葉變換,前式中，u取07時(shí)的F(u)、Fe(u)和Fo(u)的關(guān)系可用右圖描述。 左方的兩個(gè)節(jié)點(diǎn)為輸入節(jié)點(diǎn)，代表輸入數(shù)值；右方兩個(gè)節(jié)點(diǎn)為輸出節(jié)點(diǎn)，表示輸入數(shù)值的疊加，運(yùn)算由左向右進(jìn)行。線旁的W18和W18為加權(quán)系數(shù)，定義由F(1)、 F(5)、Fe(1)和Fo(1)所構(gòu)

9、成的結(jié)構(gòu)為蝶形運(yùn)算單元, 其表示的運(yùn)算為：,蝶形運(yùn)算單元,2.4 快速離散傅立葉變換,由于Fe(u)和Fo(u)都是4點(diǎn)的DFT，因此，如果對它們再按照奇偶進(jìn)行分組，則有：,2.4 快速離散傅立葉變換,4點(diǎn)DFT分解為2點(diǎn)DFT的蝶形流程圖,2.4 快速離散傅立葉變換,8點(diǎn)DFT的蝶形流程圖,2.4 快速離散傅立葉變換,8點(diǎn)DFT逐級分解框圖,3、頻域變換的一般表達(dá)式-可分離變換,二維傅立葉變換可以利用變換核的可分離性， 用兩次一維變換來實(shí)現(xiàn)，即可先對f(x, y)的每一行進(jìn)行一維變換得到F(x, v)，再沿F(x, v)每一列取一維變換得到變換結(jié)果F(u, v)。對于其他的圖像變換，只要其變

10、換核是可分離的，同樣也可用兩次一維變換來實(shí)現(xiàn)。 如果先對f(x, y)的每一列進(jìn)行一維變換得到F(y, u)，再沿F(y, u)每一行取一維變換得到F(u, v)，其最終結(jié)果是一樣的。該結(jié)論對反變換核也適用。,3、頻域變換的一般表達(dá)式-圖像變換的矩陣表示,數(shù)字圖像都是實(shí)數(shù)矩陣， 設(shè)f(x, y)為MN的圖像灰度矩陣，通常為了分析、推導(dǎo)方便，可將可分離變換寫成矩陣的形式： F=PfQ F=P-1FQ-1 其中，F(xiàn)、f是二維MN的矩陣；P是MM矩陣；Q是NN矩陣。,4、離散余弦變換（DCT）,離散余弦變換（Discrete Cosine Transform， DCT）的變換核為余弦函數(shù)。 DCT除

11、了具有一般的正交變換性質(zhì)外，它的變換陣的基向量能很好地描述人類語音信號和圖像信號的相關(guān)特征。因此，在對語音信號、圖像信號的變換中，DCT變換被認(rèn)為是一種準(zhǔn)最佳變換。近年頒布的一系列視頻壓縮編碼的國際標(biāo)準(zhǔn)建議中，都把DCT作為其中的一個(gè)基本處理模塊。 除此之外， DCT還是一種可分離的變換。,4.1 一維離散余弦變換,一維DCT的變換定義為： 歸一化后為： 矩陣形式為： F=Gf,4.1 一維離散余弦變換,一維余弦變換的反變換為： 矩陣形式為：,4.2 二維離散余弦變換,考慮到兩個(gè)變量，很容易將一維DCT的定義推廣到二維DCT。其正變換核為： 二維DCT逆變換定義如下：,4.3 離散余弦變換示例

12、,N = 4時(shí)DCT基圖像（不同陰影代表不同數(shù)值）。,4.3 離散余弦變換示例,下兩圖給出離散余弦變換的一個(gè)示例，其中左圖是一幅原始圖象，右圖是對左圖的離散余弦變換結(jié)果（變換幅值）。右圖左上角對應(yīng)低頻分量，由圖可見，左圖中的大部分能量在低頻部分。,5、離散沃爾什-哈達(dá)瑪變換(WHT),沃爾什函數(shù)是1923年由美國數(shù)學(xué)家沃爾什提出的。沃爾什函數(shù)系是一個(gè)完備正交函數(shù)系，其值只能取1和1。從排列次序上可將沃爾什函數(shù)分為三種定義方法： 一種是按照沃爾什排列來定義（按列率排序）； 另一種是按照佩利排列來定義（按自然排序）； 第三種是按照哈達(dá)瑪排列來定義。 由于哈達(dá)瑪排序的沃爾什函數(shù)是由2n（n=0，1，

13、2，）階哈達(dá)瑪矩陣（Hadamard Matrix）得到的，而哈達(dá)瑪矩陣的最大優(yōu)點(diǎn)在于它具有簡單的遞推關(guān)系， 即高階矩陣可用兩個(gè)低階矩陣的克羅內(nèi)克積求得，因此在此只介紹哈達(dá)瑪排列定義的沃爾什變換。,5.1 一維離散沃爾什-哈達(dá)瑪變換,5.1 一維離散沃爾什-哈達(dá)瑪變換,一維離散沃爾什變換定義為： 一維離散沃爾什逆變換定義為：,5.1 一維離散沃爾什-哈達(dá)瑪變換,由哈達(dá)瑪矩陣的特點(diǎn)可知，沃爾什-哈達(dá)瑪變換的本質(zhì)上是將離散序列f(x)的各項(xiàng)值的符號按一定規(guī)律改變后，進(jìn)行加減運(yùn)算。 因此，它比采用復(fù)數(shù)運(yùn)算的DFT和采用余弦運(yùn)算的DCT要簡單得多。,5.2 二維離散沃爾什-哈達(dá)瑪變換,很容易將一維WH

14、T的定義推廣到二維WHT，二維WHT的正變換核和逆變換核分別為：,5.2 二維離散沃爾什-哈達(dá)瑪變換,二維WHT具有能量集中的特性，而且原始數(shù)據(jù)中數(shù)字越是均勻分布，經(jīng)變換后的數(shù)據(jù)越集中于矩陣的邊角上。因此，可用于壓縮圖像信息。,5.3 離散沃爾什-哈達(dá)瑪變換示例,下圖給出N = 4時(shí)的哈達(dá)瑪基本函數(shù)的圖示。,6、小波變換簡介,信號分析是為了獲得時(shí)間和頻率之間的相互關(guān)系。 傅立葉變換提供了有關(guān)頻率域的信息，但有關(guān)時(shí)間的局部化信息卻基本丟失。 與傅立葉變換不同，小波變換是通過縮放母小波（Mother wavelet）的寬度來獲得信號的頻率特征， 通過平移母小波來獲得信號的時(shí)間信息。對母小波的縮放和

15、平移操作是為了計(jì)算小波系數(shù)，這些小波系數(shù)反映了小波和局部信號之間的相關(guān)程度。,6、小波變換簡介,下圖表示了正弦波和小波的區(qū)別，由此可以看出，正弦波從負(fù)無窮一直延續(xù)到正無窮，正弦波是平滑而且是可預(yù)測的， 而小波是一類在有限區(qū)間內(nèi)快速衰減到0的函數(shù)，其平均值為0， 小波趨于不規(guī)則、不對稱。,正弦波和小波 （a） 正弦波曲線； (b) 小波曲線,6.1 連續(xù)小波變換(CWT),連續(xù)小波變換（Continuous Wavelet Transform，CWT）用下式表示： 此式表示小波變換是信號f(x)與被縮放和平移的小波函數(shù)()之積在信號存在的整個(gè)期間里求和的結(jié)果。CWT的變換結(jié)果是許多小波系數(shù)C，這

16、些系數(shù)是縮放因子（scale）和平移（positon）的函數(shù)。,6.1 連續(xù)小波變換(CWT),基本小波函數(shù)()的縮放和平移操作含義如下： (1) 縮放。簡單地講， 縮放就是壓縮或伸展基本小波， 縮放系數(shù)越小， 則小波越窄，如下圖所示。,小波的縮放操作,6.1 連續(xù)小波變換(CWT),(2) 平移。簡單地講，平移就是小波的延遲或超前。在數(shù)學(xué)上， 函數(shù)f(t)延遲k的表達(dá)式為f(t-k)，如下圖所示。,小波的平移操作 (a) 小波函數(shù)(t)； (b) 位移后的小波函數(shù)(t-k),6.1 連續(xù)小波變換(CWT),CWT計(jì)算主要有如下五個(gè)步驟： 第一步：取一個(gè)小波， 將其與原始信號的開始一節(jié)進(jìn)行比較

17、。 第二步：計(jì)算數(shù)值C，C表示小波與所取一節(jié)信號的相似程度，計(jì)算結(jié)果取決于所選小波的形狀。 第三步：向右移動小波，重復(fù)第一步和第二步，直至覆蓋整個(gè)信號。 第四步：伸展小波，重復(fù)第一步至第三步。 第五步：對于所有縮放，重復(fù)第一步至第四步。 小波的縮放因子與信號頻率之間的關(guān)系是：縮放因子scale越小，表示小波越窄，度量的是信號的細(xì)節(jié)變化，表示信號頻率越高；縮放因子scale越大， 表示小波越寬，度量的是信號的粗糙程度，表示信號頻率越低。,6.2 離散小波變換(DWT),在每個(gè)可能的縮放因子和平移參數(shù)下計(jì)算小波系數(shù)，其計(jì)算量相當(dāng)大，將產(chǎn)生驚人的數(shù)據(jù)量，而且有許多數(shù)據(jù)是無用的。 如果縮放因子和平移參

18、數(shù)都選擇為2j（j0且為整數(shù)）的倍數(shù)，即只選擇部分縮放因子和平移參數(shù)來進(jìn)行計(jì)算，就會使分析的數(shù)據(jù)量大大減少。 使用這樣的縮放因子和平移參數(shù)的小波變換稱為雙尺度小波變換（Dyadic Wavelet Transform），它是離散小波變換（Discrete Wavelet Transform, DWT）的一種形式。通常離散小波變換就是指雙尺度小波變換。,6.2 離散小波變換(DWT),執(zhí)行離散小波變換的有效方法是使用濾波器，該方法是Mallat于1988年提出的，稱為Mallat算法。這種方法實(shí)際上是一種信號分解的方法，在數(shù)字信號處理中常稱為雙通道子帶編碼。 用濾波器執(zhí)行離散小波變換的概念如下頁

19、圖所示。S表示原始的輸入信號，通過兩個(gè)互補(bǔ)的濾波器組，其中一個(gè)濾波器為低通濾波器，通過該濾波器可得到信號的近似值A(chǔ) (Approximations)，另一個(gè)為高通濾波器，通過該濾波器可得到信號的細(xì)節(jié)值D (Detail),6.2 離散小波變換(DWT),小波分解示意圖,6.2 離散小波變換(DWT),在小波分析中，近似值是大的縮放因子計(jì)算的系數(shù)，表示信號的低頻分量，而細(xì)節(jié)值是小的縮放因子計(jì)算的系數(shù)，表示信號的高頻分量。實(shí)際應(yīng)用中，信號的低頻分量往往是最重要的，而高頻分量只起一個(gè)修飾的作用。如同一個(gè)人的聲音一樣， 把高頻分量去掉后，聽起來聲音會發(fā)生改變，但還能聽出說的是什么內(nèi)容，但如果把低頻分量

20、刪除后，就會什么內(nèi)容也聽不出來了。,6.2 離散小波變換(DWT),由上圖可以看出離散小波變換可以表示成由低通濾波器和高通濾波器組成的一棵樹。原始信號經(jīng)過一對互補(bǔ)的濾波器組進(jìn)行的分解稱為一級分解，信號的分解過程也可以不斷進(jìn)行下去，也就是說可以進(jìn)行多級分解。如果對信號的高頻分量不再分解，而對低頻分量進(jìn)行連續(xù)分解，就可以得到信號不同分辨率下的低頻分量， 這也稱為信號的多分辨率分析。 如此進(jìn)行下去， 就會形成下圖所示的一棵比較大的分解樹， 稱其為信號的小波分解樹（Wavelet Decomposition Tree）。實(shí)際中， 分解的級數(shù)取決于要分析的信號數(shù)據(jù)特征及用戶的具體需要。,6.2 離散小波

21、變換(DWT),多級信號分解示意圖 （a） 信號分解； (b) 小波分?jǐn)?shù)； （c）小波分解樹,6.3 小波重構(gòu),將信號的小波分解的分量進(jìn)行處理后，一般還要根據(jù)需要把信號恢復(fù)出來，也就是利用信號的小波分解的系數(shù)還原出原始信號，這一過程稱為小波重構(gòu)（Wavelet Reconstruction）或叫做小波合成（Wavelet Synthesis）。 這一合成過程的數(shù)學(xué)運(yùn)算叫做逆離散小波變換（Inverse Discrete Wavelet Transform， IDWT）。 由小波分解的近似系數(shù)和細(xì)節(jié)系數(shù)可以重構(gòu)出原始信號。同樣，可由近似系數(shù)和細(xì)節(jié)系數(shù)分別重構(gòu)出信號的近似值或細(xì)節(jié)值，這時(shí)只要近似系

22、數(shù)或細(xì)節(jié)系數(shù)置為零即可。,6.3 小波重構(gòu),小波重構(gòu)算法示意圖,6.3 小波重構(gòu),1）重構(gòu)近似信號與細(xì)節(jié)信號 由上圖可知，由小波分解的近似系數(shù)和細(xì)節(jié)系數(shù)可以重構(gòu)出原始信號。同樣，可由近似系數(shù)和細(xì)節(jié)系數(shù)分別重構(gòu)出信號的近似值或細(xì)節(jié)值，這時(shí)只要近似系數(shù)或細(xì)節(jié)系數(shù)置為零即可。 下圖是對第一層近似信號或細(xì)節(jié)信號進(jìn)行重構(gòu)的示意圖。,6.3 小波重構(gòu),重構(gòu)近似和細(xì)節(jié)信號示意 （a） 重構(gòu)近似信號； (b) 重構(gòu)細(xì)節(jié)信號,6.3 小波重構(gòu),2）多層重構(gòu) 在上圖中，重構(gòu)出信號的近似值A(chǔ)1與細(xì)節(jié)值D1之后，則原信號可用A1D1S重構(gòu)出來。對應(yīng)于信號的多層小波分解，小波的多層重構(gòu)如下圖所示。由圖可見重構(gòu)過程為：A

23、3D3A2；A2D2A1；A1+D1S。,多層小波重構(gòu)示意圖,6.3 小波重構(gòu),信號重構(gòu)中，濾波器的選擇非常重要，關(guān)系到能否重構(gòu)出滿意的原始信號。低通分解濾波器（L）和高通分解濾波器（H）及重構(gòu)濾波器組（L和H）構(gòu)成一個(gè)系統(tǒng)， 這個(gè)系統(tǒng)稱為正交鏡像濾波器（Quadrature Mirror Filters， QMF）系統(tǒng)，如下圖所示。,6.3 小波重構(gòu),多層小波分解和重構(gòu)示意圖,6.4 小波包分析,小波分析是將信號分解為近似與細(xì)節(jié)兩部分，近似部分又可以分解成第二層近似與細(xì)節(jié)，可以這樣重復(fù)下去。對于一個(gè)N層分解來說，有N+1個(gè)分解信號的途徑。 而小波包分析的細(xì)節(jié)與近似部分一樣，也可以分解，對于N層分解，它產(chǎn)生2N個(gè)不同的途徑。如下圖：,6.4 小波包分析,小波包分解也可得到一個(gè)分解樹，稱其為小波包分解樹（Wavelet Packet Decomposition Tree），這種樹是一個(gè)完整的二叉樹。 小波包分解方法是小波分解的一般化，可為信號分析提供更豐富和更詳細(xì)的信息。信號S可表示為AA2ADA3DDA3D1等。,6.5 用小波變換進(jìn)行圖像分解,使用小波變換完成圖像分解的方法很多，例如，均勻分解（Uniform decomposition）、非均勻分解（N