基于類別多核局部判別嵌入的人臉識(shí)別

王永茂，徐正光，吳金霞

(1.北京科技大學(xué)自動(dòng)化學(xué)院，北京100083;2.河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南焦作454003)

0 引言

為了緩解人臉識(shí)別中存在的維數(shù)災(zāi)難問題，需要進(jìn)行有效的降維.主元成分分析(PCA，Principle Component Analysis)［1］是最流行的降維方法之一，但其本質(zhì)是線性的，不能很好地描述人臉圖像中諸如光照、表情和姿態(tài)等復(fù)雜的非線性變化.基于流形的降維方法是近年來興起的一類降維方法，其中代表性的算法有等距映射(ISOMAP)［2］、局部線性嵌入(LLE，Locally Linear Embedding)［3］和拉普拉斯映射(LE，Laplacian Eigenmap)［4］，它們能夠很好學(xué)習(xí)到非線性流形結(jié)構(gòu)，但是基于流形的降維方法的一大缺陷是不能直接映射新的測(cè)試點(diǎn)，為了解決這一問題，許多學(xué)者先后提出局部保形投影(LPP，Locality Preserving Projection)［5］、近鄰保形嵌入(NPE，Neighborhood Preserving Embedding)［6］等線性降維算法，它們分別為L(zhǎng)E算法與LLE算法的線性逼近.

上述提到的線性或非線性降維方法的設(shè)計(jì)初衷并不是應(yīng)用于分類，而Fisher判別分析(FDA，F(xiàn)isher Discriminant Anaysis)［7］得到的最佳映射子空間具有較好的鑒別能力，因此對(duì)于分類任務(wù)能夠起到較好的效果.為了保持?jǐn)?shù)據(jù)的流形結(jié)構(gòu)，研究者提出了一類既考慮類別信息又考慮鄰域結(jié)構(gòu)信息的降維方法［8－13］，這些降維方法既具有較好的鑒別能力又能很好保持?jǐn)?shù)據(jù)的近鄰特性.局部判別分析(LDE，Local Discrimiant Embedding)［8］是其典型代表.然而，LDE本質(zhì)上仍然是線性方法，不能夠很好揭示數(shù)據(jù)復(fù)雜的非線性結(jié)構(gòu)，許多學(xué)者提出利用非線性核技巧在維數(shù)很高的空間內(nèi)求解子空間的核局部判別嵌入(KLDE，Kernel Local Discriminant Embedding)降維方法［8，14］.該方法將輸入的數(shù)據(jù)空間轉(zhuǎn)換到一個(gè)高維空間，其映射關(guān)系在全局范圍內(nèi)定義，在映射的過程中改變了數(shù)據(jù)分布，不能夠很好保持?jǐn)?shù)據(jù)的幾何結(jié)構(gòu).為解決這一問題，筆者提出一種基于類別多核局部判別嵌入算法(LMKLDE，Label Mulitple Kernel Local Discrimiant Embedding)，首先針對(duì)給定樣本數(shù)據(jù)的類別信息，定義類別局部核函數(shù)，形成多核，接著將不同的局部核函數(shù)進(jìn)行線性組合，作為最終的核函數(shù)引入到LDE算法中，得到了LMKLDE算法.

1 LDE

假設(shè)有一數(shù)據(jù)集 X={(x1，l1)，(x2，l2)，…，(xN，lN)}，xi是一個(gè)D維向量，N為樣本的個(gè)數(shù)，li∈ L={1，2，…，m} 為xi的類別標(biāo)簽，L是類別標(biāo)簽集，m為類別總數(shù).LDE算法的目的就是尋找一投影矩陣V，得到X的低維嵌入Y={y1，y2，…，yN}，使得Y=VTX，yi是一個(gè)d維向量，且d＜D.

