计算机论文：无参数局部保持投影及人脸识别

  摘 要 局部保持投影( LPP) 通过构造近邻图来保持样本的局部结构，在构图过程中，LPP 面临复杂的参数选择问题． 为解决此问题，提出无参数局部保持投影( PLPP) 算法． 首先设计一种无参数的构图方法，能够动态地获取样本的近邻点并配置相应的边权． 其次，利用该构图方法，PLPP 通过寻求最佳投影矩阵，用于保持样本在低维空间的局部结构． 由于 PLPP 在构图过程中并未设置任何参数且采用余弦距离设置边权，因此 PLPP 计算更加方便快捷且对离群样本更具鲁棒性． 另外，为进一步提升 PLPP 的识别性能，在 PLPP 的基础上通过加入样本的类别信息，提出监督的无参数局部保持投影算法( SPLPP) ． 最后，在 ORL、FERET 及 AR 人脸库上的实验验证了 PLPP 与 SPLPP 的有效性．关键词 人脸识别，特征提取，流形学习，图构建，无参数局部保持投影
   1 引 言特征提取是模式识别领域关键技术之一，其通过线性或非线性变换将原始数据变换到维数较少的数据空间，从而得到高维数据最本质的特征． 近几十年来，研究者提出大量的特征提取算法，如主分量分析( Principal Component Analysis，PCA)、线性鉴别分析( Linear Discriminant Analysis，LDA)、约束聚类最优离散余弦变换( Constrained Clustering-BasedOptimal Discrete Cosine Transform，CCODCT)等．PCA 与 LDA 均为全局线性方法，一些研究表明，高维数据极可能存在于一个非线性流形上，因此 PCA 与 LDA 无法揭示数据内在的非线性结构．近年来，比较着名的非线性流形学习算法有局部线性嵌入、等距映射及拉普特征映射等． 然而这些算法对未知样本并未作出定义，因此泛化能力较弱． 针对此点，He提出局部保持投影( LocalityPreserving Projections，LPP) 算法． 随着 LPP 在人脸识别领域的成功应用，研究人员针对 LPP 存在的缺陷提出一系列的局部保持降维算法，如无监督鉴别投影、鉴别的局部保持投影( Discriminant Local-ity Preserving Projection，DLPP)、依类局部保持投影、边界费舍尔分析( Marginal Fisher Analysis，MFA)等．在 LPP 中，近邻图的构建对于算法的识别性能起着至关重要的作用． 建图过程通常分为独立的两步: 图构造与边权配置． 最常用的构图法与边权配置法分别为 k 近邻图法与高斯核权重． 最近的研究表明，近邻参数 k 与核参数的选择会严重影响 LPP 的识别性能，且如何选择合适的参数使得算法达到最佳效果是当前的一个研究难点． 一些研究者提出一些改进算法，使得 LPP 识别性能对于参数并不敏感，另外文献提出一种非参数局部保持投影技术( Parameterless Locality Preserving Pro-jection，Parameterless LPP) ，在该方法中样本可自动地获取其近邻点并设置相应的权重．本文针对 LPP 在构造近邻图时面临的参数选择问题，提出无参数局部保持投影( PLPP) ． 首先设置一种无参数构图方法，能够活动地获取样本的近邻点然后配置相应的边权． 其次，利用该构图方法，PLPP 通过寻求最佳投影矩阵用于保持样本的局部结构． 同时，为进一步增强 PLPP 的识别能力，在PLPP 基础上通过加入样本的类别信息提出监督的无参数局部保持投影． 最后，在 ORL、FERET 和 AR人脸库上的实验验证了 PLPP 与监督的无参数局部保持投影算法( Supervised LPP，SPLPP) 的有效性．
       2 局部保持投影简介设有 n 个训练样本X = { x1，x2，…，xn} ，其中xi∈RN． 线性特征提取算法的目的在于利用一组投影向量W = { w1，w2，…，wd}将 N维空间的数据映射到d( d ＜ N) 维特征空间，从而得到样本在低维特征空间中的表示 yi= WTxi，其中 W ∈ RN ×d． 为方便讨论，本文首先考虑一维投影向量的情形，设投影向量为 w．LPP 旨在保持样本数据的局部几何结构． LPP首先构造近邻图 G = { X，E，H} ，其中，X = { x1，x2，…，xn}为训练样本组成的顶点集合，E 为图的边集合，H 为边权重矩阵，其元素用于描述两点之间的相似度．LPP 采用 k 近邻法与核函数构造边权矩阵，具体地，H 可表示为Hij=exp －‖xi－ xj‖2t( )，if xi∈ Nk( xj)or xj∈ Nk( xi)0， otherwise{其中，Nk( xi) 表示 xi的 k 近邻集合，0 ＜ exp －‖xi－ xj‖2t( )≤ 1，t ＞ 0 为可调节的核参数，‖xi－ xj‖ 表示 xi与xj两点间的欧氏距离．LPP 的目标函数可定义为12arg minw( yi－ yj)2Hij=12arg minw( wTxi－ wTxj)2Hij= arg minwwTX( D － H) XTw= arg minwwTXLXTw，其中，D 为对角矩阵，对角线上的元素为边权重矩阵对应的行和或列和( 因为 H 是一个对称矩阵) ，即Dii=∑nj = 1Hij，8 66模式识别与人工智能 26 卷L = D － H 称为拉普拉斯矩阵( Laplacian matrix)．另外，LPP 还施加一个限制 wTXDXTw = 1． 因此，LPP 目标函数可改写成:JLPP= arg minwTXDXTw = 1wTXLXTw．要求满足上式目标函数的最优投影向量，只需求解下式特征方程 d 个最小特征值对应的特征向量:XLXTw = λXDXTw，其中，λ 表示特征值，w 表示特征向量．
       3 无参数局部保持投影由第 2 节内容可知，LPP 构造近邻图时需要两个参数: 近邻参数 k 与核参数 t． 文献指出 t 与 k的选择会严重影响 LPP 的识别性能，主要体现在:1) t 与 k 的选择有时会使 LPP 无法准确刻画样本的流形结构，从而使 LPP 识别率降低; 2) 需耗费大量时间选择合适的参数来确定样本的邻域及配置边权从而使识别效率降低． 为避免复杂的参数选择，本节提出无参数局部保持投影( PLPP) 算法，具体内容如下所述．
       3． 1 余弦距离LPP 利用高斯核定义两个样本点之间的相似度，权重 Hij代表 xi与 xj之间的相似度，由其定义可知，两点间欧氏距离越小，相似度越大，反之，则相似度越小，因此 LPP 所构建的近邻图反映的是两个样本间的欧氏距离关系． 由文献可知，欧氏距离对离群数据点比较敏感，而余弦距离对离群数据更为鲁棒，在很多情况下具有较好的性能． 这里，为介绍 PLPP 的构图过程，首先引入样本间的余弦距离．令 cos( xi，xj) 表示样本 xi与 xj间的余弦距离，则cos( xi，xj) 的计算公式为cos( xi，xj) =xTixj‖xi‖·‖xj‖． ( 1)在处理实际问题( 如人脸识别) 时，由于采集的数据通常是非负的，因此任意两个样本之间的余弦距离满足: 0 ＜ cos( xi，xj) ≤ 1． 另外，余弦距离反映两个样本向量之间的夹角大小，余弦距离越大，夹角越小，这两点的相似度越高; 反之，这两点的夹角越大，相似度越低．
       3． 2 无参数近邻图构造设PLPP 构造的近邻图可表示为G ={ X，E，S} ，其中，X ={ x1，x2，…，xn} 为训练样本组成的顶点集合，E为图的边集合，S为边权重矩阵，其矩阵元素用于度量两点之间的相似度．PLPP 的构图过程同样分为图构造与边权配置两步，具体内容如下．定义 PLPP 图构造方式 如果 cos( xi，xj) ＞cos( xi，m) ，则 xj是 xi的近邻点，并在图上用边表示，其中，m =1n∑ni = 1xi表示总体样本中心点．在定义中，cos( xi，m) 表示 xi与总体样本中心点 m 的余弦距离，由于余弦距离反映样本间的夹角大小，因此上述构图方式可理解为: 当 xj与 xi的夹角小于 xi与 m 的夹角时，xj是 xi的近邻点，并将 xj与 xi用边相连． 图1 为 xi选择 xj为其近邻点时的示意图． 由图 1 可知，xj与 xi的夹角为 ∠xioxj，xi与中心点 m 的夹角为 ∠xiom，由于 ∠xioxj小于 ∠xiom，因此 xj是 xi的近邻点．图 1 xi选择 xj为其近邻点时的示意图Fig． 1 Illustration of xjdetermined as neighbor of xi近邻图建成后，需要为其配置边权重，PLPP 采用余弦距离配置边权重，定义如下:
