余弦度量的多流形最大間距鑒別保持嵌入

林克正,王海燕,林璇璣,李 驁

(哈爾濱理工大學 計算機科學與技術學院,哈爾濱 150080) E-mail:wanghaiyan45@yeah.net

1 引 言

目前,基于統計學習的算法是人臉識別中被廣泛應用的方法,比較有代表性的算法如主成分分析[1](Principal Component Analysis,PCA)和線性鑒別分析[2](Linear Discriminant Analysis,LDA),這兩種方法都是線性方法,后來衍生出了對應的非線性方法,通過融入核方法,提出了對應的核主成分分析[3]( Kernel Principal Component Analysis,KPCA)算法和核鑒別分析[4](Kernel Discriminant Analysis,KDA)算法.隨著“流形”概念的提出,基于流形學習的人臉特征提取方法得到越來越多的青睞,隨之而來也出現了很多流形學習算法.其中,等距映射算法[5](Isometric Mapping,ISOMAP)和局部線性嵌入算法[6](Locally Linear Embedding,LLE)和拉普拉斯特征映射[7](Laplacian Eigenmap,LE),是比較經典的流形學習算法.基于流形學習的人臉識別方法都是以最大程度保持樣本降維后的本質特征和原始空間拓撲結構為目標.上面的流形學習方法對新樣本數據沒有定義,泛化能力不強.針對這個問題,有人提出了局部保持投影算法[8]( Locality Preserving Projections,LPP),該方法和LE原理相似,通過對樣本構建鄰接圖,來描述樣本的鄰域關系和相似度情況,雖然在一定程度上反映了樣本的局部結構和樣本總體布局,但是對正確分類并沒有起到最直接的促進結果.通過加入樣本類別信息進行構圖,有人提出了邊界費舍爾分析[9](Margin Fisher Analysis,MFA).MFA通過構造內蘊圖和懲罰圖有效地區分了不同類樣本的邊界,然而MFA也存在小樣本的奇異值問題等.為了進一步保持樣本的鄰域結構,同時對同一鄰域范圍內的不同類樣本進行區分,Huang等人提出了LMMDE(Local Maximal Margin Discriminant Embedding,LMMDE)算法[10],LMMDE算法既利用了樣本類間鄰域結構也利用了類內鄰域結構信息,同時保持了樣本的局部結構特征,相比于MFA算法,識別率有所提升.然而上述提出的幾種流形學習方法面臨以下的問題:

1) MFA和LMMDE算法均需要構造鄰接圖(MFA需要構造兩類圖,需要兩個近鄰參數k1和k2;LMMDE需要一個近鄰參數k),近鄰參數k的選取不當會對識別率造成影響;

2) 在實際的人臉識別工作中,可供選擇的樣本數量較少,在少樣本情況下的各算法的識別率還有待于提高.鑒于以上問題,在LMMDE算法原理基礎上,引入余弦距離和多流形[11]的思想,提出了余弦度量的多流形最大間距鑒別保持嵌入(Multi-manifold Maximal Margin Discriminant Preserving Embedding based on Cosine Measure).該算法中,首先對樣本分塊,為單個樣本構造流形,整個訓練樣本集就構成多流形;然后在確定多流形中各個樣本的鄰域時,采用余弦距離的度量方式替換傳統的歐式距離;最后重新定義計算測試樣本和訓練樣本的流形間距離來對樣本進行分類.由于CMMMMDPE方法采用余弦距離的度量方式,不僅避免了近鄰參數k的選擇困難問題,同時使得算法對離群數據更為魯棒.多流形思想的融入,不僅解決了小樣本問題,還能充分利用樣本內部結構信息,進而提高識別率.

2 局部最大邊界鑒別嵌入

LMMDE算法的中心思想:保持降維后的樣本在原始高維空間中的鄰域結構關系,同時最大化同一鄰域內的不同類別樣本的間隔,最小化同類樣本的間隔,以達到對同一流形內的不同類樣本進行分離的目的.設高維空間中樣本集合為:X={x1,x2…,xN}∈RD,LMMDE的目標就是找到最優投影矩陣A,實現樣本數據從高維空間到低維空間的映射:X→Y∈Rd.首先對每個樣本點構造k近鄰圖,得到若干個鄰接圖.任意樣本xi的鄰域Nk(xi)表示由xi的前k個歐式距離最近的點構成的集合.

樣本的局部散布矩陣,描述了樣本的局部鄰域關系,可按以下公式進行計算:

(1)

樣本的類間鄰域散布矩陣和類內鄰域散布矩陣分別按照以下公式計算:

(2)

(3)

(4)

(5)

(6)

其中,A是投影矩陣,I是一個單位矩陣.

3 CMMMMDPE算法

3.1 余弦距離

圖嵌入的算法在進行權值矩陣的定義時,反映了樣本之間相似程度的權值通常采用熱核函數法,由熱核函數法的原理可知,兩個樣本之間的歐式距離大小決定了樣本之間的相似度,即:歐氏距離越小,樣本相似度越大;反之,樣本相似度越小.在對一些離群孤立樣本點確定近鄰時,歐氏距離并不能準確地描述這個孤立樣本點與其他樣本點的關系,尤其在分類時極有可能做出錯誤判定.一些文獻表明,余弦距離在面對離群孤立點則表現出了更加魯棒的性能[12].首先引入樣本間的余弦距離.令cos(xi,xj)表示樣本xi與xj間的余弦距離,則cos(xi,xj)的計算公式為:

(7)

3.2 多流形思想的構圖方式

多流形思想的原理是:考慮對樣本集構造一個多流形空間,即對每個樣本進行分割,最后形成若干個局部小塊樣本,由于它們來自同一個樣本,屬于相同的類別,因此將這若干個局部小塊樣本看成一個流形空間.這樣,一個樣本就構成了一個流形空間,整個樣本集就構成多流形空間.CMMMMDPE算法就是基于這樣的原理,首先對樣本空間進行重新構造,構造一個多流形的樣本空間,之后進行相應的構圖、權值的賦值、目標函數的定義等步驟.

3.2.1 構造多流形空間

首先對原始樣本數據構造多流形空間.對于一個含有N個樣本圖片數據集:I={I1,I2…,IN},它的向量形式表示成:X={x1,x2…,xN}xi∈RD.任意一個圖像樣本Ii(尺寸為p×q,這里p表示樣本圖片的高度,q表示樣本圖片的寬度).首先,對于一個樣本點xi,將其分成l個塊(l=1…t),這樣形成多幅小塊圖片xil(尺寸為a×b,這里a表示樣本圖片的高度,b表示樣本圖片的寬度).l個小塊圖片樣本構成一個流形空間.對于一個N個樣本的數據集來說,可以構造多個流形空間,即M={M1,M2,…,MN},其中Mi=[xi1,xi2,…,xil].

3.2.2 鄰域的確定

對于樣本xil,在整個多流形空間中搜索滿足余弦度量規則的小樣本成為其近鄰.樣本xil的多流形類間鄰域和多流形類內鄰域通過以下兩個公式來計算:

(8)

(9)

上面兩個式子中這種采用余弦距離的度量方式確定近鄰的方法,對于受到局部噪聲干擾而離群的小樣本來說,依然能找到正確的近鄰.xil的多流形類間近鄰反映了小塊樣本xil與多流形空間中不同類別的若干個小樣本的鄰接關系;xil的多流形類內近鄰則體現了xil與多流形空間中同類的小樣本的近鄰情況.

3.2.3 權值的賦值

在確定了各個小塊樣本xil的類間鄰域和類內鄰域后,還需要構造權值矩陣來描述樣本的相似度情況.多流形中每個小樣本xil與多流形類間鄰域內各樣本的相似度權值定義如下:

(10)

多流形中每個小樣本xil與多流形類內鄰域的各樣本的相似度權值定義如下:

(11)

3.3 多流形類間鄰域離散度、類內離散度和總體樣本局部散度

(12)

(13)

整個多流形樣本空間中,對任意樣本xil的局部鄰域內的樣本之間的相似度度量定義如下:

(14)

因此,局部離散度定義如下:

(15)

3.4 目標函數及最優投影矢量

基于余弦距離的多流形最大間距鑒別保持嵌入的思想就是:

1) 在低維嵌入空間中,保持多流形空間中小樣本在原始高維多流形空間中的局部特征和空間散布關系;

2) 充分利用多流形空間中每個小樣本的幾何結構信息,最大化不同類別樣本的多流形類間離散度與同類樣本的多流形類內離散度的差值,使流形間的類別可分性最大,多流形的同類樣本結構更加緊湊、多流形的不同類樣本更加分離.算法的目標函數可表述為:

(16)

其中,Jb(A1,A2,…,AN)、Jw(A1,A2,…,AN)、JL(A1,A2,…,AN)的計算公式如下:

(17)

(18)

(19)

其中β是平衡因子,用來平衡目標函數中各項的重要程度,將(17)、(18)、(19)帶代入目標函數(16)改寫為:

(20)

對變換矩陣A=[A1,A2,…,AN]進行求解,需要求解出每個流形的降維矩陣Ai,Ai可通過最大化下面的公式進行求解:

max{(1-β)(Jb(Ai)-Jw(Ai))-βJL(Ai)}=max{(1-β)

(21)

Jb(Ai)、Jw(Ai)、JL(Ai)公式可按照以下過程進行化簡:

(22)

(23)

(24)

其中,

(25)

(26)

(27)

Ai可通過以下公式的特征值分解問題得到:

[(1-β)(Hb-Hw)-βHL]Ai=λAi

(28)

3.5 模式識別與分類

按照CMMMMDPE算法進行降維后,每個樣本流形都得到對應的投影矩陣Ai,i=1,2,…,N,利用最近鄰分類器進行分類,分類過程如下:

Step1.對于給定的測試樣本xT和訓練樣本集中的所有樣本均按照本文算法進行特征提取,得到其在低維空間的表示MyT={yT1,yT2,…,yTt}和Myi={yi1,yi2,…,yit}.

Step2.計算多流形下測試樣本MyT與訓練樣本Myi的距離.對流形MyT中的每個局部小塊樣本yTl,用余弦距離來度量Myi中哪些局部小塊樣本可以成為yTl的近鄰點,得到的近鄰點集表示為Ni(yTl),計算公式如(29)所示.

Ni(yTl)={yir,cos(yTl,yir)

(29)

yTl到低維流形yi的距離計算公式為:

(30)

則yT到流形yi的距離可按照如下公式計算:

(31)

Step3.識別分類.按照上面步驟求出測試樣本到N個樣本流形的距離.根據最近鄰分類器原則,將測試樣本yT的類別判定為d(yT,yi)值最小的對應yi的類別屬性,判定公式如下:

(32)

4 實驗結果與分析

在本節的實驗主要是在ORL、Yale和FERET人臉庫上進行,通過加入對比算法LPP、MFA、LMMDE,驗證CMMMMDPE算法的有效性.實驗的目的主要有以下幾點:

1) 各種參數對算法的識別率影響;

2) 考查不同特征維數下的各算法識別率情況;

3) 測試樣本數量對CMMMMDPE及其對比算法的識別率的關系.

ORL人臉庫由400幅圖像組成.采集了40名受試者每人10幅圖像,這些圖像分別采集于不同時間并包含了各方面變化如:不同視角、不同光照、不同表情、不同面部裝飾物等情況.Yale人臉庫共包含了165張圖片,來自于15名受試者,每人有11張圖片.每個受試者的人臉圖片的主要差異在表情的變化及有無眼鏡裝飾光照情況的差別等.FERET人臉圖片庫的規模很大,包含了1199個人將近14000多幅圖像,均是在不同拍攝角度、姿態和不同面部表情下采集的.在本節實驗中,選取ORL和Yale人臉庫中的所有圖片;對于FERET人臉數據庫,則選用它的一個子集共包含了200×7幅圖像(由200人組成,每人有7幅圖片).圖1、圖2和圖3分別展示了Yale和FERET人臉圖片庫上某個人的人臉圖像.

圖1 ORL人臉數據庫某個人的幾幅人臉照片Fig.1 Several images of certain person on ORL face database

圖2 Yale人臉圖片庫某個人的人臉圖像Fig.2 Face images of certain person on Yale face database

圖3 FERET人臉庫上某個人的人臉圖像Fig.3 Face images of certain person on FERET face database

實驗中將圖片進行裁切,只保留臉部區域,將圖片統一處理成分辨率大小為32×32以保證實驗結果的準確性.本節實驗中涉及的Train(m)/Test(n)表示:實驗數據集中,每個人臉的圖片集中選取的訓練樣本數為m,測試樣本數為n.

4.1 參數變化對識別率的影響

本實驗中,因為CMMMMDPE算法是在LMMDE算法的基礎上進行的改進,LMMDE算法在構圖過程中需要確定近鄰參數k,CMMMMDPE算法不需要指定近鄰參數k,因此考察近鄰參數k的不同取值對LMMDE算法的識別率影響.其次,考察權重參數β的不同取值對CMMMMDPE算法識別率的影響.兩種實驗均采用以下的實驗數據:Yale人臉庫中每人的人臉圖片數量分配為:Train(5)/Test(6);FERFT人臉庫中實驗組中每個受試者的人臉圖片分配情況:Train(4)/Test(3).圖4展示了LMMDE方法的識別準確率對近鄰參數k的敏感程度.此實驗中先將β設為0.1,k的取值范圍為k={1,2,…,10}.