根據(jù)圖框架理論［9］，LDE算法構(gòu)造兩個(gè)近鄰圖：(1)描述類內(nèi)緊密性的近鄰圖Gw(固有圖)，圖中每個(gè)樣本只與同類別的k1個(gè)近鄰點(diǎn)相連，Nw(xi)表示樣本xi同類別的k1個(gè)近鄰點(diǎn);2)描述類間分離性的近鄰圖Gp(懲罰圖)：圖中每個(gè)樣本只與不同類別的k2個(gè)近鄰相連，Np(xi)表示樣本xi不同類別的k2個(gè)近鄰點(diǎn).

計(jì)算近鄰圖Gw和Gp的權(quán)值矩陣Sw和Sp，其值為

為了保證xi和xj在相距很近且具有相同類別標(biāo)記時(shí)，其低維嵌入yi和yj相距也很近;xi和xj在相距很近但具有不同類別標(biāo)記時(shí)，yi和yj相距很遠(yuǎn).LDE算法的目標(biāo)函數(shù)定義為

經(jīng)過推導(dǎo)，LDE目標(biāo)函數(shù)變?yōu)?/p>

其中Lw=Dw－Sw和Lp=Dp－Sp為拉普拉斯矩陣，Dw和Dp為對(duì)角矩陣，其值為權(quán)值矩陣Sw和Sp每一列(或行)數(shù)據(jù)之和，即

式(5)進(jìn)行廣義特征分解的前d個(gè)最大特征值對(duì)應(yīng)的特征向量組成了LDE的基向量V=［v1，v2，…，vd］.

2 類別多核函數(shù)

核函數(shù)提供了一種數(shù)據(jù)相似度度量方法，對(duì)于兩個(gè)樣本x和z，Φ(x)和Φ(z)是樣本x和z的高維非線性映射，則Φ(x)和Φ(z)的點(diǎn)積可用x和z的核函數(shù)表示，即

下面給出類別多核函數(shù)的構(gòu)造.

對(duì)于樣本x，求其到類別c中心的矢量xc，其值為

定義基于每一個(gè)類別的局部核，即

將不同的局部核函數(shù)進(jìn)行線性組合，得到最終的核函數(shù)，即

3 LMKLDE

將類別多核函數(shù)應(yīng)用到LDE算法，以處理非線性結(jié)構(gòu)數(shù)據(jù)，得到LMKLDE算法.

3.1 LMKLDE的求解過程

假設(shè)Φ為一非線性映射函數(shù)，將樣本X映射到希爾伯特空間內(nèi)［15］，得到 Φ(X)= ［Φ(x1)，Φ(x2)，…，Φ(xN)］.于是，希爾伯特空間中的廣義特征問題表示如下：

由于上式的特征向量 w為 Φ(x1)，Φ(x2)，…，Φ(xN)的線性組合，故w可表示如下：

經(jīng)過簡(jiǎn)單的變換，式(11)變?yōu)?/p>

其中：K為核矩陣，其值由式(10)定義的類別多核函數(shù)決定.求解式(13)對(duì)應(yīng)的廣義特征向量，得到d個(gè)特征向量 α1，α2，…，αd，分別對(duì)應(yīng)于d 個(gè)最大的特征值.那么對(duì)于一個(gè)測(cè)試樣本x，它在特征向量wk上的投影為

3.2 LMKLDE的時(shí)間復(fù)雜度分析

KLDE算法的時(shí)間復(fù)雜度主要有以下3個(gè)方面決定：(1)近鄰點(diǎn)的搜索;(2)核函數(shù)的構(gòu)造;(3)廣義特征向量問題的求解.

近鄰點(diǎn)的搜索的時(shí)間復(fù)雜度為O((D+k1+k2)N2)，DN2代表計(jì)算任意兩個(gè)樣本距離的時(shí)間復(fù)雜度，k1N2代表尋找同類別的k1個(gè)近鄰點(diǎn)的時(shí)間復(fù)雜度，k2N2代表尋找不同類別的k2個(gè)近鄰點(diǎn)的時(shí)間復(fù)雜度.核函數(shù)的構(gòu)造的時(shí)間復(fù)雜度為O(DN2).求解廣義特征向量的時(shí)間復(fù)雜度為O(N3).

