樣本列信息與自適應(yīng)鄰域圖的局部保持投影*

王海燕，林克正，馬 龍，李 驁

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

樣本列信息與自適應(yīng)鄰域圖的局部保持投影*

王海燕，林克正+，馬 龍，李 驁

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

k近鄰；局部保持投影；自適應(yīng)鄰域；樣本列；結(jié)構(gòu)特征

1 引言

近年來，基于子空間分析的人臉特征提取方法成為人臉識(shí)別領(lǐng)域的研究熱點(diǎn)[1]?；谧涌臻g的人臉特征提取方法，將人臉看作一個(gè)處于高維空間中的整體[2]，選擇線性或者非線性映射，將樣本數(shù)據(jù)從高維空間映射到一個(gè)低維空間內(nèi)，同時(shí)保持?jǐn)?shù)據(jù)在原有高維空間中的內(nèi)在本質(zhì)結(jié)構(gòu)特征[3]。經(jīng)過多年研究，人們已提出了一些線性的人臉特征提取算法，如主分量分析[4]（principal component analysis，PCA）、線性鑒別分析[5]（linear discriminant analysis，LDA）等。很多研究者發(fā)現(xiàn)人臉圖像空間的高維樣本數(shù)據(jù)極可能分布于一個(gè)非線性流形空間上[6-8]，因此非線性的基于子空間分析的流形學(xué)習(xí)方法應(yīng)運(yùn)而生。例如，等距映射算法[8]（isometric mapping，ISOMAP）和局部線性嵌入算法[9]（locally linear embedding，LLE）在Science雜志的發(fā)表，以及隨后被提出的拉普拉斯特征映射[10]（Laplacian eigenmap，LE），均促進(jìn)了流形學(xué)習(xí)方法的研究。但是上述這些算法對(duì)新定義的樣本數(shù)據(jù)的泛化能力不強(qiáng)。據(jù)此，He等人提出了局部保留投影[11]（locality preserving projection，LPP）。

LPP算法繼承了拉普拉斯算法[10]的思想，即在降維過程中需要通過構(gòu)造鄰接圖來保持原高維空間中樣本數(shù)據(jù)之間的結(jié)構(gòu)特征。然而，LPP是一種無監(jiān)督的降維方法，沒有利用樣本的類別信息，對(duì)有監(jiān)督的學(xué)習(xí)問題的識(shí)別效果不是太好。因此，有研究者提出了有監(jiān)督的LPP算法——鑒別局部保持投影（discriminant locality preserving projection，DLPP）[12]。然而這些LPP算法及其變體在構(gòu)建鄰接圖時(shí)采用的是一種全局性的k近鄰構(gòu)圖方法，即假設(shè)每個(gè)樣本的近鄰個(gè)數(shù)是一樣的，這樣很容易造成投影空間中樣本的局部結(jié)構(gòu)失真，同時(shí)參數(shù)k的選擇也十分困難。針對(duì)這個(gè)問題，有人提出了一種局部保持鑒別投影方法[13]，解決了全局參數(shù)k的選擇問題，樣本的局部結(jié)構(gòu)也得到了保持。然而在構(gòu)建鄰接圖時(shí)，采用的是將二維結(jié)構(gòu)的圖片樣本轉(zhuǎn)化成了一維向量形式，樣本的內(nèi)部結(jié)構(gòu)信息利用得不夠，而這些二維結(jié)構(gòu)信息很有可能幫助構(gòu)建更合理的鄰接圖，從而提高識(shí)別率。因此，本文提出一種全新的自適應(yīng)確定鄰域的構(gòu)圖方法——基于樣本的列信息的自適應(yīng)鄰域構(gòu)圖方法（adaptive neighbor and corresponding columns on graph，ANCCG）。在該方法中，將一個(gè)圖像樣本分成若干個(gè)列樣本，每個(gè)列樣本的列近鄰由該列樣本與對(duì)應(yīng)該位置的其他圖像樣本的列樣本的相關(guān)關(guān)聯(lián)度來確定。然后比較兩個(gè)樣本之間的所有列近鄰對(duì)個(gè)數(shù)和總體樣本平均近鄰對(duì)個(gè)數(shù)，來決定兩個(gè)樣本最終的近鄰關(guān)系，然后構(gòu)造樣本的近鄰圖。將該方法與LPP算法結(jié)合形成了ANCCG-LPP算法。為了提高ANCCG-LPP算法的識(shí)別率，通過加入樣本類別信息提出了監(jiān)督的ANCCG-LPP算法（supervised ANCCG-LPP，SANCCG-LPP）。整個(gè)構(gòu)圖過程是一個(gè)自適應(yīng)確定鄰域的過程，消除了參數(shù)k選擇困難問題及選擇不當(dāng)所造成的樣本空間的局部信息缺失或者過于零散問題。另外，由于充分利用了樣本的二維結(jié)構(gòu)列特征，這種方式更好地挖掘樣本之間的近鄰關(guān)系，增強(qiáng)了樣本的局部流形結(jié)構(gòu)的表征能力。

