林玉娥，李敬兆，梁興柱，林玉榮

(1.安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001;2.哈爾濱工業(yè)大學(xué)航天學(xué)院，黑龍江 哈爾濱 150001)

1 引言

近年來，基于局部近鄰思想的特征提取方法受到了學(xué)者們的關(guān)注，如局部保持投影 LPP(Locality Preserving Projections)[1]、有監(jiān)督的局部保持投影LSBS(Local Structure Based Supervised)[2]、正交的保局鑒別分析OLPP(Orthogonal Locality Preserving Projections)[3]以及邊界Fisher鑒別分析MFA(Marginal Fisher Analysis)[4,5]算法等，這些算法都是基于局部近鄰思想提出的。其中的MFA是一種有效的特征提取算法,與其他局部近鄰算法的區(qū)別是該算法綜合了保局投影方法[1]和線性鑒別分析方法[6]的優(yōu)點(diǎn)。其思想是通過構(gòu)造類內(nèi)圖S來描述類內(nèi)數(shù)據(jù)的緊致性,構(gòu)造類間圖B來描述類間數(shù)據(jù)的可分性,以二者的比值構(gòu)造目標(biāo)函數(shù),實(shí)驗(yàn)表明了該算法有效性。但是，該算法也有不足之處,對(duì)此文獻(xiàn)[7,8]指出邊界Fisher鑒別分析的目標(biāo)函數(shù)沒有充分考慮異類樣本近鄰關(guān)系的缺點(diǎn),因此分別提出了相應(yīng)的改進(jìn)算法;文獻(xiàn)[9]則針對(duì)MFA所求的鑒別向量之間的關(guān)系進(jìn)行了研究,給出了正交MFA和無相關(guān)MFA來進(jìn)一步提高M(jìn)FA算法的識(shí)別性能。

但是，上述改進(jìn)算法和原MFA算法一樣,在應(yīng)用于人臉識(shí)別等模式識(shí)別問題時(shí),均受到小樣本問題的制約,即目標(biāo)函數(shù)中存在矩陣奇異的問題。對(duì)于該問題目前多采用差分的目標(biāo)函數(shù)來避免矩陣的求逆[10～12],這種策略雖然能夠解決小樣本問題,但基于差形式的目標(biāo)函數(shù)的識(shí)別效果沒有商形式的理想[13]。

因此，本文針對(duì)上述問題進(jìn)行了研究,以MFA為理論基礎(chǔ),提出了一種適用于人臉識(shí)別等高維小樣本問題的方法，即完備的雙子空間邊界近鄰鑒別分析DSMNDA(Dual Subspace Marginal Neighborhood Discriminant Analysis)。 DSMNDA的思想是將MFA的目標(biāo)函數(shù)分解成兩部分，一部分是在邊界近鄰類內(nèi)散度矩陣的非零空間內(nèi)尋找最優(yōu)投影矩陣，另一部分是在邊界近鄰類內(nèi)散度矩陣的零空間中尋找最大化邊界近鄰類間散度矩陣的最佳投影矩陣。該算法的關(guān)鍵是求解出邊界近鄰類內(nèi)散度矩陣的零空間與非零空間,對(duì)此本文給出了完備的求解方案,即首先要對(duì)中心化處理后的樣本進(jìn)行PCA降維處理,而這一過程相對(duì)于DSMNDA目標(biāo)函數(shù)而言并不損失任何有效的鑒別信息, 對(duì)此給出了具體的理論證明。最后的實(shí)驗(yàn)結(jié)果表明了本文算法的有效性。

2 MFA 算法

設(shè)有矩陣S和B,MFA通過緊致矩陣S來描述類內(nèi)數(shù)據(jù)的緊致性,即每個(gè)樣本只與同類樣本中的k1近鄰相連；通過緊致矩陣B來描述類間數(shù)據(jù)的可分性,即只有異類樣本的k2近鄰相連。分別由式(1)和式(2)計(jì)算：

(1)

(2)

MFA的目標(biāo)函數(shù)為:

(3)

其中，Lw=Dw-S,LB=DB-B,DW和DB都是對(duì)角矩陣,其對(duì)角元素分別為(DW)ii=∑jSij和(DB)ii=∑jBij。式(3)的求解可轉(zhuǎn)換為下面的廣義特征值求解問題,即:

XLwXTwi=λiXLBXTwi，i=1,2,…,l

(4)

具體求解及證明請(qǐng)參見文獻(xiàn)[4,5]。

3 完備的雙子空間邊界近鄰鑒別分析

當(dāng)MFA的目標(biāo)函數(shù)應(yīng)用于人臉識(shí)別等高維小樣本問題時(shí),實(shí)際上并不能直接按式(4)進(jìn)行分解,還要先進(jìn)行PCA降維處理。但是，文獻(xiàn)[4,5]中均沒給出理論上的分析及證明,本文則對(duì)此進(jìn)行了分析及證明,給出了一種完備的雙子空間邊界近鄰鑒別分析-DSMNDA。

3.1 算法的理論推導(dǎo)