LMKLDE與KLDE區(qū)別僅在于核函數(shù)的構(gòu)造，核函數(shù)構(gòu)造的時(shí)間復(fù)雜度為O(mDn2)，大于KLDE的核函數(shù)構(gòu)造的時(shí)間復(fù)雜度O(Dn2)，因此，LMKLDE的執(zhí)行時(shí)間要比KLDE長(zhǎng)，當(dāng)m?D時(shí)，其執(zhí)行時(shí)間差別不大.

4 實(shí)驗(yàn)設(shè)計(jì)和結(jié)果

為了驗(yàn)證算法的有效性，分別在ORL和Yale人臉庫上進(jìn)行實(shí)驗(yàn)對(duì)比.實(shí)驗(yàn)中比較了LMKLDE與 PCA，F(xiàn)DA，LDE以及 KLDE的識(shí)別率，在KLDE，LMKLDE方法中，核函數(shù)采用線性核函數(shù)，k(x，z)=(1+xTz)d，d=1; 以及高斯核函數(shù)，k(x，z)=exp(－ x － z2/2σ2)，σ =1，對(duì)于所有方法，均采用歐式距離度量下的最近鄰分類器完成最終分類.

ORL人臉庫是由英國劍橋大學(xué)建立，共有40個(gè)人，每人10張圖像，共有400張人臉圖像，圖像的面部表情和面部細(xì)節(jié)有著不同程度的變化，人臉姿勢(shì)也有相當(dāng)?shù)某潭茸兓?，比較充分地反映了同一人不同人臉圖像的變化和差異.圖1是ORL人臉庫的部分樣本.Yale人臉庫由美國耶魯大學(xué)建立，包含15個(gè)人，每人11張圖像，共有165張人臉圖像，主要包括光照條件的變化、表情的變化及有無眼睛修飾等.圖2是Yale人臉庫的部分樣本.實(shí)驗(yàn)使用的人臉圖像經(jīng)剪切后大小均為32×32，然后將兩個(gè)人臉庫中的每個(gè)圖像進(jìn)行標(biāo)準(zhǔn)化.

在對(duì)ORL和Yale人臉庫進(jìn)行實(shí)驗(yàn)時(shí)，從每類人臉圖像中隨機(jī)選取i(i=2，3，4)張圖像作為訓(xùn)練集，剩余的圖像作為測(cè)試集，重復(fù)進(jìn)行10次，共獲得10對(duì)不同的訓(xùn)練集和測(cè)試集，分別以2Train，3Train和4Train表示，最后取平均值作為識(shí)別結(jié)果.表1和表2給出了ORL和Yale人臉庫的平均最高識(shí)別率及其對(duì)應(yīng)的子空間的維數(shù)，其中(L)為采用線性核函數(shù)的識(shí)別結(jié)果，(G)為采用高斯核函數(shù)的識(shí)別結(jié)果.

表1 ORL人臉數(shù)據(jù)庫上的實(shí)驗(yàn)結(jié)果比較Tab.1 The experiment result on ORL database

表2 Yale人臉數(shù)據(jù)庫上的實(shí)驗(yàn)結(jié)果比較Tab.2 The experiment result on Yale database

從上面的實(shí)驗(yàn)可以看出：

(1)FDA考慮樣本的類別信息，識(shí)別率高于PCA方法;

(2)LDE既考慮樣本的類別信息又考慮樣本之間的近鄰關(guān)系，對(duì)于非線性流形結(jié)構(gòu)有一定的保持作用，其識(shí)別率要高于FDA;

