最大类间相斥的局部鉴别投影
开篇：润墨网以专业的文秘视角，为您筛选了一篇最大类间相斥的局部鉴别投影范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
【 摘 要 】 局部保持投影（LPP）算法，作为Laplacian特征映射的线性扩展表示，解决了非线性算法难以获得新样本低维投影的缺点。但是，由于它是一种没有标签信息的无监督方法，不能利用已知的类别信息提高分类率。为此，引入类别信息重新定义权值矩阵，提出带有局部类别信息的局部鉴别投影，使相邻近的同类样本尽量紧凑，相邻近的异类样本尽量分开。同时，针对局部鉴别投影不能充分利用全局类别信息的缺陷，提出最大类间相斥的局部鉴别投影（MRLDP），通过最大程度地扩大异类间均值中心距离，带动异类间样本分散分布，最终得到既保持内在流形信息又使异类距离最大化的投影矩阵，并将此算法用于人脸识别。该方法在 ORL 人脸库和Yale人脸库上进行了验证，取得了较好的人脸识别效果。
【 关键词 】 局部鉴别投影；线性判别分析；局部鉴别投影；流形学习；人脸识别
【 中图分类号 】 TP391.4 【 文献标识码 】 A
1 引言
在互联网金融高速发展的形势下，要鉴别远程操作者是否是人，是哪个人？成为了一个亟待解决的问题。人脸，作为生物特征之一，为这一问题提供新的解决思路。人脸识别中的重点和难点是对人的面部信息进行有效的特征抽取。人脸图像是一种高维数据，直接处理海量的高维大数据会带来复杂的计算和系统的不稳定。在尽量保持数据信息完整的前提下，把数据投影到一个合适的子空间中，以满足数据存储与算法的需要，成为生物识别技术研究中的热点。
经典的线性子空间投影的方法主要包含主成分分析（Principle Component Analysis， PCA）以及线性鉴别分析（Linear Discriminant Analysis， LDA）。PCA是基于主分量方向上映射，根据均方误差最小原则的，生成不相关的正交向量。PCA算法简单方便，Matthew Turk等人最先将PCA应用于人脸识别，并提出了Eigenface概念。这种方法是一种无监督的人脸特征抽取方法，没有用到人脸图像的类别信息。LDA算法通过引入标签信息，使投影后样本的类内离散度最小、类间离散度最大，从而生成最佳可分的子空间。Peter等人最先采用PCA算法解决了类内离散度矩阵奇异的问题，结合LDA提出了Fisherfaces算法应用于人脸识别，取得比PCA算法更优的分类效果。
2000 年，Seung 等人在《Science》上发表的文章把研究者的目光吸引到流形学习（Manifold Learning）领域。人脸被认为是一种由某些内在变量控制形成的非线性流形结构，更能体现现实中数据的本质，因此在人脸识别领域效果更优。Tenenbaum等人基于多维尺度变换（MDS），提出了等度规映射（Isometric Mapping， ISOMAP）算法。该算法通过保持样本点的内在局部几何结构，在降维的过程中保持样本间的测地距离不变。Sam等人提出的局部线性嵌入（Locality Linear Embedding， LLE）算法。在局部意义下，降维后的数据的结构是线性的，即是说局部意义下的样本点在一个超平面上。因此任意样本点都可以通过邻域内样本点的线性加权表示得到，并在降维时保留权值不变，得到最小重构误差。Belkin等人提出的Laplacian特征映射（Laplacian Eigenmap， LE）有着很直观的维数约简目标，即在高维空间中临近的样本点在低维度投影子空间中的样本也是邻近的。为了提高对训练样本以外的样本求取低维的投影向量，He对LE进行线性化扩展为局部保持投影（Locality Preserving Projection， LPP）以及对LLE的线性化扩展为邻域保持嵌入（Neighborhood Preserving Embedding， NPE），从而解决了非线性方法难以获得新样本点低维投影的缺点。对于上述算法，都可以在图嵌入框架下进行表示，通过图嵌入框架的应用还可以设计出新的降维算法。
LPP算法中需要把2D人脸图像1D向量，导致转换后图像维度很高，破坏了图像原有空间结构。Niu等人提出的二维局部保持投影（2DLPP）算法直接对2D图像进行运算，得到了更加易于求解的特征矩阵。Cai 等人提出了正交局部保持投影方法（OLPP），在求解过程中增加了正交约束条件，与LPP算法相比，具有更好的局部保持效果。
针对LPP算法没有有效地使用样本标签信息，大量的半监督以及监督算法被提出。Zhao等人采用了局部类别信息构造权重矩阵，提出了一种有监督的局部结构鉴别投影（LSDP）。该算法能够保持局部结构的情况下使邻域内的同类样本靠近，异类样本远离，但未能充分利用全局类别信息，导致有利于分类信息的丢失。本文算法通过线性判别分析的加权类间离散度矩阵，来描述样本的全局类间信息。通过最大程度地使得异类间中心相互远离来带动异类间样本的整体分散。最终得到保持了内在流形信息又使样本类间的距离最大化的线性投影矩阵。
2 线性判别分析
不同于无监督的PCA算法，LDA算法通过引入标签信息，从而达到使投影后样本的类内离散度最小、类间离散度最大。通过最大化Fisher准则函数，生成具有最佳可分性的子空间投影。
对于训练样本N个D维样本{x1，x2，…，xN}∈RD，类Ck的个数为Nk （k = 1，2，…，c）。
则样本的总体均值向量为：
m=xi =Nk mk （1）
其中mk为每类样本的均值向量，表示为，
mk =mj （2）
样本的类内离散度矩阵：
Sw=（x-mk）（x-mk）T （3）
样本的类间离散度矩阵：
Sb=Nk（mk-m）（mk-m）T （4）
同时，待求的空间投影矩阵W∈RD×d，通过投影y = ATx，得到投影后的d维样本{y1，y2，…，yN}∈RD。
投影后总样本均值向量：
m=yi =AT xi =AT m （5）
投影后类内离散度矩阵：
SW =（y-mk）（y-mk）T
=（AT x-AT mk ） （AT x-AT mk ）T
=AT SWA （6）
投影之后类间离散度矩阵：
Sb =Nk（mk-m）（mk-m）T
=Nk（AT mk -AT m） （AT mk -AT m）T
=AT SbA （7）
Fisher准则函数：能够使降维后样本具有最大的类间距离与类内距离之比：
JF（A）=arg max= （8）
通过对JF（A）对变量A进行求导，并使为零。
===0
（9）
则：
SbA（ATSwA）-SwA（ATSbA）=0
SbA=JF（A）SwA （10）
令JF（W）λ，则
SbA=λSwA（11）
若Sw非奇异，Sw-1Sb的d个最大特征值λ1≥λ2≥…≥λd对应的特征向量{a1， a2， …， ad}作为最佳投影方向A。
3 局部鉴别投影
基于在高维空间中临近的样本点，在低维度投影子空间中的样本也应该相邻。为了提高LE算法的泛化学习能力，He等人将LE方法中从原始高维空间到低维空间的映射看拓展为线性映射，即y = ATx，提出了局部保持投影算法（LPP）。该算法的本质是拉普拉斯特征映射的线性逼近。
LPP算法首先需要建立一个图G=（V，E，W）来描述个样本点之间的近邻关系。其中V 表示图中的一个样本结点，E表示两个结点间相连接的一条边，W表示权值矩阵。然后通过图G的权值矩阵表示流形的局部机构，数据降维的过程中引入了一个目标函数，具体步骤如下：
Step1：创建邻接图
如果样本结点xi和xj是近邻关系，那么xi和xj之间则有一条边，判断近邻关系的两种方法如下：
a） ε-近邻：如果结点xi和xj满足||xi-xj||2
b） k-近邻：如果结点xi是结点xj的k个最近邻的结点之一，表示为xi∈N；或者结点xj是结点xi的k个最近邻的结点之一，表示为xj∈N。那么xi和xj近邻，否则不是近邻。
Step2：确定权重
a） 热核方法：
Wij=exp（
-） xi∈
N or xj∈
N
0 otherwise （12）
b） 0-1原则
Wij=1 xi∈
N or xj∈
N
0 otherwise （13）
Step3：最小化如下目标函数：
J（A）=|| yi- yj ||2 Wij （14）
将式（14）展开可得：
（15）
其中，L=D-W为Laplacian矩阵。D为一对角矩阵，表示样本点的自然尺度，即Dii越大，表示对于的yi越重要，因此有下面约束：
yTDy=ATXDXTA=I （16）
最小化如下目标函数改为：
min ATXLXTA
s.t. ATXDXTA （17）
Step4：完成映射.
由拉格朗日乘子法，最小化目标函数式（17）等价于求解下式广义特征方程：
XLXTA=λXDXTA （18）
求解前d个最小非零特征值λ1≥λ2≥…≥λd对应的特征向量为{a1， a2， …， ad}。
4 最大类间相斥的局部鉴别投影
局部保持投影未能有效的利用样本的判别信息，属于无监督的降维算法。而判别信息对于人脸图像识别精度的提升来说至关重要。为了在保持流形局部结构的同时引入类别信息，局部鉴别投影对权重矩阵进行了重新构造。
（19）
其中dij=|| xi-xj ||2，表示两个样本点的欧式距离，β表示控制参数。
改进的权值矩阵式（9）引入了类别信息，实现了有监督的鉴别投影。可以看出，当样本属于同一类别时，权重值大于LPP时的权值；当样本属于不同类别时，权重值小于LPP时的权值。通过上述权值的改变，使投影后的相同类别邻域样本点聚集，不同类别的样本点远离。当dij相同时，同类的权值大于不同类的权值，表明同类的样本获得更大的相似性。同时，仅对权值进行了优化，没有破坏样本的邻域选择，从而保持局部流形结构。
但局部鉴别投影仅考虑了样本k邻域内类别信息，也即是局部类别信息；未能充分利用全局类别信息，导致有利于分类信息的丢失。本文算法引入加权类间散度矩阵，通过最大程度地使得异类间中心相互远离来带动异类间样本的整体分散。
样本的总体加权均值向量为
=（20）
每类的加权均值
k =（21）
其中，Dii为局部鉴别投影中所求的的对角矩阵。此类样本均值不同于线性判别分析直接求得样本均值，本文算法考虑到了不同样本点间的权重关系，对于图中拉普拉斯对角矩阵值越大（即Dii值越大）的点赋予了一个相应较大的权重值。
投影之前类内离散度矩阵：
b=Nk（k-）（k-）T （22）
投影之后类内离散度矩阵：
Sb=Nk（ATk-AT）（ATk-AT）T =ATbA（23）
需要满足式（24）的优化条件。
min ATXLXTA
max AT
b A （24）
目标函数为最小化类内离散度矩阵Sw与类间离散度矩阵Sb之比。然而比值的形式常使算法在求解中遭遇到小样本问题的困扰。因为本文采用了与线性鉴别分析类似的加权类间离散度矩阵，其秩小于c-1。若采用PCA算法先对样本矩阵进行降维到c-1维，会导致大部分有用的分类信息流失。为克服小样本问题的困扰，我们的目标函数为最小化相似散布矩阵和差异散布矩阵之差的形式。其描述如下：
J（A）=（AT XLXTA-AT b A）（25）
通过式（25）引入拉格朗日乘子，使J（A）对A求偏导，并使之为零，得：
（XLXT- b ）A=λA（26）
由此可知最优映射矩阵A由矩阵（XLXT- b ）的前d个最小的非零特征值λ1≤λ2≤…≤λd对应的特征向量组成{a1， a2， …， ad}。
MRLDP算法总体步骤描述如下：
Step1：采用k-近邻准则，创建邻接图
Step2：确定权重Wij以及加权的类间离散度矩阵b
Step3：求解矩阵（XLXT- b ）的d个最小特征相对的特征向量{a1， a2， …， ad}组成投影矩阵A
Step4：完成样本投影y = ATx
Step5：利用欧式距离进行分类实验
4 实验结果及分析
通过在ORL人脸库与Yale人脸库上实验，对比经典的算法PCA、LDA、LPP、LDP；来评价本文提出的算法MRLDP。实验环境：CPU主频为1.80GHz，双核四线程；操作系统Windows8.1；算法通过Visual Studio 2010以及Opencv244库实现。
4.1 ORL库上的实验结果
ORL人脸库由40人的人脸图像组成，每人包含10幅图像。其中，图像的特点包括不同时期、不同表情、不同姿态与不同面部细节，同时包含平面内或垂直平面的不超过20°的偏转以及不超过10%的尺度改变。每幅图像为灰度级256的112×92灰度图像。首先对图像进行预处理，将图像剪辑、归一化成为32×22的灰度图像。从每个人的图片中随机抽取 L（L=2，3，…，5）张图片作训练样本，剩下的 10-L张图片用作测试样本。
从表1可以看出：
（1）随着学习样本数目的增加，所有的算法的识别精度都得到了提升。这表明训练样本信息直接影响着算法的识别精度，更丰富的已知样本信息才能得到更佳的投影矩阵。
（2）基于流形学习的特征抽取方法（如LPP）的最高识别精度比传统的特征抽取方法（如PCA）取得了更好的效果。这主要是由于人脸图像受光线、表情等变化的影响，导致人脸图像是非线性不可分；因而，保存的全局欧氏距离的PCA算法难以有效地表示图像空间的内在流形结构。而基于流形学习的特征抽取算法能够探索数据内部的本质结构，并在降维过程中保持数据的本质结构。通过局部k-邻域有效地保存了隐藏在图像空间内的局部结构，从而反映了图像空间分布的内在属性。
（3）有监督的特征抽取方法（如LDA）总体上要比无监督方法（如PCA）更优。主要是由于自然获取的图像或多或少受到外在变化的影响，从而导致姿态、光照的变化。使得无监督特征抽取方法所保存的局部属性难以有效地区分不同类别的人脸图像。 相反，由于监督特征抽取方法考虑到了图像的类别信息，从而尽量的避免了这个缺点。在同类人脸变化不大的ORL数据库中，流形算法LPP与有监督的算法LDA取得了相近的效果。
（4）MRLDP优于其他算法；因为MRLDP既考虑了流形结构，又加入了类别信息。同时，克服了LDP算法仅考虑了样本k邻域内类别信息，也即是局部类别信息；未能充分利用全局类别信息的缺点，通过最大程度地使得异类间中心相互远离来带动异类间样本的整体分散。最终得到更具有区分性的投影向量。
从图1可以看出，算法识别效果随着特征维数的增加而增加。因为有监督的算法抽取的是有利于分类的投影矩阵；有监督的算法（如LDA，LDP）能够利用较少的特征维数得到较好的识别效果。基于流形结构的算（LPP）优于仅考虑全局最优的算法（PCA）；在维数较低时效果稍逊有监督的算法LDA；但随着样本的增加，最终取得了优于LDA的效果。本文算法（MRLDP）同时考了到了流形结构与类别标签信息。结合局部类别信息与全局类别信息，得到更了更好的识别效果。
4.2 Yale库上的实验结果
通过Yale数据库进行对比实验可以进一步验证本文算法的有效性。作为人脸识别研究过程中常用的数据库之一，Yale 人脸库由15个人组成，每人含有三种不同光照方向、六种表情变化的11幅灰度人脸图像。这些图像光照条件变化比较大，而且面部表情（正常、悲伤、愉快、惊讶、困乏与眨眼）和脸部细节也有较为明显的改变。每张图片对面部图像进行剪裁，并归一化为32×32。
从每个人的图片中随机抽取 L（L=3，4，…，6）张图像用于训练，余下的10-L张图片用作测试。由于参数选取问题至今为止仍然不能从理论上给出最佳参考，所以通过实验对参数进行调节，采用识别效果最佳时的参数值。同时通过随机交叉验证，保证实验的客观性。
文中所列的方法在Yale库上的精度比较低，这是因为Yale库的图像受光照、姿态、表情变化的干扰较大。由于LDA没有考虑局部流形结够，识别精度低于 LPP 和 LDP，而LDP方法没有考虑全局类别信息，识别精度低于本文算法。
5 结束语
局部鉴别投影算法考虑了样本k邻域内类别信息，使同类的样本聚集，异类的样本远离从而实现了有监督的分类。本文提出的算法MRLDP结合了类间加权的离散度矩阵，从而利用全局类别信息，通过最大程度地使得异类间中心相互远离来带动异类间样本的整体分散。最终得到了更具有的分类意义的子空间投影矩阵，使在原有空间中无法区分的人脸图像在子空间中能够得到区分。实验证明，该算法可以更好地发现嵌入在高维空间中有意义的低维流形，能更好地实现复杂情况下的人脸识别。
参考文献
[1] Turk M， Pentland A. Eigenface for Recognition[J]. Journal of Cognitive Neuro Science. 1991， 3（1）：71-86.
[2] Peter N.Belhumeur. Eigenfaces vs Fisherfaces： Recognition using class specific linear projection[J].Lecture Notes in Computer Science， 1997， 19（7）：711-720.
[3] Seung H S， Lee D D. The manifold ways of perception[J]. Science，2000， 290（12）：2268-2269.
[4] Tenenbaum J B ，Langford J C. A global geometric frame- work for nonlinear dimensionality reduction[J].Science，2000， 290：2319-2323.
[5] Sam T，Roweis， Lawrence K，et. Nonlinear dimensionality reduction by locally linear embedding[J]. Science， 2000， 290：2323-2326.
[6] Belkin M，Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering [J].Neural Inform- ation Processing Systems， 2001：585-591.
[7] He X， Niyogi P. Locality Preserving Projections[J]. In Advances In Neural Information Processing Systems， 2003 23（6）：132-1361.
[8] He X F，Cai D，Yan S C，et al. Neighborhood preserving embedding[C] Beijing China：Proceedings of the Tenth IEEE International Conference on Computer Vision. 2005：1208-1213.
[9] Yan S，Xu D，Zhang B，et al. Graph embedding and extensions： a general framework for dimensionality reduc- tion[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2007， 29（1）： 40-51.
[10] Yu W.，Two-Dimensional Discriminant Locality Preserving Projections for Face Recognition[J]， Pattern Recognition Letters， 2009， 30（15）： 1378-1383.
[11] Cai D，He X F，Han J W，et al. Orthogonal laplacianfaces for face recognition[J]. IEEE Transactions Image Process， 2006，15（11）： 3608-3614.
[12] 黄鸿，李见为，冯海亮.基于半监督流形学习的人脸识别方法[J].计算机科学，2008.35（12）：220-223.
[13] Zhao H. T.， Sun S. Y.， Jing Z. L.， et al.， Local structure bas- ed supervised feature extraction[J]，Pattern Recognition， 2006， 39（8）： 1546-1550.
[14] Deng Cai， Xiaofei He， Kun Zhou， et al. Locality Sensitive Discriminant Analysis[C].Hyderabad， india： International Joint Conference On Artificial Intelligence 2007：708-713.
[15] Zhao H T， Sun S Y ， Jing Z L ， et al.， Local structure based on supervised feature extraction[J]， Pattern Recognition 2006.39 （8）： 1546-1550.
基金项目：
国家自然科学基金项目（60875004）。
作者简介：
李文洋 （1990-），男，河北衡水人，扬州大学，硕士研究生；主要研究方向和关注领域：图像处理、模式识别。
施成建（1977-），男，江苏扬州人，扬州大学，硕士研究生，扬州市科委；主要研究方向和关注领域：图像处理、计算机应用；
华继钊（1968-），男，江苏宝应人，南京理工大学，博士，副教授，研究生导师；主要研究方向和关注领域：计算机应用、模式识别。