圖像變換2離散余弦變換.ppt

1,3. 2 離散余弦變換,圖像處理中常用的正交變換除了傅里葉變換外，還有其他一些有用的正交變換。其中離散余弦就是一種。離散余弦變換表示為DCT。,2,3.2.1 離散余弦變換的定義,一維離散余弦變換的定義由下式表示,(374),(375),3,式中 是第 個余弦變換系數(shù)， 是廣義頻率變量， ； 是時域N點序列，,一維離散余弦反變換由下式表示,(376),顯然，式(374)式(375)和式(376)構成了一維離散余弦變換對。,4,二維離散余弦變換的定義由下式表示,(377),5,式(377)是正變換公式。其中 是空間域二維向量之元素。 ， 是變換系數(shù)陣列之元素。式中表示的陣列為N N,6,二維離散余弦反變換由下式表示,(378),7,8,9,10,余弦變換與傅里葉變換有什么關系？,11,式中的符號意義同正變換式一樣。式(377)和式(378)是離散余弦變換的解析式定義。更為簡潔的定義方法是采用矩陣式定義。如果令N4，那么由一維解析式定義可得如下展開式,(379),12,寫成矩陣式,(380),若定義 為變換矩陣， 為變換系數(shù)矩陣， 為時域數(shù)據(jù)矩陣，則一維離散余弦變換的矩陣定義式可寫成如下形式,(381),13,同理，可得到反變換展開式,(382),寫成矩陣式,14,即,(384),當然，二維離散余弦變換也可以寫成矩陣式,(385),式中 是空間數(shù)據(jù)陣列， 是變換系數(shù)陣列， 是變換矩陣， 是 的轉置。,15,3.2.2 離散余弦變換的正交性,由一維DCT的定義可知,它的基向量是,(386),16,在高等數(shù)學中，切比雪夫多項式的定義為,(387),17,式中 是 和 的多項式。它的第N個多項式為,如果,那么,將此式代入,18,顯然，這與一維DCT的基向量是一致的。因為切比雪夫多項式是正交的，所以DCT也是正交的。另外，離散余弦變換的正交性也可以通過實例看出。如前所示，當N時，,(388),則,19,顯然,這是滿足正交條件的。從上述討論可見，離散余弦變換是一類正交變換。,20,3.2.3 離散余弦變換的計算,與傅里葉變換一樣，離散余弦變換自然可以由定義式出發(fā)進行計算。但這樣的計算量太大，在實際應用中很不方便。所以也要尋求一種快速算法。 首先，從定義出發(fā)，作如下推導,21,(389),22,式中 是取其實部的意思。如果把時域數(shù)據(jù)向量作下列延拓，即：,(390),則 的離散余弦變換可寫成下式,23,(391),24,由式(391)可見,是2N點的離散傅里葉變換。所以，在作離散余弦變換時，可以把序列長度延拓為2N，然后作離散傅里葉變換，產(chǎn)生的結果取其實部便可得到余弦變換。,25,同樣道理，在作反變換時，首先在變換空間，把 作如下下延拓,(392),那么，反變換也可用式(393)表示,26,(393),27,由式(393)可見，離散余弦反變換可以從 的2N點反傅里葉變換實現(xiàn)。,28,3.3 離散K-L變換,又稱為霍特林(Hotelling)變換 KL(Karhunen-Loeve)或DKT 以圖像的統(tǒng)計性質(zhì)為基礎的 變換核矩陣由圖像陣列的協(xié)方差矩陣的特征值和特征向量所決定又稱為特征向量變換,29,當變量之間存在一定的相關關系時，可以通過原始變量的線性組合，構成數(shù)目較少的不相關的新變量代替原始變量，而每個新變量都含有盡量多的原始變量的信息。這種處理問題的方法，叫做主成分分析，新變量叫做原始變量的主成分。 目的是尋找任意統(tǒng)計分布的數(shù)據(jù)集合之主要分量的子集。相應的基向量組滿足正交性且由它定義的子空間最優(yōu)地考慮了數(shù)據(jù)的相關性。將原始數(shù)據(jù)集合變換到主分量空間使單一數(shù)據(jù)樣本的互相關性(cross-correlation)降低到最低點。,30,圖像協(xié)方差矩陣,假設對某幅NN的圖像f(x,y)，在某個傳輸通道上傳輸了M次，因會受到各種因素的隨機干擾，接收到是一個圖像集合,將M次傳送的圖像集合寫成M個N2維向量X1,X2,Xi,XM, 生成向量的方法可以采用行堆疊或列堆疊的方法，對第i次獲得的圖像fi(x,y)，可用N2維向量Xi表示：,31,問題是：如何選取一個合適的正交變換A，使得變換后的圖像Y=AX 1)是具有MN2個分量的向量 2)由Y經(jīng)反變換而恢復的 (向量X的估值)和原始圖像具有最小的均方誤差，即,稱滿足這兩個條件的正交變換A為K-L變換。如果能找到這樣一個變換，那么就意味著經(jīng)過一個變換，不僅刪除了N2-M個分量，并且由變換結果Y重新恢復的圖像,是有效的過濾了隨機干擾的原圖像的最佳逼近。,32,X向量的協(xié)方差矩陣CX定義為,設ei和i是協(xié)方差矩陣CX對應的特征向量和特征值，將特征值按減序排列，即,則K-L變換核矩陣A的行用CX的特征值i所對應的特征向量ei構成：,33,直接求矩陣 CX的特征值和特征向量很困難。這是因為CX是N2N2維矩陣，盡管圖像的大小N可能不是很大的，但N2卻是很大的數(shù)據(jù)。這樣求其特征向量和特征值速度較慢。但如果樣本圖象個數(shù)M不太多，可以先計算出MM維方陣LATA的特征值k和特征向量 vk,左乘矩陣A，則有,是矩陣CX的 特征向量,可以選擇P(PM)個較大特征值對應的特征向量（主成分），構造新的P維主成分空間Q,因為CX是實對稱矩陣，總能找到一個標準正交的特征向量集合，使A-1=AT，那么可得K-L反變換為,34,K-L變換的性質(zhì)和特點,（1）Y的平均值向量my0，即為零向量0,（2）Y向量的協(xié)方差,35,（3）對角性,對角線上的元素是原始圖像向量的協(xié)方差矩陣CX對應的特征值i，它也是Y向量的方差。而非對角線上的元素值為0，說明Y向量中各元素之間相關性小，而CX的非對角線上元素不為0，說明原始圖像元素之間相關性強，這就是采用K-L變換進行編碼，數(shù)據(jù)壓縮比大的原因,顯然K-L坐標系將矩陣CX對角化了，換句話說，通過K-L變換，消除了原有向量X的各分量之間的相關性，從而可能去掉那些帶有較少信息的坐標軸，以達到降低特征空間維數(shù)的目的。,36,在原來坐標系中，要用兩個分量X1,X2來表示各個樣本，而在K-L坐標系中，只要用e1就可以，去掉e2并不會帶來很大的誤差,假設矩陣CX只有少數(shù)幾個數(shù)值大的特征值，而其余的特征值數(shù)值很小，K-L坐標系就可以有效的進行信息壓縮,37,K-L變換的最大優(yōu)點是去相關性好，可用于數(shù)據(jù)壓縮和圖像旋轉 主要困難是由于協(xié)方差矩陣CX求特征值和特征向量解方程的計算量大，同時K-L變換是非分離的，二維不可分，一般情況下，K-L變換沒有快速算法,38,實例,以K-L變換進行自動的人臉識別為例說明,我們把一幅數(shù)字圖像看成一個矩陣或一個數(shù)組，用B(i,j)或bij 表示，一幅NN大小的人臉圖像按列相連構成一個N2維矢量,x=( b11 b21bN1 b12b22bN2 b1N b2NbNN),它可視為N2維空間中的一個點，假設N=128。由于人臉結構的相似性，當把很多這樣的人臉圖像歸一化之后，這些圖像在這一超高維空間中不是隨機或散亂分布的，而是存在某種規(guī)律，因此可以通過K-L變換用一個低維子空間描述人臉圖像，同時又能保存所需要的識別信息,39,圖像的歸一化,對于一個全自動的人臉識別系統(tǒng)，其首要的工作是人臉圖像的分割以及主要器官的定位。另外，由于K-L變換本質(zhì)上依賴于圖像灰度在空間分布上的相關性，因此還需要對人臉圖像進行一系列的預處理，以達到位置校準和灰度歸一化的目的,假設已根據(jù)分割及定位算法，得到了人臉正面圖像左右兩眼中心的位置，并分別記為Er和El，則可通過下述步驟達到圖像校準的目的,40,1、進行圖像旋轉，以使Er和El的連線ErEl保持水平。這保證了人臉方向的一致性，體現(xiàn)了人臉在圖像平面內(nèi)的旋轉不變性,2、根據(jù)圖所示的比例關系，進行圖像裁剪。圖中，O點為ErEl的中點，且d=ErEl。經(jīng)過裁剪，在2d2d的圖像內(nèi)，可保證O點固定于(0.5d,d)處。這保證了人臉位置的一致性，體現(xiàn)了人臉在圖像平面內(nèi)的平移不變性,3、進行圖像縮小和放大變換，得到統(tǒng)一大小的標準圖像，規(guī)定標準圖像的大小為128128象素點，則縮放倍數(shù)為=2d/128。這使得d=ErEl為定長(64個象素點)，即保證了人臉大小的一致性，體現(xiàn)了人臉在圖像平面內(nèi)的尺度不變性,41,經(jīng)過校準，不僅在一定程度上獲得了人臉表示的幾何不變性，而且還基本上消除了頭發(fā)和背景的干擾。,完成了旋轉、平移和尺度不變性后，需要對校準的圖像做灰度拉伸，以改善圖像的對比度，然后采用直方圖修正技術使圖像具有統(tǒng)一的均值和方差，一部分消除光照強度的影響,假設人臉數(shù)據(jù)庫中，由20人，每人10幅人臉圖像,42,K-L變換,以歸一化后的標準圖像做為訓練樣本集，以該樣本集的總體散布矩陣為協(xié)方差矩陣，即,xi為第i個訓練樣本的圖像向量， 為訓練樣本集的平均圖像，M為訓練樣本的總數(shù),為了N2N2維矩陣的特征值和正交歸一的特征向量，直接計算是困難的，因此引入一個定理，奇異值分解SVD,43,設A是一秩為r的nr維矩陣，則存在兩個正交矩陣：,以及對角陣,滿足,其中i為矩陣AAT和ATA的非0特征值，u和v分別為AAT和ATA對應于i的特征向量，上述分解稱為矩陣A地奇異值分解，為A的奇異值,推論,44,由于可表示為：,故，構造矩陣：,容易求其特征值i及相應的正交歸一特征向量vi( i=0,1,2M-1)。由推論可知，的正交歸一化特征向量ui為,這就是圖像的特征向量，它是通過計算較低維矩陣R的特征值與特征向量而間接求出的,45,將特征值從大到小排序：0 1 r-