基于稀疏恢复的l1范数凸包分类器在人脸识别中的应用

刘勇进，赵敬红

(沈阳航空航天大学 a 理学院;b 计算机学院，沈阳 110136)



信息科学与工程

基于稀疏恢复的l1范数凸包分类器在人脸识别中的应用

刘勇进a，赵敬红b

(沈阳航空航天大学 a 理学院;b 计算机学院，沈阳 110136)

摘要：人脸识别是统计模式识别领域中经典的分类问题，为了提高算法的分类性能，优化技术被广泛应用到人脸识别领域。提出基于稀疏恢复的l1范数凸包分类算法，将原始训练数据集进行低秩恢复，利用恢复出的低秩矩阵和误差矩阵构成新训练集字典建立各类训练样本凸包模型，并在l1范数意义下，计算观测样本与各类凸包模型差值，用所得差值等价观测样本到各类样本凸包的距离，将距离最小的一类视为判别输出类。在ORL(Olivetti Research Lab)标准人脸图像库上进行实验分析，实验证明基于稀疏恢复的l1范数凸包分类算法具有较高的识别效率。

关键词：人脸识别；l1范数；凸包；距离

随着优化技术和压缩感知[1]的不断深入研究，模式识别中的人脸分类问题备受关注，为了优化算法的效率，优化技术被应用到人脸的分类中。一般意义上，我们所指的统计模式中的模式是由多个高维空间中的各个点组成的。因此，模式识别中的分类问题可以看作是对高维空间中点的分类，人脸识别中相同类别人脸的分类问题可以用两类图像距离差的最小值表示[2]。在线性赋范空间中，我们可以把欧式空间中不同模式之间的相似性测量等价于范数问题。范数通常被看作是重要的测度工具，在统计模式识别以及优化技术中，不同的范数标准具有不同的物理意义以及分类结果，其中，l1范数、l2范数和l∞范数应用最为普遍。本文算法在l1范数意义下，利用低秩恢复出的新字典进行人脸分类。

随着l1范数最优化技术的发展，近年来，低秩子空间恢复[3]被引入到模式识别领域，并受到诸多学者的广泛关注。众所周知，一般的人脸分类都是基于单一个体的人脸图像可以被多张人脸图像线性表示，并位于同一个低秩子空间中，然而在现实世界中，由于光照、遮挡、表情以及姿态变化等多种因素的影响，我们得到的人脸图像往往不再具有原来的低秩结构，这直接影响了判别的正确性。最近几年，Ma、Candes[4-5]对人脸图像矩阵的低秩恢复进行了大量的研究并提出了一些有深远意义的思想，提出了一种有效的矩阵低秩恢复算法(Low Rank Matrix Recovery，LRR)，该算法可以将训练集人脸图像恢复成两个矩阵，分别是低秩矩阵和误差矩阵。Candes、Ma等人[5-6]通过将低秩恢复理论应用于人脸的分类，进一步优化了算法的性能，提高了实验的判别效果。元晓振、王庆[7]提出了一种多核学习的方法，利用空间信息限制求解矩阵权重。Yang、Zhang[8]利用Gabor的特征对训练字典进行了压缩处理。

鉴于以上方法破坏了人脸图像的低秩结构，本文提出了基于稀疏恢复的l1范数凸包分类算法，将原始矩阵分解恢复出的低秩和误差矩阵构成新训练集字典应用到最近邻凸包分类器上进行人脸识别。首先，将训练集图像分解成两个不同的矩阵，其中一个为低秩矩阵，即不受噪声污染的“干净”脸，另一个为误差矩阵，即从原始人脸图像中分离出的噪声部分。其次利用低秩矩阵和稀疏误差矩阵构成的新训练集字典建立各类训练样本的凸包模型，计算测试样本与训练字典各类凸包模型的差值，再利用差值等价观测样本点到训练集各类样本凸包模型的距离进行人脸图像的分类。本文在ORL标准人脸库上进行实验，将基于稀疏恢复的范数凸包分类算法与支持向量机(Support Vector Machine，SVM)[9]、最近邻分类器(1 Nearest Neighbor，1NN)[9]和最近邻凸包分类器(Nearest Neighbor Convex Hull，NNCH)[9]做了实验对比，结果显示基于稀疏恢复的l1范数凸包分类算法相较于其他分类器识别率更高。

