李白燕，李 平，陳慶虎

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

0 引言

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

1 LLE，SLLE和KNPP概述

1.1 局部線性嵌入LLE

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

1)在高維空間中尋找每個(gè)樣本點(diǎn)Xi的K個(gè)近鄰點(diǎn);

2)由每個(gè)樣本點(diǎn)的近鄰點(diǎn)計(jì)算出該樣本點(diǎn)的局部重建權(quán)值矩陣;

3)由該樣本點(diǎn)的局部重建權(quán)值矩陣和其近鄰點(diǎn)計(jì)算出該樣本點(diǎn)的輸出值Yi。

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

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

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

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

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

1)求出距離每個(gè)數(shù)據(jù)點(diǎn)Φ(xi)最近的k個(gè)點(diǎn)，距離可以通過(guò)核矩陣K來(lái)計(jì)算，核矩陣K的元素為Kij=Φ(Xi)·Φ(Xj)。

2)通過(guò)求解式(2)所示的最小二乘問(wèn)題，計(jì)算Xi到它的鄰域點(diǎn)之間的最佳重建權(quán)重Wij

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

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

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

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

2 改進(jìn)的算法IM_SLLE

下面結(jié)合SLLE和KNPP算法，提出改進(jìn)算法，步驟如下:

1)計(jì)算每個(gè)樣本點(diǎn)的K個(gè)近鄰點(diǎn)

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

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

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

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

圖1 SLLE與IM_SLLE距離比較

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

2)計(jì)算樣本點(diǎn)的局部重建權(quán)值矩陣Wij

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

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

3 實(shí)驗(yàn)結(jié)果

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

圖2 樣本圖片

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

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

實(shí)驗(yàn)結(jié)果表明，線性算法LDA對(duì)人臉識(shí)別弱于其他非線性算法，因?yàn)榉蔷€性算法提取的特征對(duì)人臉流形的描述更加細(xì)致。在非線性人臉識(shí)別算法中，LLE算法具有鄰域保持特性，但由于缺乏類(lèi)別信息，效果很難達(dá)到最優(yōu)。KNPP屬于無(wú)監(jiān)督的子空間學(xué)習(xí)方法，因?yàn)镵NPP具有鄰域保持特性，而且它通過(guò)利用局部信息來(lái)描述人臉的非線性流形，效果優(yōu)于LLE。改進(jìn)算法結(jié)合了KNPP與SLLE的優(yōu)點(diǎn)，屬于有監(jiān)督的局部保持的非線性子空間學(xué)習(xí)方法，優(yōu)于其他幾種。這表明IM_SLLE更利用分類(lèi)識(shí)別。

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

表2 SLLE與IM_SLLE抗噪能力比較

4 小結(jié)

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

［1］閆娟，程武山，孫鑫.人臉識(shí)別的技術(shù)研究與發(fā)展概況［J］.電視技術(shù)，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］龐彥偉，俞能海，沈道義，等.基于核鄰域保持投影的人臉識(shí)別［J］.電子學(xué)報(bào)，2006，34(8):1522－1524.

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