雙向二維局部保持鑒別投影應用于人臉識別

周慧，陳熙，劉增力

昆明理工大學信息工程與自動化學院，昆明650500

雙向二維局部保持鑒別投影應用于人臉識別

周慧，陳熙，劉增力

昆明理工大學信息工程與自動化學院，昆明650500

雙向二維局部保持映射（雙向2DLPP）與二維局部保持映射（2DLPP）比較，雙向2DLPP同時對圖像的行方向和列方向進行降維處理，可以采用較少的系數(shù)有效地表示圖像。為了進一步增強雙向2DLPP算法的分類能力，將雙向2DLPP所提取的特征采用線性判別式分析（LDA）進行分類，從而形成了一種新的監(jiān)督算法：鑒別雙向二維局部保持投影。理論分析表明，無論在計算量還是內(nèi)存要求方面，所提鑒別雙向二維局部保持投影算法比雙向2DLPP和主成分分析+線性判別式分析（PCA+LDA）要少，而且在ORL和Yale數(shù)據(jù)庫上的人臉識別實驗表明，新算法的識別性能比雙向2DLPP和PCA+LDA算法要好，且具有較少的計算復雜度。

雙向二維局部保持映射；線性判別式分析；人臉識別；計算復雜度

1　引言

局部保持映射［1］（LPP）是一種廣泛應用于模式識別，計算機視覺等領(lǐng)域的線性數(shù)據(jù)降維技術(shù)。在LPP中，二維圖像矩陣首先必須轉(zhuǎn)換成一維向量，但是將圖像轉(zhuǎn)化成向量就失去了圖像本身的結(jié)構(gòu)特性，同時轉(zhuǎn)化后的向量維數(shù)很高，這就容易導致計算復雜度太大。為了解決這個問題，二維局部保持映射［2-3］根據(jù)局部保持準則直接從圖像矩陣中提取特征。文獻［4-5］中的實驗表明采用2DLPP進行人臉識別的識別率要高于LPP，同時計算復雜度要小得多。然而，2DLPP進行特征表示所需的系數(shù)很多，例如，假設(shè)一幅圖像大小是128×128，那么2DLPP中所需的表示系數(shù)為128×d，通常為了得到較高的識別率，d應該大于5。為了減少表示系數(shù)，可以同時在行方向和列方向?qū)D像進行降維處理，從而提出了二方向二維局部保持映射［6］（（2D）2LPP）。二方向二維局部保持映射在數(shù)據(jù)降維時強調(diào)的是數(shù)據(jù)的局部結(jié)構(gòu)，而實際中很多情況下降維后需要對數(shù)據(jù)進行分類，于是將提取的特征交給LDA進行分類，從而形成了一種新的監(jiān)督算法：（2D）2LPP+LDA。ORL人臉數(shù)據(jù)庫［7］和Yale數(shù)據(jù)庫［8］上的人臉識別試驗表明（2D）2LPP+LDA具有比（2D）2LPP更好的人臉特征提取和分類能力，而理論分析表明（2D）2LPP+LDA在計算量和內(nèi)存要求方面比PCA+LDA要少。

2　鑒別雙向二維局部保持映射

2.1行方向二維局部保持映射

假設(shè)a是一個n維單位列向量，Xi表示一幅m行n列的圖像，在一維LPP算法中Xi必須先轉(zhuǎn)化成一個m×n維的向量，但是在2DLPP算法中，可以直接將圖像Xi投影到單位列向量a上，如式（1）所示：

Yi就是所謂的投影特征向量，它實際上是圖像Xi在垂直方向上的投影。給定一個訓練樣本集T=｛X1，X2，…，XN｝，則2DLPP的目標函數(shù)為：

Wij是圖像Xi和Xi之間的相似度，Wij可按式（3）計算。

下面根據(jù)2DLPP的目標函數(shù)，通過矩陣運算推導2DLPP投影矩陣的計算方法。

在上面的推導中X是一個mN×n的矩陣，它是通過在列方向排列所有圖像矩陣得到的，即：， D是一個對角矩陣，。L=D-W是拉普拉斯矩陣。Im是一個m階單位矩陣。操作符?表示克羅內(nèi)克積［9］，通過使用克羅內(nèi)克積，L?Im可表示為：

