基于改進的監(jiān)督LLE人臉識別算法

李白燕，李 平，陳慶虎

(1.黃淮學院信息工程系，河南 駐馬店 463000;2.武漢大學電子信息學院，湖北 武漢 430079)

0 引言

人臉識別仍是現(xiàn)階段模式識別和計算機視覺領域的研究熱點之一［1］，由于人臉圖像受光照、姿態(tài)、表情等影響，人臉數(shù)據(jù)是異常高維的數(shù)據(jù)。目前對高維數(shù)據(jù)的處理，有兩種基本方法:一種是將高維數(shù)據(jù)映射到線性可分的高維空間中，即基于內(nèi)核的技術，如支持向量機(SVM)技術［2］;另一種方法是降低數(shù)據(jù)維數(shù)，雖然看似信息丟失，需要估計的參數(shù)減少，但可能會有更好的識別性能。許多線性降維方法，如主成分分析(PCA)［3］和Fisher線性判別分析(LDA)［4］是行之有效的。但是大量研究表明，人臉空間更可能是一個高維的非線性子空間，即人臉位于一個非線性流形上，因此線性降維方法不能反映人臉的非線性數(shù)據(jù)結構，不足以描述人臉特征。目前流形學習可分為全局映射和局部映射兩類。前者主要有等距映射(isomap)［5］;后者有局部線性嵌入(Locally Linear Embedding，LLE)［6］和拉普拉斯特征映射(Laplacian Eigenmaps)［7］。但是這些方法都沒有明晰的投影矩陣，從而不能直接映射新的測試點(該點不同于訓練集合中的任何點)，這個問題也被稱為 out－of－sample 問題［8］。其中 LLE 有很多優(yōu)點:不需要一個迭代算法，很少的參數(shù)需要進行設置，而且該方法避免了局部極小問題，具有鄰域保持特性。但是該算法會出現(xiàn)上述所說的問題，而且屬于基于重構的無監(jiān)督的學習方法，效果并非最優(yōu)。因此，Dick de Ridder等在LLE學習算法的基礎上引入監(jiān)督機制，稱為SLLE［9］，SLLE是以監(jiān)督的方式提取人臉的非線性的流形特征，該算法分類性能優(yōu)于LLE，通常情況下也會優(yōu)于其他的一些映射算法，龐等人在LLE基礎上，提出了一種新的基于核子空間的學習方法，即核鄰域保持投影(KNPP)［10］。該方法引入一個線性變換矩陣來近似LLE，然后通過非線性核技巧在維數(shù)很高的空間里求解子空間，它可以解決 out－of－sample問題。KNPP最大的優(yōu)點在于它和LLE一樣具有鄰域保持特性，但是KNPP屬于無監(jiān)督學習方法，需要發(fā)展為有監(jiān)督的方法。因此，在SLLE與KNPP算法的啟發(fā)下，本文提出一種新方法，簡稱為IM_SLLE。

1 LLE，SLLE和KNPP概述

1.1 局部線性嵌入LLE

給定 N 個輸入向量 X=［X1，X2，…，XN］，其中，Xi∈RD，通過 LLE 算法將得到輸出值 Y=［Y1，Y2，…，YN］，Yi∈Rd且d?D。無監(jiān)督LLE歸結為3步［6］:

1)在高維空間中尋找每個樣本點Xi的K個近鄰點;

2)由每個樣本點的近鄰點計算出該樣本點的局部重建權值矩陣;

3)由該樣本點的局部重建權值矩陣和其近鄰點計算出該樣本點的輸出值Yi。

1.2 監(jiān)督局部線性嵌入SLLE

SLLE的主要目的是找到將類間結構和類內(nèi)結構分開的映射，其方法是在Xi和Xj(屬于不同類)加上一個距離參數(shù)，修改K個近鄰點的計算方法，從而增加了樣本點的類別信息。而步驟2)和步驟3)同LLE。SLLE在計算點與點之間的距離采用如下公式［9］

式中:Δ是沒有考慮類別信息的歐式距離，Δ'是結合了類別信息的距離，Λij取值為0或1，當兩點屬于同類時，取為0，否則取1;α 是控制點集之間的距離參數(shù)，α∈［0，1］，α是一個經(jīng)驗參數(shù)。當取為0時，此時的SLLE和LLE算法相同。

1.3 核鄰域保持投影KNPP［10］

給定 N 個輸入向量 X=［X1，X2，…，XN］，其中，Xi∈RD，假設通過非線性映射函數(shù)Φ:X→Φ(X)把X映射到Hilbert空間F中。KNPP的目的是對F中的數(shù)據(jù)點Φ(X)=［Φ(X1)，Φ(X2)，…，Φ(XN)］降維，把它們映射為d維空間中的新的數(shù)據(jù)點X=［Y1，Y2，…YN］，其中 d?D。

