第3章-正交變換(08)-數(shù)字圖像處理課件-820

第3章圖像信號(hào)的正交變換3.1頻域世界與頻域變換3.2離散傅立葉變換3.3頻域變換的一般表達(dá)式3.4離散余弦變換3.5離散沃爾什哈達(dá)瑪變換3.6離散K-L變換3.7小波變換簡(jiǎn)介圖7-2正弦波的振幅A和相位φ

圖7-3圖7-1（a）波形的頻域表示(a)幅頻特性；(b)相頻特性時(shí)域和頻域之間的變換可用數(shù)學(xué)公式表示如下：

為能同時(shí)表示信號(hào)的振幅和相位，采用復(fù)數(shù)表示法：

完成這種變換，一般采用的方法是線(xiàn)性正交變換。

(3-1)(3-2)3.2離散傅立葉變換3.2.1連續(xù)函數(shù)的傅立葉變換當(dāng)一個(gè)一維信號(hào)f(x)滿(mǎn)足狄里赫萊條件，即f(x)

（1）具有有限個(gè)間斷點(diǎn)；（2）具有有限個(gè)極值點(diǎn)；（3）絕對(duì)可積。則其傅立葉變換對(duì)（傅立葉變換和逆變換）一定存在。在實(shí)際應(yīng)用中，這些條件一般總是可以滿(mǎn)足的。

一維傅立葉變換對(duì)定義為：(3-3)(3-4)

式中：x稱(chēng)為時(shí)域變量，u稱(chēng)為頻域變量。信號(hào)的傅立葉變換F(u)——頻譜

頻譜反映了該輸入信號(hào)由哪些頻率成分(含幅度和相位)構(gòu)成。

二維傅立葉變換對(duì)為

式中：x,y為時(shí)域變量；u,v為頻域變量。二維信號(hào)的傅立葉變換F(u,v)——圖像頻譜。3.2.2離散傅立葉變換（DiscreteFourierTransform，DFT)

1.一維DFT

要在數(shù)字圖像處理中應(yīng)用傅立葉變換，還需要解決兩個(gè)問(wèn)題：

一是在數(shù)學(xué)中進(jìn)行傅立葉變換的f(x)為連續(xù)（模擬）信號(hào)，而計(jì)算機(jī)處理的是數(shù)字信號(hào)；

二是數(shù)學(xué)上采用無(wú)窮大概念，而計(jì)算機(jī)只能進(jìn)行有限次計(jì)算。通常將受這種限制的傅立葉變換稱(chēng)為離散傅立葉變換。

(3.24)式中：x，u=0，1，2，…,N－1。

注：下式中的系數(shù)1/N也可以放在上式中，有時(shí)也可在傅立葉正變換和逆變換前分別乘以 ，這是無(wú)關(guān)緊要的，只要正變換和逆變換前系數(shù)乘積等于1/N即可。

設(shè){f(x)|f(0),f(1),f(2),…,f(N-1)}為一維信號(hào)f(x)的N個(gè)抽樣，其離散傅立葉變換對(duì)為由歐拉公式可知

并利用cos(－θ)=cos(θ)，可得

可見(jiàn)，離散序列的傅立葉變換仍是一個(gè)離散的序列，每一個(gè)u對(duì)應(yīng)的傅立葉變換結(jié)果是所有輸入序列f(x)的加權(quán)和（每一個(gè)f(x)都乘以不同頻率的正弦和余弦值），u決定了每個(gè)傅立葉變換結(jié)果的頻率。

通常傅立葉變換為復(fù)數(shù)形式，

式中，R(u)和I(u)分別是F(u)的實(shí)部和虛部。也可表示成指數(shù)形式：

F(u)=|F(u)|ejφ(u)其中頻譜或幅度譜相位譜能量譜或功率譜

2.二維DFT

很容易將一維離散傅立葉變換推廣到二維。二維離散傅立葉變換對(duì)定義為式中：x,y為時(shí)域變量，u,v為頻域變量。

