有監督正交局部保留投影及其在人臉識別中的應用*

董昌劍，陳秀宏，陳達遙

(江南大學數字媒體學院,江蘇 無錫 214122)

有監督正交局部保留投影及其在人臉識別中的應用*

董昌劍，陳秀宏，陳達遙

(江南大學數字媒體學院,江蘇 無錫 214122)

針對局部保留投影算法(LPP)的無監督和非正交問題，提出了一種有監督的正交局部保留投影算法SOLPP。該算法同時考慮了樣本的類別信息以及投影向量間的相互正交性，首先利用樣本的類標簽信息重新定義了類內和類間相似度矩陣，同時最大化類間離散度與類內離散度之比，有效地保持了樣本的局部結構；其次對投影基向量進行正交化，在保持數據空間結構的同時進一步提高了人臉識別效果。在ORL和FERET人臉庫上的實驗表明，該方法的識別率要優于SLPP等算法。

人臉識別；圖像降維；有監督；正交化；局部保留投影

1 引言

圖像降維是人臉識別中重要的預處理步驟之一，其目的是在保留人臉的主要信息的同時將高維的特征空間嵌入到一個維數相對較低的空間。根據是否使用標簽信息，降維方法可分為有監督的和無監督的，其對應的兩個最常用的降維方法分別是主成分分析法PCA(Principal Component Analysis)[1]和線性判別分析法LDA(Linear Discriminant Analysis)[2]。

近年來基于流形技術的降維方法吸引許多人研究，并基于不同的準則和目的提出了多種流形降維算法。He Xiao-fei等[3,4]提出了一種局部保留投影LPP(Locality Preserving Projection)的線性降維算法，并已被證實在許多應用中可以得到比PCA和LDA更好的效果。LPP的本質是一種無監督的降維方法，其主要思想是通過變換，使原始空間中相互離得近的點對在降維后的低維空間中也保持較近，從而保留原始數據的局部結構。該方法對于類內距離較近的數據能夠找到好的投影方向，但當兩個不同的類距離較近甚至部分重合時，則會被投影到一起，得到的結果不理想。為此，申中華[5]提出了有監督局部保留投影算法SLPP(Supervised Locality Preserving Projection)，它同時考慮了局部保留特性和類間分離性，得到了較好的投影效果。李曉曼等人[6～9]提出的基于類別信息的監督局部保留投影方法使樣本點在低維空間能夠同時保持流形的局部幾何結構和分類信息。但是,他們都沒有考慮投影向量間的正交性。LPP本身是通過求解一個不對稱特征方程的最小特征值所對應特征向量得到投影向量，它并不能保證各方向均為正交的，從而導致人臉數據重建因難。Cai D[7]等提出了一種正交拉普拉斯算法，保證了向量間的正交性，但是沒有考慮標簽信息及類間離散度問題。

基于對上述算法的優缺點分析，并參考一些較新的改進算法[8～12]，本文將有監督的局部保留投影與正交拉普拉斯算法相結合，在同時考慮局部保留特性、類間分離性和投影向量正交性的條件下，提出一種新的有監督正交局部保留投影SOLPP(Supervised Orthogonal Locality Preserving Projection)的人臉識別算法，并在ORL和FERET人臉庫上進行實驗，以說明該方法優于SLPP等方法。

2 LPP算法回顧

假設樣本集X=[x1,x2,…,xn]，xi∈Rm，i=1,2,…,n。數據的線性降維就是尋找一個投影矩陣A=[a1,a2,…,ad]∈Rm×d，將這些樣本映射到一個低維的特征空間。在這個低維樣本空間中，樣本集表示為Y=[y1,y2,…,yn],且Y=ATX。變換矩陣A可通過最小化如下LPP的目標函數來得到：

其中yi=aTxi，S為相似矩陣，用k近鄰法定義為：

經過簡單代數計算后，可得:

aTX(D-S)XTa=aTXLXTa

上述約束問題很容易轉換為一個求解特征值問題:

XLXTa=λXDXTa

