基于核正交半監督鑒別分析的人臉識別算法

王燕, 劉花麗, 蘇文君

WANG Yan , LIU Huali, SU Wenjun

蘭州理工大學 計算機與通信學院，甘肅 蘭州 730050

College of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050, China

1 引言

人臉識別因其在身份驗證和識別場合具有巨大的應用價值，以及對模式識別理論的發展具有重要的學術意義而備受關注。在人臉識別中，如何有效地從高維數據中提取具有高可分性的低維特征是特征提取的關鍵。而眾多度量可分性準則的算法中，主成分分析（PCA）[1]和線性判別分析（LDA）[2]是最具有代表性的算法。

近幾年涌現出許多流形學習方法來發現人臉圖像數據中的非線性流形結構，如等距映射（ISOmetric MAPping，ISOMAP）[3]、局部線性嵌入（Locally Linear Embedding，LLE）[4]、拉普拉斯特征映射(Laplacian Eigenmap，LE)[5]。但是，以上三種方法應用于人臉識別時不能有效的處理新來的樣本點[6]。為了克服這一問題，學者們將線性映射的思想引入人臉識別，較為典型的算法包括局部保持投影(Locality Preserving Projection，LPP)[7]、邊界 Fisher分析(Marginal Fisher Analysis，MFA)[8]和無監督判別投影(Unsupervised Discriminant Projection，UDP)[9]。這些算法旨在保留原始人臉圖像數據中的局部鄰域信息，從而試圖發現隱藏在人臉圖像數據中內在的低維非線性局部結構。然而當有類別標簽的人臉樣本數據不足時，有監督算法的泛化能力降低。需要說明的是，獲取樣本的類別信息十分耗時，而無標簽的數據相對來說容易得到，半監督分類利用大量廉價的無標簽樣本信息來增加分類的精確度[10]。而這些算法都是線性的，不能更好地發掘樣本中的高階非線性因素。隨著核函數在支持向量機(Support Vector Machine,SVM) 中的成功應用, 出現了如核鄰域保持投影(KernelNPP,KNPP)[11]及核無監督判別分析(KernelUDP,KUDP)[12]等非線性子空間方法，更好地發掘人臉受光照、姿態和表情等影響的非線性因素。但對于分類問題不能提取出最具有鑒別性的特征。文獻[13]提出核空間正交及不相關鄰域保持鑒別嵌入算法，能夠利用樣本的類別信息，但是不能充分利用無標記樣本信息。

為此，本文針對非線性和有標記樣本不足問題，提出了一種基于核正交半監督鑒別分析的人臉識別算法。在核空間，其目標函數是在監督算法MFA的基礎上，將UDP的局部和非局部散度矩陣引入，改進為半監督的算法，同時保證各向量正交。該算法不僅能有效地提取人臉圖像的非線性結構信息，而且將監督算法浪費的無標簽樣本和無監督算法沒有利用分類的標簽信息充分利用，進一步提高了分類的魯棒性。

2 半監督鑒別分析

2.1 邊界Fisher判別分析

MFA的目標是將k1近鄰的樣本拉近的同時將k2近鄰的樣本推遠。其好處是避免少數幾個相距較遠的樣本主導，避免了 LDA滿足高斯分布這一條件。假設{(x1, l1),(x2, l2),…,(xN,lN)}為人臉訓練樣本數據集，其中，xi∈RD表示一個D維向量，li∈L={1,2,…,c}是樣本xi的類別標簽，L為類別標簽集。數據點xi通過投影矩陣WD×d可以得到低維映射yi∈Rd,d＜D ，即

MFA定義類內散布矩陣Sw來表示同類數據點的集中程度：

2.2 無監督判別分析

UDP是Yang等[9]人提出的一種流形學習的線性化算法。除了反映人臉樣本間的內在數據關系外，還能夠對人臉樣本進行有效分類。UDP的目標就是最大化非局部散度與局部散度的比，得到有效的分類方向，從而使樣本數據點在該方向上投影。為此，我們定義一個N×N的鄰接矩陣H如下所示：