圖4 LMMDE算法在不同k取值下的識別率

從圖4的實驗結果可以看出,當近鄰參數k從1變化到10時,LMMDE在Yale人臉庫和FERET人臉庫上的識別率具有較大的變化.其中,在Yale人臉庫上LMMDE的識別正確率變化的最大幅度為5%左右,而在FERET人臉庫上的識別率變化幅度約為3%.兩個實驗人臉庫上的結果均表明LMMDE算法對于近鄰參數的變化比較敏感,可見LMMDE算法對近鄰參數k的依賴性較強.CMMMMDPE在確定樣本近鄰的過程中,通過比較兩個樣本之間的余弦角距離,來確定哪些樣本可以成為近鄰,不需要設置近鄰參數k,較好地解決了近鄰參數k選擇不好所帶來的識別率問題,從而驗證了CMMMMDPE的有效性.

圖5 CMMMMDPE算法在β取不同數值時的識別率

在進行參數β對算法識別率關系的實驗中,β的取值范圍為:β={0.1,0.2,…,0.9}.圖5展示了CMMMMDPE算法識別率在不同人臉庫上隨權重參數β的變化情況.實驗結果表明CMMMMDPE的識別率高低與權重參數β成反比的趨勢,即:β越小,樣本的鑒別信息對識別率更要重要,反之,樣本局部結構特性對算法識別率的作用更大,β取值為0.1時,CMMMMDPE的識別率最佳.

4.2 識別率與特征維數實驗

在Yale人臉庫的實驗組為:Train(5)/Test(6).在FERET人臉庫的實驗組為:Train(4)/Test(3).實驗中涉及的參數設置如下:LPP和LMMDE算法的近鄰參數k的范圍是k={1,2,…,10};令l表示訓練樣本數,則MFA中的類內近鄰參數kw=l-1;而類間近鄰參數kb=C·kw,C表示樣本的類別數.實驗中涉及的權重參數β預先設為0.1;識別分類階段均采用最近鄰分類器,其中CMMMMDPE算法在模式分類時則采用本文的流形距離計算公式來進行分類.每個實驗重復進行20次,取平均值.圖6和圖7展示了Yale和FERET人臉庫實驗上不同特征維數下各算法的識別率.

圖6 Yale人臉庫上的各算法在余弦距離分類器下的識別率Fig.6 Recognition rate of each algorithm by using cosine distance based classifier on Yale face database

圖6和圖7的實驗結果表明,隨著特征維數的增加,各算法的識別率是逐步增加的.利用樣本類別信息的算法的識別率均高于LPP算法,LMMDE算法在保持樣本的局部結構的同時還盡量區分開鄰域內類別不同的樣本,因此LMMDE的識別率均高于MFA.CMMMMDPE的識別率最高.然而在Yale人臉數據庫上的實驗結果表明,CMMMMDPE算法在特征維數達到一定數值以后,識別率甚至有所下降,這是因為當樣本維數太高時,CMMMMDPE方法容易提取出非關鍵特征從而造成對識別分類的干擾,阻礙了正確分類過程.總的來說,本文算法CMMMMDPE由于加入多流形思想,使得每個流形空間中的小塊樣本充分發揮了樣本內部結構信息的作用,同時引入的余弦距離度量方式對分類識別也起到較好的作用.

圖7 FERET人臉庫上的各算法在歐式距離分類器下的識別率Fig.7 Recognition rates of each algorithms by using euclidian distance based classifier on FERET face database

4.3 樣本數對識別率的影響

本文算法由于加入了多流形思想,目的是為了解決樣本數量較少時的識別分類問題,驗證小樣本下的識別率情況,因此本節實驗主要在圖片數量較少的ORL和Yale人臉庫上進行.在ORL和Yale人臉庫上的實驗樣本選擇數據集上的所有圖片.在ORL人臉庫的實驗組為:Train(5)/Test(5)、Train(4)/Test(6)、Train(3)/Test(7)、Train(2)/Test(8);在Yale人臉庫上的實驗組為:Train(5)/Test(6)、Train(4)/Test(7)、Train(3)/Test(8)、Train(2)/Test(9).表1和表2展示了不同人臉庫中各算法在訓練樣本數量和測試樣本數量取不同取值時的識別率情況.表中數據表明:隨著訓練集圖片個數的增加,CMMMMDPE的識別率有小幅度提升并且一直高于其它算法,并且在樣本數量較少的情況下CMMMMDPE的識別率效果顯著優于其他對比算法,最佳識別率達到93.9%左右.對于CMMMMDPE算法來說,在小樣本情況下(樣本數為2或者3),相比于樣本數量較多的情況下識別率只是略有下降,說明CMMMMDPE對小樣本情況下能得到較多有用的分類信息.而與此形成對比的是其他算法則對訓練樣本的數量有顯著的依賴.