在人臉識別中，LPP算法經常會遇到小樣本問題，即矩陣XDXT是奇異的。為了解決這個問題，通常先對原始圖像數據采用PCA降維，保證矩陣XDXT是非奇異的;然后在PCA子空間應用LPP算法。因此,LPP算法的投影矩陣A=[a1,a2,…,ad]就由矩陣(XDXT)-1XLXT的前d個最小特征值所對應的特征向量構成。

3 有監督的正交局部保留投影(SOLPP)

3.1LPP算法的缺點

LPP算法是一種非監督的降維算法，它的主要目的是使原始空間中兩個距離相近的點在低維投影空間中也相距很近，這樣可以有效地保持原始空間的局部結構。但是，由于LPP算法沒有考慮數據中的類別信息，對于屬于同一類的相近點來說，在低維空間中相距很近是合適的，但對于屬于不同類的相近點來說，在低維空間中如果也保持靠近就會影響最后的識別效果。其次，降維后的低維空間的兩個數據點的歐氏距離可以表示成：

如果A是正交的，則AAT=I,原始圖像的空間結構就能被完好地保存。但是，由于LPP算法中矩陣(XDXT)-1XLXT是非對稱的，其解也不可能是一組相互正交的特征向量，因些對數據重建造成一定困難，不能有效地保持圖像的空間結構。

3.2SOLPP算法

針對LPP的非監督本質，引入有監督的處理機制，充分利用不同人臉圖像的類別信息。通過上述對LPP的分析可以看出，為了獲得更好的投影降維效果，不但要保留類內的局部結構，使同一類的樣本點相距很近，還要最大化類間分離度，使不同類的樣本點相距較遠，以便得到最佳的分類特征，提高分類識別的精度。

類內局部結構的保留可通過最小化式(1)得到：

(1)

其中,W是類內相似度矩陣，Wij和LPP中的Sij相似，不同的是Sij表示的是全局樣本中的兩點xi和xj的相似度，而Wij表示的是同一類內的兩個樣本的相似程度。這樣最小化式(1)就可以保證同一類內的點在投影到低維空間后相距較近。

同時，類間分離度可通過最大化式(2)得到：

(2)

其中,B是類間相似度矩陣，Bij表示不同類的兩個樣本xi和xj的相似程度。這樣最大化式(2)就可以保證不同類的點在投影到低維空間后相距較遠。這里仍使用熱核來計算相似度。在SLPP 中，首先是建立類間鄰接圖和類內鄰接圖，然后分別定義了樣本類內相似度矩陣B和類間的相似度矩陣W。為了充分利用樣本的類別信息以及減少構建鄰接圖的過程，可以將其重新定義為：

因此,目標函數可重寫為：

經過簡單的變換后目標函數可變為：

(3)

其中,LB=DB-B,LW=DW-W是拉普拉斯矩陣。DB和DW都是對角矩陣，對角元素分別是B和W對應的列或行上的元素之和。則最大化目標函數式(3)可轉化為求下面廣義特征值問題的最大特征值對應的特征向量：

XLBXTa=λXLWXTa

(4)

同樣，在小樣本情況下，矩陣XLWXT可能會出現奇異性，因此首先對原始圖像數據進行PCA降維，以保證矩陣XLWXT是非奇異的。則式(4)的前k個最大特征值對應的特征向量構成投影矩陣。

則正交基向量可通過下面的迭代方法計算得到：

Step1計算q1，q1由廣義特征方程XLBXTq=λXLWXTq的最大的特征值所對應的特征向量得到。

Step2計算qk，qk通過計算方程M(k)q=λq的最大特征值所對應的特征向量得到，其中M(k)的定義如下：

最后得到正交投影矩陣U*=[q1,q2,…,qk]。

綜上所述，利用SOLPP算法進行人臉識別的基本步驟如下：

(1) 為了保證XLXT是非奇異的，首先對原始人臉圖像進行PCA降維處理，將高維的人臉特征通過轉換矩陣投影到低維的PCA子空間中去，并求得投影矩陣UPCA。

(2) 使用熱核函數建立類內相似度矩陣W和類間相似度矩陣B，并計算拉普拉斯矩陣LB=DB-B,LW=DW-W。求解下面的廣義特征值問題得到初始投影基向量：