1)求出距離每個數(shù)據(jù)點Φ(xi)最近的k個點，距離可以通過核矩陣K來計算，核矩陣K的元素為Kij=Φ(Xi)·Φ(Xj)。

2)通過求解式(2)所示的最小二乘問題，計算Xi到它的鄰域點之間的最佳重建權重Wij

3)分解核矩陣K并計算矩陣M和Q。K=PΛPT，M=(I－W)(I－W)T，Q=PTMP，其中 I表示單位矩陣。

4)求解下面的特征值分解問題得到向量ri:Qli=liri，其中0＜l1＜… ＜ld。

5)計算向量 βi并對其歸一化 βi=PΛ－1ri，βi←βi/，其中 i=1，2，…，d。

6)采用yin=βnjKji實現(xiàn)非線性降維其中n=1，2，…，d。yin表示向量yi的第n個元素。

2 改進的算法IM_SLLE

下面結合SLLE和KNPP算法，提出改進算法，步驟如下:

1)計算每個樣本點的K個近鄰點

在SLLE算法中，式(1)中的Δ采樣歐氏距離得到，在本算法中通過核矩陣K來計算，K的元素為Kij=Φ(Xi)·Φ(Xj)，其中Φ是引入的非線性映射函數(shù)。然后在根據(jù)式(1)計算Δ'從而找到K個近鄰點，計算方法中已經(jīng)加入了樣本點的類別信息，不過可將式(1)進一步進行改進。一個理想的分類機制應最大類間差異而最小化類內(nèi)差異［11］，因此將SLLE中的式(1)通過減少類內(nèi)距離而擴展類間距離，得到

式中:Δ通過核矩陣K計算得到的Xi和Xj之間的距離，參數(shù)δ防止當Δ較大時，Δ'按指數(shù)增長太快，因此δ與樣本點的緊密度有關，常數(shù)ε在［0，1］之間取值，合理的取值可使不同類之間的數(shù)據(jù)更相似，以至使類間差異可能比類內(nèi)差異更小。

下面分析一下改進后的特點。圖1a是采用式(1)計算的Δ'歐氏距離從0～3線性變化，ε設為0.2。水平軸代表歐式距離Δ，縱軸代表Δ'，實線表示不同類之間距離的變化，虛線表示同類間距離的變化。從圖1可以看出，在SLLE中，類間差異會隨著類內(nèi)差異的線性增加而增加，將不利于隨后的分類識別。因為類間與類內(nèi)的距離比值是不變化的，這樣使嵌入數(shù)據(jù)的判別能力和泛化的能力被限制在一定的范圍。另外，SLLE對數(shù)據(jù)中的噪聲也是非常敏感的，具體來說，類間距離和類內(nèi)距離的范圍都是［0，+∞］，這意味著噪聲可能會改變原始的差異到中間的任何值，特別是當噪聲比較強時，數(shù)據(jù)間的鄰域關系可能被完全破壞。

采用式(3)所計算出的Δ'如圖1b所示，這里水平軸代表核矩陣K距離Δ，其他同圖1a，從圖中可以看出，隨著距離Δ的增加，類間差異比類內(nèi)差異大，因此類間距離與類內(nèi)距離的比值變得越來越大，這樣克服了SLLE存在的問題，有利于分類識別。另外，當距離Δ增加時，類間差異增加快而類內(nèi)差異增加慢，這表明這種算法對數(shù)據(jù)中的噪聲有抑制的能力。一方面，類間距離通常是比較大的，所以如果它越小，噪聲存在的可能性就越大，Δ'減小得越慢。另一方面，類間距離通常是比較小的，如果它越大，噪聲存在的可能性就越大，Δ'增長得越慢。因此，隨著噪聲存在的可能性增加，改進算法抑制噪聲的能力也逐步加強。

圖1 SLLE與IM_SLLE距離比較

類間差異的范圍在［1－ε，+∞］，而類內(nèi)差異的范圍是［0，1］，因此不管數(shù)據(jù)中的噪聲是多么強大，類間差異和類內(nèi)差異能被控制在一定的范圍，這就表明該算法能限制噪聲的影響。

2)計算樣本點的局部重建權值矩陣Wij

傳統(tǒng)的LLE算法是首先定義一個誤差函數(shù)并最小化［6，11］，如式(4)所示

通過式(5)可求出 Wi(i=1，2，…，N)，其他步驟同1.3節(jié)KNPP的步驟，在這里不再贅述。

3 實驗結果