1最近邻凸包分类器

最近邻凸包分类器(NNCH)[9]是周晓飞等人提出的一种新型分类器，其主要是将训练集各类样本分别建立凸包模型，以凸包作为原始数据各类样本的粗略估算，将测试样本点与每类凸包模型的差值等价测试点到凸包的距离作为人脸图像分类的标准，选取其中距离最短的一类作为最终的结果输出类。最近邻凸包分类器相较于最近邻分类器识别效果更好，凸包模型的引入使得原始训练点集的分布得到了最大限度的扩展。

(1)

周晓飞等人利用该模型进行了一系列实验分析，实验结果证明了在l1范数意义下比在l2范数意义下对人脸图像的识别率更高，相较于1NN、NNCH、SVM分类器，其识别效率最好。

2低秩子空间恢复

一般的人脸分类方法都是处于相同的低秩子空间中，并且同一个人的单张人脸图像可以被多张人脸图像线性表示，然而在现实世界中，由于受到光照、遮挡、表情、姿态变化的影响，我们得到的图像往往不再具有原来的低秩结构，严重影响了分类的性能[15]。因此，如何正确地从受到污染的图像中分离出误差部分，即恢复出低秩人脸子空间，是本文的研究重点。

设矩阵D中有N类数据，D=[D1,D2,…,DN],对矩阵D进行低秩恢复，得到低秩矩阵A和误差矩阵E，因此，可表示为D=A+E。其中，A表示该类的“干净”脸图像，具有低秩结构，E表示被分离出的破坏图像低秩结构的误差，即原始人脸图像中的遮挡、光照、表情以及姿态部分，且此误差项在空间域上是稀疏的。我们可以将上述低秩恢复算法的求解看作是凸优化中求最小秩的问题：

(2)

其中i=1,2,…,N,λ可以控制A和E之间的平衡关系。但是公式(2)很难解出最优解，其是NP难问题，John、Ma等人[3]提出在特定条件下，l0范数能够转化为l1范数，同时秩可以转化为核范数，因此公式(2)可以近似地等价求解以下凸优化问题：

(3)

其中i=1,2,…,N，||||1是l1范数，表示矩阵中所有元素的绝对值之和。||||*是核范数，表示矩阵的奇异值之和。

3基于稀疏恢复的l1范数凸包分类器

通过上述分析可知，如何正确地从受到遮挡、光照、表情以及姿态等污染的人脸图像中分解出低秩人脸子空间，也就是分离出受到污染的误差部分，是基于稀疏恢复的l1范数凸包分类器识别率提高的关键。

本文提出基于稀疏恢复的l1范数凸包分类算法，将低秩矩阵分解理论以及l1范数凸包分类器应用于人脸分类中，首先，将训练集D恢复成两个不同的矩阵，其中一个为低秩矩阵A，另一个为误差矩阵E，其中，低秩矩阵A表示恢复出的未受噪声污染的人脸，遵循低秩子空间结构，矩阵E表示从原始人脸图像分离出的遮挡、光照、表情以及姿态等误差部分，其次利用矩阵A和矩阵E组成的新字典建立各类凸包模型，将观测样本与凸包模型的差值近似等价观测样本到凸包模型的距离作为人脸图像分类标准，选取其中距离最小的一类作为最终结果输出类。

基于稀疏恢复的l1范数凸包分类算法步骤：

Input：设训练集D=[D1,D2，…，DN]，观测样本y，参数λ>0,ε>0。

Step1：分别对训练集D中的每一类人脸进行低秩恢复，即Di=Ai+Ei，利用恢复出的低秩矩阵A和稀疏误差矩阵E组成新字典B=[A,E]。