　　Sij=cos( xi，xj) ， if cos( xi，xj) ＞ cos( xi，m)0， otherwise{( 2)注意，当cos( xi，xj) ＞ cos( xi，m)时，cos( xi，xj) ＞ cos( xj，m)不一定成立，即Sij= Sji不一定成立，因此S不一定为对称矩阵，这也是 PLPP 与 LPP 的区别之一．由 PLPP 的构图过程可看到，PLPP 构图并没有设置任何的调节参数，因此相较于 LPP 算法，PLPP避免了复杂的参数选择且构图更简捷快速． 另外，PLPP 采用余弦距离度量样本间的相似性，增强算法对离群样本的鲁棒性．
       3． 3 PLPP 目标函数PLPP 同样旨在保持数据的局部结构，因此PLPP 寻求最佳投影向量使得下列目标函数最小化:无参数局部保持投影及人脸识别867∑ni = 1∑nj = 1‖yi－ yj‖2Sij=∑ni = 1∑nj = 1( y2i－ 2yiyj+ y2j) Sij=∑ni = 1∑nj = 1( Sijy2i+ Sijy2j－ Sijyiyj－ Sijyjyi)=∑ni = 1Dcijy2i+∑nj = 1Drijy2j－∑ni = 1∑nj = 1Sijyiyj－∑nj = 1∑ni = 1Sijyjyi= wTX( ( Dc+ Dr) － ( S + ST) ) XTw= wTX( D － S) XTw= wTXLXTw， ( 3)其中，Dc与 Dr为对角矩阵，其对角线上的元素分别为Dcii=∑nj = 1Sij，Drjj=∑ni = 1Sij．D = Dc+ Dr同样为对角矩阵，S = S + ST为对称矩阵，L = D － S 为拉普拉斯矩阵．类似于 LPP，PLPP 施加了一个限制wTXDXTw = 1．同样地，要求满足 PLPP 目标函数的投影向量，只需求解以下特征方程的 d 个最小特征值对应的 d 个投影向量即可:XLXTw = λXDXTw．
      3． 4 监督的 PLPP由3．2 节可知，PLPP 在构造邻接图时并没有利用样本的类别信息，而通常在算法中如果考虑了样本的类别信息的话则能够提高算法的识别性能，因此提出了监督的 PLPP( Supervised PLPP，SPLPP) ． 在监督的 PLPP 中，边权重矩阵定义方式为Sij=cos( xi，xj) ，如果 cos( xi，xj) ＞ cos( xi，m)且 xi与 xj属于同一类0， otherwise{( 4)只需将式( 4) 中定义的权重矩阵代入式( 3) 即可得到监督 PLPP 的目标函数，其投影向量的求解方式与 PLPP 相同．
      3． 5 PLPP 算法根据前文所述，可得 PLPP 算法如下．step 1 根据式( 1) 计算样本 xi与其他点的余弦距离 cos( xi，xj) 及 xi与总体样本中心点 m 的余弦距离 cos( xi，m) ．step 2 根据定义 1 建立近邻图，并根据式( 2)构造权重矩阵 S．step 3 计算对角矩阵 Dc与 Dr，其对角线上的元素分别为Dcii=∑nj = 1Sij，Drjj=∑ni = 1Sij．step 4 计算对角矩阵 D 与拉普拉斯矩阵 L，其中 D = Dc+ Dr，L = D － S．step 5 求解特征方程XLXTw = λXDXTw的 d 个最小特征值对应的 d 个特征向量 w1，w2，…，wd．step 6 令W = { w1，w2，…，wd} ，样本 x 在 d 维特征空间中的表示为 y = WTx．step 7 利 用 分 类 器 对 投 影 后 的 样 本 进行分类．
      4 实验与结果分析为验证文中所提方法的有效性，将各算法在ORL、FERET 和 AR 人脸库上进行实验，并将实验结果进行比较． 实验中，在运行 LPP、DLPP 时，近邻参数与核参数采用穷取法选择，其选择范围分别为{ 1，2，…，10} 、{ 105，106，107，108} ，最后结果采用最佳识别效果．
      4． 1 人脸库简介ORL 人脸库中包含 40 人，每人 10 幅图像，其中，有些图像是拍摄于不同时期的，有些图像人的面部表情和面部细节有着不同程度的变化，另外有些图像人脸姿态也有相当程度的变化，每幅图像的分辨率为 112×92，在实验时为计算方便，本文将每幅图像的分辨调整为 32×32．FERET 人脸库包含 200 人，每人 7 幅图像，这 7幅图像中人脸姿态、表情、光照均有不同程度的变化，每幅图像分辨率大小为 80×80，在实验中，为方便运算，本文将每幅图像的分辨率调整为 32×32．AR 人脸库中包含 120 人，每人有 26 幅图像，每幅图像分辨率为 50×40． 在本文中，本文采用每人的14 幅无遮挡图像作实验，图 3 为 AR 库中某人的 14幅图像，这 14 幅图像中，前 7 幅图像与后 7 幅图像拍摄于不同的时期，且每 7 幅图像中人脸姿态、表情、光照条件等均有变化．
      4． 2 实验4． 2． 1 图像可视化由于在现实生活中采集的人脸图像数据维数较高，如，在 ORL 库中，每幅图像为 32×32 =1 024 维，8 68模式识别与人工智能 26 卷而人的视觉感觉最多为 3 维，因此高维的人脸图像数据在空间中通常是不可视的，也就无法看出这些数据之间的联系且无法直观地比较各种特征提取算法的差异性． 针对此问题，我们将 LPP、PLPP 及SPLPP 算法在 ORL 库上进行图像可视化实验． 实验时，选择 ORL 库中的前 6 人( 分别用符号"* "、"○"、"+"、"△"、"?"及"☆"表示) ，每人 10 幅图像，共 60 幅图像，分别利用 LPP、PLPP、SPLPP 算法将初始的 1 024 维数据映射到 2 维空间，映射结果如图 2 所示．( a) LPP( b) PLPP( c) SPLPP图 2 LPP、PLPP 及 SPLPP 的二维映射结果可见，同类样本经过投影后靠得较近，这说明 LPP、PLPP 及 SLPP 均能保持样本的局部结构． 然而，从分类角度来看，LPP 并不能较好地区分这 6 类样本，其中有大量的不同类样本重叠在一起;相较于 LPP，PLPP 能较明确地将不同类样本划分开来，但仍有部分样本发生重叠; 相较于 LPP 与PLPP，由于 SPLPP 利用样本的类别信息，因此SPLPP 能较好地分离出不同类样本．
       4． 2． 2 人脸识别为验证所提算法在人脸识别方面的有效性，本文在 FERET 库和 AR 库上进行人脸识别实验． 在FERET 人脸库上，选择每人前 l( 为 4) 幅图像作为训练样本，剩余 3 幅图像作为测试样本． 由于人脸图像样本维数较高，因此先利用 PCA 方法对原始图像降维并移除部分噪声，PCA 降维轴数取为 80，然后使用各算法提取特征，最后分别使用基于欧氏距离和余弦距离的最近邻分类器进行分类． 为 LPP、PLPP 与 SPLPP 使用基于欧氏距离的最近邻分类器进行分类，识别率随投影轴数变化的曲线图，为LPP、PLPP 与 SPLPP 使用基于余弦距离的最近邻分类器进行分类，识别率随投影轴数变化的曲线图．