基于稀疏恢復(fù)的l1范數(shù)凸包分類器在人臉識別中的應(yīng)用

劉勇進，趙敬紅

(沈陽航空航天大學 a 理學院;b 計算機學院，沈陽 110136)

?

信息科學與工程

基于稀疏恢復(fù)的l1范數(shù)凸包分類器在人臉識別中的應(yīng)用

劉勇進a，趙敬紅b

(沈陽航空航天大學 a 理學院;b 計算機學院，沈陽 110136)

摘要：人臉識別是統(tǒng)計模式識別領(lǐng)域中經(jīng)典的分類問題，為了提高算法的分類性能，優(yōu)化技術(shù)被廣泛應(yīng)用到人臉識別領(lǐng)域。提出基于稀疏恢復(fù)的l1范數(shù)凸包分類算法，將原始訓練數(shù)據(jù)集進行低秩恢復(fù)，利用恢復(fù)出的低秩矩陣和誤差矩陣構(gòu)成新訓練集字典建立各類訓練樣本凸包模型，并在l1范數(shù)意義下，計算觀測樣本與各類凸包模型差值，用所得差值等價觀測樣本到各類樣本凸包的距離，將距離最小的一類視為判別輸出類。在ORL(Olivetti Research Lab)標準人臉圖像庫上進行實驗分析，實驗證明基于稀疏恢復(fù)的l1范數(shù)凸包分類算法具有較高的識別效率。

關(guān)鍵詞：人臉識別；l1范數(shù)；凸包；距離

隨著優(yōu)化技術(shù)和壓縮感知[1]的不斷深入研究，模式識別中的人臉分類問題備受關(guān)注，為了優(yōu)化算法的效率，優(yōu)化技術(shù)被應(yīng)用到人臉的分類中。一般意義上，我們所指的統(tǒng)計模式中的模式是由多個高維空間中的各個點組成的。因此，模式識別中的分類問題可以看作是對高維空間中點的分類，人臉識別中相同類別人臉的分類問題可以用兩類圖像距離差的最小值表示[2]。在線性賦范空間中，我們可以把歐式空間中不同模式之間的相似性測量等價于范數(shù)問題。范數(shù)通常被看作是重要的測度工具，在統(tǒng)計模式識別以及優(yōu)化技術(shù)中，不同的范數(shù)標準具有不同的物理意義以及分類結(jié)果，其中，l1范數(shù)、l2范數(shù)和l∞范數(shù)應(yīng)用最為普遍。本文算法在l1范數(shù)意義下，利用低秩恢復(fù)出的新字典進行人臉分類。

隨著l1范數(shù)最優(yōu)化技術(shù)的發(fā)展，近年來，低秩子空間恢復(fù)[3]被引入到模式識別領(lǐng)域，并受到諸多學者的廣泛關(guān)注。眾所周知，一般的人臉分類都是基于單一個體的人臉圖像可以被多張人臉圖像線性表示，并位于同一個低秩子空間中，然而在現(xiàn)實世界中，由于光照、遮擋、表情以及姿態(tài)變化等多種因素的影響，我們得到的人臉圖像往往不再具有原來的低秩結(jié)構(gòu)，這直接影響了判別的正確性。最近幾年，Ma、Candes[4-5]對人臉圖像矩陣的低秩恢復(fù)進行了大量的研究并提出了一些有深遠意義的思想，提出了一種有效的矩陣低秩恢復(fù)算法(Low Rank Matrix Recovery，LRR)，該算法可以將訓練集人臉圖像恢復(fù)成兩個矩陣，分別是低秩矩陣和誤差矩陣。Candes、Ma等人[5-6]通過將低秩恢復(fù)理論應(yīng)用于人臉的分類，進一步優(yōu)化了算法的性能，提高了實驗的判別效果。元曉振、王慶[7]提出了一種多核學習的方法，利用空間信息限制求解矩陣權(quán)重。Yang、Zhang[8]利用Gabor的特征對訓練字典進行了壓縮處理。

