基于正交拉普拉斯脸的人脸识别算法研究

直觉上，自然存在的人脸数据可以由支持的概率分布采样生成或者近似于环绕空间的子流线型分布。据此，我们提出了一种基于外观的人脸识别算法，称为正交拉普拉斯脸（Orthogonal Laplacianface，简称OLPP）。该算法基于局部保持映射（Locality Preserving Projection，简称LPP）算法，其中LPP算法的目标是找到在面部流形空间中拉普拉斯-贝特拉算子特征函数的一个线性近似。然而，LPP是非正交的，于是就给重建数据带来了困难。OLPP方法是生成正交基函数，相比于LPP将会拥有更好的邻域保护能力。因为邻域保护能力与分辨能力有着潜在的联系，所以OLPP有望比LPP具有更高的分辨能力。基于三个人脸数据库的实验结果表明了我们所提算法的有效性。

  

关键字： 基于外观的视觉 人脸识别 局部保持投影 正交局部保持投影

 

1 引言

最近，基于外观的人脸识别受到了很多关注^[20][14]。 一般来说，将尺寸为n1×n2的人脸图像表示为图像空间R ^n1×n2中的矢量。 我们用脸空间来表示所有人脸图像的集合。 虽然图像空间具有很高的维度，但是脸空间通常是嵌入在环绕空间中的维度很低的子流形。试图解决这个问题的一种常见方法是使用降维技术^{[1][2][8][12][11][17]}。发现脸部流形结构的最流行的方法包括Eigenface^[20]，Fisherface^[2]和Laplacianface^[9]。

人脸表征与流形学习的问题有着本质的联系 ^[3][16][19]这是一个新兴的研究领域。给定一组高维数据点，流形学习技术旨在发现数据空间的几何特性，如欧几里得嵌入，本征维度，连通分量，同源性等。特别是表征学习与嵌入问题密切相关，而聚类可以被认为是寻找到连通的分量。寻找面部空间的欧几里得嵌入来进行识别是本文工作的重点。流形学习技术可以分为线性和非线性方法。 对于脸部处理，出于计算复杂性的考虑，我们将特别关注线性方法。

本文提出了一种新的正交拉普拉斯算法。 O-Laplacianface本质上基于Laplacianface方法，它建立一个可以完美的反映出人脸流形的几何关系和采样点之间的分类关系的邻接图，然后通过保留这样的图形结构来获得投影。该算法有着与拉普拉斯脸相同的局部保留特征，不同的是它的基函数是正交的，正交基函数会保留脸部空间的度量结构。事实上， 如果我们由O-Laplacianface获得所有维度，那么投影映射只是一个旋转映射，不会扭曲度量结构。而且，我们的实验研究表明，O-Laplacianface比Laplacianface具有更多的局部保持能力。局部保存能力会直接关系到判别能力^[9]，预计O-Laplacianface具有比Laplacianface更高的分辨能力。

本文的其余部分安排如下，在第1.2节中，我们会简要回顾一下Laplacianface算法，紧接着第1.3节介绍我们的O-Laplacianface算法，在第1.4节会给出了我们的算法的理论证明。第1.5节给出了关于人脸识别的广泛的实验结果。最后，我们在第1.6节为未来工作提供了一些结论性意见和建议。

2 LAPLACIANFACE算法的简单回顾

Laplacianface是最近提出的用于人脸表示和识别的线性方法。 它基于局部保持投影^[10]，并且明确地考虑了人脸空间的流形结构。

给定一个人脸图像的集合令。设S是数据点上定义的相似度矩阵。 Laplacianface可以通过求解下面的最小化问题来获得：

约束项：

其中是拉普拉斯矩阵^[4]，。用来衡量 的局部密度。Laplacianface构造的相似矩阵S如下所示：

这里的事实上是热核权重，这样选择的理由和参数t的设定可以参考文献[3]。

拉普拉斯脸的目标函数中加入了一个惩罚项，以防止邻近的和被投影后离得很远 因此，最小化目标函数是为了确保如果和“接近”，则和也是接近的^[9]。 最后，Laplacianface的基函数是与下面广义特征问题的最小特征值有关的特征向量：

Laplacianface算法中在经过一些预处理后是非奇异的，因此，Laplacianface的基函数可以看作是矩阵最小特征值有关的特征向量。因为 一般来说是不对称的，所以Laplacianface的基函数是非奇异的。