u,x=0,1,2,…,M-1；v,y=0,1,2,…,N-1；系數(shù)1/MN可以在正變換或逆變換中。二維離散函數(shù)的傅立葉頻譜、相位譜和能量譜分別為式中，R(u,v)和I(u,v)分別是F(u,v)的實(shí)部和虛部。

傅立葉頻譜相位譜能量譜3.2.3離散傅立葉變換的性質(zhì)

表7-1二維離散傅立葉變換的性質(zhì)

1.可分離性

由可分離性可知，一個(gè)二維傅立葉變換可分解為兩步進(jìn)行，其中每一步都是一個(gè)一維傅立葉變換。圖7-4用兩次一維DFT計(jì)算二維DFT

2.平移性質(zhì)

平移性質(zhì)表明，只要將f(x,y)乘以因子(－1)x+y，再進(jìn)行離散傅立葉變換，即可將圖像的頻譜原點(diǎn)（0，0）移動(dòng)到圖像中心（M／2,N／2）處。圖3-5是簡(jiǎn)單方塊圖像平移的結(jié)果。圖3-5傅立葉頻譜平移示意圖(a)原圖像；（b）無(wú)平移的傅立葉頻譜；（c）平移后的傅立葉頻譜(a)(b)(c)3.旋轉(zhuǎn)不變性由旋轉(zhuǎn)不變性可知，如果時(shí)域中離散函數(shù)旋轉(zhuǎn)θ0角度，則在變換域中該離散傅立葉變換函數(shù)也將旋轉(zhuǎn)同樣的角度。（a）原始圖像；（b）原始圖像的傅立葉頻譜；（c）旋轉(zhuǎn)45°后的圖像；（d）圖像旋轉(zhuǎn)后的傅立葉頻譜(a)(b)(d)(c)3.2.4快速離散傅立葉變換離散傅立葉變換計(jì)算量非常大，運(yùn)算時(shí)間長(zhǎng)?？梢宰C明其運(yùn)算次數(shù)正比于N2，特別是當(dāng)N較大時(shí)，其運(yùn)算時(shí)間將迅速增長(zhǎng)，以至于無(wú)法容忍。為此，研究離散傅立葉變換的快速算法（FastFourierTransform，F(xiàn)FT）是非常有必要的?？焖俑盗⑷~變換算法（FFT）是1965年Cooley和Tukey首先提出的。采用該FFT算法，其運(yùn)算次數(shù)正比于NlbN，當(dāng)N很大時(shí)計(jì)算量可以大大減少。例如，F(xiàn)FT的運(yùn)算次數(shù)和DFT的運(yùn)算次數(shù)之比，當(dāng)N=1024時(shí)，比值為1／102.4；當(dāng)N=4096時(shí)，比值可達(dá)1／341.3。

由于二維離散傅立葉變換具有可分離性，即它可由兩次一維離散傅立葉變換計(jì)算得到，因此，僅研究一維離散傅立葉變換的快速算法即可。先將式寫(xiě)成(7-21)式中，W=e-j2π／N

，稱(chēng)為旋轉(zhuǎn)因子。

圖7-108點(diǎn)DFT逐級(jí)分解框圖3.3頻域變換的一般表達(dá)式3.3.1可分離變換

二維傅立葉變換可用通用的關(guān)系式來(lái)表示：（何東健P153）(3-73)(3-74)式中：g(x,y,u,v)稱(chēng)為正向變換核

h(x,y,u,v)稱(chēng)為反向變換核。如果g(x,y,u,v)=g1(x,u)g2（y,v） (7-38)

h(x,y,u,v)=h1(x,u)h2(y,v) (7-39)

則稱(chēng)正、反變換核是可分離的。進(jìn)一步，如果g1和g2，h1和h2在函數(shù)形式上一樣，則稱(chēng)該正、反變換核是對(duì)稱(chēng)的。

二維傅立葉變換對(duì)是一個(gè)特殊情況，它們的核為

可見(jiàn)，它們都是可分離的和對(duì)稱(chēng)的。

