無參數無相關最大化判別邊界算法

梁興柱，林玉娥，許光宇

?

無參數無相關最大化判別邊界算法

梁興柱，林玉娥，許光宇

(安徽理工大學計算機科學與工程學院，安徽 淮南 232001)

在人臉識別算法中，無參數局部保持投影(PFLPP)是一種有效的特征提取算法，但忽略了異類近鄰樣本在分類中所起的作用，并且對于近鄰的處理僅利用樣本與總體均值的距離關系來判斷，因此并不能有效地確定近鄰關系?；诖?，提出一種無參數無相關最大化判別邊界算法，有效地利用了樣本的類別信息，定義了無參數同類近鄰樣本的相似權值與異類近鄰樣本的懲罰權值，樣本鄰域大小可根據類內平均余弦距離和類間余弦距離自適應確定，為了進一步增強算法的性能，給出了具有不相關性的目標函數。UMIST和AR人臉庫上的實驗結果表明，該算法相對于不相關保局投影分析算法和PFLPP算法，具有運算量低、識別性能高的優勢。

人臉識別；特征提取算法；無參數；無相關

目前，人臉識別技術已廣泛地被應用，而特征提取算法是人臉識別技術的一個關鍵環節。近年來，主要的特征提取算法有，基于全局思想的主成分分析(principal component analysis，PCA)[1]和線性判別分析(linear discriminant analysis，LDA)[1]算法，基于局部保持思想的保局投影映射(locality preserving projections，LPP)[2]。其中LPP是以保持樣本的局部結構為目標，可以提取出更加有效的分類特征，因此學者們提出了大量的改進方案，如XU等[3]提出的邊界近鄰判別分析算法，既有類似于LDA的目標函數，同時又能保持樣本的局部結構信息，因此取得了較好的識別結果；一般通過對所求投影矩陣進行約束限制，可以有效地提高算法的識別性能，文獻[4-7]提出了具有正交性約束或不相關性約束的改進算法；文獻[8]則針對局部保持投影的近鄰權值構造進行了研究，由于傳統的近鄰權值是基于歐氏距離的，而歐氏距離對于樣本噪聲非常敏感，因此提出了稀疏判別局部保持投影算法；但上述算法在應用于人臉識別問題中均會遇到小樣本問題，對此文獻[9-10]提出了基于大間距的目標函數，文獻[11-12]提出基于矩陣指數變換的策略。但是針對小樣本問題，文獻[9-12]所提的算法均是基于向量模式的，即需要人臉圖像按行或列拉直成一維向量，為此文獻[13-14]結合人臉圖像的固有特點提出了基于圖像模式的局部保持算法，并給出了基于1范式的目標函數，其有效地解決了小樣本問題，而且具有更加穩定的數值解，從而進一步增強了算法的性能。

然而上述算法，均需設置參數，即樣本近鄰的大小及近鄰權值。參數的取值將直接影響著算法的識別性能，因此如何自適應地設置算法的參數是當前一個有意義的研究。對此參數選擇問題，文獻[15-20]分別提出了不同的改進方案，其中文獻[15]提出了基于樣本余弦距離的無參數局部保持投影算法(parameter-free locality preserving projection，PFLPP)，有效地解決了算法參數設置問題。PFLPP使用樣本余弦距離作為近鄰的權值，近鄰大小通過樣本與總體均值的余弦距離比較動態確定樣本的近鄰，有效地保持了樣本的局部結構，并取得了較好的識別結果。PFLPP無需設置參數，更適合實際的分類問題，然而其忽略了異類近鄰樣本的作用，而且僅考慮與總體均值進行比較的近鄰配置方案并不能有效地保持樣本的局部近鄰結構，同時也未對所求投影矩陣進行約束限制，基于此，本文提出一種無參數無相關最大化判別邊界算法(parameter-free uncorrelated maximum discriminant margin algorithm，PUMDMA)。PUMDMA重新定義了同類近鄰相似權值和異類近鄰懲罰權值，給出了采用樣本的類內距離和類間距離的自適應近鄰配置方案，無需任何參數設置。為了提取出更加有效的分類特征，PUMDMA的目標函數加入了不相關約束條件。本文的目標是先求解出樣本的不相關空間；然后在此空間中求出能最大化異類矩陣的同時，最小化同類相似近鄰矩陣的投影矩陣；最后，UMIST和AR人臉庫上的實驗結果驗證了PUMDMA的有效性。

1 無參數局部保持投影算法

首先介紹PFLPP的算法原理。

因為人臉圖像每個像素點的取值都是非負數，所以式(1)的取值范圍為0,)≤1。余弦距離表明了2個樣本向量和之間的夾角關系，2個樣本越相似其夾角越小，因此和的cos(,)越大，即cos(,)的值越接近１。反之，2個樣本和的相似度越低其夾角越大，因此和的cos(,)就越小。在PFLPP中，對于任意2個樣本和之間近鄰相似權值S的計算為

其中，為所有樣本的總體均值。

若要考慮樣本的類別信息，則式(2)需要添加限制類別的條件，即