此式中l(wèi)ij（ i，j=1，2，…，N）表示矩陣L的元素。很明顯，當a為零向量時，總是達到最小值0，為了防止出現(xiàn)這種情況，增加一個限制條件：aTXT（D?Im）Xa=1，因此2DLPP的目標函數(shù)變?yōu)椋?/p>

最小化上述目標函數(shù)的變換向量a就是廣義特征值問題（6）最小特征值所對應的特征向量。

通常一個變換向量不足以把所有模式分開，故一般選取最小d1個特征值所對應的特征向量構(gòu)成投影矩陣，投影矩陣的每一列就是一個特征向量。數(shù)據(jù)從高維到低維的映射可以表示為：

2.2列方向二維局部保持映射

假設(shè)b是一m維單位列向量，Xi表示一個大小為m×n的圖像矩陣，將圖像矩陣直接投影到向量b上得：

所得n維向量Yi就是列方向投影特征向量。與上節(jié)類似，通過矩陣運算，列方向2DLPP最小化目標函數(shù)（2）可以表示為：

這里X是一個m×nN的矩陣，它是通過在行方向排列所有圖像矩陣得到的，即：X=［X1，X2，…，XN］，D是一個對角矩陣，是拉普拉斯矩陣。In是一個n階單位矩陣。操作符?表示克羅內(nèi)克積，通過使用克羅內(nèi)克積，L?In可表示為：

上式中l(wèi)ij（ i，j=1，…，N）表示矩陣 L的元素。與前面類似，增加一個限制條件：bTXT（D?Im）Xb=1，因此列方向2DLPP的目標函數(shù)變?yōu)椋?/p>

矩陣X（L?In）XT和X（D?In）XT都是對稱正半定矩陣。最小化列方向2DLPP目標函數(shù)的變換向量b就是廣義特征值問題（10）最小特征值所對應的特征向量。

通常一個變換向量不足以把所有模式分開，故一般選取最小d2個特征值所對應的特征向量構(gòu)成投影矩陣，投影矩陣的每一列就是一個特征向量。數(shù)據(jù)從高維到低維的映射可以表示為：Xi→Yi=BTXi，B=（b1，b2，…，bd2）。

2.3鑒別雙向二維局部保持映射

前面2.1和2.2節(jié)分別對行方向和列方向二維局部保持映射的基本原理進行了較詳細的闡述，無論行2DLPP還是列2DLPP都存在表示系數(shù)太多的缺陷，如果對圖像矩陣同時進行和列二個方向上的2DLPP運算，則可以用較少的系數(shù)表示一幅圖像。假設(shè)行方向2DLPP從訓練圖像中學習到一個投影矩陣A，那么一個m行n列圖像Xi投影到這個矩陣上產(chǎn)生一個m行d1列的矩陣AXi。類似地，列方向2DLPP學習到一個投影矩陣B，將圖像Xi投影到這個矩陣上產(chǎn)生一個d2行n列的矩陣BTXi。假設(shè)同時得到了投影矩陣A和B，那么將圖像Xi同時投影到這兩個矩陣上得：

Ci也可稱為圖像表示的系數(shù)矩陣，圖像重建可以表示為：。

為了進一步增強（2D）2LPP的分類能力，設(shè)計鑒別雙向二維局部保持投影算法（（2D）2LPP+LDA）。該算法由2步構(gòu)成，首先在考慮數(shù)據(jù)局部特性的基礎(chǔ)上采用（2D）2LPP進行降維，得到每一幅圖像的投影系數(shù)矩陣Ci（i=1，2，…，N），接著將投影系數(shù)矩陣Ci轉(zhuǎn)化成向量后Di進一步采用LDA降維。設(shè)由LDA產(chǎn)生的投影矩陣為FLDA（其大小為（d1×d2）×l），則對于每幅圖像Xi（i=1，2，…，N），由（2D）2LPP+LDA產(chǎn)生投影向量Fi=Di×FLDA（i=1，2，…，N）。現(xiàn)假設(shè)一幅測試圖像XT，其相應投影向量為FT，則FT與任意一幅訓練圖像Fi投影系數(shù)矩陣之間的距離可以表示為：

3　試驗與分析