如前所述，二維傅立葉變換可以利用變換核的可分離性，用兩次一維變換來(lái)實(shí)現(xiàn)。對(duì)于其他的圖像變換，只要其變換核是可分離的，同樣也可用兩次一維變換來(lái)實(shí)現(xiàn)。如果先對(duì)f(x,y)的每一列進(jìn)行一維變換得到F(y,u)，再沿F(y,u)每一行取一維變換得到F(u,v)，其最終結(jié)果是一樣的。該結(jié)論對(duì)反變換核也適用。3.3.2圖像變換的矩陣表示

數(shù)字圖像都是實(shí)數(shù)矩陣，設(shè)f(x,y)為M×N的圖像灰度矩陣通常為了分析、推導(dǎo)方便，可將可分離變換寫(xiě)成矩陣的形式：F=PfQf=P-1FQ-1

其中，F(xiàn)、f是二維M×N的矩陣；P是M×M矩陣；Q是N×N矩陣。(3.81)(3-79)式中，u=0,1,2,…,M－1，v=0,1,2,…,N－1。對(duì)二維離散傅立葉變換，則有

(3.85)

實(shí)踐中，除了DFT變換之外，還采用許多其他的正交變換。例如：離散余弦變換沃爾什-哈達(dá)瑪變換

K-L變換。3.4離散余弦變換（DCT）

離散余弦變換（DiscreteCosineTransform，DCT）的變換核為余弦函數(shù)。是一種可分離的變換。