PFLPP的目標函數為

2 無參數無相關最大化判別邊界算法

2.1 PUMDMA的原理

由PFLPP的近鄰權值計算式(2)和式(3)，表明其僅考慮了樣本的近鄰關系，卻忽略了異類近鄰樣本在分類中所起的作用，而且其近鄰配置方案采用總體均值進行鄰域確定并不能有效地保持樣本的局部近鄰結構。故此，本文提出PUMDMA算法，考慮了同類近鄰樣本與異類近鄰樣本的作用，同時給出一種改進的自適應近鄰確定方案，PUMDMA目標函數能夠在保持同類樣本近鄰結構的同時，最大化異類近鄰邊界，從而達到正確分類的目標。首先給出2個定義。

定義1和2給出了類內平均余弦距離和類間余弦距離的定義與計算方法。根據定義1和2，分別給出本文的無參數同類近鄰樣本相似權值和無參數異類近鄰樣本懲罰權值的計算公式。

假設2個樣本和為同類樣本，則其近鄰相似權值計算為

同理假設樣本和是異類樣本，則其近鄰懲罰權值計算為

結合式(7)和式(8)分別定義無參數類內相似矩陣和無參數類間懲罰矩陣，計算為

計算為

PUMDMA的目標尋找投影矩陣，能夠最大化無參數類間懲罰矩陣，同時能夠最小化無參數類內相似矩陣，故有

在模式識別中，通常具有不相關的投影矩陣可以提高算法的識別率[21]，若要使所求得的投影矩陣具有不相關性，應滿足

2.2 PUMDMA的求解過程

對于人臉識別問題，由于圖像的維數太高，即存在著小樣本問題，因此對于式(13)并不能直接求解，為此可將式(13)改寫最大化差形式的目標函數

對PUMDMA具體求解步驟歸納如下：

(2) 根據式(9)和式(10)分別計算出無參數類內近鄰相似矩陣和無參數類間懲罰矩陣；

3 算法的測試與分析

針對PUMDMA、ULPP和PFLPP3種算法提取特征數目與識別率的變化進行了比較，分析了3種算法識別性能的變化情況，實驗結果如圖1和圖2所示。本次實驗中，選擇2個人臉庫的每人前6幅作為訓練樣本，剩余圖像作為測試樣本。

圖1 在UMIST人臉庫上識別率與特征數目的變化

圖2 在AR人臉庫上識別率與特征數目的變化

圖1和圖2的結果表明了隨著特征數目增加，PUMDMA、ULPP和PFLPP 3種算法識別率的變化情況。無論是在小的測試集UMIST人臉庫，還是大的測試集AR人臉庫上，PUMDMA均取得了優于ULPP和PFLPP較好地識別結果。另可以發現在特征與類別大約一致的時候，3種算法均取得了較穩定的識別結果，說明PUMDMA采用余弦距離作為權系數，自適應方式確定樣本近鄰及其不相關的約束是可行有效的。

為了進一步測試算法的性能，在UMIST和AR兩個人臉庫分別取訓練樣本5~8個，余下圖像作為測試樣本，每次隨機選擇訓練樣本，進行10次重復，用10次的平均結果作為每種算法的識別結果，見表1和表2。

表1 UMIST人臉庫上的識別結果(%)

表2 AR人臉庫上的識別結果(%)

表1和表2的結果表明了PUMDMA的識別結果明顯優于另外2種算法的識別結果，是因為PUMDMA綜合了ULPP和PFLPP算法的優勢，既具有不相關性的約束，又無需參數的設置。PUMDMA也改進了PFLPP不足，其目標函數兼顧了同類近鄰樣本和異類近鄰樣本的作用，并能夠自適應地確定樣本近鄰，因此能更好地保持樣本的局部結構，從而提取出判別能力更強的特征。另外，由于PUMDMA的目標函數采用最大化差形式，也避免了人臉識別中的小樣本問題。因此，PUMDMA取得了最好地識別結果。

基于局部保持投影的算法都需要計算所有樣本間的距離，然后再進行由小到大的排序，選出前個近鄰，構成近鄰矩陣。而本文算法是無需進行排序，排序改為比較運算，因此計算量并沒有增加。如果采用快速排序的時間復雜度為(nlogn)，而本文的比較時間復雜度為()。為此本文對上述3種算法投影矩陣計算時間進行了比較，在2個數據庫上分別選擇前5個樣本作為訓練樣本，對于3種算法的最優投影矩陣計算時間進行了測試，結果見表3。

表3 AR方法運算時間比較(s)

從表3可以看出，本文算法的計算速度快于ULPP算法，ULPP算法也同時考慮了同類與異類樣本，但本文算法無需排序計算；而相對PFLPP要多花一些時間，是因為PFLPP僅考慮了同類近鄰，而沒有考慮異類近鄰，但從識別結果來看，有關損失是值得的。

4 結束語

