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

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

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

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

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

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

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

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

式中：x稱為時域變量，u稱為頻域變量。信號的傅立葉變換F(u)——頻譜

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

二維傅立葉變換對為

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

1.一維DFT

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

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

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

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

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

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

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

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

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

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

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

2.二維DFT

很容易將一維離散傅立葉變換推廣到二維。二維離散傅立葉變換對定義為式中：x,y為時域變量，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)的實部和虛部。

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

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

1.可分離性

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

2.平移性質(zhì)

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

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

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

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

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

h(x,y,u,v)稱為反向變換核。如果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)

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

二維傅立葉變換對是一個特殊情況，它們的核為

可見，它們都是可分離的和對稱的。

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

數(shù)字圖像都是實數(shù)矩陣，設(shè)f(x,y)為M×N的圖像灰度矩陣通常為了分析、推導(dǎo)方便，可將可分離變換寫成矩陣的形式：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。對二維離散傅立葉變換，則有

(3.85)

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

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

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

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

一維DCT的變換核定義為

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

將變換式展開整理后，可以寫成矩陣的形式，即

F=Gf（7-50）其中

一維DCT的逆變換IDCT定義為

(3.64)

式中，

x,u=0,1,2,…,N－1?？梢娨痪SDCT的逆變換核與正變換核是相同的。

3.4.2二維離散余弦變換考慮到兩個變量，很容易將一維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來完成，其算法流程與DFT類似，即

類似一維矩陣形式的DCT，可以寫出二維DCT的矩陣形式如下：

F=GfGT

3.4.3DCT變換的特點DCT變換的基本思想：

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

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

DCT變換的特點：實數(shù)變換確定的變換矩陣（與變換對象內(nèi)容無關(guān)）準(zhǔn)最佳變換性能（與K-L變換相比）二維DCT是可分離的變換DCT的本質(zhì)仍然是DFT，所表現(xiàn)的頻域特征是相同的。二維DCT的頻譜分布與DFT相差一倍。有快速DCT（FCT）算法。由于DFT和IDFT已有快速算法FFT和IFFT，因此可用它們實現(xiàn)快速DCT和IDCT算法FCT及IFCT。不過，由于FFT及IFFT中要涉及到復(fù)數(shù)運(yùn)算，因此這種FCT及IFCT算法并不是最佳的。有多種快速DCT（FCT），介紹一種由FFT的思路發(fā)展起來的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點DFT。因此，在作DCT時，可把長度為N的f(x)的長度延拓為2N點的序列fe(x)，然后對fe(x)作DFT，最后取DFT的實部便可得到DCT的結(jié)果。同理對于離散余弦逆變換IDCT，可首先將F(u)延拓為u=0,1,2,…,N-1u=N,N+1,…,2N-1(7-62)IDCT為

（7-63）可見，IDCT可由 的2N點的IDFT來實現(xiàn)。

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

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

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

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

N=2n階哈達(dá)瑪矩陣每一行的符號變化規(guī)律對應(yīng)于某一個沃爾什函數(shù)的符號變化規(guī)律，即N=2n階哈達(dá)瑪矩陣的每一行對應(yīng)于一個離散沃爾什函數(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)算用符號記作A⊙B，其運(yùn)算規(guī)律如下：設(shè)則(7-68)(7-69)2.離散沃爾什-哈達(dá)瑪變換

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

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

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

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

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個二維數(shù)字圖像信號矩陣分別為和求這兩個信號的二維WHT。

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

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

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

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

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

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

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

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

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

K-L變換的特點：優(yōu)點：去相關(guān)性能很好。Y的各個元素是互不相關(guān)的，可見經(jīng)過K-L變換數(shù)據(jù)已經(jīng)解除了各個元素之間的相關(guān)性。這是最大優(yōu)點。可將它用于圖像數(shù)據(jù)的旋轉(zhuǎn)或壓縮處理。常作為理論值參考。

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

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

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

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