完備自適應(yīng)近鄰圖嵌入的局部鑒別投影算法*

王永茂 李 賡

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,焦作,454000)

?

完備自適應(yīng)近鄰圖嵌入的局部鑒別投影算法*

王永茂 李 賡

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,焦作,454000)

針對(duì)基于自適應(yīng)近鄰圖嵌入的局部鑒別投影算法(Neighborhood graph embedding based local adaptive discriminant analysis, LADP)僅僅利用局部類內(nèi)離差矩陣主元空間的鑒別信息而丟失了其零空間內(nèi)大量鑒別信息的不足，結(jié)合全空間的基本思想提出了完備的基于自適應(yīng)近鄰圖嵌入的局部鑒別投影算法(Complete LADP,CLADP)。在局部類內(nèi)離差矩陣的零空間內(nèi)，通過(guò)最大化局部類間離差矩陣提取不規(guī)則鑒別特征，在局部類間離差矩陣的主元空間內(nèi)，通過(guò)最大化局部類間離差矩陣的同時(shí)最小化局部類內(nèi)離差矩陣提取規(guī)則鑒別特征，最后將不規(guī)則鑒別特征和規(guī)則鑒別特征串聯(lián)形成CLADP特征。在ORL，Yale以及PIE人臉庫(kù)上的人臉識(shí)別實(shí)驗(yàn)結(jié)果證明了CLADP的有效性。

人臉識(shí)別;自適應(yīng)近鄰圖；局部鑒別分析；完備特征；降維

引 言

在諸如人臉識(shí)別的應(yīng)用領(lǐng)域中經(jīng)常會(huì)遇到高維數(shù)據(jù)，降維是重要的預(yù)處理手段之一。降維的過(guò)程就是將高維數(shù)據(jù)投影到一個(gè)低維空間內(nèi),同時(shí)保持高維數(shù)據(jù)內(nèi)在的本質(zhì)特征。根據(jù)投影變換是否為線性變換，降維方法可以分為線性方法和非線性方法。主元成分分析(Principle component analysis，PCA)與線性鑒別分析(Linear discriminant analysis，LDA)[1]是兩種最為經(jīng)典的線性降維方法。相比于線性降維方法，非線性降維方法可以很好地處理復(fù)雜的非線性分布的數(shù)據(jù)，非線性降維方法一般分為兩大類：基于流形學(xué)習(xí)的降維方法[2]和基于核空間的降維方法[3]。經(jīng)典的基于流形學(xué)習(xí)的降維方法包括：等距映射、局部線性嵌入(Locally linear embedding，LLE)以及拉普拉斯映射(Laplacian eigenmap，LE)，但這些算法的最大缺陷就是不能映射新的測(cè)試樣本，為此，局部Fisher鑒別分析(Local fisher discriminant analysis,LFDA)[4]、局部保形投影(Locality preserving projection，LPP)[5]以及近鄰保持嵌入(Neighborhood preserving projection，簡(jiǎn)稱NPE)[6]等線性的基于流形學(xué)習(xí)的降維方法相繼提出。另外基于核空間的降維方法也是近年來(lái)的一個(gè)重要研究方向，傳統(tǒng)的線性降維方法可以利用核技巧得到其相應(yīng)的非線性降維方法，如核主元成分分析(Kernel PCA，KPCA)和核線性鑒別分析(Kernel LDA，KDA)等。為了更好地揭示各種降維方法之間的共同特征，Yan等和提出了統(tǒng)一的圖嵌入框架理論[7]，在降維的過(guò)程中，需要構(gòu)造兩類圖，一個(gè)是固有圖，用于描述在降維過(guò)程需要保持的幾何特性；一個(gè)是懲罰圖，用于描述在降維過(guò)程中需要避免的幾何特性，現(xiàn)存的大部分降維方法都可以用圖嵌入框架來(lái)描述，其差別僅僅表現(xiàn)在圖構(gòu)造的不同。