DCT除了具有一般的正交變換性質(zhì)外，它的變換陣的基向量能很好地描述人類(lèi)語(yǔ)音信號(hào)和圖像信號(hào)的相關(guān)特征。因此，在對(duì)語(yǔ)音信號(hào)、圖像信號(hào)的變換中，DCT變換被認(rèn)為是一種準(zhǔn)最佳變換。近年頒布的一系列壓縮編碼的國(guó)際標(biāo)準(zhǔn)建議中(如JPEG、H.263）都把DCT作為其中的一個(gè)基本處理模塊。3.4.1一維離散余弦變換

一維DCT的變換核定義為

一維DCT定義如下：式中，u,x=0,1,2,…,N－1。

將變換式展開(kāi)整理后，可以寫(xiě)成矩陣的形式，即

F=Gf（7-50）其中

一維DCT的逆變換IDCT定義為

(3.64)

式中，

x,u=0,1,2,…,N－1。可見(jiàn)一維DCT的逆變換核與正變換核是相同的。

3.4.2二維離散余弦變換考慮到兩個(gè)變量，很容易將一維DCT的定義推廣到二維DCT。其正變換核為

式中，C(u)和C(v)的定義同前式；

x,u=0,1,2,…,M－1；

y,v=0,1,2,…,N－1。二維DCT定義如下：設(shè)f(x,y)為M×N的圖像矩陣，則

式中：x,u=0,1,2,…,M－1；

y,v=0,1,2,…,N－1。二維DCT逆變換定義如下：

二維DCT的逆變換核與正變換核相同，且是可分離的，即式中：C(u)和C(v)的定義同前式；

x,u=0,1,2,…,M－1；

y,v=0,1,2,…,N－1。

通常根據(jù)可分離性，二維DCT可用兩次一維DCT來(lái)完成，其算法流程與DFT類(lèi)似，即

類(lèi)似一維矩陣形式的DCT，可以寫(xiě)出二維DCT的矩陣形式如下：

F=GfGT

3.4.3DCT變換的特點(diǎn)DCT變換的基本思想：

將N點(diǎn)的f(x)延拓后形成2N點(diǎn)的實(shí)偶函數(shù)，其DCT也是一個(gè)2N點(diǎn)的實(shí)偶函數(shù)，然而實(shí)際有效信息只有一半。所以各取時(shí)域和頻域的一半作為DCT。圖3-11DFT和DCT的頻譜分布（a）DFT頻譜分布；（b）DCT頻譜分布從圖中可以看出，對(duì)于DCT而言，(0,0)點(diǎn)對(duì)應(yīng)于頻譜的低頻成分，(N-1,N-1)點(diǎn)對(duì)應(yīng)于高頻成分，而同階的DFT中，(N／2,N／2)點(diǎn)對(duì)應(yīng)于高頻成分（注：此頻譜圖中未作頻譜中心平移）。

DCT的本質(zhì)仍然是DFT，所表現(xiàn)的頻域特征和DCT所表現(xiàn)的頻域特征是相同的。二維DCT的頻譜分布與DFT相差一倍，如圖3-11所示。

DCT變換的特點(diǎn)：實(shí)數(shù)變換確定的變換矩陣（與變換對(duì)象內(nèi)容無(wú)關(guān)）準(zhǔn)最佳變換性能（與K-L變換相比）二維DCT是可分離的變換DCT的本質(zhì)仍然是DFT，所表現(xiàn)的頻域特征是相同的。二維DCT的頻譜分布與DFT相差一倍。有快速DCT（FCT）算法。由于DFT和IDFT已有快速算法FFT和IFFT，因此可用它們實(shí)現(xiàn)快速DCT和IDCT算法FCT及IFCT。不過(guò)，由于FFT及IFFT中要涉及到復(fù)數(shù)運(yùn)算，因此這種FCT及IFCT算法并不是最佳的。有多種快速DCT（FCT），介紹一種由FFT的思路發(fā)展起來(lái)的FCT。3.4.4快速離散余弦變換（FCT）首先，將f(x)延拓為x=0,1,2,…,N-1x=N，N+1,…,2N-1

按照一維DCT的定義，fe(x)的DCT為

由于 為fe(x)的2N點(diǎn)DFT。因此，在作DCT時(shí)，可把長(zhǎng)度為N的f(x)的長(zhǎng)度延拓為2N點(diǎn)的序列fe(x)，然后對(duì)fe(x)作DFT，最后取DFT的實(shí)部便可得到DCT的結(jié)果。同理對(duì)于離散余弦逆變換IDCT，可首先將F(u)延拓為u=0,1,2,…,N-1u=N,N+1,…,2N-1(7-62)IDCT為

（7-63）可見(jiàn)，IDCT可由 的2N點(diǎn)的IDFT來(lái)實(shí)現(xiàn)。

3.5離散沃爾什-哈達(dá)瑪變換（WHT）

傅立葉變換和余弦變換，是由正弦－余弦或余弦函數(shù)為基本正交函數(shù)展開(kāi)而構(gòu)成的，而沃爾什（Walsh）變換是由兩個(gè)數(shù)值，即＋1或－1為基函數(shù)的級(jí)數(shù)展開(kāi)而成的，它也滿(mǎn)足完備正交特性。由于沃爾什函數(shù)是二值正交函數(shù)，與數(shù)字邏輯中的兩個(gè)狀態(tài)相對(duì)應(yīng)，因此，更適應(yīng)于計(jì)算機(jī)技術(shù)、數(shù)字信號(hào)處理等應(yīng)用領(lǐng)域。3.5.1一維離散沃爾什-哈達(dá)瑪變換(何P157)

1.沃爾什（Walsh）函數(shù)

它是一個(gè)完備正交函數(shù)系，其值只能?。?和－1。從排列次序上可將沃爾什函數(shù)分為三種定義方法：按照沃爾什排列來(lái)定義（按列率排序）；按照佩利排列來(lái)定義（按自然排序）；按照哈達(dá)瑪排列來(lái)定義。由于哈達(dá)瑪排序的沃爾什函數(shù)是由2n（n=0，1，2，…）階哈達(dá)瑪矩陣（HadamardMatrix）得到的，而哈達(dá)瑪矩陣的最大優(yōu)點(diǎn)在于它具有簡(jiǎn)單的遞推關(guān)系，即高階矩陣可用兩個(gè)低階矩陣的克羅內(nèi)克積求得，因此在此只介紹哈達(dá)瑪排列定義的沃爾什變換。

N=2n階哈達(dá)瑪矩陣每一行的符號(hào)變化規(guī)律對(duì)應(yīng)于某一個(gè)沃爾什函數(shù)的符號(hào)變化規(guī)律，即N=2n階哈達(dá)瑪矩陣的每一行對(duì)應(yīng)于一個(gè)離散沃爾什函數(shù)，哈達(dá)瑪矩陣與沃爾什函數(shù)系不同之處僅僅是行的次序不同。

2n階哈達(dá)瑪矩陣有如下形式：

哈達(dá)瑪矩陣的階數(shù)是按N＝2n(n＝0,1,2,…)規(guī)律排列的，階數(shù)較高的哈達(dá)瑪矩陣，可以利用矩陣的克羅內(nèi)克積運(yùn)算，由低階哈達(dá)瑪矩陣遞推得到，即

矩陣的克羅內(nèi)克積(KroneckerProduct)運(yùn)算用符號(hào)記作A⊙B，其運(yùn)算規(guī)律如下：設(shè)則(7-68)(7-69)2.離散沃爾什-哈達(dá)瑪變換

一維離散沃爾什變換定義為

(7-70)一維離散沃爾什逆變換定義為

(7-71)式中，變換核Walsh(u,x)為沃爾什函數(shù)。若將Walsh(u,x)用哈達(dá)瑪矩陣表示，并將變換寫(xiě)成矩陣形式，則為和(7-72)(7-73)式中，［HN］為N階哈達(dá)瑪矩陣。

由哈達(dá)瑪矩陣的特點(diǎn)可知，沃爾什-哈達(dá)瑪變換的本質(zhì)上是將離散序列f(x)的各項(xiàng)值的符號(hào)按一定規(guī)律改變后，進(jìn)行加減運(yùn)算，因此，它比采用復(fù)數(shù)運(yùn)算的DFT和采用余弦運(yùn)算的DCT要簡(jiǎn)單得多。

3.5.2二維離散沃爾什變換

將一維WHT的定義推廣到二維WHT。二維WHT的正變換核和逆變換核分別為和式中：x,u=0,1,2,…,M－1；

y,v=0,1,2,…,N－1。二維離散沃爾什變換的矩陣形式表達(dá)式為

式中，為M階哈達(dá)瑪矩陣，為N階哈達(dá)瑪矩陣?yán)?：有2個(gè)二維數(shù)字圖像信號(hào)矩陣分別為和求這兩個(gè)信號(hào)的二維WHT。