對(duì)于MFA的目標(biāo)函數(shù)又可寫成下面最大化的形式：

(5)

但是，無論是式(3)的極小化還是式(5)的最大化都存在著矩陣不可逆的問題，受文獻(xiàn)[14]的啟發(fā),本文對(duì)此進(jìn)行了分析并給出如下策略：

假設(shè)X=[x1,x2,…,xN]為高維歐氏空間Rn樣本集,首先將樣本中心化處理,即有:

[x1-m,x2-m,…,xN-m]

(6)

m樣本的均值為向量,假設(shè)有C={n1,n2,…,nc}個(gè)類別,每類有Nl個(gè)樣本,共有N個(gè)樣本。定義St為總體散度矩陣,由下式計(jì)算:

(7)

因此,樣本經(jīng)過中心化處理后，目標(biāo)函數(shù)式(5)可改寫為:

(8)

定義1設(shè)α1,α2,…,αn表示St的標(biāo)準(zhǔn)正交的特征向量集,令Z={x|Stx=0,x∈Rn},即Z為St的零空間,則有Z⊥=span{α1,α2,…,αk} (Z⊥代表Z的正交補(bǔ)空間),Z=span{αk+1,αk+2,…,αn}, 其中k=rank(St)。

□

定理2對(duì)于目標(biāo)函數(shù)式(8)，Z中不存有效解。

由定理1和ηr∈Z可知：

故Z中不存在式(8)的有效解。

□

由定理2可知,對(duì)于目標(biāo)函數(shù)的有效解只存在于子空間Z⊥中。設(shè):

wr=P1br

(9)

其中,P1=[α1,α2,…,αk],br∈Rk,該映射表示對(duì)于所求得的任何一個(gè)鑒別向量都是由Z⊥中的基向量線性組合生成的,則有W=P1B,B=[b1,b2,…,bl]。因此,式(8)可轉(zhuǎn)換為:

(10)

(11)

(12)

(13)

(14)

(15)

3.2 DSMNDA的具體實(shí)現(xiàn)

DSMNDA的具體求解步驟如下：

(1)首先根據(jù)式(7)對(duì)輸入的數(shù)據(jù)進(jìn)行中心化處理。

(2)對(duì)中心化后的數(shù)據(jù)根據(jù)式(1)和式(2)計(jì)算出S和B,再分別計(jì)算(DW)ii=∑jSij、(DB)ii=∑jBij、Lw=Dw-S和LB=DB-B。

(3)對(duì)St進(jìn)行特征值分解,計(jì)算出St非零特征值所對(duì)應(yīng)的特征向量集P1=[α1,α2,…,αk]。

4 實(shí)驗(yàn)結(jié)果與討論

為了驗(yàn)證所提出DSMNDA的性能,分別在FERET[15]和AR[16]人臉庫上進(jìn)行了測試，并采用簡單的最近鄰算法進(jìn)行分類。FERET人臉圖庫,選擇其一個(gè)子集來進(jìn)行測試。該子集包括70人,每人6幅圖像, 每幅人臉圖像的尺寸為92×112。在AR人臉庫選擇了其中的一個(gè)子集來進(jìn)行測試。該子集包括100人,每人15幅圖像,每幅人臉圖像的分辨率為100×80。 對(duì)于MFA和DSMNDA的近鄰選擇,本文選擇為同類3近鄰,異類為5近鄰,分別進(jìn)行了如下實(shí)驗(yàn)：

Figure 1 Performance comparisons with different samples on FERET face database 圖1 FERET人臉庫上不同樣本下的識(shí)別結(jié)果

Figure 2 Performance comparisons with different samples on AR face database 圖2 AR人臉庫上不同樣本下的識(shí)別結(jié)果

(2)本次實(shí)驗(yàn)將DSMNDA與其它的幾個(gè)經(jīng)典的算法進(jìn)行了比較，分別是正交的LPP算法(記為ODLPP， ODLPP也加入的其所對(duì)應(yīng)的零空間信息)、正交的MFA和不相關(guān)的MFA(分別記為OMFA和UMFA)。在兩個(gè)人臉庫上,每人隨機(jī)選擇T幅圖像作為訓(xùn)練樣本,T的取值為3～5,剩余圖像作為測試樣本。取10次平均識(shí)別結(jié)果作為每種算法的識(shí)別結(jié)果,實(shí)驗(yàn)結(jié)果如表1與表2所示。

Table 1 Recognition results on FERET face database表1 FERET人臉庫上的識(shí)別結(jié)果比較

Table 2 Recognition results on AR face database表2 AR人臉庫上的識(shí)別結(jié)果

5 結(jié)束語

