格拉斯曼流形上點的識別

格拉斯曼流形上點的識別

0子空間局部感知結(jié)構(gòu)和局部識別傳統(tǒng)的圖像識別領(lǐng)域通常以單幅靜態(tài)圖像作為研究對象，并在可控場景中獲得良好的性能。然而,基于單幅靜態(tài)圖像學(xué)習(xí)算法在很多實際應(yīng)用場景中效果不佳。隨著數(shù)字成像和海量存儲設(shè)備等硬件設(shè)備快速發(fā)展以及互聯(lián)網(wǎng)資源的觸手可及,人們能夠獲取的圖像涵蓋了物體的各種表觀變化,如姿態(tài)、表情、光照角度等,從而為基于圖像集合學(xué)習(xí)問題提供了豐富的數(shù)據(jù)。在這類問題中,每個圖像集合通常包含同一類別的多個圖像樣本,利用了圖像樣本綜合信息提取特征,提升算法的性能,因此,基于圖像集合的識別問題受到越來越廣泛的關(guān)注。研究表明,將圖像集合建模為子空間,可以達到更好的性能。Yamaguchi等人提出了針對人臉識別問題的互子空間方法(MSM),開創(chuàng)了利用子空間對圖像集合非參數(shù)建模方法研究的先河,引起各領(lǐng)域科學(xué)研究者的廣泛關(guān)注,衍生出一系列改進算法。Fukui等人提出約束互子空間方法(CMSM),通過把圖像集合投影到一個對分類最有利的子空間上,然后計算投影后的圖像集合之間的相似性,算法的不足之處在于需人為設(shè)置子空間的維數(shù)及其相應(yīng)的參數(shù),在無監(jiān)督情況下進行參數(shù)的選擇還沒有可靠的理論依據(jù)。Kim對Fukui的工作做了進一步的發(fā)展,提出了基于典型相關(guān)的圖像集合判別(DCC)學(xué)習(xí)和識別算法,采用主角作為子空間相似性度量,并期望尋求投影方向,使得數(shù)據(jù)映射到低維空間后,類間樣本盡可能“分開”。Chu等人提出基于圖像集的核判別變換(KDT),該算法是DCC算法的非線性拓展。Li等人把集成策略用于圖像集合的分類,提出了提升的全局和局部主角方法(BGLPA)。Wang等人提出了基于流形-流形距離框架的圖像集合人臉識別方法,將流形表示為一組局部線性模型的組合,采用子空間刻畫各局部模型。監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)是降維算法的兩種重要形式。通常,對無標(biāo)簽數(shù)據(jù)進行大量的標(biāo)定工作會耗費很大的代價。如果只使用少量的標(biāo)記樣本,那么所訓(xùn)練出的學(xué)習(xí)系統(tǒng)很難具有良好的泛化能力,如果只使用未標(biāo)記樣本則浪費了標(biāo)記樣本中所提供的有用信息。因此,無論是監(jiān)督算法還是無督算法都不能獲得令人滿意的結(jié)果。半監(jiān)督學(xué)習(xí)是介于監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)之間,它利用少量帶標(biāo)簽樣本來指導(dǎo)降維,同時又利用大量的不帶標(biāo)簽樣本來刻畫并保持樣本的局部幾何結(jié)構(gòu)。處理子空間問題的一種變通的方法是將子空間表示為格拉斯曼流形(Grassmannmanifold)上的點。近年來,一些研究者探討了在格拉斯曼流形上實現(xiàn)判別分析。這類算法的基本出發(fā)點是把格拉斯曼流形上松散分布的樣本,通過非線性變換壓縮到一個低維的格拉斯曼流形中,使樣本在該低維格拉斯曼流形中分布更緊湊,更利于分類,降低計算復(fù)雜度。Hamm等人提出了格拉斯曼流形判別分析(GDA),該方法將子空間表示成格拉斯曼流形上的點,利用格拉斯曼核度量子空間的相似度,實現(xiàn)格拉斯曼流形上數(shù)據(jù)非線性判別分析。盡管GDA表現(xiàn)出優(yōu)越的性能,然而該方法并沒有明確考慮數(shù)據(jù)分布的內(nèi)蘊幾何結(jié)構(gòu),從而影響樣本的判別性和模型的泛化能力。鑒于此,Harandi等人在圖嵌入框架的基礎(chǔ)上,提出了一種基于格拉斯曼流形局部判別分析方法(GEDAGM),采用在格拉斯曼流形上構(gòu)建類內(nèi)圖和類間圖刻畫類內(nèi)緊致性與類間可分性,以此獲取流形上數(shù)據(jù)的幾何結(jié)構(gòu)和局部信息。在全局方法無法奏效的情況下,局部學(xué)習(xí)方法提供了有效的解決方案。本文提出一種新穎的格拉斯曼流形上的半監(jiān)督判別分析方法(SDAGM),通過在格拉斯曼流形上構(gòu)建所有樣本(有標(biāo)簽和無標(biāo)簽)的近鄰圖來估計樣本分布的幾何結(jié)構(gòu),然后將其作為正則化項整合到GDA目標(biāo)函數(shù)中,在此正則化項的作用就是用來估計樣本空間的內(nèi)蘊幾何結(jié)構(gòu),從而學(xué)習(xí)更為有效的投影矩陣。本文方法具有以下優(yōu)點:1)以圖像集合為輸入單位,將子空間表示為格拉斯曼流形上的點,由此,圖像集合的判別分析問題轉(zhuǎn)化為格拉斯曼流形上數(shù)據(jù)的判別分析問題;2)引入投影核度量格拉斯曼流形之間距離,提升算法時間效率;3)在圖嵌入框架基礎(chǔ)上,通過引入“局部保持”正則化項,將格拉斯曼流形上的判別分析與正則化項整合于單個目標(biāo)函數(shù)。1莎拉斯曼流型及其初步分析1.1空間的線性子空間3g解釋格拉斯曼流形已成功應(yīng)用于控制領(lǐng)域和信號處理,近年來才逐步用于機器學(xué)習(xí)和模式識別領(lǐng)域。以下為格拉斯曼流形的定義。定義假設(shè)樣本均勻采樣于D維歐氏空間中的m維流形上,格拉斯曼流形GD,m是D×m正交矩陣等價類集合,即GD,m={Y|Y=XV,?V∈Ok},式中,X、Y是D×m正交矩陣,V是m×m正交矩陣,Ok為正交群的一個特例,即有Ok={Q|QTQ=I,det(Q)=1}。依據(jù)定義,如果格拉斯曼流形上的兩個點能夠通過正交變換相互獲得時,那么這兩個點是等價的。即矩陣W1=W2Q,式中,Q是r×r正交矩陣,并且列空間span(W1)=span(W2),從而W1和W2等價。由此可見,格拉斯曼流形GD,m直觀解釋為格拉斯曼流形是空間RD中所有m維線性子空間的集合,GD,m上的每個點是一個D×m維正交矩陣列空間所張成的子空間。如果圖像集合用線性子空間描述,則它們之間的距離可以用兩個子空間的主角來表示。事實上,格拉斯曼流形上兩點之間的距離可以由格拉斯曼核來表示。采用投影核來表示格拉斯曼流形上兩點之間的距離。1.2類間散度矩陣格拉斯曼流形上的判別分析基本思想是通過非線性映射將格拉斯曼流形M上數(shù)據(jù)點映射到一個新的格拉斯曼流形M′上,使各類內(nèi)樣本盡可能“緊湊”,類間樣本盡可能“分開”。所以使得最大化判別準(zhǔn)則為J=argmaxSΜ′BSΜ′WJ=argmaxSM′BSM′W(1)假設(shè)樣本集X來自格拉斯曼流行M上,M是D×m正交矩陣等價類集合。設(shè)帶標(biāo)簽的樣本集為XL={Xi}li=1li=1?M,樣本分別屬c個類別;不帶標(biāo)簽樣本集為XU={Xi}l+ui=l+1?M,式中,l+u=n。樣本集全體為X=XL∪XU={Xi}ni=1ni=1,Xi∈RD×m,i=1,2,…,n。X(i)j表示第i個類中第j個樣本。ni表示第i類中元素的個數(shù)。存在非線性映射Φ:M→M′,Xi→Yi把樣本映射到新的格拉斯曼流M′上。定義流形M′上的類間散度矩陣SΜ′B和類內(nèi)散度SΜ′W矩陣為SΜ′B=c∑i=1ni(mΜ′i-mΜ′)(mΜ′i-mΜ′)ΤSΜ′W=c∑i=1ni∑j=1(Y(i)j-mΜ′i)(X(i)j-mΜ′i)ΤmΜ′i=1nini∑j=1Y(i)jmΜ′=1cc∑i=1nimΜ′i=1lc∑i=1ni∑j=1Y(i)j與核學(xué)習(xí)方法相類似,假設(shè)流形M所嵌入的高維特征空間的特征向量為αi,αi一定位于所有的訓(xùn)練樣本X所張成的子空間中,即存在系數(shù)aij(j=1,…,l)使αi=l∑j=1aijXj,有Yi=[〈α1,Xi〉,〈α2,Xi〉,…,〈αd,Xi〉]T(2)式中,d為G′上子空間的維數(shù),即G′為RD上d維子空間所在的格拉斯曼流形,假設(shè)d個特征向量構(gòu)成投影矩陣α=[α1,…,αd]。由?αs,Xi?=?l∑j=1asjXj,Xi?=l∑j=1asj?Xj,Xi?=l∑j=1asjkLij=AΤsΚLi(3)式中,As=[as1,as2,…,asl]T,KLi=[kLi1,kLi2,…,kLil]T。把式(3)代入式(2)得Yi=[AΤ1KLi,AΤ2KLi,…,ATdKLi]T=ATKLi(4)式中,A=[A1|A2|…|Ad]。將式(4)代入式(1),經(jīng)過簡單數(shù)學(xué)推導(dǎo),得J=argmaxAΤΚLW(ΚL)ΤAAΤΚL(Ι-W)(ΚL)ΤA式中,核矩陣KL=[KL1|KL2|…|KLl],W是分塊對角矩陣。第i塊的矩陣W(i)=1ni1Tni/ni(1ni表示1的個數(shù)是ni個全1向量)。記所有帶標(biāo)簽數(shù)據(jù)的樣本矩陣為XL=[X(1),X(2),…,X(c)],定義L×L矩陣W=[W(1)0?00W(2)?0???00?W(c)](5)投影矩陣可通過廣義特征值問題KLW(KL)TA=λKL(I-W)(KL)TA求得。2基于內(nèi)涵幾何結(jié)構(gòu)的分類方法格拉斯曼判別分析是一種監(jiān)督判別分析方法,其目的是降維之后不同類樣本之間的可分性最大,然而該方法并沒有明確考慮對分類問題尤為重要的內(nèi)蘊幾何結(jié)構(gòu)。SDAGM包括一個正則化項,能夠更好地保持和優(yōu)化數(shù)據(jù)點之間的幾何結(jié)構(gòu)和判別信息。2.1注意點及分類參數(shù)的確定基于圖的半監(jiān)督降維算法的關(guān)鍵之處是一致性先驗假設(shè)。也就是說近鄰圖像集合在投影低維流形時有相似的嵌入。具體而言,已知n個數(shù)據(jù)點X={X1,X2,…,Xn}分布在格拉斯曼流形上,如果數(shù)據(jù)點Xi屬于Xj的k-近鄰,或者Xj屬于Xi的k-近鄰,則稱Xi和Xj為近鄰點,并在圖上以邊相連,并附上相應(yīng)的權(quán)重Sij,其定義如下:Sij={exp(-∥Xi-Xj∥2/2σ2)Xi∈Νk(Xj)且Xj∈Νk(Xi)0其他(6)式中,Nk(Xi)和Nk(Xj)分別表示Xi和Xj的k-最近鄰,σ和k為自由參數(shù)。依據(jù)流形假設(shè),如果數(shù)據(jù)點之間有邊連接,則被投影到低維流形時,數(shù)據(jù)點依然保持近鄰。定義局部保持正則化項R=12∑i,j(Yi-Yj)2Sij=12∑i,j(ΑΤΚi-ΑΤΚj)2Sij=∑iΑΤΚiΚΤiΑSij-∑ijΑΤΚiΚΤjΑSij=AΤΚDΚΤΑ-ΑΤΚSΚΤΑ=ΑTΚLΚTΑ(7)式中,A=[A1|A2|…|Ad]為投影矩陣;K=[K1|K2|…|Kn]為核矩陣;矩陣D為一對角矩陣,且Dii=∑jSij,S為權(quán)矩陣,L=D-S為圖拉普拉斯矩陣。最小化正則化項式(7)意味著,如果圖中有權(quán)相連的兩點Xi和Xj被映射后反而遠離時,S的損失函數(shù)會產(chǎn)生很大的補償。因此,最小化正則化項就是試圖確保如果Xi和Xj近鄰,那么Yi和Yj同樣近鄰。在格拉斯曼流上的判別分析的基礎(chǔ)上,考慮當(dāng)數(shù)據(jù)取樣于嵌入在高維空間低維流形數(shù)據(jù)的幾何結(jié)構(gòu),最大化目標(biāo)函數(shù)J=argmaxAΤΚLW(ΚL)ΤAAΤΚL(Ι-W)(ΚL)ΤA+βAΤΚLΚΤA(8)式中,β為正則化參數(shù),用于折中目標(biāo)函數(shù)中兩項的重要程度;易知,若β=0,則SDAGM就退化為GDA。最大化準(zhǔn)則函數(shù)可以通過求解廣義特征值問題,即KLW(KL)TA=λ(KL(I-W)(KL)T+βKLKT)A(9)如果Α1,A2,…,Ad為式(9)廣義特征方程的前d個最大特征值所對應(yīng)的特征向量,定義投影矩陣A=[A1|A2|…|Ad]。對于一個新的圖像集Xq在αk上的投影為Vkq=?αk,Xq?=?n∑j=1akjXj,Xq?=n∑j=1akj?Xj,Xq?=AΤkΚq(10)式中,Kq=[〈X1,Xq〉,…,〈Xn,Xq〉]T。獲取降維后樣本的特征向量之后,采取最近鄰分類器進行分類。設(shè)有n訓(xùn)練圖像集合{X1,X2,…,Xn},這些圖像樣本集是由N個單圖像組成的,共有c類,經(jīng)過SDAGM算法提取的特征向量為{V1,V2,…,Vn},每一個圖像集合都屬于一個類別ωk,k=1,…,c。測試圖像集合Xtest的經(jīng)變換后的特征向量為Vtest,如果滿足d(Vtest,Vi)=minid(Vtest,Vi),Vi∈ωki=1,…,N;k=1,…,c則測試圖像集合Xtest∈ωk。2.2缺失標(biāo)簽樣本的降維為了不失一般性,假設(shè)帶標(biāo)簽樣本集XL={X1,X2,…,Xl}中的樣本點是按照它們的標(biāo)簽順序排列的。SDAGM算法描述如下:數(shù)據(jù)X={X1,X2,…,Xl,Xl+1,…,Xn}?M,式中,l表示帶標(biāo)簽的樣本的個數(shù),n表示X中全部樣本的個數(shù)。帶標(biāo)簽的樣本Xi|li=1∈RD×m,無標(biāo)簽樣本Xi|ni=l+1∈RD×m,降維后的維數(shù)為d。1)在XL上,按照式(5)構(gòu)造Wl×l。定義矩陣W∈Rn×n如下W=[Wl×l000]對Xi∈XL和Xj∈XL,計算核矩陣Kl×l。定義核矩陣ΚL=[Κl×l000],ΚL∈Rn×n定義矩陣?Ι為?Ι=[Ι000]式中,I為l×l階單位矩陣。2)在X上依據(jù)近鄰數(shù),構(gòu)建近鄰圖,按照式(6)計算權(quán)值矩陣S,并求出拉普拉斯矩陣L=D-S。對所有Xi∈X和Xj∈X,計算核矩陣K。3)求解廣義特征值問題ΚLW(ΚL)ΤA=λ(ΚL(?Ι-W)(ΚL)Τ+βΚLΚΤ)A得到最優(yōu)投影矩陣A=[A1|A2|…|Ad],式中,Ai為前d個最大特征值對應(yīng)的特征向量。3傳統(tǒng)圖像降維方法為了全面驗證SDAGM有效性,針對本文算法與其他相關(guān)算法的關(guān)系,做了一系列對比實驗。對比的算法包括邊界費舍爾分析(MFA)、線性判別分析(LDA)、核費舍爾判別分析(KFDA)、GEDAGM、黎曼局部保持映射(RLPP)、GDA。其中,MFA、LDA和KFDA是經(jīng)典的基于單圖像降維方法,而GEDAGM、RLPP和GDA是近年提出的基于圖像集合的方法。為了保證對比實驗的充分性與廣泛性,選用了4個具有不同特點的數(shù)據(jù)集,包括3個基準(zhǔn)人臉數(shù)據(jù)集CMUPIE、ExtendedYaleB和Honda/UCSD與一個物體識別ETH-80數(shù)據(jù)集。3.1人臉圖像的調(diào)整CMUPIE數(shù)據(jù)集包括68個人的41368幅人臉圖像。這些圖像具有變化的13種姿態(tài)、43種不同光照和4種面部表情,平均每人約為170張圖像。在實驗中,僅選取接近正面視角的人臉圖像構(gòu)成的子集,該子集包括不同光照和表情變化下的5個poses(C05、C07、C09、C27、C29)人臉圖像,圖1給出了某人的部分人臉圖像。把圖像調(diào)整為32×32大小,并將像素灰度值歸一化處理(零均值、單位方差)。ExtendedYaleB數(shù)據(jù)集包括38個人的2414幅正面人臉圖像,其中每個人大約64張圖像。這些圖像均在實驗室控制光照的條件下拍攝。把圖像調(diào)整為32×32像素大小,并將像素灰度值做歸一化處理。圖2顯示了來自某個人的部分人臉圖像。實驗選取Honda/UCSD數(shù)據(jù)集的第一個子集,其中包括20個對象的59段視頻,每人有2～5段視頻,每段視頻大約含有300～500幀圖像,圖像大小為486×640,人臉發(fā)生2維或3維的姿態(tài)變化、表情變化、光照變化和尺度變化。把圖像調(diào)整為32×32像素大小,并將像素灰度值歸一化到單位區(qū)間。部分實驗人臉圖像如圖3所示。ETH-80數(shù)據(jù)集包括8類不同對象,每類物體包括10組不同的子類,如圖4所示,每個子類包含該子類不同視角下的41幅圖像。實驗中把圖像調(diào)整為32×32像素大小,并將像素灰度值作歸一化處理。3.2實驗環(huán)境配置3.2.1低維特征空間的檢測隨機地從每類中選擇一半圖像作為訓(xùn)練集,剩余部分用于測試集。首先基于訓(xùn)練樣本,并分別利用MFA、LDA、KFDA算法獲取從高維空間到低維特征空間顯式線性映射,然后將訓(xùn)練和測試樣本通過線性映射投影至各自的低維特征空間,最終基于測試樣本,采用最近鄰分類器計算識別率。實驗重復(fù)執(zhí)行20遍,平均識別率作為最終性能的評價指標(biāo)。為了避免小樣本問題,在執(zhí)行算法之前,采用了主成分分析(PCA)算法對數(shù)據(jù)進行預(yù)處理,在降維過程中保留95%的數(shù)據(jù)能量。KFDA中的核函數(shù)選擇通用的高斯核,根據(jù)經(jīng)驗將σ固定為訓(xùn)練樣本的平均范數(shù)σ0,近鄰參數(shù)k設(shè)置搜索范圍為{1,2,…,l-1},l為每類中訓(xùn)練樣本個數(shù)。3.2.2測試集和測點布置對于CMUPIE,取20個人做實驗,每次采用無放回隨機地選擇每個人的10幅人臉圖像組成一個圖像集合,這樣每個人可構(gòu)成17個圖像集合,其中10個圖像集合作為訓(xùn)練集,7個圖像集合作為測試集,訓(xùn)練集中4個圖像集合無標(biāo)簽。對于ExtendedYaleB,取20人做實驗,同樣采用無放回隨機地選擇每個人的6幅人臉圖像組成一個圖像集合,這樣每個人可構(gòu)成10個圖像集,其中6個圖像集合作為訓(xùn)練集,4個圖像集合作為測試集,訓(xùn)練集中2個圖像集合無標(biāo)簽。對于Honda/UCSD,選擇一個視頻段中100幅圖像構(gòu)成訓(xùn)練集,每個圖像集合是由10幅圖像構(gòu)成,這樣每個人有10個訓(xùn)練圖像集合,其中2個是無標(biāo)簽的圖像集合;選擇另外一個視頻100幅圖像構(gòu)成測試集,同樣每個測試圖像集合是由10幅圖像構(gòu)成的。對于ETH-80數(shù)據(jù)集,采用每個子類不同視角下的41幅圖像組成一個圖像集,這樣每個物體可構(gòu)成10個圖像集合,其中3個圖像集合作為訓(xùn)練集,7個圖像集合作為測試集,在訓(xùn)練集中1個圖像集未帶標(biāo)簽。近鄰參數(shù)k設(shè)置搜索范圍為{1,2,…,l-1},l為每類中訓(xùn)練樣本個數(shù);核函數(shù)均使用投影核。實驗重復(fù)執(zhí)行20遍,平均識別率作為最終性能的評價指標(biāo)。3.3不同方法對應(yīng)的結(jié)果及維數(shù)通過最近鄰分類器來評價和比較不同降維算法的性能。表1給出了各種方法對應(yīng)的最好結(jié)果及其對應(yīng)的維數(shù)。針對圖像集合方法,圖5給出了各種降維算法的平均識別率對特征維數(shù)的變化曲線。3.4sdagm的實驗針對不同的數(shù)據(jù)集,配置恰當(dāng)?shù)膮?shù),能夠提升算法的識別性能。然而,為參數(shù)選擇合適的值是不容易的。通常采用交叉驗證的方式進行參數(shù)選擇,但非常耗時,并需要大量的訓(xùn)練樣本,在實際中難以實現(xiàn)。參數(shù)選擇對于帶標(biāo)號數(shù)據(jù)很少的機器學(xué)習(xí)算法而言,目前還沒有非常有效的方法。圖6顯示了對應(yīng)的不同近鄰參數(shù)k所構(gòu)建的近鄰圖,SDAGM在4個數(shù)據(jù)集上的識別率對比。具體地,固定低維子空間維數(shù)d=20和正則化參數(shù)β=20,遍歷不同近鄰數(shù)k對應(yīng)的識別率,參數(shù)β用于折中類內(nèi)方差和樣本的正則化項。如果β選取較小,則意味著正則化項在目標(biāo)函數(shù)中所占的比重少,這樣,對樣本內(nèi)蘊幾何結(jié)構(gòu)的影響也較小,極端情形是β取0時,算法退化為GDA方法;相反,如果參數(shù)β選取較大,則正則化項在目標(biāo)函數(shù)中所占的比重較大,突出了數(shù)據(jù)的幾蘊幾何結(jié)構(gòu)作用,弱化了樣本的類內(nèi)方差。為了提高算法的時間效率,β大多采用經(jīng)驗選取。圖7顯示固定低維子空間維數(shù)取d=20和近鄰數(shù)k=5,不