XLBXTa=λXLWXTa

(3) 采用迭代正交化方法對上面得到的初始投影基向量進行正交化，得到正交投影矩陣U*。

(5) 利用最小近鄰分類法對測試圖像進行分類。對于每一個投影后的測試圖像，比較其與投影后的訓練圖像之間的歐氏距離，并決策為與其最近的圖像的同類。進而通過決策的正確與否求出SOLPP算法的人臉識別效率。

4 仿真實驗與結果分析

4.1ORL上人臉識別實驗結果

為了驗證算法的有效性，在ORL庫上對本文算法進行測試，并與PCA、LDA、LPP、SLPP算法進行比較。ORL人臉庫包括40個人的400幅112×92大小的人臉圖片。人的臉部表情和臉部細節有著不同程度的變化，人臉姿態也有相當程度的變化，深度旋轉和平面旋轉達20°,人臉的尺度也有10%的變化。本文實驗使用的人臉圖片經剪切后大小均為64×64。圖1是ORL人臉庫的一些人臉照片。

Figure 1 ORL face database圖1 ORL人臉庫

ORL人臉庫上每人有10張圖片，本文用每人的前4、5、6張圖像進行訓練，用剩下的圖片進行測試。其中變量d的值從1取到最大特征維數，最佳識別率便可通過k的不同取值來得到。表1為PCA、LDA、LPP、SLPP、SOLPP幾種方法在不同訓練樣本數下的最佳識別率的比較。圖2為訓練圖像為前4張時不同方法在不同特征向量維數下的識別率比較。

Table 1 Best recognition rates on ORL表1 ORL人臉庫上的最佳識別率 %

Figure 2 Recognition rates of different dimension on ORL圖2 ORL人臉庫上不同維數下的識別率(4Train)

4.2 FERET上人臉識別實驗結果

FERET人臉庫由FERET項目組創建，包含200個人的1 400張人臉灰度圖像，其中圖像具有多姿態、不同光照環境的特點。圖3是FERET人臉庫的一些人臉照片

Figure 3 FERET face database圖3 FERET人臉庫

FERET人臉庫中每人有7張圖片，本文用每人的前3、4、5張圖像進行訓練，其余圖像進行測試。實驗結果如表2和圖4所示。

Table 2 Best recognition rates on FERET表2 FERET人臉庫上的最佳識別率 %

Figure 4 Recognition rates of different dimension on FERET圖4 FERET人臉庫上不同特征維數下的識別率(4Train)

4.3 實驗結果分析

上述實驗結果表明，本文提出的算法識別率是最高的，有監督算法的識別率要高于無監督的算法，保留局部結構算法的識別率要高于保留全局結構的算法。PCA算法的識別率最低，因為其是非監督學習算法，沒有使用類標簽信息。LDA是有監督學習算法，使用了類標簽信息，識別率較PCA有很大提高，但是忽視了流形的局部結構。LPP具有保持局部結構的特征，它的識別率要優于PCA。SLPP在LPP算法的基礎上加上類標簽信息，將有監督和保持局部結構的優點相結合，識別效果要優于前三種算法。本文提出的SOLPP算法在SLPP算法的基礎上，又考慮了投影向量間的正交性，更有效地保持了數據的空間結構，從而更好地提高了識別率。

5 結束語

本文結合了有監督局部保留投影和正交拉普拉斯算法的優點，提出了一種新的有監督正交局部保留投影算法，同時解決了LPP沒有利用類標簽信息和投影向量非正交的問題，保持了數據的局部結構和整體結構，使人臉識別的效率有了進一步的提高。最后通過仿真實驗進行了驗證。但是，該算法仍然是線性的數據降維方法，下一步的工作是嘗試使用核函數把線性降維，擴展到非線性降維以求得到更好的識別效果。

[1] Jolloffe I T. Principal component analysis[M]. New York:Springer-Verlag,1986.