一旦计算出特征向量，令为变换矩阵。因此可以求得两个数据点在降维空间的欧式距离为：

如果是正交矩阵，那么并且保持原始高维数据中的局部度量结构。

3 OLPP算法

在这一节中，我们介绍一种新的子空间学习算法，正交局部保留投影（OLPP）。正交Laplacianface算法在人脸表示和识别的基础就是OLPP。该算法的理论证明将在第1.4节介绍。

在基于外观的人脸分析中，常常面临人脸图像向量（ ）的维数远大于人脸图像数量（ ）的情况。因此，的矩阵 是奇异的。为了解决这个问题，我们首先应用PCA将人脸信息无丢失的映射到一个子空间，这样就变成非奇异的了。

OLPP算法的流程如下所示：

1.  PCA投影。通过去除与零特征值相对应的成分将脸部图像投影到PCA子空间中。用 表示PCA的变换矩阵。通过PCA投影，提取的特征是统计不相关，新数据矩阵的级数等于特征的数量（维度）。

2.  构造邻接图：G表示有 个节点的图。第 个节点与面部图像 相对应。如果是接近的，那么就用一条边将其连起来。所以如果类信息是已知得到，我们就可以直接将两个属于同一类的数据点连起来。

3.  选择权重：如果节点和是相连接的，那么，否则。图G的权重矩阵S模拟了脸部流型的局部结构。

4.  计算正交基函数。定义D为对角阵，元素为S的行（或列，S是对称的）之和，。同样定义，在谱图理论中被称为拉普拉斯矩阵^[4]，令是正交基向量，定义

正交基向量可以通过以下过程得到

l  是最小特征值的特征向量

l是的最小特征值的特征向量

5.  OLPP嵌入：令，那么嵌入方式如下所示。

是面部图像的的维表示，是转换矩阵。

4 OLPP算法证明

这一节，我们将为我们提出的算法提供理论证明。

4.1 可选择的正交嵌入

定义是一个投影图。局部保留函数的定义如下。

                            （1）

数据由底层流形数据抽样得到。我们假设有映射，梯度是流形上的向量场，利于对于很小的

因此，我们可以看出如果很小，附近的点将被映射到近的点。我们可以用

                      （2）

来衡量平均图的局部保持能力^[3]。有限个样本 和一个线性投影映射，是方程（2）的离散近似^[10]。 同样，评估投影图的局部保持能力。

最小化函数将直接得到原有的LPP算法，我们的OLPP算法试图去找到一组最小化局部保持函数的正交基向量。因此是最小化的依序向量，约束为。

OLPP的目标函数是，

                           (3)

并且有，

                       （4）

约束条件为。

因为经过PCA映射后正定，对于任意，总是可以将其标准化，例如，并且与的比例是不变的。因此，求最小值的问题就等价于在约束为的条件下，求最小值的问题。

请注意，上述规范化仅用于简化计算。 一旦我们得到最优解，我们可以重新归一化它们以得到一个正交基向量。

很容易验证是一般性特征问题最小特征值相关的特征向量。因为是非奇异的，所以就是与矩阵最小特征值相关的特征向量。

为了得到第k个基向量，我们最小化目标函数为：

                        （5）

约束为：

，

我们可以用拉格朗日成字符来变换上述的目标函数，并包含所有的约束

设置相对于的偏导数为零进行优化

                                     （6）

将（6）式的左边乘以，可以得到

                            （7）

                

对比（5）式，确切地表示出要最小化的表达式。

将（6）式的左边依次乘以，于是便可得到一系列k-1个等式

……

我们定义：

，

利用上述简化符号，之前的k-1个等式可以用一个简单的矩阵关系表示

因此

               （8）

我们将（6）式的左边乘以 得到

用矩阵表示法表示为

利用等式（8），我们得到

正如（7）式所示,只是最小化的标准，于是是最小特征值相关的特征向量。

最后，我们得到最优的正交基向量。O-Laplacianface的正交基保留了面部空间的度量结构。值得注意的是，这里提出的推到出自文献[5]。

回到Laplacianface方法中，基向量的前k个特征向量与广义特征问题最小特征值相关。

                      （9）

因此，基向量满足以下等式：

显然，Laplacianface（LPP）方法的变换是非正交的。 事实上，它是 正交。

4.2 局部保持能力

LPP和OLPP算法都试图保持局部几何特征。通过最小化局部保持函数，它们找到基向量。

                         （10）

 

反映出投影映射的局部保持能力。