鑒于以上方法破壞了人臉圖像的低秩結(jié)構(gòu)，本文提出了基于稀疏恢復(fù)的l1范數(shù)凸包分類算法，將原始矩陣分解恢復(fù)出的低秩和誤差矩陣構(gòu)成新訓練集字典應(yīng)用到最近鄰?fù)拱诸惼魃线M行人臉識別。首先，將訓練集圖像分解成兩個不同的矩陣，其中一個為低秩矩陣，即不受噪聲污染的“干凈”臉，另一個為誤差矩陣，即從原始人臉圖像中分離出的噪聲部分。其次利用低秩矩陣和稀疏誤差矩陣構(gòu)成的新訓練集字典建立各類訓練樣本的凸包模型，計算測試樣本與訓練字典各類凸包模型的差值，再利用差值等價觀測樣本點到訓練集各類樣本凸包模型的距離進行人臉圖像的分類。本文在ORL標準人臉庫上進行實驗，將基于稀疏恢復(fù)的范數(shù)凸包分類算法與支持向量機(Support Vector Machine，SVM)[9]、最近鄰分類器(1 Nearest Neighbor，1NN)[9]和最近鄰?fù)拱诸惼?Nearest Neighbor Convex Hull，NNCH)[9]做了實驗對比，結(jié)果顯示基于稀疏恢復(fù)的l1范數(shù)凸包分類算法相較于其他分類器識別率更高。

1最近鄰?fù)拱诸惼?/p>

最近鄰?fù)拱诸惼?NNCH)[9]是周曉飛等人提出的一種新型分類器，其主要是將訓練集各類樣本分別建立凸包模型，以凸包作為原始數(shù)據(jù)各類樣本的粗略估算，將測試樣本點與每類凸包模型的差值等價測試點到凸包的距離作為人臉圖像分類的標準，選取其中距離最短的一類作為最終的結(jié)果輸出類。最近鄰?fù)拱诸惼飨噍^于最近鄰分類器識別效果更好，凸包模型的引入使得原始訓練點集的分布得到了最大限度的擴展。

(1)

周曉飛等人利用該模型進行了一系列實驗分析，實驗結(jié)果證明了在l1范數(shù)意義下比在l2范數(shù)意義下對人臉圖像的識別率更高，相較于1NN、NNCH、SVM分類器，其識別效率最好。

2低秩子空間恢復(fù)

一般的人臉分類方法都是處于相同的低秩子空間中，并且同一個人的單張人臉圖像可以被多張人臉圖像線性表示，然而在現(xiàn)實世界中，由于受到光照、遮擋、表情、姿態(tài)變化的影響，我們得到的圖像往往不再具有原來的低秩結(jié)構(gòu)，嚴重影響了分類的性能[15]。因此，如何正確地從受到污染的圖像中分離出誤差部分，即恢復(fù)出低秩人臉子空間，是本文的研究重點。

設(shè)矩陣D中有N類數(shù)據(jù)，D=[D1,D2,…,DN],對矩陣D進行低秩恢復(fù)，得到低秩矩陣A和誤差矩陣E，因此，可表示為D=A+E。其中，A表示該類的“干凈”臉圖像，具有低秩結(jié)構(gòu)，E表示被分離出的破壞圖像低秩結(jié)構(gòu)的誤差，即原始人臉圖像中的遮擋、光照、表情以及姿態(tài)部分，且此誤差項在空間域上是稀疏的。我們可以將上述低秩恢復(fù)算法的求解看作是凸優(yōu)化中求最小秩的問題：

(2)

其中i=1,2,…,N,λ可以控制A和E之間的平衡關(guān)系。但是公式(2)很難解出最優(yōu)解，其是NP難問題，John、Ma等人[3]提出在特定條件下，l0范數(shù)能夠轉(zhuǎn)化為l1范數(shù)，同時秩可以轉(zhuǎn)化為核范數(shù)，因此公式(2)可以近似地等價求解以下凸優(yōu)化問題：

(3)

其中i=1,2,…,N，||||1是l1范數(shù)，表示矩陣中所有元素的絕對值之和。||||*是核范數(shù)，表示矩陣的奇異值之和。

3基于稀疏恢復(fù)的l1范數(shù)凸包分類器

通過上述分析可知，如何正確地從受到遮擋、光照、表情以及姿態(tài)等污染的人臉圖像中分解出低秩人臉子空間，也就是分離出受到污染的誤差部分，是基于稀疏恢復(fù)的l1范數(shù)凸包分類器識別率提高的關(guān)鍵。

