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

梁興柱，林玉娥，許光宇

?

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

梁興柱，林玉娥，許光宇

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

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

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

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

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

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

首先介紹PFLPP的算法原理。

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

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

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

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

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

2.1 PUMDMA的原理

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

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

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

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

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

計(jì)算為

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

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

2.2 PUMDMA的求解過(guò)程

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

對(duì)PUMDMA具體求解步驟歸納如下：

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

3 算法的測(cè)試與分析

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

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

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

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

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

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

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

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

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

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

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

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

本文針對(duì)PFLPP的不足，提出了PUMDMA，其特點(diǎn)是無(wú)需設(shè)置參數(shù)，同時(shí)考慮同類與異類近鄰在分類中的作用，并要求投影矩陣具有不相關(guān)性。因此，PUMDMA首先定義了無(wú)參數(shù)的同類近鄰樣本相似權(quán)值和異類近鄰樣本懲罰權(quán)值的計(jì)算公式，對(duì)于同類與異類近鄰樣本的確定，可根據(jù)樣本與類內(nèi)平均余弦距離和樣本與類間余弦距離的關(guān)系自適應(yīng)確定，最后給出了PUMDMA的目標(biāo)函數(shù)及相應(yīng)的求解步驟。UMIST和AR人臉庫(kù)的實(shí)驗(yàn)結(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]. 自動(dòng)化學(xué)報(bào), 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] 黃璞, 唐振民. 無(wú)參數(shù)局部保持投影及人臉識(shí)別[J]. 模式識(shí)別與人工智能, 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é)報(bào), 2014, 25(4): 826-838.

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

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

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

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

梁興柱(1979-)，男，安徽長(zhǎng)豐人，講師，碩士。主要研究方向?yàn)槟Ｊ阶R(shí)別、網(wǎng)絡(luò)安全等。E-mail：lxz9117@126.com