根據(jù)題意，M=N=4，其二維WHT變換核為

例2：一幅數(shù)字圖像及對(duì)其進(jìn)行二維WHT變換的結(jié)

圖7-12二維WHT結(jié)果（a）原圖像；（b）WHT結(jié)果

WHT變換的特點(diǎn)：（1)WHT是將一個(gè)函數(shù)變換成取值為＋1或－1的基本函數(shù)構(gòu)成的級(jí)數(shù)，用它來(lái)逼近數(shù)字脈沖信號(hào)時(shí)要比FFT有利。（2)WHT只需要進(jìn)行實(shí)數(shù)運(yùn)算，存儲(chǔ)量比FFT要少得多，運(yùn)算速度也快得多。（3)二維WHT具有能量集中的特性，而且原始數(shù)據(jù)中數(shù)字越是均勻分布，經(jīng)變換后的數(shù)據(jù)越集中于矩陣的邊角上。因此，二維WHT可用于壓縮圖像信息。在圖像傳輸、通信技術(shù)和數(shù)據(jù)壓縮中被廣泛使用。3.5.3快速沃爾什變換（FWHT）

類(lèi)似于FFT，WHT也有快速算法FWHT，也可將輸入序列f(x)按奇偶進(jìn)行分組，分別進(jìn)行WHT。FWHT的基本關(guān)系為(7-78)