2 局部保持投影算法

LPP算法是一個(gè)非監(jiān)督的基于鄰接圖的流形學(xué)習(xí)算法，它的宗旨是盡可能地保持投影到低維空間后的樣本在原始高維空間的流形結(jié)構(gòu)[14]。因此，LPP算法就是要尋找一組最佳投影矢量集，以使投影后樣本能最大程度地保持原高維空間中頂點(diǎn)間的相似性，以使樣本的局部離散度最小[15]。

設(shè)高維空間中含有N個(gè)樣本的數(shù)據(jù)集合為X={x1,x2…,xN}，LPP的目標(biāo)是找到一個(gè)低維表示Y=ATX。令{V,E,W}表示一個(gè)對(duì)應(yīng)樣本集的鄰接圖，V是一個(gè)樣本點(diǎn)集合；E表示圖中兩個(gè)點(diǎn)之間的邊；W表示帶權(quán)鄰接矩陣，反映了樣本點(diǎn)集合中樣本之間的關(guān)系。

2.1 LPP構(gòu)圖方式

2.1.1 k近鄰法構(gòu)造鄰接矩陣E

k近鄰法：采用歐式距離來衡量樣本空間中數(shù)據(jù)點(diǎn)的遠(yuǎn)近關(guān)系，找出k個(gè)距離樣本xi最近的點(diǎn)組成樣本xi的近鄰集合，集合中所包含的樣本點(diǎn)都是樣本xi的k近鄰；如果節(jié)點(diǎn)xj是xi的k近鄰或者xi是xj的k近鄰，則在節(jié)點(diǎn)xi與xj之間用一條邊相連；最后在構(gòu)造鄰接矩陣時(shí)，有邊相連的標(biāo)記為1，沒有邊相連的標(biāo)記為0。

2.1.2 構(gòu)造權(quán)值矩陣

在確定好樣本的鄰接矩陣之后，僅僅是基本確定了樣本點(diǎn)之間的鄰接情況，還需通過在邊上加權(quán)重來描述鄰接圖中兩個(gè)樣本點(diǎn)之間的邊的重要性。因此為了進(jìn)一步描述樣本點(diǎn)之間的相似程度和彼此間的依賴程度，需要構(gòu)造帶權(quán)鄰接矩陣。LPP算法的權(quán)值矩陣的構(gòu)造方式如下。

熱核法：如果 xi與xj相連接，則權(quán)值wij=exp(-||xi-xj||2/t),否則wij=0。其中，t是核參數(shù)；||xi-xj||表示xi與xj間的歐氏距離；W∈RN×N是一個(gè)對(duì)稱半正定矩陣。

2.2 LPP算法目標(biāo)函數(shù)

為了保持原始高維空間中樣本之間的相似性和局部鄰域結(jié)構(gòu)，需要使樣本的局部離散度最小為目標(biāo)。因此LPP的目標(biāo)函數(shù)如式（1）所示：

其中,W=(wij)是采用熱核法構(gòu)造的權(quán)值鄰接矩陣；D是對(duì)角矩陣，為拉普拉斯矩陣且L=D-W。

為了求得最優(yōu)投影矢量集，將ATXDXTA=I作為限制條件加入到LPP的目標(biāo)函數(shù)中去。這里，I是單位矩陣。因此，最優(yōu)投影矢量集可通過下式求得：

投影矩陣A?可通過式（3）的前d個(gè)最小的特征值集合 λ=[λ1,λ2,…,λd]對(duì)應(yīng)的特征向量得到。

假定求解出來的特征向量為 [α1,α2,…,αd]，則經(jīng)過LPP算法，高維空間樣本的低維表示為Y=ATX。

3 ANCCG-LPP算法

3.1 樣本列信息的自適應(yīng)構(gòu)圖方式

假設(shè)含有N個(gè)訓(xùn)練樣本的圖片集合為I={I1,I2…,IN}，對(duì)于一個(gè)圖像樣本Ii（尺寸為 p×q，這里 p表示樣本圖片的高度，q表示樣本圖片的寬度）。圖片集合I的向量形式的集合可表示為X={x1,x2…,xN},xi∈RD。首先，對(duì)于一個(gè)圖像樣本Ii，將其分成l個(gè)列(l=1,2,…,q)，令表示樣本Ii的第l列，表示對(duì)應(yīng)樣本Ii的第l列的向量形式。對(duì)于所有其他樣本圖片矩陣的第l列，通過一種自適應(yīng)的方式來確定樣本的每個(gè)列樣本的列近鄰和鄰域，最終確定樣本近鄰。分以下幾個(gè)步驟來確定樣本xi的鄰域。

定義1樣本列的平均相關(guān)度可通過式（4）計(jì)算。上式的意義在于：計(jì)算樣本圖片Ii對(duì)應(yīng)第l位置的列樣本與其他樣本中對(duì)應(yīng)l列的列樣本的平均關(guān)聯(lián)度，描述的是兩個(gè)樣本之間對(duì)應(yīng)列樣本之間的相似性。

