无参数无相关最大化判别边界算法

梁兴柱，林玉娥，许光宇



无参数无相关最大化判别边界算法

梁兴柱，林玉娥，许光宇

(安徽理工大学计算机科学与工程学院，安徽 淮南 232001)

在人脸识别算法中，无参数局部保持投影(PFLPP)是一种有效的特征提取算法，但忽略了异类近邻样本在分类中所起的作用，并且对于近邻的处理仅利用样本与总体均值的距离关系来判断，因此并不能有效地确定近邻关系。基于此，提出一种无参数无相关最大化判别边界算法，有效地利用了样本的类别信息，定义了无参数同类近邻样本的相似权值与异类近邻样本的惩罚权值，样本邻域大小可根据类内平均余弦距离和类间余弦距离自适应确定，为了进一步增强算法的性能，给出了具有不相关性的目标函数。UMIST和AR人脸库上的实验结果表明，该算法相对于不相关保局投影分析算法和PFLPP算法，具有运算量低、识别性能高的优势。

人脸识别；特征提取算法；无参数；无相关

目前，人脸识别技术已广泛地被应用，而特征提取算法是人脸识别技术的一个关键环节。近年来，主要的特征提取算法有，基于全局思想的主成分分析(principal component analysis，PCA)[1]和线性判别分析(linear discriminant analysis，LDA)[1]算法，基于局部保持思想的保局投影映射(locality preserving projections，LPP)[2]。其中LPP是以保持样本的局部结构为目标，可以提取出更加有效的分类特征，因此学者们提出了大量的改进方案，如XU等[3]提出的边界近邻判别分析算法，既有类似于LDA的目标函数，同时又能保持样本的局部结构信息，因此取得了较好的识别结果；一般通过对所求投影矩阵进行约束限制，可以有效地提高算法的识别性能，文献[4-7]提出了具有正交性约束或不相关性约束的改进算法；文献[8]则针对局部保持投影的近邻权值构造进行了研究，由于传统的近邻权值是基于欧氏距离的，而欧氏距离对于样本噪声非常敏感，因此提出了稀疏判别局部保持投影算法；但上述算法在应用于人脸识别问题中均会遇到小样本问题，对此文献[9-10]提出了基于大间距的目标函数，文献[11-12]提出基于矩阵指数变换的策略。但是针对小样本问题，文献[9-12]所提的算法均是基于向量模式的，即需要人脸图像按行或列拉直成一维向量，为此文献[13-14]结合人脸图像的固有特点提出了基于图像模式的局部保持算法，并给出了基于1范式的目标函数，其有效地解决了小样本问题，而且具有更加稳定的数值解，从而进一步增强了算法的性能。

然而上述算法，均需设置参数，即样本近邻的大小及近邻权值。参数的取值将直接影响着算法的识别性能，因此如何自适应地设置算法的参数是当前一个有意义的研究。对此参数选择问题，文献[15-20]分别提出了不同的改进方案，其中文献[15]提出了基于样本余弦距离的无参数局部保持投影算法(parameter-free locality preserving projection，PFLPP)，有效地解决了算法参数设置问题。PFLPP使用样本余弦距离作为近邻的权值，近邻大小通过样本与总体均值的余弦距离比较动态确定样本的近邻，有效地保持了样本的局部结构，并取得了较好的识别结果。PFLPP无需设置参数，更适合实际的分类问题，然而其忽略了异类近邻样本的作用，而且仅考虑与总体均值进行比较的近邻配置方案并不能有效地保持样本的局部近邻结构，同时也未对所求投影矩阵进行约束限制，基于此，本文提出一种无参数无相关最大化判别边界算法(parameter-free uncorrelated maximum discriminant margin algorithm，PUMDMA)。PUMDMA重新定义了同类近邻相似权值和异类近邻惩罚权值，给出了采用样本的类内距离和类间距离的自适应近邻配置方案，无需任何参数设置。为了提取出更加有效的分类特征，PUMDMA的目标函数加入了不相关约束条件。本文的目标是先求解出样本的不相关空间；然后在此空间中求出能最大化异类矩阵的同时，最小化同类相似近邻矩阵的投影矩阵；最后，UMIST和AR人脸库上的实验结果验证了PUMDMA的有效性。

1 无参数局部保持投影算法

首先介绍PFLPP的算法原理。

因为人脸图像每个像素点的取值都是非负数，所以式(1)的取值范围为0,)≤1。余弦距离表明了2个样本向量和之间的夹角关系，2个样本越相似其夹角越小，因此和的cos(,)越大，即cos(,)的值越接近１。反之，2个样本和的相似度越低其夹角越大，因此和的cos(,)就越小。在PFLPP中，对于任意2个样本和之间近邻相似权值S的计算为

其中，为所有样本的总体均值。

若要考虑样本的类别信息，则式(2)需要添加限制类别的条件，即

PFLPP的目标函数为

2 无参数无相关最大化判别边界算法

2.1 PUMDMA的原理

由PFLPP的近邻权值计算式(2)和式(3)，表明其仅考虑了样本的近邻关系，却忽略了异类近邻样本在分类中所起的作用，而且其近邻配置方案采用总体均值进行邻域确定并不能有效地保持样本的局部近邻结构。故此，本文提出PUMDMA算法，考虑了同类近邻样本与异类近邻样本的作用，同时给出一种改进的自适应近邻确定方案，PUMDMA目标函数能够在保持同类样本近邻结构的同时，最大化异类近邻边界，从而达到正确分类的目标。首先给出2个定义。