WHT的變換核是可分離和對(duì)稱(chēng)的，因此二維WHT也可分為兩個(gè)一維的WHT分別用FWHT進(jìn)行變換而得到最終結(jié)果，由此便可實(shí)現(xiàn)二維的FWHT。3.6離散K-L變換K-L變換（Karhunen-LoeveTransform)也稱(chēng)為特征向量變換、主分量變換或霍特林變換。完全從圖像的統(tǒng)計(jì)特征出發(fā)實(shí)現(xiàn)的變換主要應(yīng)用：數(shù)據(jù)壓縮、圖像旋轉(zhuǎn)、遙感多光譜圖像的特征選擇和統(tǒng)計(jì)識(shí)別。設(shè)f(x,y)是N×N的圖像，可用N2×1維向量X表示

鑒于圖像信號(hào)是隨機(jī)變量，X向量的協(xié)方差矩陣定義為：其中，mx是X的平均值，X是N2維向量，

Cx是N2×N2實(shí)對(duì)稱(chēng)矩陣。Cx總可以找到N2個(gè)正交特征向量。設(shè)和是的特征向量和特征值，其中i=1,2,…,N2.K-L變換矩陣A的行就是Cx的特征向量。K-L變換式可表示為：其中，變換矩陣A獲得的過(guò)程為：

原始圖像f(x,y)→得到X→X的協(xié)方差矩陣→特征向量和特征值→K-L變換矩陣A。Y的協(xié)方差矩陣為：可以證明：Y的均值：Cy是對(duì)角陣，其主對(duì)角線(xiàn)上的元素是Cx的特征值。

K-L變換的特點(diǎn)：優(yōu)點(diǎn)：去相關(guān)性能很好。Y的各個(gè)元素是互不相關(guān)的，可見(jiàn)經(jīng)過(guò)K-L變換數(shù)據(jù)已經(jīng)解除了各個(gè)元素之間的相關(guān)性。這是最大優(yōu)點(diǎn)?？蓪⑺糜趫D像數(shù)據(jù)的旋轉(zhuǎn)或壓縮處理。常作為理論值參考。

缺點(diǎn)：（1）二維K-L變換是不可分離的變換；（2）是一種和圖像數(shù)據(jù)有關(guān)的變換，必須計(jì)算圖像矩陣的特征向量和特征值，計(jì)算量龐大。所以難以應(yīng)用到實(shí)際。3.7小波變換簡(jiǎn)介1.小波變換的理論基礎(chǔ)信號(hào)分析是為了獲得時(shí)間和頻率之間的相互關(guān)系。傅立葉變換提供了有關(guān)頻率域的信息，但有關(guān)時(shí)間的局部化信息卻基本丟失。

與傅立葉變換不同，小波變換是通過(guò)縮放母小波（Motherwavelet）的寬度來(lái)獲得信號(hào)的頻率特征，通過(guò)平移母小波來(lái)獲得信號(hào)的時(shí)間信息。對(duì)母小波的縮放和平移操作是為了計(jì)算小波系數(shù)，這些小波系數(shù)反映了小波和局部信號(hào)之間的相關(guān)程度。

2.連續(xù)小波變換（CWT）

圖7-13表示了正弦波和小波的區(qū)別.像傅立葉分析一樣，小波分析就是把一個(gè)信號(hào)分解為將母小波經(jīng)過(guò)縮放和平移之后的一系列小波，因此小波是小波變換的基函數(shù)。小波變換可以理解為用經(jīng)過(guò)縮放和平移的一系列小波函數(shù)代替傅立葉變換的正弦波和余弦波進(jìn)行傅立葉變換的結(jié)果。從小波和正弦波的形狀可以看出，變化劇烈的信號(hào)，用不規(guī)則的小波進(jìn)行分析比用平滑的正弦波更好，即用小波更能描述信號(hào)的局部特征。圖7-13正弦波和小波（a）正弦波曲線(xiàn)；(b)小波曲線(xiàn)正弦波：從負(fù)無(wú)窮一直延續(xù)到正無(wú)窮，是平滑而且是可預(yù)測(cè)的；小波：