步驟3確定樣本之間的列近鄰對(duì)的個(gè)數(shù)。

Nij表示兩個(gè)樣本之間列近鄰對(duì)的個(gè)數(shù)，即樣本Ii和Ij之間有多少對(duì)列向量成為列近鄰，初始的時(shí)候Nij=0。Nij代表了樣本之間的相似度。樣本之間列近鄰的確定可通過下面的式子來計(jì)算：

步驟4構(gòu)造鄰接矩陣和權(quán)值矩陣。

其中，Ni·=[Nij](j≠i,j=1,2,…,p)，它反映了樣本 Ii對(duì)于其他所有樣本的相似度。||Ni·||0表示向量Ni·中非零元素的個(gè)數(shù)，實(shí)際計(jì)算的是有多少個(gè)樣本與樣本xi之間的列近鄰個(gè)數(shù)不為0，它是向量Ni·的L0范數(shù)。||Ni·||1表示向量Ni·中所有非零元素絕對(duì)值的累加和，實(shí)際是對(duì)所有樣本與xi樣本之間的列近鄰對(duì)個(gè)數(shù)進(jìn)行求和，它是向量Ni·的L1范數(shù)。因此，上式可解釋為：Ii對(duì)于所有其他樣本的平均相似度為，如果Ii和Ij之間的樣本相似度大于這個(gè)值，那么讓Ij成為Ii的一個(gè)近鄰，即。

樣本的帶權(quán)鄰接矩陣，通過以下公式來計(jì)算：

上述這種基于樣本列信息的自適應(yīng)鄰域構(gòu)圖方法的優(yōu)點(diǎn)在于：（1）首先對(duì)樣本圖片進(jìn)行列劃分，利用劃分后的列圖片信息進(jìn)行自適應(yīng)列鄰域的尋找，這樣確定的樣本相似度，充分利用了原始樣本的二維結(jié)構(gòu)信息。（2）整個(gè)過程不需要參數(shù)的設(shè)置，避免了傳統(tǒng)k近鄰方法的參數(shù)k的選擇所帶來的嵌入空間分散瑣碎和局部空間問題。（3）權(quán)值矩陣的構(gòu)造通過加入一個(gè)反映兩個(gè)樣本相似度比重的參數(shù)，來衡量兩個(gè)邊之間的重要程度，更有助于真實(shí)地反映樣本之間的近鄰關(guān)系。（4）本文的鄰接矩陣和權(quán)值矩陣的非對(duì)稱性的特點(diǎn)，更好地描述了樣本之間的真實(shí)鄰域關(guān)系和樣本的流形結(jié)構(gòu)。

3.2 目標(biāo)函數(shù)及最優(yōu)投影矢量

令 A表示投影矩陣，xi的投影為yi，即yi=ATxi，則在嵌入空間中，希望樣本能保持局部結(jié)構(gòu)不變性，即新投影后的樣本保持其在原始高維空間的鄰域結(jié)構(gòu)關(guān)系，也即使樣本在變換后的低維空間中的局部離散度最小。因此目標(biāo)函數(shù)可表述為：

其中，矩陣D=[dii](i=1,2,…,N)是一個(gè)對(duì)角矩陣，dii=，并 且是對(duì)稱矩陣，是對(duì)角矩陣，?中的每個(gè)行元素是中的對(duì)應(yīng)每一行的所有列元素的累加和，滿足拉普拉斯矩陣的條件。因此，是拉普拉斯矩陣，加入約束條件，因此，本文算法的目標(biāo)函數(shù)為：

投影矩陣A?可通過求解式（11）的前m個(gè)最小的特征值λ對(duì)應(yīng)的特征向量得到。

由于在實(shí)際實(shí)驗(yàn)中，人臉樣本的數(shù)量N往往是有限的，遠(yuǎn)遠(yuǎn)小于樣本數(shù)據(jù)的維數(shù)n，因此經(jīng)常面臨著小樣本問題。這種情況下，為奇異矩陣，這就為投影矢量的求解帶來困難，因此在進(jìn)行本文算法之前，先將高維空間的樣本數(shù)據(jù)通過主成分分析法進(jìn)行降維，之后采用本文所提出的ANCCG-LPP算法進(jìn)行特征提取工作。

3.3 監(jiān)督的ANCCG-LPP

ANCCG-LPP算法在構(gòu)造圖的過程中，一直考慮如何利用好樣本的結(jié)構(gòu)信息來更好地揭示樣本之間的近鄰關(guān)系。為了提高本文算法的識(shí)別性能，通過加入樣本的類別信息，去除不相關(guān)樣本的干擾。因此，由3.2節(jié)ANCCG-LPP的構(gòu)圖方法結(jié)合樣本的類別信息，提出了監(jiān)督的ANCCG-LPP（SANCCG-LPP）。SANCCG-LPP算法的目標(biāo)函數(shù)的形式與ANCCGLPP的相同，投影向量的求解過程也基本相同。在計(jì)算邊權(quán)的時(shí)候考慮了類別信息，式（12）展示了SANCCG-LPP算法的邊權(quán)重矩陣的定義方式：