定义1和2给出了类内平均余弦距离和类间余弦距离的定义与计算方法。根据定义1和2，分别给出本文的无参数同类近邻样本相似权值和无参数异类近邻样本惩罚权值的计算公式。

假设2个样本和为同类样本，则其近邻相似权值计算为

同理假设样本和是异类样本，则其近邻惩罚权值计算为

结合式(7)和式(8)分别定义无参数类内相似矩阵和无参数类间惩罚矩阵，计算为

计算为

PUMDMA的目标寻找投影矩阵，能够最大化无参数类间惩罚矩阵，同时能够最小化无参数类内相似矩阵，故有

在模式识别中，通常具有不相关的投影矩阵可以提高算法的识别率[21]，若要使所求得的投影矩阵具有不相关性，应满足

2.2 PUMDMA的求解过程

对于人脸识别问题，由于图像的维数太高，即存在着小样本问题，因此对于式(13)并不能直接求解，为此可将式(13)改写最大化差形式的目标函数

对PUMDMA具体求解步骤归纳如下：

(2) 根据式(9)和式(10)分别计算出无参数类内近邻相似矩阵和无参数类间惩罚矩阵；

3 算法的测试与分析

针对PUMDMA、ULPP和PFLPP3种算法提取特征数目与识别率的变化进行了比较，分析了3种算法识别性能的变化情况，实验结果如图1和图2所示。本次实验中，选择2个人脸库的每人前6幅作为训练样本，剩余图像作为测试样本。

图1 在UMIST人脸库上识别率与特征数目的变化

图2 在AR人脸库上识别率与特征数目的变化

图1和图2的结果表明了随着特征数目增加，PUMDMA、ULPP和PFLPP 3种算法识别率的变化情况。无论是在小的测试集UMIST人脸库，还是大的测试集AR人脸库上，PUMDMA均取得了优于ULPP和PFLPP较好地识别结果。另可以发现在特征与类别大约一致的时候，3种算法均取得了较稳定的识别结果，说明PUMDMA采用余弦距离作为权系数，自适应方式确定样本近邻及其不相关的约束是可行有效的。

为了进一步测试算法的性能，在UMIST和AR两个人脸库分别取训练样本5~8个，余下图像作为测试样本，每次随机选择训练样本，进行10次重复，用10次的平均结果作为每种算法的识别结果，见表1和表2。

表1 UMIST人脸库上的识别结果(%)

表2 AR人脸库上的识别结果(%)

表1和表2的结果表明了PUMDMA的识别结果明显优于另外2种算法的识别结果，是因为PUMDMA综合了ULPP和PFLPP算法的优势，既具有不相关性的约束，又无需参数的设置。PUMDMA也改进了PFLPP不足，其目标函数兼顾了同类近邻样本和异类近邻样本的作用，并能够自适应地确定样本近邻，因此能更好地保持样本的局部结构，从而提取出判别能力更强的特征。另外，由于PUMDMA的目标函数采用最大化差形式，也避免了人脸识别中的小样本问题。因此，PUMDMA取得了最好地识别结果。

基于局部保持投影的算法都需要计算所有样本间的距离，然后再进行由小到大的排序，选出前个近邻，构成近邻矩阵。而本文算法是无需进行排序，排序改为比较运算，因此计算量并没有增加。如果采用快速排序的时间复杂度为(nlogn)，而本文的比较时间复杂度为()。为此本文对上述3种算法投影矩阵计算时间进行了比较，在2个数据库上分别选择前5个样本作为训练样本，对于3种算法的最优投影矩阵计算时间进行了测试，结果见表3。

表3 AR方法运算时间比较(s)

从表3可以看出，本文算法的计算速度快于ULPP算法，ULPP算法也同时考虑了同类与异类样本，但本文算法无需排序计算；而相对PFLPP要多花一些时间，是因为PFLPP仅考虑了同类近邻，而没有考虑异类近邻，但从识别结果来看，有关损失是值得的。

4 结束语

本文针对PFLPP的不足，提出了PUMDMA，其特点是无需设置参数，同时考虑同类与异类近邻在分类中的作用，并要求投影矩阵具有不相关性。因此，PUMDMA首先定义了无参数的同类近邻样本相似权值和异类近邻样本惩罚权值的计算公式，对于同类与异类近邻样本的确定，可根据样本与类内平均余弦距离和样本与类间余弦距离的关系自适应确定，最后给出了PUMDMA的目标函数及相应的求解步骤。UMIST和AR人脸库的实验结果表明该方法的有效性和可行性。

[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] 龚劬, 唐萍峰. 基于大间距准则的不相关保局投影分析[J]. 自动化学报, 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] 黄璞, 唐振民. 无参数局部保持投影及人脸识别[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].软件学报, 2014, 25(4): 826-838.

[18] 何进荣, 闭应洲, 丁立新, 等. 局部差异正则化的边界判别投影[J]. 计算机学报, 2018, 41(4): 780-795.

[19] 赵振华, 郝晓弘. 局部保持鉴别投影及其在人脸识别中的应用[J]. 电子与信息学报, 2013, 35(2): 463-467.

[20] 陈才扣, 侯钰. 非相似度保持投影[J]. 中国图象图形学报, 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

国家自然科学基金项目(61471004)；安徽高校自然科学研究项目(KJ2016A203，KJ2018A0084)

梁兴柱(1979-)，男，安徽长丰人，讲师，硕士。主要研究方向为模式识别、网络安全等。E-mail：lxz9117@126.com