周慧，陳熙，劉增力

昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，昆明650500

雙向二維局部保持鑒別投影應(yīng)用于人臉識(shí)別

周慧，陳熙，劉增力

昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，昆明650500

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

雙向二維局部保持映射；線性判別式分析；人臉識(shí)別；計(jì)算復(fù)雜度

1　引言

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

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

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

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

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

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

下面根據(jù)2DLPP的目標(biāo)函數(shù)，通過矩陣運(yùn)算推導(dǎo)2DLPP投影矩陣的計(jì)算方法。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3　試驗(yàn)與分析

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

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

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

圖1　預(yù)處理樣本圖像

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

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

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

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

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

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

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

表1　ORL數(shù)據(jù)庫上的平均識(shí)別率和標(biāo)準(zhǔn)偏差%

表2　Yale數(shù)據(jù)庫上的平均識(shí)別率和標(biāo)準(zhǔn)偏差%

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

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

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

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

4　結(jié)束語

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

［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的人臉識(shí)別［J］.計(jì)算機(jī)應(yīng)用研究，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算法及其在人臉識(shí)別中的應(yīng)用［J］.計(jì)算機(jī)工程與科學(xué)，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

國家自然科學(xué)基金（No.61262040，No.61271007）；云南省應(yīng)用基礎(chǔ)研究計(jì)劃項(xiàng)目（No.KKSY201203062）。

周慧（1989—），女，碩士，主要研究方向?yàn)閳D像處理、模式識(shí)別、壓縮感知等；陳熙（1976—），通訊作者，男，副教授，主要研究領(lǐng)域?yàn)樯锾卣髯R(shí)別與信息安全。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