0 引言
　　
　　在生物特征识别系统中,人脸识别由于具有成本较低、不侵犯使用者的隐私权、应用前景广阔等特点,受到了极大的关注,是当前模式识别、图像处理和计算机视觉等学科非常活跃的研究热点[1]之一。
　　正是因为人脸识别的这些特点,在过去的几年时间里,出现了很多人脸识别算法。其中,基于子空间的算法起到了主导作用,最著名的是主成分分析[2](principal component analysis)和线性判别分析[3](linear discriminant analysis)。主成分分析算法的主要思想是通过估计数据的二阶统计性质来发现数据的本征线性维数,它是在全局最小重构误差的条件下把高维观察数据投影到低维空间上,通过求解数据点协方差矩阵的最大几个特征值所对应的特征向量张成的子空间而得到。线性判别分析算法就是求出一个线性子空间,使得所有样本在这个子空间中,类内样本散度最小,类间样本的散度最大,用它降维后的低维嵌入坐标非常有利于进行样本的分类。
　　上述两种方法是线性算法,但人脸空间更可能存在于非线性子空间中。最近相关人员提出了几种流形学习算法,主要用于非线性降维,如等距映射(ISOMAP)[4]、局部线性嵌入算法(LLE)[5]、拉普拉斯特征映射(LE)[6]等。但是它们都不能解决out of sample问题,即不能直接映射新数据,因此不能直接用于人脸识别。基于以上问题,He等人[7]提出了一种线性算法LPP,该算法是拉普拉斯特征映射的线性版本,能保持数据集的局部邻近关系,又能较容易地映射新样本。
　　LPP虽然能保持数据的局部结构,但是没有利用数据集的类别信息,从而不利于分类问题。本文基于LPP和LDA的优点,既考虑LPP的局部保持特性,同时又利用LDA的易于分类问题这一特点,提出了一种基于局部特性和判别特性的降维算法。
　　
　　1 基于局部特性和判别特性降维算法
　　
　　1.1 LPP简介
　　LPP目标是保持数据之间的相似性,即原始空间上相邻的数据点在投影空间上也保持相应的邻近关系。假定数据集X={x1,x2,…,xn}含有n个样本点,每个样本点xi属于D维欧式空间,即xi∈RD,且样本数据来自一本征维数为d(d<　　Wopt=argminW∑ij(yi-yj)2Sij=argminW∑ij(W Txi-W Txj)2Sij=argminW WTXLXTW(1)
　　其中:Sij刻画了两数据xi、xj之间的相似性。
　　Sij=exp(-xi-xj2)/txi,xj为邻近点0其他
　　附加约束条件W TXDX TW=1,拉普拉斯算子L=D-S。其中:D为对角矩阵,其元素为对称矩阵S的列向量(或行向量)元素之和,即Dij=∑jSij。最后可以通过以下特征方程求解:
　　XLXTw=λXDXTw(2)
　　假定w0,w1,…,wd-1为特征方程式(2)的d个解,它们所对应的特征值分别为λ0,λ1,…,λd-1,那么可以得到如下映射:xi→yi=W Txi。其中:yi为d维向量;W为变换矩阵。
　　1.2 LDA简介
　　对于分类问题,希望能找到某个投影方向,使得不同类的数据在投影后能尽量分开。LDA算法就是找到这样一投影方向,使得数据在低维空间中同类数据尽量靠近,不同类数据尽量分离,从而保留丰富的辨别信息,使数据具有最大的可分性。
　　给定分别属于J类的n个数据样本X={x1,x2,…,xn},Cj表示第j类元素构成的集合,nj表示属于第j类元素的个数,μj=(1/n)j∑xi∈Cjxi表示第j类的均值,μ表示样本的总体均值。
　　令Sb、Sw分别为类间散度矩阵和类内散度矩阵,即
　　Sb=(1/n)∑Ji=1ni(μi-μ)(μi-μ)T(3)
　　Sw=(1/n)∑Jj=1∑xi∈Cj(xi-μj)(xi-μj)T(4)
　　问题归结为求以下特征方程:
　　Sbw=λSww(5)
　　设w1,w2,…,wd是对应于矩阵Sw-1Sb的前d个最大特征值的特征向量,则令W=[w1,w2,…,wd],投影后的数据为yi=WTxi,i∈n。
　　 　　1.3 基于局部和判别特性的降维算法
　　基于以上的简单介绍可以看出LPP能有效降低数据维数,并能保持数据间的邻近关系,LDA能找到一投影,使得投影后的数据更加有利于分类。本节将LPP和LDA的这两个特性结合起来,形成既保持数据点之间的关系又有利于分类的新颖降维算法。
　　找到一投影,使得目标函数W T(Sw+σXLX T)W/(WTSbW)最小(Sw、Sb、L定义同上),并受到一限制条件WTXDXTW=1。所以问题最后归结为以下优化问题:
　　Wopt=argminW W T(Sw+σXLX T)W/(W TSbW))s.t. W  TXDX TW=1(6)
　　这里假设Sb可逆,即假设Sb非奇异,则该优化问题可以简化成
　　Wopt=argminW W TSb-1(Sw+σXLXT)Ws.t.W TXDXTW=1(7)
　　通过Lagrange乘数法,令
　　L(W)=W TSb-1(Sw+σXLX T)W-λ(W TXDX TW-1)(8)
　　对W求偏导,得到
　　L(W)/W=2Sb-1(Sw+σXLXT)W-2λXDXTW(9)
　　令L(W)/W=0,即
　　Sb-1(Sw+σXLXT)W-λXDXTW=0(10)
　　最后求解以下广义特征方程
　　Sb-1(Sw+σXLXT)w=λXDXTw(11)
　　假定w0,w1,…,wd-1为式(11)的d个解,它们所对应的特征值分别为λ0,λ1,…,λd-1,那么可以得到如下映射:xi→yi=W Txi。其中:yi为d维向量;W为变换矩阵。
　　在求解过程中,Sb有可能是奇异的,为了解决该问题,可以先通过PCA算法,使得Sb变成非奇异。所以具体算法步骤如下:
　　a)对原数据先进行主成分分析,一方面既可以消除噪声,又可以避免Sb的奇异性,映射图像X到PCA子空间,即Y=WTPCAX。
　　b)根据式(3)(4)求得Sw、Sb,以及拉普拉斯L和D。
　　c)根据式(10)解决特征函数问题,得到特征值和所对应的特征向量,求得Wopt。
　　d)令W=WPCAWopt,根据Y=WTX,将图像X映射到目标子空间,求得目标图像。
　　
　　2 实验结果及其分析
　　
　　本算法采用公共人脸数据库ORL库来验证算法的正确性和有效性。实验过程为:先将人脸库中的图像进行光照预处理;再利用本文所提出的算法进行低维人脸特征提取;最后使用NN(nearest neighborhood)分类器进行识别。实验中比较了该算法与PCA、LDA、LPP的识别率。
　　ORL人脸数据库包含40人,每人有10张人脸图片,共400张图片。其中有一些图像是在不同时期拍摄的,人的表情和脸部细节有着不同程度的变化,如睁眼和闭眼,是否带有眼镜等。人脸姿态也有一定程度的变化,深度旋转和平面选择可达20°,人脸大小也有多达10%的变化。图1是ORL人脸数据库中的第一个人的样本。
　　为了有效地计算,所有图像都缩放成32×32像素,即每一图像可以看成是D=32×32=1 024维向量。参数σ是决定局部信息和类别信息对识别率贡献的大小,这个很难确定,在实验中,取σ=1,即假设局部信息和类别信息同等重要。每人分别随机选择3、4、5、6、7幅图像用做训练样本,其他图像用于测试样本,重复20次,最后取平均值作为识别结果。该算法(姑且称它为DRLD)与著名算法PCA、LDA、LPP进行了比较,实验结果如
　　实验结果表明,LDA算法的识别率高于PCA,这是因为LDA考虑了类别信息,更加有利于分类问题。而LPP虽然高于PCA, 但是没有LDA理想,原因是虽然考虑了人脸的局部信息,但是没有考虑类别信息,所以在人脸识别上的效果不如有监督的学习算法LDA。DRLD算法优于其他算法,这是因为它不仅考虑了人脸的局部信息,而且还考虑了类别信息,使不同类之间的可区分度加强了。显然随着训练样本数的增加,算法的识别率提高了。
　　
　　3 结束语
　　
　　本文提出了一种基于局部特性和判别特性的一种新颖数据降维算法,在一定程度上解决了流形学习方法应用于模式分类中存在的问题。该算法不仅保持了数据点之间的局部邻近关系,而且也考虑了数据之间的类别关系。它是一种线性算法,能将新数据映射到目标空间,即解决流形问题中的out of sample问题。算法中有一参数σ,它是确定类别信息与局部信息对分类问题的贡献大小。如何确定参数σ,如何将算法扩展成非线性使其能更好地用于实际应用(在此可以用核技巧kernel trick,先将数据映射到高维空间,再利用本文提出的算法),以及将算法用于其他领域是今后的一个研究方向。
　　
　　参考文献:
　　[1]ZHAO W, CHELLAPPA R, ROSENFELD A,et al.Face recognition: a literature survey, CVL technical report[R]. Maryland: University of Maryland, 2000.
　　[2]TURK M, PENTLAND A. Eigenfaces for recognition [J]. Cognitive Neurosci, 1991,3(1):71-86.
　　[3]BELHUMEUR P N, KRIEGMAN D J. Eigenfaces vs. Fisherfaces: recognition using class specific linear projection[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 1997,19(7):711-720.
　　[4]TENENBAUM J B, DeSILVA V, LANGFORD J C. A global geome-tric framework for nonlinear dimensionality reduction[J/OL]. [2000-12-22]. http://www.sciencemag.org/content/vol290/issue5500/.
　　[5]ROWIES S, SAUL L. Nonliear dimensionality reduction by locally linear embedding[J/OL]. [2000-12-22]. http://www.sciencemag.org/cgi/content/full/290/5500/2323.
　　[6]BELKIN M, NIYOGO P. Laplacian eigenmaps for dimensionality reduction and data representation[J]. Neural Computation, 2003,15(6):1373-1396.
　　[7]HE Xiao-fei, NIYOGI P. Locality preserving projections[C]//Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2004:327-334.