表1 Yale人臉庫不同訓練樣本數下的算法識別率
Table 1 Recognition rates of each algorithm with different number of train samples on Yale face database

訓練樣本數5/64/73/82/9LPP93.9±1.192.6±1.490.8±1.785.4±1.8MFA95.6±1.194.1±1.392.9±1.289.4±1.0LMMDE96.4±0.895.8±0.793.8±0.391.0±1.0CMMMMDPE98.2±0.697.4±0.696.5±0.695.2±0.6

表2 ORL人臉庫不同訓練樣本數下的算法識別率
Table 2 Recognition rates of each algorithm with different number of train samples on ORL face database

訓練樣本數5/54/63/72/8LPP87.2±1.186.7±1.480.4±1.775.1±1.8MFA89.1±1.188.9±1.385.8±1.281.2±1.0LMMDE92.4±0.892.1±0.790.8±0.385.0±1.0CMMMMDPE93.9±0.693.4±0.692.5±0.690.2±0.6

5 結 語

本文提出一種基于余弦距離和多流形思想的CMMMMDPE算法,通過融入多流形思想和余弦距離度量方式解決了LMMDE算法中近鄰參數k的選擇困難問題和小樣本識別率低問題.一方面,在確定樣本的多流形類間近鄰和多流形類內近鄰,用余弦距離的度量方式避免了構圖過程中對近鄰參數k的選取,消除了近鄰參數k對算法識別效果的影響;另一方面,通過多流形的理論為每個樣本構造流形空間,充分保持了每個流形之間的內部局部結構信息,也從全局上保持了流形局部鄰域關系,從而提高了小樣本情況下的識別率.

[1] Turk M,Pentland A.Eigenfaces for recognition[J].Journal of Cognitive Neuroscience,1991,3(1):72-86.

[2] Belhumeur P N,Hespanha J P,Kriegman D J.Eigenfaces vs.Fisherfaces:recognition using class specific linear projection[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1997,19(7):711-720.

[3] Scholkopf B,Smola A,Muller K R.Nonlinear component analysis as a kernel eigenvalue problem[J].Neural Computation,1998,10(6):1299-1319.

[4] Mika S,R?tsch G,Müller K R.A mathematical programming ap-

proach to the kernel fisher algorithm[C].Advances in Neural Information Processing Systems,2001,13:591-597.

[5] Tenenbaum J B,De Silva V,Langford J C.A global geometric framework for nonlinear dimensionality reduction [J].Science,2000,290(5500):2319-2323.

[6] Roweis S T,Saul L K.Nonlinear dimensionality reduction by locally linear embedding [J].Science,2000,290(5500):2323-2326.

[7] Belkin M,Niyogi P.Laplacian eigenmaps and spectral techniques for embedding and clustering[J].Advances in Neural Information Processing Systems,2002,14(6):585-591.

[8] He Xiao-fei,Yan Shui-cheng,Hu Yu-xiao,et al.Face recognition using laplacianfaces[J].IEEE Trans on Pattern Analysis and Machine Intelligence,2005,27(3):328-340.

[9] Yan S,Xu D,Zhang B,et al．Graph embedding and extensions:a general framework for dimensionality reduction[J]． IEEE Trans Pattern Anal and Mach Intelligence,2007,29(1):40-51.

[10] Huang P,Tang Z,Chen C,et al.Local maximal margin discriminant embedding for face recognition[J].Journal of Visual Communication & Image Representation,2013,25(2):296-305.

[11] Yang Zhang-jing,Wan Ming-hua,Wang Qiao-li,et al.Multi-manifold unsupervised linear differential projection algorithm[J].Journal of Frontiers of Computer Science and Technology,2016,10(11):1576-1586.

[12] Huang Pu,Tang Zhen-min.Parameter-free locality preserving projections and face recognition[J].Pattern Recognition and Artificial Intelligence,2013,26(9):865-871.

附中文參考文獻:

[11] 楊章靜,萬鳴華,王巧麗,等．多流形的非監督線性差分投影算法[J]．計算機科學與探索,2016,10(11):1577-1586．

[12] 黃 璞,唐振民.無參數局部保持投影及人臉識別[J].模式識別與人工智能,2013,26(9):865-871.