在降維的過(guò)程中，為了保持高維數(shù)據(jù)的流形結(jié)構(gòu)，往往要根據(jù)數(shù)據(jù)的近鄰點(diǎn)來(lái)構(gòu)造固有圖和懲罰圖，然而近鄰點(diǎn)個(gè)數(shù)的選擇對(duì)于最優(yōu)的投影變換影響較大。作者在文獻(xiàn)[8]中根據(jù)樣本的分布特性以及樣本間的相似度自適應(yīng)計(jì)算類內(nèi)和類間的近鄰點(diǎn)，提出了基于自適應(yīng)近鄰圖嵌入的局部鑒別分析算法(Neighborhood graph embedding based local adaptive discriminant analysis，LADP)。然而，同其他降維方法一樣，LADP算法也是基于向量的降維方法，在進(jìn)行降維前需要將數(shù)據(jù)轉(zhuǎn)換為一維向量形式，這種轉(zhuǎn)換大大增加了數(shù)據(jù)的維數(shù)，由于用于訓(xùn)練的數(shù)據(jù)個(gè)數(shù)有限，常常遭遇小樣本問(wèn)題[9]，這時(shí)局部類內(nèi)離差矩陣通常為奇異矩陣。為解決這一問(wèn)題，通常先利用PCA對(duì)樣本進(jìn)行降維，使得在PCA子空間內(nèi)的局部類內(nèi)離差矩陣為非奇異矩陣，這實(shí)際上僅僅利用了局部類內(nèi)離差矩陣主元空間的鑒別信息而丟失了其零空間的大量鑒別信息。為了充分利用主元空間和零空間內(nèi)的鑒別信息，基于全空間的特征提取算法[10-12]得到了廣泛的關(guān)注。本文將全空間的思想與LADP相結(jié)合，提出了完備的LADP算法(Complete LADP,CLADP)，充分利用局部類內(nèi)離差矩陣的零空間和主元空間內(nèi)的鑒別信息。

1 基于自適應(yīng)近鄰圖嵌入的局部鑒別分析算法

(1)

(2)

(3)

(4)

(5)

(6)

式(1)可以通過(guò)求解廣義特征值問(wèn)題得到

(7)

在LADP算法中，為了使SlW為非奇異矩陣，首先利用PCA方法對(duì)樣本數(shù)據(jù)進(jìn)行降維，使得SlW在PCA子空間內(nèi)滿秩，即所有的特征值均大于零，因此LADP算法僅僅利用SlW主元空間內(nèi)的鑒別信息而丟失了SlW零空間內(nèi)大量的鑒別信息。本文提出了CLADP算法，充分利用SlW零空間和主元空間內(nèi)的鑒別信息。

2 完善的LADP算法

2.1 去除鑒別無(wú)關(guān)信息

對(duì)于總體離差矩陣SlT=SlW+SlB，其零空間由矩陣SlB和SlW的公共零空間組成，在該空間內(nèi)，所有的樣本均投影到同一點(diǎn)而無(wú)法區(qū)分，所以SlT的零空間內(nèi)不含有任何鑒別信息，所有的鑒別信息存在于SlT的主元空間內(nèi)。

(8)

(9)

2.2 規(guī)則鑒別特征和不規(guī)則鑒別特征提取

(10)

(1)規(guī)則鑒別特征提取

(11)

對(duì)于一個(gè)樣本x，其規(guī)則鑒別特征為

(12)

式中：Ar=PQV為規(guī)則鑒別特征的投影變換矩陣。

(2)不規(guī)則鑒別特征提取

(13)

(14)

式中：Air=PQ⊥R為不規(guī)則特征的變換矩陣。

2.3 兩種鑒別特征融合

(1)自適應(yīng)計(jì)算xi的類內(nèi)和類間近鄰點(diǎn)集合，根據(jù)類內(nèi)類間近鄰點(diǎn)個(gè)數(shù)構(gòu)建類內(nèi)類間近鄰圖的權(quán)值矩陣W和Wp，進(jìn)而得到SlW，SlB與SlT。

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

為了評(píng)估本文提出的CLADP算法的性能，設(shè)計(jì)兩類實(shí)驗(yàn)，實(shí)驗(yàn)1在ORL人臉庫(kù)上，通過(guò)低維空間的可視化比較CLADP與LFDA，LADP的鑒別能力，對(duì)于CLADP算法，比較分別采用規(guī)則鑒別特征，不規(guī)則鑒別特征以及融合兩種特征的識(shí)別性能；實(shí)驗(yàn)2在Yale和PIE人臉庫(kù)上比較CLADP與PCA，LDA，LFDA與LADP等算法的分類性能。

3.1 ORL人臉庫(kù)上的實(shí)驗(yàn)

