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

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