在這一章將比較所提新算法與局部保持映射、正交局部保持映射［10］（OLPP）、核局部保持映射［11］（KLPP）、雙向二維局部保持投影和線性判別式分析［12］（PCA+LDA）在ORL和Yale人臉數(shù)據(jù)庫上人臉識別性能。式（3）中的最近鄰數(shù)為每類樣本數(shù)，考慮到（2D）2LPP+LDA是一種監(jiān)督算法，故加權(quán)矩陣W采用監(jiān)督方式，即只有同類樣本之間的權(quán)值按式（3）計算，不同類樣本之間的權(quán)值為0。為簡單起見，采用基于歐式距離的最近鄰分類器進行分類。

3.1數(shù)據(jù)庫

ORL數(shù)據(jù)庫包含40個人的人臉圖片，每個人10張。某些圖片是在不同時間拍攝的，圖片之間存在各種變化，例如表情（睜眼和閉眼、笑和不笑）和面部細節(jié)（戴或不戴眼鏡）。一些圖片還有20度內(nèi)的旋轉(zhuǎn)變化。圖1（a）是該數(shù)據(jù)庫中2個人的20張樣本圖像。Yale人臉數(shù)據(jù)庫包含15個人的165張灰度圖片，每個人11張。圖片主要有光照、表情和戴不戴眼鏡方面的變化。圖1（b）是該數(shù)據(jù)庫中2個人的22張樣本圖像。所有圖像的大小都調(diào)整到32×32。

圖1　預處理樣本圖像

3.2正確識別率與特征維數(shù)的關(guān)系

首先考察了正確識別率與特征維數(shù)的關(guān)系，隨機地分別從ORL和Yale數(shù)據(jù)庫中每人選擇5個樣本圖像組成ORL和Yale訓練圖像集，剩下的為各數(shù)據(jù)庫的測試圖像集。實驗重復10次，圖2（a）和（b）中畫出了在ORL和Yale數(shù)據(jù)庫中不同特征維數(shù)下的平均識別率。

圖2　正確識別率與特征維數(shù)的關(guān)系

在ORL數(shù)據(jù)庫中，（2D）2LPP+LDA首先采用（2D）2LPP將原數(shù)據(jù)降維到10×10，然后再采用LDA繼續(xù)降維，故在這種算法中，考察的特征維數(shù)是從1至100，而對于LPP、OLPP和PCA+LDA三種算法首先都是采用PCA將數(shù)據(jù)維數(shù)降到60，然后分別采用LPP、OLPP和LDA進行降維，故考察的特征維數(shù)都是從1到60。對于KLPP，首先采用核主成分分析［13-14］（KPCA）降到60維，然后采用LPP降維，故KLPP中最大可考察的維數(shù)為60。

在Yale數(shù)據(jù)庫中，（2D）2LPP+LDA首先采用（2D）2LPP將原數(shù)據(jù)降維到10×10，然后再采用LDA繼續(xù)降維，故在這種算法中，我們考察的特征維數(shù)可以是從1至100，為了較清楚的對比其他算法，我們在圖2（b）中僅顯示前75維的識別率，其余的特征維數(shù)所對應的識別率基本不變。而對于LPP、OLPP和PCA+LDA三種算法首先都是采用PCA將數(shù)據(jù)維數(shù)降到160，然后分別采用LPP、OLPP和LDA進行降維，故考察的特征維數(shù)都是從1到160。對于KLPP，首先采用KPCA降到160維，再采用LPP降維，故最大可考察的維數(shù)為160。

從圖2（a）（b）中可以看出（2D）2LPP+LDA的平均最佳識別率是最高的，而且達到一定維數(shù)后識別率很穩(wěn)定。對于（2D）2LPP算法，同時將行方向和列方向的維數(shù)從1變化到32維。

3.3正確識別率與訓練樣本集大小的關(guān)系