在LPP算法中，基于特征矩阵的瑞利熵格式（式（9））^[7]， 的值恰好是式(9)的特征值， 是其特征向量。因此LPP算法的特征值反应了LPP算法的局部保持能力。在OLPP算法中，正如式（7）所示，OLPP的特征值也反映了其局部保持能力。我们将LPP和OLPP算法进行了比较。

图1-1展示了LPP和OLPP算法的特征值。研究所用的数据集是PIE人脸数据库（详情见1.5.2节）。如图所示，OLPP算法的特征值始终小于LPP算法，这就表明OLPP算法比LPP算法有更好的局部保持能力。

图1-1 LPP和OLPP算法的特征值

文献[9]中表明局部保持能力与分辨力直接相关，所以我们可以说在人脸表示和识别领域O-Laplacianface（OLPP）比Laplacianface（LPP）有更好的表现。

5 实验结果

在本节中，我们研究了O-Laplacianface（PCA+OLPP）在人脸表示和识别领域的表示。并将其表现与在人脸识别领域最受欢迎的三种线性方法——Eigenface方法（PCA），Fisherface方法（PCA+LDA）和Laplacianface方法（PCA+LPP）作比较。Laplacianface和O-Laplacianface使用相同的建立在标签信息基础上的图结构。

本次研究测试了三个人脸数据库，分别是Yale、ORL（(Olivetti Research Laboratory）和CMU的PIE（pose, illumination,and expression）^[18]。所有的实验都使用预先标定的人脸数据。原始图像是手动标齐的（两只眼睛对齐于相同的位置），经过裁切的，最后重新调整为256个灰度值，大小为32 32的图像。每一个图像在向量空间由1024维的向量表示。不同的图案分类算法被应用在人脸识别中，例如最近邻、贝叶斯、支持向量积。在这篇论文中，我们应用简单的最近邻分类方法。欧几里得度量用来测量距离。

总之，识别过程分为三步。首先，我们从测试样本中得到人脸子空间；紧接着，被用来识别的新的人脸图像通过我们的算法映射到D维子空间；最后，新的人脸图像通过最近邻分类方法被识别。

我们所有的算法都是在Matlab7.04上实现的。Matlab形式的代码和数据库可以在http://www.ews.uiuc.edu/~dengcai2/Data/data.html上下载。

5.1 O-Laplacianfaces算法进行人脸表示

在这一小节中，我们将比较人脸表示的四种算法Eigenface，Fisherface，Laplacianface，和O-Laplacianface。对于任意一种算法，基向量被当做是基图像，其它任何图像都是这些基图像的线性组合。在图像域中看这些图像的样子是很有意思的一件事情。

利用ORL人脸数据库，我们在图1-2分别展示了6张O-Laplacianfaces，Eigenfaces，Fisherfaces和Laplacianfaces。

图1-2 由ORL数据库中的人脸图像得到的Eigenfaces，Fisherfaces，Laplacianfaces和O-Laplacianfaces

5.2 Yale数据库

Yale人脸数据库有Yale计算机视觉和控制中心构建。包括15个不同个体的165张灰度图片。图像有不同的光线条件、面部表情（正常、高兴、伤心、困、惊喜、眨眼）。图1-3显示了Yale数据库同一个人的11张图片。每个人含有标签的 张图片的随机的子集构成训练集，数据库中剩下的图片便被当做是测试集。对于每一个 ，由平均20次随机分裂中得到。既然，对于LDA算法，最多有 -1非零特征值，所以空间降维的最大值是 -1，其中 是个体的数量^[2]。通常来说，以上所有算法的表现随着维数的变化而变化。从表1中可以看出，Eigenface，Fisherface，Laplacianface，O-Laplacianface和baseline方法得到的最好结果和最理想的维数。对于baseline方法，用来进行识别的图像维度是1024，没有经过降维处理。

图1-3 来自Yale数据库的人脸示例图像。对于每一个对象，都有11张在不同光线条件下带有表情的人脸图像。

表5-1：对比算法通过Yale数据库的表现

Method	2 Train	3 Train	4 Train	5 Train
Baseline	56.5%	51.1%	47.8%	45.6%
Eigenfaces	56.5%(29)	51.1%(44)	47.8%(58)	45.2%(71)
Fisherfaces	54.3%(9)	35.5%(13)	27.3%(14)	22.5%(14)
Laplacianfaces	43.5%(14)	31.5%(14)	25.4%(14)	21.7%(14)
O-Laplacianfaces	44.3%(14)	29.9%(14)	22.7%(15)	17.9%(14)

（a）2 Train       （b）3 Train          （c）4 Train        （d）5 Train

图1-4 Yale数据库中错误率VS下降维度

可以看出，我们的算法表现最好。Laplacianfaces 和Fisherfaces的表现跟我们的算法还有可比性，但是Eigenfaces算法表现很差。图1-4显示错误率与维数约减成反比。具有参考价值的是，在只有两个训练样本的情况下，Fisherfaces方法的表现甚至比baseline和Eigenfaces方法还要差。这一结果与文献[12]中Eigenface方法在小样本集的情况下比Fisherface方法有更好的表现的观察一致。

5.3 ORL数据库

ORL人脸数据库应用于测试。它包含40个个体的400张图片。一些图片在不同的时间采集，有不同的表情（睁眼或闭眼，笑或者不笑），和细节（一个或两个眼镜）。图像允许倾斜和20度以内的旋转。一个个体的10个样本图片如图1-5中所示。每个人含有标签的 （=2，3，4）张图片的随机子集构成训练集，数据库中剩下的图片便被当做是测试集。对于每一个给定的 ，由平均20次随机分裂中得到。实验方案与之前一样。识别结果在表2和图1-6中可以查看。我们的O-Laplacianface比其他的算法表现优越。

图1-5 ORL数据库中人脸图像，对于任一图像，都有10张不同的人脸表情细节的图像。

表5-2：对比算法在ORL数据库的表现

Method	2 Train	3 Train	4 Train	5 Train
Baseline	33.8%	24.6%	18.0%	14.1%
Eigenfaces	33.7%(78)	24.6%(119)	18.0%(159)	14.1%(199)
Fisherfaces	28.9%(22)	15.8%(39)	10.5%(39)	7.75%(39)
Laplacianfaces	23.9%(39)	13.4%(39)	9.58%(39)	6.85%(40)
O-Laplacianfaces	20.4%(40)	11.4%(39)	5.92%(48)	3.65%(59)

图1-6 ORL数据库中错误率VS维度约减

5.4 PIE数据库

CMU PIE数据库包括68个个体的41368个人脸图像。人脸图像由13个同步摄像机和21个闪光灯在不同姿势、照明和表情下拍摄得到。我们选择5种接近正面的姿势（C05，C07，C09，C27，C29）并且取其在不同照明、光线和表情下的所有图像，每一个个体最终剩下大约170张接近正面的图像。如图1-7所示为有着不同姿势、表情和光线的一个个体的图像。每个人含有标签的 （=2，3，4）张图片的随机子集构成训练集，数据库中剩下的图片便被当做是测试集。对于每一个给定的 ，由我们平均20次随机分裂中得到。表5-3给出识别结果。

如图表所示，我们的方法要比明显比其他方法表现更好。Laplacianfaces 和Fisherfaces的表现跟我们的算法还有可比性，但是Eigenfaces算法表现很差。图1-8显示错误率与维数约减成反比。

图1-7 CMU PIE数据库中的人脸图像。对于每一个个体，由170个不同姿势、光线和表情的接近正面的人脸图像

表5-2：对比算法在PIE数据库的表现

Method	2 Train	3 Train	4 Train	5 Train
Baseline	69.9%	55.7%	38.2%	27.9%
Eigenfaces	69.9%(338)	55.7%(654)	38.1%(889)	27.9%(990)
Fisherfaces	31.5%(67)	22.4%(67)	15.4%(67)	7.77%(67)
Laplacianfaces	30.8%(67)	21.1%(134)	14.1%(146)	7.13%(131)
O-Laplacianfaces	21.4%(108)	11.4%(265)	6.51%(493)	4.83%(423)

图1-8 PIE数据库中错误率VS维度约减

5.5 讨论

实验总结如下：

1.我们提出的O-Laplacianface方法始终比Eigenface，Fsherface和Laplacianface方法表现突出。

2. Fisherface，Laplacianface和 O-Laplacianface方法都比基于线性的方法表现突出。Eigenface没有任何改进的原因是没有编码分辨信息。

3. 从低维人脸空间在实验中表现可以看出，降维在人脸识别的预处理中十分重要的。

6总结和展望

我们提出了一种用于人脸表示和识别的新算法，称为正交拉普拉斯脸。正与实验结果所示，正交拉普拉斯脸比拉普拉斯脸有更好的分辨能力。

未来我们将就几个仍然模糊不清的问题进行研究：

1 在大部分已有的人脸分析中，都是假设数据空间是连通的。相应的，数据空间有固定的维度。但是，现实世界中的数据可能并不是这样的。具体来说，不同人的人脸流形可能具有不同的几何特征，例如，维度。数据空间也可以是非连通的，不同的人脸部位（单个流形）也可以有不同的维度。目前还不清楚这些情况发生的概率以及要如何去处理这些问题。

2 正交拉普拉斯脸是线性的，正交拉普拉斯曲面是线性的，但是它也可以在再生核希尔伯特空间的情况下执行，这会导致非线性映射。 OLPP在再生核希尔伯特空间上的性能需要进一步研究。

作者信息

参考文献

[1] A. U. Batur and M. H. Hayes. Linear subspace for illumination robust face recognition. In

IEEE Conference on Computer Vision and Pattern Recognition, 2001.

[2] P.N. Belhumeur, J.P. Hepanha, and D.J. Kriegman. Eigenfaces vs. fisherfaces: recognition using class specific linear projection. IEEE Trans. on Pattern Analysis and Machine Intelligence,19(7):711–720, 1997.

[3] M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and

clustering. In Advances in Neural Information Processing Systems 14, pages 585–591. MIT Press, Cambridge, MA, 2001.

[4] Fan R. K. Chung. Spectral Graph Theory, volume 92 of Regional Conference Series in Math-ematics. AMS, 1997.

[5] J. Duchene and S. Leclercq. An optimal transformation for discriminant and principal com-ponent analysis. IEEE Trans. on PAMI, 10(6):978–983, 1988.

[6] R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification. Wiley-Interscience,Hoboken,

NJ, 2nd edition, 2000.

[7] G. H. Golub and C. F. Van Loan. Matrix computations. Johns Hopkins University Press, 3rd

edition, 1996.

[8] R. Gross, J. Shi, and J. Cohn. Where to go with face recognition. In Third Workshop on Empirical Evaluation Methods in Computer Vision, Kauai, Hawaii, December 2001.

[9] X. He, S. Yan, Y. Hu, P. Niyogi, and H.-J. Zhang. Face recognition using laplacianfaces. IEEE

Trans. on Pattern Analysis and Machine Intelligence, 27(3), 2005.

[10] Xiaofei He and Partha Niyogi. Locality preserving projections. In Advances in Neural Infor-mation Processing Systems 16. MIT Press, Cambridge, MA, 2003.17

[11] Q. Liu, R. Huang, H. Lu, and S. Ma. Face recognition using kernel based fisher discrimi-

nant analysis. In Proc. of the fifth International Conference on Automatic Face and Gesture

Recognition, Washington, D. C., May 2002.

[12] A. M. Martinez and A. C. Kak. PCA versus LDA. IEEE Trans. on PAMI, 23(2):228–233,

2001.

[13] B. Moghaddam and A. Pentland. Probabilistic visual learning for object representation. IEEE Trans. on PAMI, 19(7):696–710, 1997.

[14] H. Murase and S. K. Nayar. Visual learning and recognition of 3-d objects from appearance.International Journal of Computer Vision, 14, 1995.

[15] P. J. Phillips. Support vector machines applied to face recognition. Advances in Neural

Information Processing Systems, 11:803–809, 1998.

[16] S Roweis and L Saul. Nonlinear dimensionality reduction by locally linear embedding. Science,290(5500):2323–2326, 2000.

[17] T. Shakunaga and K. Shigenari. Decomposed eigenface for face recognition undervarious

lighting conditions. In IEEE Conference on Computer Vision and Pattern Recognition, Hawaii,

December 2001.

[18] T. Sim, S. Baker, and M. Bsat. The CMU pose, illuminlation, and expression database. IEEE Trans. on PAMI, 25(12):1615–1618, 2003.

[19] J. Tenenbaum, V. de Silva, and J. Langford. A global geometric framework for nonlinear

dimensionality reduction. Science, 290(5500):2319–2323, 2000.

[20] M. Turk and A. Pentland. Eigenfaces for recognition. Journal of Cognitive Neuroscience,

3(1):71–86, 1991.

[21] M. Turk and A. P. Pentland. Face recognition using eigenfaces. In IEEE Conference on Computer Vision and Pattern Recognition, Maui, Hawaii, 1991.