本文針對PFLPP的不足，提出了PUMDMA，其特點是無需設置參數，同時考慮同類與異類近鄰在分類中的作用，并要求投影矩陣具有不相關性。因此，PUMDMA首先定義了無參數的同類近鄰樣本相似權值和異類近鄰樣本懲罰權值的計算公式，對于同類與異類近鄰樣本的確定，可根據樣本與類內平均余弦距離和樣本與類間余弦距離的關系自適應確定，最后給出了PUMDMA的目標函數及相應的求解步驟。UMIST和AR人臉庫的實驗結果表明該方法的有效性和可行性。

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

[2] HE X F, YAN S C, HU Y, et al. Face recognition using Laplacianfaces [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(3): 328-340.

[3] XU D, YAN S, TAO D, et al. 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.

[4] CAI D, HE X. F, HAN J W. Orthogonal laplacianfaces for face recognition [J]. IEEE Transactions on Image Processing, 2006, 15(11): 3608-3614.

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

[6] 龔劬, 唐萍峰. 基于大間距準則的不相關保局投影分析[J]. 自動化學報, 2013, 39(9): 1575-1580.

[7] WU F, JING X Y, DONG X W, et al. Uncorrelated multi-set feature learning for color face recognition [J]. Pattern Recognition, 2016, 60(12): 630-646.

[8] ZHANG J, WANG J, CAI X. Sparse locality preserving discriminative projections for face recognition [J]. Neurocomputing, 2017, 260(18): 321-330.

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

[10] WAN M, LAI Z, YANG G, et al. Local graph embedding based on maximum margin criterion via fuzzy set [J]. Fuzzy Sets and Systems, 2017, 318(7): 120-131.

[11] LU G F, WANG Y, ZOU J, et al. Matrix exponential based discriminant locality preserving projections for feature extraction [J]. Neural Netw, 2017, 97(4): 127-136.

[12] DORNAIKA F, TRABOULSI Y E. Matrix exponential based semi-supervised discriminant embedding for image classification [J]. Pattern Recognition, 2017, 61: 92-103.

[13] CHEN S B, WANG J, LIU C Y, et al. Two-dimensional discriminant locality preserving projection based on L1-norm maximization [J]. Pattern Recognition Letters, 2017, 87(1): 147-154.

[14] ZHANG Z, LI F Z, ZHAO M B, et al. Robust neighborhood preserving projection by nuclear/L2,1-norm regularization for image feature extraction [J]. IEEE Transactions on Image Processing, 2017, 26(4): 1607-1622.

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

[16] LI B, DU J, ZHANG X P. Feature extraction using maximum nonparametric margin projection [J]. Neurocomputing, 2016, 188(5): 225-232.

[17] 何進榮, 丁立新, 李照奎,等.基于邊界判別投影的數據降維[J].軟件學報, 2014, 25(4): 826-838.

[18] 何進榮, 閉應洲, 丁立新, 等. 局部差異正則化的邊界判別投影[J]. 計算機學報, 2018, 41(4): 780-795.

[19] 趙振華, 郝曉弘. 局部保持鑒別投影及其在人臉識別中的應用[J]. 電子與信息學報, 2013, 35(2): 463-467.

[20] 陳才扣, 侯鈺. 非相似度保持投影[J]. 中國圖象圖形學報, 2012, 17(10): 1232-1236.

[21] JIN Z, YANG J. Face recognition based on the uncorrelated discrimination transformation [J]. Pattern Recognition, 2001, 34(7): 1405-1416.

Parameter-Free Uncorrelated Maximum Discriminant Margin Algorithm

LIANG Xing-zhu, LIN Yu-e, XU Guang-yu

(School of Computer Science and Engineering, Anhui University of Science and Technology, Huainan Anhui 232001, China)

The parameter-free locality preserving projection (PFLPP) is an effective feature extraction algorithm for face recognition, but it cannot effectively determine the neighbor relationship because it does not consider neighborhood relationship between the samples from different classes, and this algorithm judges the neighborhood relationship only by the distance between the samples and the population mean. In this paper, parameter-free uncorrelated maximum discriminant margin algorithm is proposed, which effectively uses the class information of the samples and needn’t set any parameters. The algorithm defines the similar weights of the neighbor samples from the same class and the punishment weights of the neighbor samples from different classes. The size of the sample neighborhood can be adaptively determined by the mean of the intraclass cosine distance and the inter-class cosine distance. In order to further enhance the performance of the algorithm, the uncorrelated objective function based on the maximum discriminant margin is put forward. The experimental results of UMIST and AR face database show that the proposed method has the advantages of low computation and high recognition performance compared with PFLPP and uncorrelated locality preserving projections analysis.

face recognition; feature extraction algorithm; parameter-free; uncorrelated

TP 391.4

10.11996/JG.j.2095-302X.2019010105

A

2095-302X(2019)01-0105-06

2018-07-03；

2018-07-20

國家自然科學基金項目(61471004)；安徽高校自然科學研究項目(KJ2016A203，KJ2018A0084)

梁興柱(1979-)，男，安徽長豐人，講師，碩士。主要研究方向為模式識別、網絡安全等。E-mail：lxz9117@126.com