式中，c(xi)和c(xj)分別表示xi和xj所屬的類標(biāo)簽。在實(shí)際計(jì)算過程中，將式（9）中的邊權(quán)重矩陣公式用式（12）替換，即可得到SANCCG-LPP算法的目標(biāo)函數(shù)公式，通過加入相應(yīng)的約束條件求出對(duì)應(yīng)的特征向量。

3.4 本文算法步驟

根據(jù)前面的推導(dǎo)和分析，以ANCCG-LPP算法為例，具體闡述該算法的具體操作步驟。

步驟1對(duì)原始高維空間中的樣本進(jìn)行PCA降維至k維空間。利用公式計(jì)算樣本的總體散布矩陣，采用奇異值分解的思想，間接求出總體散布矩陣對(duì)應(yīng)的前k個(gè)非零的最大特征值對(duì)應(yīng)的特征向量，作為最優(yōu)投影矢量集，即APCA=[η1,η2,…,ηk]，最終得到原始樣本經(jīng) PCA 降維至低維空間的表示為

步驟2構(gòu)造鄰接圖ANCCG。對(duì)圖片進(jìn)行分塊，分成l列，對(duì)每個(gè)圖片列樣本利用式（4）、（5）得出樣本對(duì)應(yīng)的列近鄰點(diǎn)集；根據(jù)式（6）確定任意兩個(gè)樣本xi和xj之間列近鄰對(duì)個(gè)數(shù)；根據(jù)式（7）計(jì)算鄰接矩陣，確定樣本的近鄰關(guān)系；利用式（8）計(jì)算樣本的帶權(quán)鄰接矩陣WANCCG，同時(shí)計(jì)算帶權(quán)鄰接矩陣的轉(zhuǎn)置(WANCCG)T。

步驟4通過目標(biāo)函數(shù)求最優(yōu)投影矩陣。計(jì)算式（11）的前d個(gè)最小特征值對(duì)應(yīng)的特征向量[α1,α2,…,αd]，得最優(yōu)投影矩陣為 AANCCG=[α1,α2,…,αd]。

步驟6對(duì)測試樣本采用步驟1～步驟4，得到對(duì)應(yīng)測試樣本的最優(yōu)投影，采用最近鄰分類器進(jìn)行分類。

步驟7對(duì)于監(jiān)督的算法SANCCG-LPP，最優(yōu)投影的計(jì)算和求解過程與上述步驟一樣，只需將公式中有的地方換成即可。

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證ANCCG-LPP和SANCCG-LPP算法的有效性，將本文算法和其他所有算法都統(tǒng)一在ORL人臉庫和Extended Yale B人臉庫上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)中將Matlab R2014作為測試平臺(tái)，所有算法的分類器都采用最近鄰分類器，采用的核參數(shù)范圍為{105,106,107}，結(jié)果取最佳識(shí)別率。

ORL人臉庫，由10個(gè)人的400幅圖像組成，分別在不同的面部表情、姿態(tài)和細(xì)節(jié)有輕微變化的情況下拍攝，其中有些圖像是在不同的時(shí)期拍攝的。在實(shí)驗(yàn)時(shí)為計(jì)算方便，統(tǒng)一將圖片進(jìn)行裁切處理，只保留臉部區(qū)域。本文將每幅圖像的大小調(diào)整為32×32像素。

Extended Yale B人臉庫，由28個(gè)人的16 128幅圖像組成，分別在不同姿態(tài)和不同光照條件下拍攝。本實(shí)驗(yàn)中統(tǒng)一對(duì)圖片進(jìn)行裁切，只保留臉部區(qū)域，并將圖片大小設(shè)置為32×32像素。

4.1 結(jié)構(gòu)變化實(shí)驗(yàn)

為了與傳統(tǒng)的k近鄰構(gòu)圖方法形成對(duì)比，比較出本文算法在構(gòu)造圖的過程中樣本空間結(jié)構(gòu)關(guān)系變化。本實(shí)驗(yàn)從ORL人臉庫選取10張照片，其中1、2、4、6、7是屬于同一個(gè)人的照片，3和5是另外一個(gè)人的照片，其他照片是隨機(jī)選取的他人照片，形成一個(gè)實(shí)驗(yàn)數(shù)據(jù)集。在這個(gè)數(shù)據(jù)集上分別采用傳統(tǒng)k近鄰構(gòu)圖方法和本文ANCCG的構(gòu)圖方法。按照本文構(gòu)圖方法得出的樣本相似度矩陣(Nij)如圖1。圖2和圖3分別展示了ANCCG構(gòu)圖方法和k近鄰構(gòu)圖方法的鄰接矩陣。

