劉勇進(jìn)，趙敬紅

(沈陽(yáng)航空航天大學(xué) a 理學(xué)院;b 計(jì)算機(jī)學(xué)院，沈陽(yáng) 110136)

?

信息科學(xué)與工程

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

劉勇進(jìn)a，趙敬紅b

(沈陽(yáng)航空航天大學(xué) a 理學(xué)院;b 計(jì)算機(jī)學(xué)院，沈陽(yáng) 110136)

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

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

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

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

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

1最近鄰?fù)拱诸?lèi)器

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

(1)

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

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

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

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

(2)

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

(3)

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

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

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

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

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

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

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

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

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

(4)

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

(5)

Step5:計(jì)算測(cè)試點(diǎn)y與每一類(lèi)凸包模型差值近似等價(jià)距離的度量結(jié)果：

(6)

Output:測(cè)試樣本點(diǎn)y的類(lèi)別標(biāo)簽:

label(y)=afgmindi(y)

(7)

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

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

4實(shí)驗(yàn)及分析

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

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

表1　實(shí)驗(yàn)對(duì)比表(識(shí)別率%)

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

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

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

圖1　SVM、1NN、NNCH、LRR_l1NNCH各組識(shí)別率比較

5結(jié)論

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

參考文獻(xiàn)(References)：

[1]彭義剛，索金莉，戴瓊海，等.從壓縮傳感到低秩矩陣恢復(fù)：理論與應(yīng)用[J].自動(dòng)化學(xué)報(bào)，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)合稀疏表示人臉識(shí)別算法[A].電子學(xué)報(bào)，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]元曉振，王慶.一種基于稀疏編碼的多核學(xué)習(xí)圖像分類(lèi)方法[J].電子學(xué)報(bào)，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ù)拱诸?lèi)器在人臉識(shí)別中的應(yīng)用[J].計(jì)算機(jī)科學(xué)，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]鄧乃揚(yáng)，田英杰.數(shù)據(jù)挖掘中的新方法-支持向量機(jī)[M].北京：科學(xué)出版社，2004.

[13]劉建偉，李雙成，付捷,等.L1范數(shù)正則化SVM聚類(lèi)算法[J].計(jì)算機(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.

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

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

中圖分類(lèi)號(hào)：O224

文獻(xiàn)標(biāo)志碼：A

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

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金面上項(xiàng)目(項(xiàng)目編號(hào)：11371255)；遼寧省高等學(xué)校優(yōu)秀科技人才支持計(jì)劃(項(xiàng)目編號(hào)：LR2015047)

收稿日期：2015-09-23