本文針對(duì)MFA算法的不足，對(duì)其進(jìn)行了改進(jìn)，提出一種能夠有效解決小樣本問題的特征提取算法，即完備的雙子空間邊界近鄰鑒別分析——DSMNDA。該算法實(shí)質(zhì)是將MFA的目標(biāo)函數(shù)分解成為兩部分，一部分是在類內(nèi)邊界近鄰的零空間中求出能夠最大化類間邊界近鄰的投影矩陣，另一部分是在類內(nèi)邊界近鄰的非零空間求出能夠同時(shí)最大化類間邊界近鄰且最小化的類內(nèi)邊界近鄰的投影矩陣。對(duì)此本文給出了一種完備的求解方法,即對(duì)于目標(biāo)函數(shù)中的樣本,首先對(duì)中心化處理過的樣本進(jìn)行PCA降維,而這一過程是不損失任何有效鑒別信息的, 并給出了相應(yīng)的理論證明；然后再對(duì)低維的樣本進(jìn)行相應(yīng)的特征值分解求出兩個(gè)投影矩陣，在識(shí)別階段，只要將每個(gè)樣本得到的兩個(gè)特征向量串聯(lián)起來形成一個(gè)向量，按最近鄰方法識(shí)別即可。實(shí)驗(yàn)結(jié)果表明了該方法的有效性,但該方法本質(zhì)上是一種線性的方法，也沒有考慮樣本的稀疏性，下一步我們將結(jié)合稀疏性[17]及核映射學(xué)習(xí)方法對(duì)算法進(jìn)行拓展，從而進(jìn)一步增強(qiáng)算法的識(shí)別性能。

[1] He X F, Yan S C,Hu Y.Face recognition using Laplacianfaces [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(3):328-340.

[2] Zhang H, Sun S, Jing Z, et al. Local structure based supervised feature extraction[J]. Pattern Recognition, 2006,39(8):1546-1550.

[3] Zhu L,Zhu S N. Face recognition based on orthogonal discriminant locality preserving projections[J].Neurocomputing, 2007,70(9):1543-1546.

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

[5] Xu D,Yan S, Tao D. Marginal fisher analysis and its variants for human gait recognition and content-based image retrieval[J].IEEE Transactions on Image Processing, 2007,16(11):2811-2821.

[6] Belhumeur P N, Hespanha J P, Kriegam 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.

[7] Xie Jun, Liu Jian. A new local discriminant projection method[J]. Chinese Journal of Computers,2011,31(11):2243-2250.(in Chinese)

[8] Fang B, Cheng M, Tang Y Y. Improving the discriminant ability of local margin based learning method by incorporating the global between-class separability criterion[J]. Neurocomputing,2009,73(1):536-541.

[9] Yu Yao-liang, Zhang Li-ming. Orthogonal MFA and uncorrelated MFA[J].Pattern Recognition and Artificial Intelligence,2008,21(5):604-608.(in Chinese)

[10] Lin Ke-zheng,Wang Hui-xin,Bu Xue-na.Discriminant maximum margin criterion based on locality preserving projections[J]. Pattern Recognition and Artificial Intelligence, 2010,23(2):178-185.(in Chinese)

[11] Lu Gui-fu,Lin Zhong, Jin Zhong. Face recognition based on two-dimensional maximum difference marginal fisher analysis[J]. Computer Science, 2010,35(7):251-253.(in Chinese)

[12] Lu G F, Lin Z, Jin Z. Face recognition using discriminant locality preserving projections based on maximum margin criterion [J]. Pattern Recognition, 2010,43 (3):3572-3579.

[13] Tao Y T, Yang J. Quotient vs. difference:Comparison between the two discriminant criteria [J]. Neurocomputing, 2010, 73(10-12):1808-1817.

[14] Lu Gui-fu, Lin Zhong, Jin Zhong. Optimal discriminant analysis based on kernel extension of graph embedding and face recognition[J]. Journal of Software,2011,22(7):1561-1570. (in Chinese)

[15] http://www.nist.gov/humanid/feret/feret_master.html.

[16] http://cobweb.ecn.purdue.edu/～aleix/aleix_face_DB.html.

[17] Yan De-qin, Liu Sheng-lan, Li Yan-yan. An embedding dimension reduction algorithm based on sparse analysis[J]. Acta Automatica Sinica, 2011, 37(11):1306-1312.(in Chinese)

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

[7] 謝鈞,劉劍.一種新的局部判別投影方法[J].計(jì)算機(jī)學(xué)報(bào),

2011,31(11):2243-2250.

[9] 于耀亮,張立明.正交MFA和不相關(guān)MFA[J].模式識(shí)別與人工智能,2008,21(5):604-608.

[10] 林克正,王慧鑫,卜雪娜.基于局部保持投影的鑒別最大間距目標(biāo)[J].模式識(shí)別與人工智能,2010,23(2):178-185.

[11] 盧桂馥,林忠,金忠.基于最大差值的二維邊界Fisher的人臉識(shí)別[J].計(jì)算機(jī)科學(xué)，2010,35(7):251-253.

[14] 盧桂馥,林忠,金忠.基于核化圖嵌入的最佳鑒別分析與人臉識(shí)別[J].軟件學(xué)報(bào),2011,22(7):1561-1570.

[17] 閆德勤, 劉勝藍(lán), 李燕燕. 一種基于稀疏嵌入分析的降維方法[J]. 自動(dòng)化學(xué)報(bào), 2011, 37(11):1306-1312.