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

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

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

1 引言

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

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

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

2 MFA 算法

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

(1)

(2)

MFA的目標函數為:

(3)

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

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

(4)

具體求解及證明請參見文獻[4,5]。

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

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

3.1 算法的理論推導

對于MFA的目標函數又可寫成下面最大化的形式：

(5)

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

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

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

(6)

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

(7)

因此,樣本經過中心化處理后，目標函數式(5)可改寫為:

(8)

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

□

定理2對于目標函數式(8)，Z中不存有效解。

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

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

□

由定理2可知,對于目標函數的有效解只存在于子空間Z⊥中。設:

wr=P1br

(9)

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

(10)

(11)

(12)

(13)

(14)

(15)

3.2 DSMNDA的具體實現

DSMNDA的具體求解步驟如下：

(1)首先根據式(7)對輸入的數據進行中心化處理。

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

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

4 實驗結果與討論

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

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

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

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

Table 1 Recognition results on FERET face database表1 FERET人臉庫上的識別結果比較

Table 2 Recognition results on AR face database表2 AR人臉庫上的識別結果

5 結束語

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

[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)

附中文參考文獻：

[7] 謝鈞,劉劍.一種新的局部判別投影方法[J].計算機學報,

2011,31(11):2243-2250.

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

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

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

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

[17] 閆德勤, 劉勝藍, 李燕燕. 一種基于稀疏嵌入分析的降維方法[J]. 自動化學報, 2011, 37(11):1306-1312.