本文提出基于稀疏恢復(fù)的l1范數(shù)凸包分類算法，將低秩矩陣分解理論以及l(fā)1范數(shù)凸包分類器應(yīng)用于人臉分類中，首先，將訓練集D恢復(fù)成兩個不同的矩陣，其中一個為低秩矩陣A，另一個為誤差矩陣E，其中，低秩矩陣A表示恢復(fù)出的未受噪聲污染的人臉，遵循低秩子空間結(jié)構(gòu)，矩陣E表示從原始人臉圖像分離出的遮擋、光照、表情以及姿態(tài)等誤差部分，其次利用矩陣A和矩陣E組成的新字典建立各類凸包模型，將觀測樣本與凸包模型的差值近似等價觀測樣本到凸包模型的距離作為人臉圖像分類標準，選取其中距離最小的一類作為最終結(jié)果輸出類。

基于稀疏恢復(fù)的l1范數(shù)凸包分類算法步驟：

Input：設(shè)訓練集D=[D1,D2，…，DN]，觀測樣本y，參數(shù)λ>0,ε>0。

Step1：分別對訓練集D中的每一類人臉進行低秩恢復(fù)，即Di=Ai+Ei，利用恢復(fù)出的低秩矩陣A和稀疏誤差矩陣E組成新字典B=[A,E]。

Step2:將新訓練集B數(shù)據(jù)進行歸一化，使其具有l(wèi)2范數(shù)。

Step3:由壓縮感知理論可知，在α，β充分稀疏的情況下，可以通過求解l1范數(shù)問題求解以下最優(yōu)解：

(4)

Step4:利用構(gòu)造出的新字典B分別建立各類凸包模型:

(5)

Step5:計算測試點y與每一類凸包模型差值近似等價距離的度量結(jié)果：

(6)

Output:測試樣本點y的類別標簽:

label(y)=afgmindi(y)

(7)

對于人臉圖像的分類問題，運用以上模型對原始訓練樣本進行低秩分解，然后利用分解的新字典分別建立各類訓練樣本凸包模型，即conv(Bi)，計算測試樣本點到各類凸包的l1范數(shù)距離d(y,conv(Bi))=min||y-Aα-Eβ||1，最后依據(jù)最近鄰原則選取距離最小的一類作為判別輸出類。

基于稀疏恢復(fù)的l1范數(shù)凸包分類器在多分類問題中無需設(shè)置參數(shù)，雖然支持向量機(SVM)也可以看作是通過建立訓練樣本凸包模型進行分類，但與本文算法區(qū)別在于支持向量機(SVM)只適用于二分類問題，在多分類問題中并不適用。

4實驗及分析

本文將基于稀疏恢復(fù)的l1范數(shù)凸包分類器用于人臉識別，并在ORL(OlivettiResearchLab)標準人臉庫上進行實驗。ORL標準人臉圖像庫中共有400幅人臉圖像，其中每個人分別擁有10幅圖像，且全部為灰度圖像，其格式統(tǒng)一為“.PGM”，這10幅圖像分別用數(shù)字“1,2，…，10”依次編號，圖像中含有遮擋、光照、表情以及姿態(tài)等造成的誤差。在實驗過程中，我們將人臉圖像的格式全部轉(zhuǎn)換為“.JPG”，并將圖像進行雙三次差值，按列展開，形成一維向量的形式。

本文取40個人中每人5張作為訓練字典，余下的當作觀測樣本，樣本的選擇次序根據(jù)編號依次提取，首尾相接。我們將本文算法分別與1NN,NNCH和SVM進行比較分析。實驗結(jié)果如表1所示。

表1　實驗對比表(識別率%)

其中，識別率=識別出的圖像數(shù)量/人臉圖像總數(shù)。

表1中可以分析出，第1、3組實驗結(jié)果顯示SVM分類器實驗結(jié)果的識別率相較于其他分類器最低，基于稀疏恢復(fù)的l1范數(shù)凸包分類算法的識別率最高，最近鄰?fù)拱诸惼飨噍^于最近鄰分類器的識別率偏低，在第4組實驗中基于稀疏恢復(fù)的l1范數(shù)凸包分類算法的識別率達到最高，效果最好。

圖1顯示，第6組實驗4種算法的識別效率都呈現(xiàn)下降趨勢，從數(shù)據(jù)庫中我們分析出其主要受到表情和姿態(tài)變化的影響較大。

圖1　SVM、1NN、NNCH、LRR_l1NNCH各組識別率比較

5結(jié)論

本文針對人臉在高維空間低秩結(jié)構(gòu)被破壞的問題，利用凸包粗略逼近原始數(shù)據(jù)，將人臉的分類轉(zhuǎn)化為在l1范數(shù)測度下，計算測試樣本點與每一類凸包模型的差值，即點到凸包的距離測量問題，提出基于稀疏恢復(fù)的l1范數(shù)凸包分類算法，并應(yīng)用到人臉識別領(lǐng)域。通過與SVM、1NN和NNCH進行對比分析，結(jié)果表明本文算法的分類性能高于其他算法。