上一節(jié)考察了PCA+LDA、LPP、KLPP、OLPP和（2D）2LPP+LDA中正確識別率與特征維數(shù)的關(guān)系，這一節(jié)繼續(xù)考察識別率與訓練樣本集大小的關(guān)系。首先隨機從ORL和Yale數(shù)據(jù)庫中每個人選擇3，4，5，6，7，8個樣本組成不同大小的ORL和Yale訓練樣本集，剩下的圖片都作為各數(shù)據(jù)庫的測試集。比較了PCA+LDA、LPP、KLPP、OLPP和（2D）2LPP+LDA幾種算法在這些不同個數(shù)訓練集上的識別性能，每個訓練集上重復10次試驗，表1和表2分別記錄了在ORL和Yale數(shù)據(jù)庫這些算法在不同訓練集上的識別率及標準偏差。從表1和表2中可知，隨著每類訓練樣本數(shù)增大，識別率都有所上升。在表中所列幾種算法中，（2D）2LPP+LDA識別率是最好的，而且標準偏差較小，說明識別結(jié)果較穩(wěn)定。

表1　ORL數(shù)據(jù)庫上的平均識別率和標準偏差%

表2　Yale數(shù)據(jù)庫上的平均識別率和標準偏差%

3.4計算復雜度與內(nèi)存需求分析

本文所提算法和PCA+LDA都是監(jiān)督算法，在前面一節(jié)比較了本文所提算法與PCA+LDA在識別率方面的性能，本節(jié)繼續(xù)對PCA+LDA與（2D）2LPP+LDA的計算復雜度、內(nèi)存需求進行比較分析。為了計算PCA+ LDA的投影特征空間，首先需要計算一個N×N的特征值問題，然后求解一個dPCA×dPCA的廣義特征值問題，這里N是訓練樣本集的樣本數(shù)，dPCA是PCA階段的特征維數(shù)。然而，（2D）2LPP+LDA算法中在（2D）2LPP算法中需要求解一個m×m特征值問題和一個n×n特征值問題，然后在LDA階段需要求解一個krow×kcol廣義特征值問題，這里m，n，krow和kcol分別是原圖像的行數(shù)、原圖像的列數(shù)和（2D）2LPP中列方向2DLPP和行方向2DLPP降到的維數(shù)。由于一個M×M特征值問題的計算復雜度［15］為：O（M3），那么PCA+LDA投影矩陣的計算復雜度為，（2D）2LPP+LDA的計算復雜度為O（m3+n3+［max（krow，kcol）］3），假定m，n，dPCA和max（krow，kcol）都小于訓練樣本數(shù)，則（2D）2LPP+LDA比PCA+LDA需要更少的計算量計算投影矩陣。

下面繼續(xù)分析將測試圖像投影到PCA+LDA和（2D）2LPP+LDA特征空間所需的計算量，在這里假設(shè)這兩種算法的最終投影特征空間維數(shù)相同，都為dLDA，則將Np幅測試圖像投影到PCA+LDA特征空間所需的計算量為：Np×（m×n）×dLDA，而（2D）2LPP+LDA算法需要的乘法次數(shù)為：Np×［m×n×min（kcol，krow）+（krow×kcol）×max（m+dLDA，n+dLDA）］。在內(nèi)存方面，PCA+LDA算法中僅需保存一個投影矩陣，大小為（m×n）×dLDA，而（2D）2LPP+LDA算法中需要保存三個特征矩陣，總的大小為：kcol×m+krow×n+krow×kcol×dLDA。表3總結(jié)了（2D）2LPP+LDA和PCA+LDA算法所需的計算量和內(nèi)存要求。假設(shè)在ORL數(shù)據(jù)庫上采用200個訓練樣本，如果m，n，krow和kcol分別取值30、30、10和10，N=200，dLDA=39，dPCA=160，d（2D）2LPP=10×10，則據(jù)表3可以看出（2D）2LPP+LDA算法無論在計算復雜度和內(nèi)存需求方面都比PCA+LDA具有優(yōu)勢。

表3?。?D）2LPP+LDA和PCA+LDA在ORL數(shù)據(jù)庫上的計算復雜度和內(nèi)存需求比較

4　結(jié)束語

本文提出了一種有效的人臉識別算法：（2D）2LPP+LDA，（2D）2LPP與現(xiàn)在的2DLPP的主要區(qū)別在于后者是在行方向處理圖像，而前者同時在行和列兩個方向處理圖像，這樣就能用更少的系數(shù)進行特征表示，顯著提高了識別速度，而（2D）2LPP提取的特征采用LDA分類進一步增強了算法的分類能力。ORL和Yale數(shù)據(jù)庫上的人臉識別實驗證實了所提算法的有效性。