ORL人臉庫(kù)是由英國(guó)劍橋大學(xué)建立，共有40個(gè)人，每人10張圖像，共有400張人臉圖像，圖像的面部表情和面部細(xì)節(jié)有著不同程度的變化，人臉姿勢(shì)也有相當(dāng)程度的變化，比較充分地反映了同一人不同人臉圖像的變化和差異，ORL人臉庫(kù)圖像經(jīng)剪切后大小均為32像素×32像素，用一個(gè)1 024維的向量表示。圖1是ORL人臉庫(kù)的部分樣本。

圖1 ORL人臉數(shù)據(jù)庫(kù)Fig．1 ORL face database

3.1.1 實(shí)驗(yàn)1

通過(guò)對(duì)低維空間的可視化來(lái)比較CLADP與LDA，LFDA，LADP的鑒別能力。在實(shí)驗(yàn)中，隨機(jī)從ORL人臉庫(kù)中選取6個(gè)人的人臉圖像，分別用符號(hào)“*”，“□”，“○”，“+”，“△”和“☆”表示，任意選擇每個(gè)人的5幅圖像作為訓(xùn)練圖像，剩余的圖像作為測(cè)試圖像，分別采用LDA，LFDA，CLADP和LADP等算法將其投影到二維子空間內(nèi)，LFDA算法中近鄰點(diǎn)的個(gè)數(shù)k=4，LDA，LFDA與LADP算法中PCA步驟，保持99%的主元能量，圖2為ORL人臉庫(kù)上6人臉的二維子空間可視化結(jié)果。

圖2 ORL圖像庫(kù)上6人臉的二維子空間Fig．2 Two dimension subspace of six persons in ORL face database

為了更加有效清晰比較各種算法的鑒別能力，采用Fisher標(biāo)準(zhǔn)值(Fisher criterion,FC)來(lái)評(píng)價(jià)在二維子空間內(nèi)樣本之間的區(qū)分程度[13]，F(xiàn)C定義如下

(15)

式中：Sw和Sb分別為二維子空間內(nèi)樣本類內(nèi)和類間離差矩陣。FC值越大，說(shuō)明在相應(yīng)的子空間內(nèi)的不同類別的樣本的區(qū)分度越大，即鑒別能力越強(qiáng)。表1為在ORL人臉庫(kù)的二維子空間內(nèi)，各種算法的FC值。

表1 二維子空間內(nèi)人臉Fisher標(biāo)準(zhǔn)值

從圖2可以看出，對(duì)于ORL人臉庫(kù)，在CLADP算法得到二維子空間內(nèi)6個(gè)人的人臉圖像具有較大的區(qū)分程度，LDA，LFDA與LADP算法得到的子空間內(nèi)不同類別的人臉具有不同程度的交疊，反映在FC值上，CLADP為17.52，LADP，LFDA與LDA分別為6.66，2.47與3.91，說(shuō)明在二維子空間內(nèi)，CLADP的鑒別能力最強(qiáng)，LADP與LDA次之，LFDA最弱。

3.1.2 實(shí)驗(yàn)2

對(duì)于CLADP，比較分別采用規(guī)則鑒別特征，不規(guī)則鑒別特征以及融合兩種特征的識(shí)別性能。實(shí)驗(yàn)中，隨機(jī)選取每一個(gè)人的3幅圖像組成訓(xùn)練樣本集，剩余的圖像組成測(cè)試樣本集，重復(fù)進(jìn)行10次，共得到10組不同的訓(xùn)練樣本集和測(cè)試樣本集。表2所示為分別采用規(guī)則特征，不規(guī)則特征以及融合兩種特征的平均最高識(shí)別率以及對(duì)應(yīng)的維數(shù)。從表2可以看出，單獨(dú)采用規(guī)則鑒別特征其平均最高識(shí)別率為85.36%，單獨(dú)采用不規(guī)則鑒別特征其平均最高識(shí)別率為87.69%，而融合了規(guī)則和不規(guī)則鑒別特征的CLADP算法的平均識(shí)別率進(jìn)一步提高至88.19%。

表2 不同特征下LADP算法的識(shí)別率

3.2 Yale以及PIE人臉庫(kù)上的實(shí)驗(yàn)