局部散度 JL(W)能夠將高維空間中靠的近的樣本點降到低維空間中仍然保持近鄰關系，其定義如下：

非局部散度 JN(W)不同于局部散度，是將高維空間中非近鄰的樣本點降維后保持疏遠關系。其定義如下：

局部散度矩陣SL、非局部散度矩陣SN分別定義為：

基于UDP準則思想，最小化局部散度的同時最大化非局部散度。其目標函數定義如下：

2.3 半監督鑒別分析

將高維空間中同類近鄰的人臉樣本點在低維空間中仍然保持近鄰關系，而異類近鄰點在低維空間中保持疏遠關系。同時，考慮到有標記的人臉樣本不足問題，將MFA和UDP進行結合，其目標函數形如UDA[14](UDP—based Discriminant Analysis)表示如下：

其中：Sb和Sw通過有標簽人臉訓練樣本計算而來，即 MFA算法中的類間散布矩陣和類內散布矩陣。JN和JL是通過全部數據集計算出來的，即UDP算法中的非局部散布矩陣和局部散布矩陣。α和β用來調節JN和JL的貢獻度的常系數。

3 核正交半監督鑒別分析

假設存在一個非線性映射φ:RD→H,H表示高維內積空間。φ(xi)是xi在H中的值，對于空間H中φ(xi)與φ(xj)間的距離，定義為,其中,是核矩陣K的(i, j)個元素。表示H中的內積運算，稱為核函數。常用的核函數主要包括：1）線性核函數：多項式核函數：K(x, y)=(1+xTy)d；3）高斯核函數：

3.1 算法推導

本文算法的目的是對H中數據點φ(X)=[φ(x1),φ(x2),…,φ(xN+M)]通過線性映射 Z=WTφ(x)進行降維，并將人臉圖像映射為l維空間中的新樣本數據點： Z=[z1, z2,…,zN+M]。核空間轉換矩陣中的W={w1,w2,…,wn}的列向量wt(1 ≤t≤n)是 由φ(X)=[φ(x1),φ(x2),…,φ(xN+M)]張成，故存在一組系數B={b1, b2,… bN+M}，使得

則可定義核空間類內散布矩陣如下：

其中 KN=φ(XN)Tφ(X)。

核空間類間散布矩陣為：

核空間局部散度矩陣如下所示：

其中 K=φ(X)Tφ(X)。

核空間非局部散度矩陣表示如下：

本文算法旨在尋求一組滿足正交條件且最大化核空間目標函數的基向量。核正交半監督鑒別分析的目標函數表示如下：

利用拉格朗日乘數，以上受約束最小化問題可以轉換成如下方程：

最終通過對以上方程求解可得：

bk為方程(18)的最小特征值對應的特征向量。其中，最后得到核空間的投影矩陣 B=[b1, b2,…,bl]，對于輸入樣本xi，其在核空間的半監督鑒別分析即為；其中 表示 的第 個元zmi素。

3.2 算法步驟

核正交半監督判別分析步驟如下:

Setp 1.選擇合適的核函數，將人臉的訓練集樣本數據映射至高維特征空間。

Step2.構造近鄰圖。對任意 xi∈XN，選擇人臉圖像的同類點鄰域，異類點鄰域以及全局鄰域。

Setp3.根據式（11）、（12）、（13）和（14），分別計算人臉訓練集數據在H 中的Sw、Sb、JL和JN。

Step4.求解式（16）和（18），得到l個最大特征值對應的一組特征向量 B=[b1, b2,…,bl]。

Step5.對人臉的訓練樣本和測試樣本進行非線性降維，采用最近鄰分類器對特征分類，確定人臉測試樣本集所屬的類別。

4 人臉識別實驗

在ORL和YALE人臉庫上分別進行實驗來驗證本文算法的性能，并與PCA，LDA，LPP，MFA、UDP進行對比。實驗中，參數α和β均設置為0.1，采用了高斯核函數k(x, y)=exp()，式中高斯核參數中的δ為經驗值，取δ=5.5e+7。LPP、MFA、UDP以及本文算法中k近鄰參數k取 3。實驗用最近鄰分類器來分類，識別率取 10次實驗的最大平均值。所有人臉圖像為灰度圖像，本文使用的人臉圖像經裁剪后大小均為32×32像素。

