梁興柱，林玉娥，許光宇

?

無參數(shù)無相關(guān)最大化判別邊界算法

梁興柱，林玉娥，許光宇

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

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

人臉識別；特征提取算法；無參數(shù)；無相關(guān)

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

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

1 無參數(shù)局部保持投影算法

首先介紹PFLPP的算法原理。

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

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

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

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

2 無參數(shù)無相關(guān)最大化判別邊界算法

2.1 PUMDMA的原理

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

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

假設(shè)2個樣本和為同類樣本，則其近鄰相似權(quán)值計算為

同理假設(shè)樣本和是異類樣本，則其近鄰懲罰權(quán)值計算為

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

計算為

PUMDMA的目標(biāo)尋找投影矩陣，能夠最大化無參數(shù)類間懲罰矩陣，同時能夠最小化無參數(shù)類內(nèi)相似矩陣，故有

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

2.2 PUMDMA的求解過程

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

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

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

3 算法的測試與分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

[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] 龔劬, 唐萍峰. 基于大間距準(zhǔn)則的不相關(guān)保局投影分析[J]. 自動化學(xué)報, 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] 黃璞, 唐振民. 無參數(shù)局部保持投影及人臉識別[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ìn)榮, 丁立新, 李照奎,等.基于邊界判別投影的數(shù)據(jù)降維[J].軟件學(xué)報, 2014, 25(4): 826-838.

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

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

[20] 陳才扣, 侯鈺. 非相似度保持投影[J]. 中國圖象圖形學(xué)報, 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

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

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