通過(guò)在Yale以及PIE人臉庫(kù)上的實(shí)驗(yàn)，比較本文提出的CLADP與PCA,LDA，LFDA和LADP等算法的識(shí)別性能。Yale人臉庫(kù)由美國(guó)耶魯大學(xué)建立，包含15個(gè)人，每人11張圖像，共有165張人臉圖像，主要包括光照條件的變化(左側(cè)光照、右側(cè)光照、中央光照)，表情的變化(正常、高興、悲傷、睡眠、驚訝、眨眼)及有無(wú)眼睛修飾等。PIE人臉圖像庫(kù)由68人的41 368幅不同姿態(tài)、不同光照、不同表情的圖像組成。在本文中，選擇了僅包括光照變化的20人的正面人臉的400張人臉圖像組成的PIE子庫(kù)(每人20張圖像)作為實(shí)驗(yàn)圖像。在實(shí)驗(yàn)中，所有圖像均根據(jù)眼睛坐標(biāo)進(jìn)行旋轉(zhuǎn)、剪切、縮放到大小為32像素×32像素的圖像，未作任何其他處理。圖3顯示了預(yù)處理后各人臉圖像庫(kù)的圖像示例。

圖3 預(yù)處理后的圖像Fig．3 Preprocessed face images

在每個(gè)庫(kù)上進(jìn)行實(shí)驗(yàn)，從每一個(gè)類別中選取m個(gè)樣本組成訓(xùn)練樣本集，記作Gm，其余的n個(gè)樣本組成測(cè)試樣本集，記作Pn，然后利用各種特征提取方法提取特征，最后利用歐式距離作為相似度度量的最近鄰分類器完成分類任務(wù)，每組實(shí)驗(yàn)均重復(fù)10次。對(duì)于PCA以及LDA，LFDA，LADP中PCA步驟，實(shí)驗(yàn)中保持99%的能量，另外，LFDA中的近鄰點(diǎn)個(gè)數(shù)k設(shè)置為n-1,n為訓(xùn)練樣本集中每一個(gè)類別的個(gè)數(shù)。表3和表4分別給出了各種特征提取方法在Yale以及PIE上的平均最高識(shí)別率(括號(hào)中的數(shù)值為對(duì)應(yīng)的維數(shù))。

表3 Yale圖像庫(kù)上的平均最高識(shí)別率

表4 PIE圖像庫(kù)上的平均最高識(shí)別率

從表3和表4可以看出，本文提出的CLADP算法在Yale和PIE人臉庫(kù)上均取得了較好的識(shí)別效果。在Yale人臉庫(kù)上，CLADP算法的識(shí)別率平均比PCA算法高23.37%，比LDA算法高7.64%，比LFDA算法高4.8%，比LADP算法高2.83%；在PIE人臉子庫(kù)上，CLADP算法的識(shí)別率平均比PCA算法高44.46%，比LDA算法高5.36%，比LFDA算法高6.6%，比LADP算法高3.94%。隨著訓(xùn)練樣本的增加，CLADP與PCA，LDA，LFDA，LADP等算法的識(shí)別率都相應(yīng)地提高。

4 結(jié)束語(yǔ)

本文在分析LADP算法僅僅利用局部類內(nèi)離差矩陣主元空間內(nèi)鑒別信息的不足之處的基礎(chǔ)上，提出了同時(shí)利用主元空間和零空間內(nèi)鑒別信息的CLADP算法，由于零空間的鑒別信息對(duì)于識(shí)別任務(wù)具有更加重要的作用，因此相較于LADP算法，CLADP算法具有更強(qiáng)的識(shí)別性能。通過(guò)人臉識(shí)別實(shí)驗(yàn)，本文將CLADP算法與PCA，LDA，LFDA，LADP等4種流行的降維算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明CLADP算法具有最好的識(shí)別率。

[1] Martinez A M, Kak A C. PCA versus LDA[J].IEEE Trans Pattern Analysis and Machine Intelligence, 2001, 23(2):228-233.

[2] 陳國(guó)明.數(shù)據(jù)降維中若干問(wèn)題的研究及應(yīng)用[D].廣州:中山大學(xué),2009.

Chen Guoming.Research and application of several problems in data dimensionality reduction[D].Guangzhou:Sun Yat-Sen University,2009.

[3] 林月娥.特征提取方法研究及其在人臉識(shí)別中的應(yīng)用[D].哈爾濱:哈爾濱工程大學(xué),2009.

Lin Yue′e. Research and application of feature extraction for face recognition[D].Harbin:Harbin Engineering University,2009.