圖1是在ORL人臉庫的樣本集上用本文方法計(jì)算出來的相似度矩陣。圖中不帶圓圈的數(shù)字表示的是兩個(gè)樣本之間的相似度情況。圖中第2行第4列的值為17，表示的是用本文自適應(yīng)列近鄰法計(jì)算出來的列近鄰數(shù)，即樣本4中有17列成為了樣本2的列近鄰。圖中第4行第2列的值為14，即樣本2中有14列成為了樣本4的列近鄰?？梢?，本文方法的相似度矩陣是不對(duì)稱的，這就更好地反映了樣本之間的結(jié)構(gòu)和關(guān)系。

Fig.1 Similarity matrix ofANCCG method圖1 ANCCG算法的相似度矩陣

Fig.2 Adjacency matrix ofANCCG method圖2 ANCCG算法的鄰接矩陣

圖2、圖3是在實(shí)驗(yàn)數(shù)據(jù)集計(jì)算出來的ANCCG鄰接圖的鄰接矩陣和k鄰接圖的鄰接矩陣。黑色方塊表示的是兩個(gè)樣本是鄰接的。從圖中可以看出，在ANCCG鄰接圖的鄰接矩陣中，鄰接的樣本大致都屬于同一個(gè)人，而在k鄰接矩陣中，這種正確的樣本鄰接關(guān)系沒有得到很好的體現(xiàn)。例如，在ANCCG鄰接圖的鄰接矩陣中的第5行，只有樣本3和5鄰接，事實(shí)上樣本3和5也是來自同一個(gè)人；k鄰接圖的鄰接矩陣中的第5行，樣本1、3、8、10都和樣本5鄰接，而事實(shí)上，只有樣本3是和樣本5來自同一人，樣本1、8和10分別來自不同的人。同時(shí)傳統(tǒng)的k近鄰圖的鄰接矩陣是對(duì)稱的，而ANCCG圖構(gòu)造出來的鄰接圖是不對(duì)稱的，這更好地體現(xiàn)了真實(shí)樣本空間的情況。

Fig.3 Adjacency matrix of k adjacency graph圖3 k鄰接圖方法的鄰接矩陣

4.2 識(shí)別率實(shí)驗(yàn)

為驗(yàn)證本文方法的識(shí)別率情況，各算法的識(shí)別率實(shí)驗(yàn)選擇在ORL、Yale Extended B人臉庫上進(jìn)行，將算法 LPP[11]、LDP[12]、LPDP[13]與本文提出的 ANCCGLPP、SANCCG-LPP算法進(jìn)行對(duì)比分析，其中在傳統(tǒng)k近鄰構(gòu)圖方法中，k近鄰參數(shù)的選擇范圍是{1,2,…,10}。實(shí)驗(yàn)結(jié)果主要從兩方面進(jìn)行分析：（1）分析特征維數(shù)與識(shí)別率的關(guān)系；（2）分析樣本數(shù)與識(shí)別率的關(guān)系。

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

ORL人臉庫中，每人隨機(jī)選擇5張作為訓(xùn)練集，其他的作為測試集，即訓(xùn)練樣本200張圖片，測試樣本200張圖片。Yale Extended B人臉庫中對(duì)于每一個(gè)志愿者分別隨機(jī)選擇50張圖片作為訓(xùn)練樣本，其他的作為測試樣本。實(shí)驗(yàn)中參數(shù)k的取值范圍(k=3,4,5)，每個(gè)實(shí)驗(yàn)重復(fù)20次，最后選取最佳識(shí)別率結(jié)果。圖4、圖5分別顯示了樣本在ORL、Yale Extended B人臉庫上各算法特征維數(shù)與識(shí)別率的關(guān)系。

Fig.4 Recognition rate comparison on ORL face database圖4 ORL人臉庫的識(shí)別率對(duì)比

Fig.5 Recognition rate comparison on Yale Extended B face database圖5 Yale Extended B人臉庫的識(shí)別率對(duì)比

由圖4、圖5可知，在ORL人臉庫和Yale Extended B人臉庫中，隨著特征維數(shù)的增加，本文ANCCG-LPP算法的識(shí)別率都比LPP算法的識(shí)別率有顯著提升。然而由于ANCCG-LPP算法沒有利用樣本的類別信息，在ORL人臉庫的實(shí)驗(yàn)結(jié)果顯示，ANCCG-LPP算法的識(shí)別率要比利用樣本類別信息的DLPP、LPDP算法略低。在Yale Extended B人臉庫的實(shí)驗(yàn)結(jié)果顯示，在特征維數(shù)大于160以后，ANCCG-LPP算法的識(shí)別率高于DLPP。這可能是因?yàn)殡S著特征維數(shù)的增加，樣本內(nèi)部結(jié)構(gòu)信息的影響逐漸增加。相比于LPP算法的識(shí)別率，本文算法在Yale Extended B人臉庫的識(shí)別率比在ORL人臉庫上的識(shí)別率提高得較為明顯，而由于Yale Extended B人臉庫的光照、姿態(tài)條件更加復(fù)雜，可見本文算法在人臉圖像光照、姿態(tài)、表情比較復(fù)雜的情況下的識(shí)別率比較理想。本文提出的SANCCG-LPP算法不僅充分利用了樣本的二維結(jié)構(gòu)的列樣本特征，同時(shí)加入了樣本的類別信息，因此它的識(shí)別率是最高的。