4.1 ORL人臉數據庫的實驗

ORL人臉庫是由英國劍橋大學建立，包括 40個人，每個人10張112×92的在不同時間采集的正面人臉圖像組成。其中包括不同視角、不同表情（高興、微笑、生氣、吃驚、閉眼、睜眼等）和不同面部細節（戴或不戴眼鏡、有或無胡須、不同發型），人臉姿態有變化和旋轉不超過 20°。圖 1所示的是來自ORL人臉庫的某一人的10張圖像。

圖1 ORL人臉庫圖像示例

對于 ORL人臉庫的實驗驗證，隨機地從每個人的圖片中選擇 L(L=3,4,…,7)張圖片作為訓練樣本，余下的10-L張圖片作為測試樣本。其中，監督算法LDA和MFA在訓練時所采用的全是具有標簽信息的訓練樣本。而在本文算法訓練時只需要使用到2個帶有標簽的人臉樣本，余下的訓練樣本就是把標簽信息去掉的樣本。如下表1為六種算法分別在不同訓練樣本的情況下識別率的對比，而圖2是這六種算法均采用4個訓練樣本降到不同維數的識別率的對比。

表1 ORL人臉庫上的識別結果比較

MFA 85.68 90.80 93.38 95.63 96.72 UDP 84.92 90.23 93.24 94.58 96.53本文算法 91.59 95.47 97.86 98.16 98.78

圖2 ORL人臉庫的4Train的識別率

從表1和圖2可以看出，本文算法在ORL人臉庫上能夠取得最高的識別率。在有標記訓練樣本為2張人臉，并利用其余無標記樣本時，本文算法在維數為38時達到最高識別率95.47%，且在特征維數達到38以后, 基本穩定在一個特定范圍。同時可看出，MFA和UDP算法的識別率高于LDA和PCA算法的識別率。

4.2 YALE人臉數據庫的實驗

YALE人臉庫由15個人，每個人有11張共165張圖像組成。這些圖像在光照條件下變化比較大，而且面部表情（正常、驚訝、傷心、開心和眨眼等）和細節（戴或不戴眼鏡、有或無胡須）也有比較明顯的變化。YALE人臉庫中的某一個人的11張圖像如圖3所示。

圖3 YALE人臉庫圖像示例

在YALE人臉庫實驗中，也是隨機地從每個人的圖像中選取 L(L=3,4,…,7)張圖片作為訓練樣本，而余下11-L張作測試樣本。在YALE中對于帶有標簽信息和不帶標簽信息的人臉樣本選取和 ORL相同。如下表2為六種算法在不同訓練樣本情況下識別率的對比，而圖4是六種算法均采用4個訓練樣本降到不同維數的識別率的對比。

表2 YALE人臉庫上的識別結果比較

PCA 49.32 53.74 56.03 58.60 60.53 LDA 58.47 69.80 73.62 78.31 79.65 LPP 68.35 76.76 77.24 80.33 83.85 MFA 68.15 77.37 81.12 83.68 86.03 UDP 68.23 77.14 79.58 82.39 85.80本文算法 71.53 81.52 83.17 85.45 89.86

圖4 YALE人臉庫的4Train的識別率

從表2和圖4可以看出，由于YALE庫的圖像受姿態、光照、表情變化的干擾較大，因此文中所列的所有方法的識別率相對較低。從實驗結果可以看出，PCA和LDA保持全局線性結構進行維數約減，不能很精確地描述非線性流形，其識別率最低。本文算法在維數為54時達到最高識別率81.52%，高于LPP，MFA及UDP的識別率。LPP，MFA和UDP算法最高識別率分別為 76.76%，77.37%和77.14%，它們的特征維數分別為28，39和56時取得最大識別率。

4.3 實驗分析

