基于NPP和LDA融合算法的人脸识别

【摘 要】流形学习算法NPP具有保持数据局部几何结构的特点，而经典线性特征提取算法LDA则能够很好应对分类问题，充分利用二者优势，并进行算法融合，提出NPP-LDA算法。该算法是一种有监督算法，能够利用类别信息，且保持了数据的局部信息。将算法应用于人脸识别，ORL人脸数据库实验结果表明算法具有较好的性能。

【关键词】NPP；LDA；融合；人脸识别

0 引言

随着计算机视觉和模式识别的迅速发展，人脸识别已成为一研究热点。人脸数据一般为高维图像数据，计算机处理时不得不面临“维数灾难”问题，特征提取（即维数约简）十分必要。通过提取高维数据中的有用部分，可减少数据冗余，降低分类识别复杂度。

传统特征提取以线性方法为主，典型算法包括PCA[1-2]、LDA[3-4]等。线性方法认为数据集的全局结构为线性，且变量之间互相独立，在数学上可通过欧氏空间来描述。然而在实际获取人脸数据时，往往受到各种可见和隐蔽因素的影响。而各个因素对模式类的影响不仅仅是线性叠加的，这样获得的数据集实际上具有高度的非线性。2000年以来，以流形学习算法为代表的非线性特征提取方法的产生，为人脸识别提供了另一研究方向，典型算法包括ISOMAP[5]、LLE[6]、Laplacian Eigenmaps[7]等。但这些算法复杂度非常高，且没有明确的映射关系矩阵，很难处理新样本。而后提出的LPP[8]和NPP[9]算法分别为Laplacian Eigenmaps和LLE的线性近似，既保留了原算法的非线性特点，又能直接处理新样本点。

本文综合考虑人脸识别中线性算法LDA在分类识别中的优势，及流形学习算法NPP在保持数据局部几何信息上的优势，对二者进行融合，提出基于NPP和LDA融合的人脸识别算法NPP-LDA，实验结果证明了算法的优越性。

1 NPP算法

设初始的D维数据集为X={x1，x2，…，xN}，共有C个模式类？棕1，？棕2，…，？棕C，特征提取需要寻找映射矩阵A，使得D维的高维数据映射到d（d？垲D）维的低维空间中，那么映射后的数据集为Y={y1，y2，…，yN}

可通过Y=ATX得到。NPP算法的具体步骤为：

（1）寻找每个样本的邻域，有两种方法。一种为取与每个xi的欧氏距离最小的k个点为xi的邻域，另一种为取与每个xi的欧氏距离小于σ的点为xi的邻域，k和σ需人工确定；

（2）计算利用邻域重构xi时的权值Wij，使代价函数最小，代价函数为：

而权值Wij满足约束条件 jWij=1，且当xi和xj不是近邻点时Wij=0。

（3）最终变换矩阵A={a1，a1，…，ad}的求解可以转化为广义特征值问题

T，I是单位矩阵，向量a1，a1，…，ad可以根据它们对应的特征值0

（4）降维后的数据可以通过Y=ATX计算。

2 NPP和LDA融合的特征提取算法NPP-LDA

LDA算法为了应对分类问题，定义了类间散布矩阵和类内散布矩阵，将二者引入到NPP算法当中，最大化类间距离，便可使算法更适合分类。

数据的整体散布矩阵为：

数据的类内散布矩阵为：

那么类间的散布矩阵Sb可由St-Sw计算得到，即：

其中L=G-D。

则类间距离可通过下面函数计算：

Jb（A）= pi-pj2

= ATx- ATx2

= AT（qi-qj）2 （6）

=trace{ AT（qi-qj）（qi-qj）TA}

=trace{ATSb A}=trace{ATXLXTA}

其中pi=（1/ni）？蒡x？缀？棕iy。

NPP算法的代价函数为：

JNPP（ A）= yi- yiWij2

=Y（I-W）2

=trace{Y（I-W）（I-W）TYT}（7）

=trace{YMYT}

=trace{（ATX）M（ATX）T}

=trace{ATXMXTA}

其中，约束条件为：

YYT= ATXXTA=I （8）

NPP算法为了保持邻域数据结构需要最小化代价函数JNPP，而为了更好的应对分类，需要同时最大化类间距离Jb。同时满足两种需求，只需最小化：

J（A）=JNPP（A）-Jb（A）

=tr{AXMXTAT}-tr{AXLXTAT}（9）