4.2.2 樣本數(shù)與識(shí)別率的關(guān)系

在訓(xùn)練樣本數(shù)與識(shí)別率關(guān)系的實(shí)驗(yàn)中，ORL人臉庫上的實(shí)驗(yàn)選擇了40個(gè)志愿者，每個(gè)人分別取2、3、4、5張圖片作為訓(xùn)練樣本集，其他的為測試樣本集，即組成了4個(gè)訓(xùn)練樣本集/測試樣本集組合對(duì)80/320,120/280,160/240,200/200；Yale Extended B人臉庫中，隨機(jī)選擇包含了不同姿態(tài)、光照和表情的16個(gè)志愿者的人臉圖像，每個(gè)人分別隨機(jī)選取20、30、40、50幅作為訓(xùn)練樣本，對(duì)分別由320幅、480幅、640幅、900幅圖像組成的訓(xùn)練樣本集采用相同的測試集合，對(duì)應(yīng)訓(xùn)練集中的每個(gè)志愿者選擇50幅圖片共800幅圖像作為測試樣本集。為了考查幾種算法的識(shí)別率大小及其識(shí)別率波動(dòng)范圍情況，在兩個(gè)人臉庫中所選的訓(xùn)練樣本/測試樣本組都進(jìn)行10次重復(fù)實(shí)驗(yàn)，最后結(jié)果取平均識(shí)別率。對(duì)應(yīng)ORL人臉庫和Yale Extended B人臉庫中不同算法的識(shí)別率與訓(xùn)練樣本數(shù)的關(guān)系情況如表1和表2所示。表1和表2中的訓(xùn)練樣本數(shù)是選取一個(gè)志愿者的不同數(shù)量的圖像作為訓(xùn)練樣本。

由表1可知，不同的訓(xùn)練樣本數(shù)情況下，各算法的識(shí)別率都是隨著訓(xùn)練樣本數(shù)的增加而提高的，LDP、LPDP、本文算法都較LPP的識(shí)別率有很大提高。隨著訓(xùn)練樣本數(shù)的增加，本文算法的識(shí)別率提高的幅度最大，樣本數(shù)的增多，為本文算法在通過列信息特征確定樣本間的相似程度的過程提供較大的參考價(jià)值，使得本文算法能充分發(fā)揮樣本二維結(jié)構(gòu)中列樣本信息的優(yōu)勢。類別信息的加入，使得算法識(shí)別率進(jìn)一步提升。同時(shí)各算法在進(jìn)行重復(fù)實(shí)驗(yàn)時(shí)，識(shí)別率在一定范圍內(nèi)變化。

相比于ORL人臉庫上的實(shí)驗(yàn)結(jié)果，由表2中各算法識(shí)別率后面的數(shù)字可知，在Yale Extended B人臉庫中進(jìn)行實(shí)驗(yàn)的所有算法的識(shí)別率的波動(dòng)范圍較大，這是因?yàn)閅ale Extended B人臉庫的人臉圖像的表情、姿態(tài)、光照更為復(fù)雜，導(dǎo)致識(shí)別率上下波動(dòng)更加明顯。本文算法較其他算法的波動(dòng)幅度小，說明算法更加穩(wěn)定。表1和表2的結(jié)果都表明訓(xùn)練樣本數(shù)量對(duì)識(shí)別率的重要影響。在ORL人臉庫中的實(shí)驗(yàn)結(jié)果顯示ANCCG-LPP算法的各個(gè)訓(xùn)練樣本下的識(shí)別率都要略低于DLPP、LPDP這兩種利用了樣本鑒別信息的算法；而在Yale Extended B人臉庫的結(jié)果則表明ANCCG-LPP算法的識(shí)別率要高于DLPP，但仍比LPDP低。這說明ANCCG構(gòu)圖方式能對(duì)復(fù)雜情況如姿態(tài)、表情、光照的人臉圖像進(jìn)行更有效的投射。ORL人臉庫中的圖像情況相對(duì)簡單，類別信息發(fā)揮了重要的作用。

Table 1 Recognition rate comparison on ORL face database with different methods表1 在ORL人臉庫中不同算法的識(shí)別率對(duì)比

Table 2 Recognition rate comparison on Yale Extended B face database with different methods表2 在Yale Extended B人臉庫中不同算法的識(shí)別率對(duì)比

5 結(jié)束語