[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 and Machine Intelligence,1997,19(7):711-720.

[3] He X F, Niyogi P. Locality preserving projections[C]∥Proc of Conference on Advances in Neural Information Processing Systems, 2003:585-591.

[4] He X F, Yan S C, Hu Y X. Face recognition using Laplacianfaces[J]. Pattern Analysis and Machine Intelligence, 2005,27(3):328-340.

[5] Shen Zhong-hua,Pan Yong-hui,Wang Shi-tong.A supervised locality preserving algorithm for dimensionality reduction[J]. Pattern Recognition and Artificial Intelligence,2008,21(2):233-239.(in Chinese)

[6] Li Xiao-man, Wang Jing.Supervised locality preserving projection based on class information[J]. Journal of Computer Applications, 2012,32(2):531-534.(in Chinese)

[7] Cai D, He X, Han J. Orthogonal Laplacian faces for face recognition[J].IEEE Transactions on Image Processing, 2006, 15(11):3608-3614.

[8] Jin Yi,Ruan Qiu-qi.Kernel based orthogonal locality preserving projections for face recognition[J].Journal of Electronics & Information Technology,2009,31(2):283-287.

[9] Wong W K, Zhao H T.Supervised optimal locality preserving projection[J].Pattern Recognition, 2012,45(1):186-197.

[10] Zhang Liang, Huang Shu-guang, Guo Hao.A fast kernel supervised locality preserving projection algorithm[J].Journal of Electronics & Information Technology,2011,33(5):1049-1054.

[11] Shu Xin, Gao Yao, Lu Hong-tao. Efficient linear discriminant analysis with locality preserving for face recognition[J].Pattern Recognition, 2012,45(5):1892-1898.

[12] Yang Wan-kou, Sun Chang-yin, Lei Zhang. A multi-manifold discriminant analysis method for image feature extraction[J]. Pattern Recognition,2011,44(8):1649-1657.

附中文參考文獻：

[5] 申中華,潘永惠,王士同.有監督的局部保留投影降維算法[J]. 模式識別與人工智能,2008,21(2):233-239.

[6] 李曉曼, 王靖. 基于類別信息的監督局部保持投影方法[J]. 計算機應用, 2012,32(2):531-534.

DONGChang-jian,born in 1991,MS candidate,his research interests include artificial intelligence, and pattern recognition.

陳秀宏(1964-),男,江蘇泰興人,教授，研究方向為人工智能和模式識別。E-mail:xiuhongc@263.net

CHENXiu-hong,born in 1964,professor,his research interests include artificial intelligence, and pattern recognition.

陳達遙(1988-),男,湖南益陽人，碩士生，研究方向為人工智能和模式識別。E-mail:404704115@qq.com

CHENDa-yao,born in 1988,MS candidate,his research interests include artificial intelligence, and pattern recognition.

Supervisedorthogonallocalitypreservingprojectionanditsapplicationinfacerecognition

DONG Chang-jian,CHEN Xiu-hong,CHEN Da-yao

(School of Digital Media,Jiangnan University,Wuxi 214122,China)

Aiming at the unsupervised and non-orthogonal property of the locality preserving projection, a supervised orthogonal locality preserving projection algorithm is proposed. The algorithm considers both of the class information and the orthogonal basis functions. Firstly, the within-class similarity matrix and the between-class similarity matrix are redefined by using the class information, the ratio of the between-class scatter and the within-class scatter is maximized, and the locality structure is preserved effectively. Secondly, the projection vector is orthogonalized, and the space structure of data is reserved as well as the effect of face recognition is further improved. Experimental results on ORL and FETER face databases demonstrate that the effectiveness of our proposed algorithm is better than other algorithms.

face recognition;image dimensionality reduction;supervised;orthogonalization;locality preserving projection

1007-130X(2014)08-1576-05

2013-01-03;

：2013-04-03

中央高校基本科研業務費專項資金資助(JUSRT211A70 )

TP391.4

：A

10.3969/j.issn.1007-130X.2014.08.027

董昌劍(1991-),男,安徽濉溪人，碩士生，研究方向為人工智能和模式識別。E-mail:723985704@qq.com

通信地址：214122 江蘇省無錫市江南大學數字媒體學院

Address:School of Digital Media,Jiangnan University,Wuxi 214122,Jiangsu,P.R.China