采用Yale人臉庫對文中所提出的改進算法上進行評測。Yale人臉庫包含15個人的165個灰度圖像，這些圖像是在不同的光照、不同表情下取得的，還分戴眼鏡和不戴眼鏡兩種情況。如圖2所示。隨機選取了30幅圖像(每人2幅)作為識別測試集，剩下的135幅作為訓練集。首先將圖像裁剪和縮放為60×60的標準。

圖2 樣本圖片

實驗中將改進算法與LLE算法、SLLE算法以及KNPP算法進行比對，分類方法都采用最近鄰分類器，同時對所有的算法都采用最佳的參數(shù)，實驗結果如表1所示。另外為了驗證非線性算法比線性算法能更好地描述人臉的流形結構，實驗增加了對LDA識別率的比對。

表1 在Yale中幾種算法在相應的維數(shù)下識別率比較

實驗結果表明，線性算法LDA對人臉識別弱于其他非線性算法，因為非線性算法提取的特征對人臉流形的描述更加細致。在非線性人臉識別算法中，LLE算法具有鄰域保持特性，但由于缺乏類別信息，效果很難達到最優(yōu)。KNPP屬于無監(jiān)督的子空間學習方法，因為KNPP具有鄰域保持特性，而且它通過利用局部信息來描述人臉的非線性流形，效果優(yōu)于LLE。改進算法結合了KNPP與SLLE的優(yōu)點，屬于有監(jiān)督的局部保持的非線性子空間學習方法，優(yōu)于其他幾種。這表明IM_SLLE更利用分類識別。

接下來，在預處理好的人臉圖像中不同程度的加入噪聲，來驗證IM_SLLE算法對噪聲的抑制能力，結果如表2所示，該結果是在最優(yōu)參數(shù)下得到的。從表2可以看出，在不同程度的噪聲下，IM_SLLE都有優(yōu)于SLLE算法識別率。

表2 SLLE與IM_SLLE抗噪能力比較

4 小結

本文針對LLE，SLLE和KNPP算法各自的有缺點，提出了一種改進算法I－SLLE，該算法在LLE的基礎上引入有監(jiān)督的學習機制，利用δ和ε參數(shù)加入樣本的類別信息，通過最小化局部數(shù)據(jù)的全局重構誤差，結合核鄰域保持投影，提取高維人臉數(shù)據(jù)的非線性特征。在人臉庫Yale中比較了改進算法和其他的人臉識別算法，該算法有較好的識別性能。

［1］閆娟，程武山，孫鑫.人臉識別的技術研究與發(fā)展概況［J］.電視技術，2006，30(12):81－84.

［2］BURGES C.A tutorial on support vector machines for pattern recognition［EB/OL］.［2010－12－15］.http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.3829＆rep=rep1＆type=pdf.

［3］TURK M，PENTALND A.Eigenfaces for recognition［EB/OL］.［2010－12－15］.http://www.face－rec.org/algorithms/PCA/jcn.pdf.

［4］BELHUMEUR P，HESPANHA J，KRIENGMAN D.Eigenfaces vs.fisherfaces:recognition using class specific linear projecttions［EB/OL］.［2010－12－15］.http://cs.gmu.edu/～kosecka/cs803/pami97.pdf.

［5］TENENBAUM J B，SILVA V，LANGFORD J C，et al.A global geometric framework for nonlinear dimensionality reduction［EB/OL］.［2010－12－15］. http://citeseerx.ist.psu.edu/viewdoc/download? doi =10.1.1.110.6050＆rep=rep1＆type=pdf.

［6］ROWEIS S，SAUL L.Nonlinear dimensionality reduction by locally linear embedding［EB/OL］.［2010－12－15］.http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.7171＆rep=rep1＆type=pdf.

［7］BELKIN M，NIYOGI P.Laplacian eigenmaps for dimensionality reduction and data representation［EB/OL］.［2010－12－15］. http://cseweb.ucsd.edu/～saul/teaching/cse291s07/laplacian.pdf.

［8］BENGIO Y，PALEMENT J，VINCENT P，et al.Out of sample extensions for LLE，isomap，MDS，eigenmaps，and spectral clustering［EB/OL］.［2010－12－15］.http://www.iro.umontreal.ca/～lisa/pointeurs/tr1238.pdf.

［9］DERIDDER D，KOUROPTEVA O，OKUN O，et al.Supervised locally linear embedding［EB/OL］.［2010－12－15］.http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.6218＆rep=rep1＆type=pdf.

［10］龐彥偉，俞能海，沈道義，等.基于核鄰域保持投影的人臉識別［J］.電子學報，2006，34(8):1522－1524.

［11］陳高曙，曾慶寧.基于LLE算法的人臉識別方法［J］.計算機應用研究，2007，24(10):176－177.