Step2:将新训练集B数据进行归一化，使其具有l2范数。

Step3:由压缩感知理论可知，在α，β充分稀疏的情况下，可以通过求解l1范数问题求解以下最优解：

(4)

Step4:利用构造出的新字典B分别建立各类凸包模型:

(5)

Step5:计算测试点y与每一类凸包模型差值近似等价距离的度量结果：

(6)

Output:测试样本点y的类别标签:

label(y)=afgmindi(y)

(7)

对于人脸图像的分类问题，运用以上模型对原始训练样本进行低秩分解，然后利用分解的新字典分别建立各类训练样本凸包模型，即conv(Bi)，计算测试样本点到各类凸包的l1范数距离d(y,conv(Bi))=min||y-Aα-Eβ||1，最后依据最近邻原则选取距离最小的一类作为判别输出类。

基于稀疏恢复的l1范数凸包分类器在多分类问题中无需设置参数，虽然支持向量机(SVM)也可以看作是通过建立训练样本凸包模型进行分类，但与本文算法区别在于支持向量机(SVM)只适用于二分类问题，在多分类问题中并不适用。

4实验及分析

本文将基于稀疏恢复的l1范数凸包分类器用于人脸识别，并在ORL(OlivettiResearchLab)标准人脸库上进行实验。ORL标准人脸图像库中共有400幅人脸图像，其中每个人分别拥有10幅图像，且全部为灰度图像，其格式统一为“.PGM”，这10幅图像分别用数字“1,2，…，10”依次编号，图像中含有遮挡、光照、表情以及姿态等造成的误差。在实验过程中，我们将人脸图像的格式全部转换为“.JPG”，并将图像进行双三次差值，按列展开，形成一维向量的形式。

本文取40个人中每人5张作为训练字典，余下的当作观测样本，样本的选择次序根据编号依次提取，首尾相接。我们将本文算法分别与1NN,NNCH和SVM进行比较分析。实验结果如表1所示。

表1　实验对比表(识别率%)

其中，识别率=识别出的图像数量/人脸图像总数。

表1中可以分析出，第1、3组实验结果显示SVM分类器实验结果的识别率相较于其他分类器最低，基于稀疏恢复的l1范数凸包分类算法的识别率最高，最近邻凸包分类器相较于最近邻分类器的识别率偏低，在第4组实验中基于稀疏恢复的l1范数凸包分类算法的识别率达到最高，效果最好。

图1显示，第6组实验4种算法的识别效率都呈现下降趋势，从数据库中我们分析出其主要受到表情和姿态变化的影响较大。

图1　SVM、1NN、NNCH、LRR_l1NNCH各组识别率比较

5结论

本文针对人脸在高维空间低秩结构被破坏的问题，利用凸包粗略逼近原始数据，将人脸的分类转化为在l1范数测度下，计算测试样本点与每一类凸包模型的差值，即点到凸包的距离测量问题，提出基于稀疏恢复的l1范数凸包分类算法，并应用到人脸识别领域。通过与SVM、1NN和NNCH进行对比分析，结果表明本文算法的分类性能高于其他算法。

参考文献(References)：

[1]彭义刚，索金莉，戴琼海，等.从压缩传感到低秩矩阵恢复：理论与应用[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]胡正平，李静.基于低秩子空间恢复的联合稀疏表示人脸识别算法[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范数最近邻凸包分类器在人脸识别中的应用[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]邓乃扬，田英杰.数据挖掘中的新方法-支持向量机[M].北京：科学出版社，2004.

[13]刘建伟，李双成，付捷,等.L1范数正则化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-)，男，江西赣州人，教授，主要研究方向：矩阵优化，变分分析与优化，数值计算，E-mail:yjliu@sau.edu.cn。

基金项目：国家自然科学基金面上项目(项目编号：11371255)；辽宁省高等学校优秀科技人才支持计划(项目编号：LR2015047)

收稿日期：2015-09-23