參考文獻(References)：

[1]彭義剛，索金莉，戴瓊海，等.從壓縮傳感到低秩矩陣恢復(fù)：理論與應(yīng)用[J].自動化學報，2013，39(7)：981-988.

[2]SHI J B，MALIK J.Normalized cuts and image segmentation[J].IEEE Trans.on Pattern Analysis and Machine Intelligence，2000，22(8)：888-905.

[3]胡正平，李靜.基于低秩子空間恢復(fù)的聯(lián)合稀疏表示人臉識別算法[A].電子學報，2013，41(5)：987-989.

[4]CAI J，CANDES E，SHEN Z.A singular value thresholding algorithm for matrix completion[J].SIAM Journal on Optimization，2010，20(4)：1956-1982.

[5]CANDES E，LI X，MA Y，et al.Robust principal component analysis[J].Journal of the ACM，2011，58(3)：112-115.

[6]WRIGHT J，PENG Y，MA Y.Robust principal component analysis:exact recovery of corrupted low-rank matrices by convex optimization[A].23rd Annual Conference on Neural Information Processing Systems，2009：2080-2088.

[7]元曉振，王慶.一種基于稀疏編碼的多核學習圖像分類方法[J].電子學報，2012，40(4)：773-779.

[8]YANG M，ZHANG L.Gabor feature based sparse represen for face recognition with gabor occlusion dictionary[A].Europeon Conference on Computer Vision，2010，448-461.

[9]周曉飛，姜文瀚，楊靜宇.l_1范數(shù)最近鄰?fù)拱诸惼髟谌四樧R別中的應(yīng)用[J].計算機科學，2007，34(4)：234-238.

[10]ROWEIS S，SAUL L.Nonlinear dimensionality reduction by locally linear embedding[J].Science，2000，290(5500)：2323-2326.

[11]LI S Z，LU J.Face recognition using the nearest feature line method[J].IEEE Trans Neural Networks，1999，10：439-443.

[12]鄧乃揚，田英杰.數(shù)據(jù)挖掘中的新方法-支持向量機[M].北京：科學出版社，2004.

[13]劉建偉，李雙成，付捷,等.L1范數(shù)正則化SVM聚類算法[J].計算機工程，2012，38(12)：185-187.

[14]MAIRAL J，ELAD M，SAPIRO G.Sparse represent-ation for color image restoration[J].IEEE Trans.Image Processing，2008，17(1)：53-69.

[15]MAIRAL J，BACH F，PONCE J.Nonlocal sparse models for image restoration[C].Proc.ICCV，2009，2272-2279.

(責任編輯：劉劃英文審校：隋華)

Application ofl1norm convex hull classifier based on sparse recovery to face recognition

LIU Yong-jina，ZHAO Jing-hongb

(a.College of Science; b.College of Computer Science,Shenyang Aerospace University,Shenyang,110136,China)

Abstract：In order to improve the classification performance of the algorithms,optimization technology is widely used in the field of face recognition,which is considered as a classical classification problem of statistical pattern recognition.In this paper,an l1norm convex hull classification algorithm based on sparse recovery is put forward.Low rank matrix is recovered from the original training data,and then convex hulls of different training -sample models are established in the light of the new training set dictionary composed of the recovered low rank matrix and error matrix.In the sense of l1norm,the difference between test sample and various kinds of convex hull model is calculated.The results are then used to test the distance between sample and various kinds of convex hull,and the category with smallest distance is considered as discriminant output class.The experimental analysis conducted on the ORL (Olivetti Research Lab) face image database shows that l1norm convex hull classification algorithm based on sparse recovery has higher recognition efficiency.

Key words：face recognition;l1norm;convex hull;distance

doi:10.3969/j.issn.2095-1248.2016.01.009

中圖分類號：O224

文獻標志碼：A

文章編號：2095-1248(2016)01-0042-05

作者簡介：劉勇進(1977-)，男，江西贛州人，教授，主要研究方向：矩陣優(yōu)化，變分分析與優(yōu)化，數(shù)值計算，E-mail:yjliu@sau.edu.cn。

基金項目：國家自然科學基金面上項目(項目編號：11371255)；遼寧省高等學校優(yōu)秀科技人才支持計劃(項目編號：LR2015047)

收稿日期：2015-09-23