本文充分考慮傳統(tǒng)k近鄰構(gòu)圖方法中全局k值的選擇方式所帶來的空間結(jié)構(gòu)零散或者損失空間結(jié)構(gòu)信息等問題，結(jié)合人臉圖像樣本的內(nèi)部結(jié)構(gòu)信息，提出了根據(jù)樣本的內(nèi)部結(jié)構(gòu)信息來自適應(yīng)確定鄰域的方法。一方面充分利用了人臉圖像的原始結(jié)構(gòu)信息，更好地反映樣本之間的近鄰關(guān)系，構(gòu)造一個(gè)樣本局部流形結(jié)構(gòu)更加緊湊的嵌入空間，為分類打下基礎(chǔ)；另一方面，基于樣本的二維結(jié)構(gòu)信息來自適應(yīng)地獲取樣本鄰域的方法，解決了參數(shù)k的選擇困難問題，提高了樣本空間的信息表征能力，更好地描述了樣本空間的數(shù)據(jù)分布。最后還加入了樣本類別信息，進(jìn)一步提高了算法的識(shí)別率。實(shí)驗(yàn)結(jié)果表明：在人臉圖像情況復(fù)雜時(shí)，ANCCG-LPP算法能最大程度地發(fā)揮樣本內(nèi)部結(jié)構(gòu)列信息的作用來自適應(yīng)地構(gòu)造樣本局部流形空間結(jié)構(gòu)。

[1]Gu Xiaohua,Gong Weiguo,Yang Liping.Supervised graghoptimized locality preserving projections[J].Optics and Precision Engineering,2011,19(3):672-680.

[2]Deng Sujuan,Zhou Xinyi,Tang Nianqing.Research and design of face recognition system combined with subspace projection and manifold learning[J].Journal of Chengdu Normal University,2015,31(3):109-112.

[3]Wang Yongmao,Li Geng.Local discriminant projection algorithm based on complete adaptive neighborhood graph embedding[J].Journal of Data Acquisition and Processing,2015,30(6):1271-1278.

[4]Turk M,Pentland A.Eigenfaces for recognition[J].Journal of Cognitive Neuroscience,1991,3(1):71-86.

[5]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.

[6]Cui Peng,Zhang Rubo.A semi-supervised coefficient selection method for face recognition[J].Journal of Harbin Engineering University,2012,33(7):855-861.

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

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

[9]Roweis S T,Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.

[10]Belkin M,Niyogi P.Laplacian eigenmaps and spectral techniques for embedding and clustering[J].Advances in Neural Information Processing Systems,2002,14(6):585-591.

[11]He Xiaofei,Yan Shuicheng,Hu Yuxiao,et al.Face recognition using Laplacian faces[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(3):328-340.

[12]Yu Weiwei,Teng Xiaolong,Liu Chongqing.Face recognition using discriminant locality preserving projections[J].Image and Vision Computing,2006,24(3):239-248.

[13]Zhao Zhenhua,Hao Xiaohong.Linear locality preserving and discriminating projection for face recognition[J].Journal of Electronics&Information Technology,2013,35(2):463-467.

[14]Li Bin.Research of feature extraction method based on GIST feature and manifold learning[D].Changchun:Jilin University,2015.

[15]Huang Pu,Tang Zhenmin.Parameter-free locality preserving projections and face recognition[J].Pattern Recognition and Artificial Intelligence,2013,26(9):865-871.

附中文參考文獻(xiàn)：

[1]辜小花,龔衛(wèi)國,楊利平.有監(jiān)督圖優(yōu)化保局投影[J].光學(xué)精密工程,2011,19(3):672-680.

[2]鄧素娟,周鑫燚,唐年慶.結(jié)合子空間投影和流形學(xué)習(xí)的人臉識(shí)別系統(tǒng)研發(fā)[J].成都師范學(xué)院學(xué)報(bào),2015,31(3):109-112.

[3]王永茂,李賡.完備自適應(yīng)近鄰圖嵌入的局部鑒別投影算法[J].數(shù)據(jù)采集與處理,2015,30(6):1271-1278.

[6]崔鵬,張汝波.半監(jiān)督系數(shù)選擇法的人臉識(shí)別[J].哈爾濱工程大學(xué)學(xué)報(bào),2012,33(7):855-861.

[13]趙振華,郝曉弘.局部保持鑒別投影及其在人臉識(shí)別中的應(yīng)用[J].電子與信息學(xué)報(bào),2013,35(2):463-467.

[14]李斌.基于GIST特征和流形學(xué)習(xí)的特征抽取方法的研究[D].長春:吉林大學(xué),2015.

[15]黃璞,唐振民.無參數(shù)局部保持投影及人臉識(shí)別[J].模式識(shí)別與人工智能,2013,26(9):865-871.

WANG Haiyan was born in 1988.She is an M.S.candidate at Harbin University of Science and technology.Her research interests include image processing and pattern recognition,etc.

王海燕（1988—），女，黑龍江齊齊哈爾人，哈爾濱理工大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閳D像處理，模式識(shí)別等。

林克正（1962—)，男，山東蓬萊人，2001年于哈爾濱工程大學(xué)控制理論與控制工程專業(yè)獲得博士學(xué)位，現(xiàn)為哈爾濱理工大學(xué)教授、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)閳D像處理，機(jī)器視覺，模式識(shí)別等。發(fā)表學(xué)術(shù)論文70余篇,主持完成了黑龍江省教育廳科研基金項(xiàng)目，承擔(dān)過多項(xiàng)國家科技攻關(guān)項(xiàng)目。