[4] Sugiyama M. Dimensionality reduction of multimodal labeled data by local Fisher discriminant analysis[J].Journal of Machine Learning Research,2007,8(5):1027-1067.

[5] He X F， Niyogi P. Locality preserving projection[C]//Proceedings of the 16th Advances in Neural Information Processing Systems. Vancouver, Canada: Neural Information Processing Systems Foundation, 2003:153-160.

[6] He X F, Cai D, Yan S C, et al. Neighborhood preserving embedding [C]// Proceedings of 10th IEEE International Conference on Computer Vision. Beijing, China: IEEE, 2005: 1208-1213.

[7] Yan S C,Xu D, Zhang B Y, et.al. Graph embedding and extension:A general framework for dimensionality reduction[J]. IEEE Trans on Pattern Analysis and Machine Intelligence,2007,29(1):40-51.

[8] 王永茂,徐正光,趙珊. 基于自適應(yīng)近鄰圖嵌入的局部鑒別投影算法[J]. 電子與信息學(xué)報(bào), 2013,35(3):633-638.

Wang Yongmao, Xu Zhengguang, Zhao Shan. Neighborhood graph embedding based local adaptive discriminant projection[J]. Journal of Electronics and Information Technology,2013,35(3):633-638.

[9] 江艷霞，任波.基于加權(quán)鄰域極大邊界準(zhǔn)則的人臉識(shí)別[J].數(shù)據(jù)采集與處理,2011,26(5):515-520.

Jiang Yanxia, Ren Bo. Face recognition based on weighted neighborhood maximum margin criterion[J]. Journal of Data Acquisition and Processing, 2011, 26(5):515-520.

[10]楊利平, 龔衛(wèi)國(guó), 辜小花,等. 完備鑒別保局投影人臉識(shí)別算法[J]. 軟件學(xué)報(bào),2010,21(6):1277-1286.

Yang Liping, Gong Weiguo, Gu Xiaohua, et al.Complete discriminant locality preserving projections for face recognition[J].Journal of Software,2010,21(6):1277-1286.

[11]殷俊, 金忠. 完備非監(jiān)督鑒別投影于人臉圖像分析[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖像學(xué)學(xué)報(bào), 2010, 22(11): 1913-1918.

Yin Jun, Jin Zhong.Complete unsupervised discriminant projection and face image analysis[J].Journal of Computer Aided Design and Computer Graphics,2010,22(11):1913-1918.

[12]Wang Y, Wu Y. Complete neighborhood preserving embedding for face recognition[J]. Pattern Recognition, 2010, 43(3):1008-1015.

[13]Raducanu B, Dornaika F. A supervised non-linear dimensionality reduction approach for manifold learning[J]. Pattern Recognition, 2012, 45(6): 2432-2444.

Local Discriminant Projection Algrorithm Based on Complete Adaptive Neighborhood Graph Embedding

Wang Yongmao, Li Geng

(School of Computer Science and Technology, Henan Polytechnic University, Jiaozuo, 454000, China)

The existing adaptive neighborhood graph embedding method based on local discriminant projection(LADP) only uses discriminant information in the principle space of local within-class scatter matrix, which leads to the loss of discriminant information in the null space. To overcome the drawback of LADP, a complete LADP(CLADP) is proposed for face recognition. In the null space of local within-class scatter matrix, irregular discriminant features are extracted by maximizing the local between-class scatter matrix. In the principle space of local within-class scatter matrix, regular discriminant features are extracted by maximizing the local between-class scatter matrix and minimizing the local within-class scatter matrix. Finally, irregular discriminant features and regular discriminant features are combined as the features of CLADP for face recognition. The experimental results on ORL, Yale face database and PIE subset illustrate the effectiveness of the proposed CLADP.

face recognition; adaptive neighborhood graph; local discriminant analysis; complete feature; dimensionality reduction

河南省教育廳科學(xué)技術(shù)研究(12B520021)資助項(xiàng)目；河南理工大學(xué)博士基金(B2014-043)資助項(xiàng)目。

2014-03-05；

2014-05-12

TP391.4

A

王永茂(1976-)，男，博士，副教授，研究方向：圖像處理與模式識(shí)別，E-mail：wymyjs2000@hpu.edu.cn。

李賡(1981-)，男，講師，研究方向：模式識(shí)別和智能處理。