=tr{AX（M-L）XTAT}

约束条件同式（8）。

那么关于含约束条件的最小化目标函数问题 {J（A）}，可通过拉格朗日乘子法求解，即：

这样问题最终转化为了X（M-L）XTA=？姿XXTA的广义特征值问题。由此得出NPP和LDA融合的特征提取算法步骤为：

步骤1：计算每个xi的邻域，方法同NPP算法步骤（1）；

步骤2：计算重构权值矩阵W，方法同NPP算法步骤（2）；

步骤3：映射矩阵A的求解转换为X（M-L）XTA=？姿XXTA的广义特征值问题，最终A={a1，a1，…，ad}可以根据它们对应的特征值新排序得到。

步骤4：通过Y=ATX进行特征提取。

3 实验与结果分析

选用ORL人脸数据库进行测试，并与PCA、LDA、LPP和NPP算法进行性能比较。分类算法统一采用最近邻算法。

ORL数据库共有40个人的400幅人脸图像，每人10幅，表情姿态各不相同。原始图像分辨率为92×112，进行压缩后得到大小为23×28的图像。随机选用每人6幅（共240幅）图像作为训练集，剩余部分作为测试集，重复多次，取平均识别率和最高识别率。表1给出了不同算法的最高识别率及对应的低维空间的维数，图1给出了各种算法在不同低维空间维数（以10递进）的平均识别率曲线。

表1 不同算法最高识别率及对应低维空间维数

从表1可以看出NPP-LDA算法在低维空间维数为40时取得了最高识别率92.54%，相对于其它算法识别率最高，且低维空间维数仅大于LDA。而LDA由于算法由于自身限制，最多只能提取比类别数小1个特征，故在低维空间为39时就取得了最高识别率，但在所有比较的算法中，识别率最差。LPP和NPP算法性能相近，略低于本文算法。

图1 各种算法在不同低维空间维数下的平均识别率曲线

由图1可知，本文算法在各种低维空间维数下的平均识别率均高于其它算法，且识别率在低维空间维数大于40以后基本稳定，只有轻微的波动。NPP和LPP算法的平均识别率曲线互有交叉，水平十分接近。PCA算法则随着低维空间维数的增加逐渐上升，但识别率明显低于NPP、LPP和本文算法。LDA算法在低维空间维数达到39后便具有最大识别率，且保持不变，不存在低维空间维数大于39的情况。

4 结论

综合考虑传统线性特征提取方法LDA在分类方面的优势，及流形学习算法NPP保持数据局部结构优势，融合两种算法，推导出NNP-LDA算法。通过人脸识别实验验证，NPP-LDA算法能够较好地进行人脸识别，性能较PCA、LDA、LPP、NPP等有一定优势。

【参考文献】

[1]孙即祥.现代模式识别[M].第二版.北京：高等教育出版社，2008.

[2]Hoyle David C. Automatic PCA dimension selection for high dimensional data and small sample sizes[Z]. Journal of Machine Learning Research， 2008， 9（12）： 2733-2759.

[3]Song Fengxi， Zhang David， Wang Jizhong， et al.. A parameterized direct LDA and its application to face recognition[J]. Neurocomputing， 2007， 71（1-3）： 191-196.

[4]Abrishami Moghaddam H， Matinfar M. Fast adaptive LDA using quasi-Newton algorithm[J]. Pattern Recognition Letters， 2007， 28（5）： 613-621.

[5]Tenenbaum J B， Silva V， Langford J C. A global geometric framework for nonlinear dimensionality reduction[Z]. Science， 2000， 290（5500）： 2319-2323.

[6]Roweis S T， Saul L K. Nonlinear dimensionality reduction by locally linear embedding[Z]. Science， 2000， 290（5500）： 2323-2326.

[7]Belkin M and Niyogi P. Laplacian eigenmaps for dimensionality reduction and data representation[Z]. Neural Computation， 2003，15（6）： 1373-1396.

[8]He X F， Yan S C， Hu Y X， et al.. Face recognition using Laplacian faces. IEEE Transaction on Pattern Analysis and Machine Intelligence， 2005， 27（3）： 328-340[Z].

[9]Pang Y W， Zheng L， Liu Z K， et al.. Neighborhood preserving projections （NPP）： a novel linear dimension reduction method. ICIC 2005， Part I， Lecture Notes in Computer Science， Springer， Berlin， 2005， vol. 3644： 117-125[Z].