［1］He X F，Niyogi P.Locality preserving projections［C］//Proc Conf Advances in Neural Information Processing Systems，2003.

［2］Chen S，Zhao H，Kong M，et al.2D-LPP：A two dimensional extension of locality preserving projections［J］.Neurocomputing，2007，70：912-921.

［3］孫麗娟，楊丹，張小洪，等.基于SR-2DLPP的人臉識別［J］.計算機應用研究，2009，26（7）：2789-2792.

［4］Ben N，Shiu S C K，Pal S K.Two dimensional Laplacianfaces method for face recognition［J］.LNCS RSCTC，2006.

［5］Zhang Zhiwei，Yang Fan.2DLPP：A novel method for small sample size faces recognition［J］.Journal of Optoelectronics· Laser，2008，19（7）：972-975.

［6］靳麗麗，陳秀宏.一種雙向2DLPP算法及其在人臉識別中的應用［J］.計算機工程與科學，2010，32（9）：50-64.

［7］The ORL Face Database，Cambridge，U.K，AT&T（Olivetti）Research Laboratories［EB/OL］.［2013-05-05］.http：//www.uk. research.att.com/facedatabase.html.

［8］YaleUniv.Facedatabase［EB/OL］.（2002）.http：//cvc.yale. edu/projects/yalefaces/yalefaces.html.

［9］Jain A K.Fundamentals of digital image processing［M］.［S.l.］：Prentice Hall，2011.

［10］Cai D，He X，Han J，et al.Orthogonal laplacianfaces for facerecognition［J］.IEEETransactionsonImageProcessing，2006，15（11）：3608-3614.

［11］Feng G，Hu D，Zhang D，et al.An alternative formulation of kernel LPP with application to image recognition［J］. Neurocomputing，2006，69：1733-1738.

［12］Zhao W，Chellappa R，Phillips P J.Subspace linear discriminantanalysisforfacerecognition，TechReport CAR-TR-914［R］.Center for Automation Research，University of Maryland，1999.

［13］Kim K I，Jung K，Kim H J.Face recognition using kernel principal component analysis［J］.IEEE Signal Processing Letters，2002，9（2）：40-42.

［14］Yang Jian，Zhang D.Two-dimensional PCA：A new approach to appearance-based Face representation and recognition［J］. IEEE Trans on PAMI，2004，226（4）：131-137.

［15］Golub G H，Van Loan C F.Matrix Computation［M］.3rd ed. Baltimore，MD：The Johns Hopkins Univ Press，1996.

Discriminant bidirectional two-dimensional local preserving projection and its application in face recognition.

ZHOU Hui，CHEN Xi，LIU Zengli

School of Information Engineering andAutomation，Kunming University of Science and Technology，Kunming 650500，China

Recently，bidirectional two-dimensional Local Preserving Projection（2DLPP）is proposed for face representation and recognition.Compared with two-dimensional Local Preserving Projection（2DLPP），the main idea behind bidirectional 2DLPP is that bidirectional 2DLPP simultaneously considering the row and column directions of images.Bidirectional 2DLPP needs fewer coefficients for image representation than 2DLPP which essentially works in the row direction of images.Furthermore，to enhance the classification ability of bidirectional 2DLPP，a new supervised algorithm is proposed:bidirectional 2DLPP plus LDA，in which images preprocessed by bidirectional 2DLPP are processed by LDA.Theoretical analyses show that bidirectional 2DLPP plus LDA algorithm has advantages over PCA+LDA，2DLPP and bidirectional 2DLPP in computation complexity and memory requirements.The results of face recognition experimental on ORL and Yale face databases also show good performance of the methods with less computation.

discriminant bidirectional two-dimensional local preserving projection；linear discriminant analysis；face recognition；calculation complexity

A

TP391.41

10.3778/j.issn.1002-8331.1311-0027

國家自然科學基金（No.61262040，No.61271007）；云南省應用基礎(chǔ)研究計劃項目（No.KKSY201203062）。

周慧（1989—），女，碩士，主要研究方向為圖像處理、模式識別、壓縮感知等；陳熙（1976—），通訊作者，男，副教授，主要研究領(lǐng)域為生物特征識別與信息安全。E-mail：xcbiometrics@126.com

2013-11-03

2014-01-07

1002-8331（2015）22-0163-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-04-01，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0027.html