(3)KLDE以及LMKLDE在核空間提取圖像的高階非線性信息，其識(shí)別率高于其他方法，但KLDE方法的核函數(shù)在全局范圍內(nèi)定義，而LMKLDE方法的核函數(shù)是類別局部核函數(shù)的線性組合，考慮了樣本的幾何分布，因此LMKLDE的識(shí)別率高于KLDE.

5 結(jié)論

筆者在LDE算法的基礎(chǔ)上提出了一種基于類別多核局部判別嵌入的人臉識(shí)別算法.算法通過將不同類別的局部核函數(shù)進(jìn)行線性組合所得到最終的核函數(shù)引入到LDE算法中，得到LMKLDE算法，能夠較好的保持?jǐn)?shù)據(jù)的幾何結(jié)構(gòu).在ORL和Yale人臉庫上的實(shí)驗(yàn)結(jié)果表明，在姿態(tài)、光照和表情等變化的情況下，該算法都具有良好的性能.

［1］TURK M，PENTLAND A.Eigenfaces for recognition［J］.Journal of Cognitive Neuroscience，1991，3(1)：72－86.

［2］TENENBAUM J B，SILVA V，LANGFORD J C.A global geometric framework for nonlinear dimensionality reduction［J］.Science，2000，290(12)：2319 －2323.

［3］ROWEIS S T，SAUL L K.Nonlinear dimensionality reduction by locally linear embedding ［J］.Science，2000，290(12)：2323 －2326.

［4］BELKIN M，NIYOGI P.Laplacian eigenmaps for dimensionality reduction and data representation ［J］.Neural Computation，2003，15(6)：1373 －1396.

［5］HE Xiao-fei，YAN Shui-cheng.Face recognition using laplacianfaces［J］.IEEE Transaction on Pattern Analysis and Machine Intelligence，2005，27(3)：328 －340.

［6］HE Xiao-fei，CAI Deng，YAN Shui-cheng，et al.Neighborhood preserving embedding［C］//Tenth IEEE International Conference on Computer Vision.Piscataway：Institute of Electrical and Electronics Engineers Inc.，2005：1208 －1213.

［7］BELHUMEUR P N，HESPANHA J P，KRIEGMAN D J.Eigenfaces vs.fisherfaces：Recognition using class specific linear projection［J］.IEEE Transaction on Pattern Analysis and Machine Intelligence，1997，19(7)：711 －720.

［8］CHEN HW，CHANG HW，LIU TL.Local Discriminant Embedding and Its Variants［C］//2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Pis cataway：Institute of Electrical and Electronics Engineers computer Society，2005：816－853.

［9］YAN Shui-cheng，XU Dang，ZHANG Ben-yu，et al.Graph Embedding and Extensions：A general framework for dimensionality reduction［J］.IEEE transaction on Pattern Analysis and Machine Intelligence，2007，29(1)：40 －51.

［10］王超，王士同.最大間距準(zhǔn)則與局部保持結(jié)合的特征提取方法［J］.計(jì)算機(jī)工程，2009，35(14)：209－211.

［11］張召，業(yè)寧，業(yè)巧林.局部保持多投影向量Fisher判別分析算法［J］.計(jì)算機(jī)學(xué)報(bào)，2010，33(5)：385－396.

［12］魏萊，王守覺，徐菲菲，等.近鄰邊界Fisher判別分析［J］.電子與信息學(xué)報(bào)，2009，31(3)：509 －513.

［13］CAI Hong-ping，KRYSTIAN M，JIRI M.Learning linear discrimiant projection for dimensionality reduction of image descriptors［J］.IEEE Transaction on Pattern Analysis and Machine Intelligence，2011，33(2)：338 －351.

［14］王慶軍，張汝波，潘海為.基于核正交局部判別嵌入的人臉識(shí)別［J］.光電子激光，2010，21(9)：1386－1389.

［15］申中華，潘永惠，王士同.有監(jiān)督的局部保留投影降維算法［J］.模式識(shí)別與人工智能，2008，21(2)：233 －239.