本文算法在MFA的基礎上，將無監督UDP加入到目標函數中，并引入核技巧在保證特征空間各向量相互正交的條件下，可得到利于有效分類的投影矩陣。實驗表明，本文算法對于姿態、表情、光照等變化體現出極強的魯棒性，相比其它幾種算法，識別效果是最優的。該算法在核空間中利用了樣本空間的判別信息和局部幾何結構，當僅有少量的標簽樣本時，可以利用大量的無標簽樣本幫助估計數據的流形結構，提高學習性能。作為識別來說，更多的特征將會引入不利于分類的信息，當維數達到一定的程度，識別率不再會因維數的增加而提高，甚至可能有所下降。而MFA僅僅利用有限的有標簽樣本，LPP、UDP利用無標簽樣本，同時這些算法實質上是線性的，所以識別率低于本文算法。PCA的識別率低于LDA，這是由于PCA是無監督的。LDA的識別率要比MFA低，MFA的識別率也比本文算法低，這說明核正交半監督鑒別分析能夠取得比較理想的性能。

5 結束語

本文針對流形學習算法中非線性和有標簽樣本不足問題，提出了一種核正交半監督鑒別分析的人臉識別方法，使用高斯核函數，在核空間中提取人臉非線性特征，并保證各向量間相互正交，從而更有效的提取出人臉非線性局部結構。算法既能充分利用有標記樣本的監督信息，又能挖掘出隱藏在無標記數據中的潛在信息，很好的保持了數據的局部和全局信息。然而，由于核函數的選擇都是根據經驗來選取的，至今還沒有一個確定的理論依據和選擇標準。因此，如何更有效地利用核空間發掘人臉圖像中非線性高維數據的本質的、內在的結構將是今后的一個研究方向。

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

[2]Belhumeur P,Hespanha J,Kriegmand D.Eigenfaces vs.Fisherfaces:Recognition using class specific linear projection[J].Pattern Analysis and Machine Intelligence,1997, 19(7) :711-720.

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

[4]Roweiss L,Saul L.Nonlinear dimensionality reduction by locally linear embedding[J].Science, 2000,290(5500):2323-2326.

[5]Belkin M,Niyogi P.Laplacian eigenmaps for dimensionality reduction and data representation[J].Neural Computation, 2003, 15(6):1373-1396.

[6]Bengio Y,Palement J,Vincent P,et al.Out-of-sample extensions for LLE, isomap, MDS, eigenmaps, and spectral clustering[J].Neural Computation, 2004, 16(10):2179-2219.

[7]He Xiaofei, Yan Shuicheng, Hu Yuxiao, et al.Face Recognition Using Laplacianfaces[J].IEEE Trans on Pattern Analysis and Machine Intelligence, 2005, 27(3):328-340.

[8]Yan Shuicheng, Xu Dong, Zhang Benyu, et al.Graph Embedding and Extensions:A General Framework for Dimensionality Reduction[J].IEEE Trans on Pattern Analysis and Machine Intelligence, 2007, 29(1):40-51.

[9]Yang Jian,Zhang D,Yang Jingyu,et al.Globally Maximizing, Locally Minimizing:Unsupervised Discriminant Projection with Applications to Face and Palm Biometrics[J].IEEE Trans on Pattern Analysis and Machine Intelligence, 2007, 29(4):650-664.

[10]魏萊,王守覺.基于流形距離的半監督判別分析[J].軟件學報,2010, 21(10):2445-2453.

[11]龐彥偉,俞能海,沈道義,劉政凱.基于核鄰域保持投影的人臉識別[J].電子學報,2006,34(8):1542-1544.

[12]王慶軍,張汝波,潘海為.核正交UDP及其在人臉識別中的應用[J].計算機輔助設計與圖形學學報，2010,22(10):1783-1787.

[13]劉冠群,王慶軍,張汝波,潘海為.核空間正交及不相關鄰域保持鑒別嵌入算法[J].哈爾濱工程大學學報，2011,32(7):938-942.

[14]Qiu H N, Lai J H, Huang J, et al.Semi-supervied discriminant analysis based on UDP regularization[C].Proc of the 19th International Conference on Pattern Recognition.Tampa:IEEE, 2008:1-4.