Muhammad Rafique was born in 1989.He is an M.S.candidate at Harbin University of Science and Technology(international student).His research interests include image processing and pattern recognition,etc.

馬龍（1989—），男，巴基斯坦人，哈爾濱理工大學(xué)碩士研究生（留學(xué)生），主要研究領(lǐng)域?yàn)閳D像處理，模式識(shí)別等。

LI Ao was born in 1986.He received the Ph.D.degree in communication and information systems from Harbin Engineering University in 2014.Now he is a lecturer at Harbin University of Science and Technology.His research interests include sparse representation,image restoration and computer vision,etc.

李驁（1986—），男，黑龍江哈爾濱人，2014年于哈爾濱工程大學(xué)通信與信息系統(tǒng)專業(yè)獲得博士學(xué)位，現(xiàn)為哈爾濱理工大學(xué)講師，主要研究領(lǐng)域?yàn)橄∈璞硎荆瑘D像復(fù)原，計(jì)算機(jī)視覺等。主持國家自然科學(xué)基金1項(xiàng)、黑龍江省自然科學(xué)基金1項(xiàng)，參與船舶工業(yè)國防科技預(yù)研項(xiàng)目1項(xiàng)，發(fā)表學(xué)術(shù)論文10余篇，授權(quán)發(fā)明專利1項(xiàng)。

Local Preserving Projection Based on Sample Column Information and Adaptive Neighborhood Graph*

WANG Haiyan,LIN Kezheng+,Muhammad Rafique,LIAo
School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China

Through introducing the column information of sample,this paper proposes an improved locality preserving projection(LPP)algorithm named adaptive neighbor and corresponding columns of the samples based graph construction method on LPP(ANCCG-LPP)to overcome the defects which parameter k is difficultly selected in traditional k-nearest neighbor graph and the original structure of the image sample is easily ignored by one dimensional vector of the sample for LPP.In the proposed algorithm,corresponding column neighbors of column samples are determined adaptively by the column information of the samples,and then the neighbors of the sample are determined adaptively by the number of coupled column neighbors between two samples.Finally,the optimal projection vectors are solved by redefining the weight matrix to optimize the objective function.Supervised ANCCG-LPP algorithm based on ANCCG-LPP is put forward through adding class information of the samples.The simulation experiments on ORL,Yale Extended B face databases validate the effectiveness of theANCCG-LPP and SANCCG-LPP.

k-nearest neighbor;locality preserving projection;adaptive neighborhood;sample column;structural characteristics

the Ph.D.degree in control theory and control engineering from Harbin Engineering University in 2001.Now he is a professor and M.S.supervisor at Harbin University of Science and Technology.His research interests include image processing,machine vision and pattern recognition,etc.

2016-06, Accepted 2016-10.

A

TP391.4

+Corresponding author:E-mail:link@hrbust.edu.cn

WANG Haiyan,LIN Kezheng,Muhammad Rafique,et al.Local preserving projection based on sample column information and adaptive neighborhood graph.Journal of Frontiers of Computer Science and Technology,2017,11(9)：1474-1483.

10.3778/j.issn.1673-9418.1606030

*The National Natural Science Foundation of China under Grant No.61501147(國家自然科學(xué)基金);the Natural Science Foundation of Heilongjiang Province under Grant No.F2015040(黑龍江省自然科學(xué)基金).

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2016-10-18, http://www.cnki.net/kcms/detail/11.5602.TP.20161018.1622.006.html

摘 要：針對(duì)局部保持投影（locality preserving projection，LPP）算法在傳統(tǒng)k近鄰構(gòu)圖過程中出現(xiàn)的參數(shù)k選擇困難問題和樣本的一維向量容易忽略樣本的原始結(jié)構(gòu)特征問題，引入樣本的列信息思想，提出了一種基于樣本對(duì)應(yīng)列信息的自適應(yīng)鄰域構(gòu)圖的局部保持投影算法（adaptive neighbor and corresponding columns based graph construction on LPP,ANCCG-LPP）。該算法根據(jù)樣本間的列信息自適應(yīng)地得出所有樣本列的列近鄰，然后根據(jù)樣本間成對(duì)的列近鄰個(gè)數(shù)自適應(yīng)地確定樣本的鄰域；最后通過重新定義權(quán)值矩陣來優(yōu)化目標(biāo)函數(shù)進(jìn)行最優(yōu)投影向量集的求解。在ANCCG-LPP算法的基礎(chǔ)上，通過加入樣本的類別信息，提出了有監(jiān)督的ANCCGLPP算法。在ORL、Yale Extended B人臉庫上的仿真實(shí)驗(yàn)驗(yàn)證了該算法的有效性。