对ORL人脸数据库识别过程中的参数选择策略

冯加明

摘  要： 对ORL人脸数据库的识别大致分为两步骤：使用PCA对训练集降维提取特征向量和使用KNN对样本集进行分类。在该过程中，有两个参数直接影响着人脸识别的准确率：PCA选取的特征向量数目n和KNN中的k值。如果对它们的选取没有一个良好的策略，就会出现正确率太低、时间复杂度太高、过拟合等问题。文章采用状态空间搜索找到准确率与时间复杂度中的平衡点，得到了有效的搜索结果。

关键词： 人脸识别; PCA; KNN; 图搜索

中图分类号：TP183          文献标识码：A     文章编号：1006-8228（2021）02-27-04

Parameter selection strategy for recognition of ORL face database

Feng Jiaming

（Dalian Maritime University， DaLian， LiaoNing 116026， China）

Abstract： The recognition of ORL face database is roughly divided into two parts： using PCA to reduce the dimension of the training set， extracting feature vectors， and using KNN to classify the sample set. In the processes， two parameters directly affect the accuracy of face recognition： the number of feature vectors n selected by PCA and the K value in KNN. If there is no good strategy for their selection， there will be problems such as low accuracy， high time complexity， over fitting and so on. This paper uses state space search to find the balance between accuracy and time complexity， and effective search results has been obtained.

Key words： face recognition; PCA; KNN; graph search

0 引言

人脸识别是模式识别图像处理中一个重要的方向。1965年，Bledose等人在PanoramicResearchInc上首次发表了一篇关于人脸识别的报告[1]，开创了人脸识别研究的先河。1965年至1990年，人脸识别的主要方法是基于几何结构特征和模板匹配。1991年，麻省理工学院的Turk等人提出了一种”特征脸Eigenface”[2]，被称为后来其他大多数人脸识别算法的基准。1992年，Brunelli等人的实验结果表明基于模板匹配的方法一般优于基于几何特征的方法[3]。1997年，Belhumeur等人提出了Fisherface[4]，一种基于子空间分析的人脸识别算法。二十一世纪出现了许多对局部领域图像进行手工特征提取的方法，例如对人脸比较有效的基于无监督学习的特征LeamingDescriptors[5]与GaborFace、LBPFace[6]等。

本文使用的数据集为ORL人脸数据集。采用十次十折交叉实验求得平均正确率构造K-N-正确率矩阵并绘制三维图像。

1 相关技术

1.1 PCA主成分分析

PCA本質上是一种线性降维的方法[7]。

PCA的主要思想是将原本的高维特征映射到低维度上，即全新的正交特征，亦称主成分。PCA的工作就是从原始的空间中顺序地找一组相互正交的坐标轴，新的坐标轴的选择与数据本身是密切相关的。利用正交变换作为映射矩阵，其具体步骤如下。

⑴ 假设一共有a张b*c的图像，则将其展开储存在一个a*（b*c）的二维矩阵X内（见图1）。

⑵ 将X的每一行的每个值减去该行的平均值。这两步统称数据标准化。

⑶ 求出协方差矩阵C：

⑷ 使用pythonnumpy库中的linalg.eig函数对协方差矩阵C进行奇异向量分解，求出其特征值矩阵和特征向量。由于本文是对ORL人脸数据库的分析，所以求出的特征值可以展开为特征脸，用于构造判别空间的基向量（见图2）。

⑸ 按降序对特征值进行排序并选择前N个特征向量。

⑹ 利用选择出的特征向量转换原始数据集，得到N维特征子空间。

1.2 KNN（k近邻法）[8]

KNN（k-Nearest Neighbors）是一种分类算法，最初由Cover和 Hart 在1968年提出。其应用场景较为广泛，包括文字匹配，图像识别，文本分类等。

该方法的核心思路为：在与测试集样本中按某种距离（此处为欧氏距离）最相似的K个点中，属于某一类的点最多，则该测试集样本也属于这个类别。

欧式距离在本文问题中的变形：

其中S表示的是第i个训练集样本T和第j个测试集样本t之间的欧氏距离。N为PCA中选取的特征数量。

1.3 GBFS贪婪最佳优先算法[9]

GBFS的搜索策略与深度优先搜索（DFS）和广度优先搜索（BFS）并没有本质上的区别。但GBFS引入了“优先队列”的数据结构概念。在GBFS的节点删除中使用代价函数h（p）来作为判断节点优先级的标准。在本文中，其含义为从原点到点p所需的代价。

GBFS也有一定的缺点：当遇到局部搜索障碍的时候，GBFS無法找到最优路径甚至最终无法找到最优解。所以在本次实验中将选取多个搜索起始点以减小该因素带来的不利影响。

2 基于PCA与KNN的人脸识别实验

2.1 数据来源

ORL人脸数据集为40组每组10张共400张112*92的黑白灰度色值图像（见图3）。在1992年4月至1994年4月期间由英国剑桥的Olivetti研究实验室创建。

每一个类别的人脸图像，都是在不同的情况下采集的。所有的图像都是在较暗的均匀背景下拍摄的正脸或有轻微偏移的图像[10]。

2.2 Python实现流程（如图4）

求得的正确率（TP）随着K-N变化的矩阵三维图如图5所示。

2.3 h（p）函数的选取

由于本文的主旨是寻求时间复杂度与准确率之间的平衡点，所以分别对PCA与KNN的时间复杂度进行分析。

⑴ PCA中选取的特征值个数N参与以下两个过程：创建数组以及计数循环。可知程序关于N的时间复杂度为O（N）。

⑵ 而KNN的时间复杂度同时依赖于样本的特征维度与K值的选择，所以最终求得KNN的时间复杂度为O（N*K）[11]。

主程序中，PCA与KNN是两个完全独立的过程，所以，程序的总时间复杂度为二者的累加，即

h（p）=TP-e（N+N*K）

其中e为一个常数，用于将h（p）的值调整至0到1的范围内。

2.4 图搜索的过程

首先，确定一个搜索起始点，那么对于这个点，其搜索方向见图6。

为了降低GBFS受到局部最优陷阱的影响，本文采用横坐标从0到20步长为2，纵坐标0到200步长为20的11个起始点进行多次搜索。程序判断下一搜索方向的点的h（p）值是否大于当前搜索点，并选择其最大点替换。

搜索边界为：当搜索点周围不存在比搜索点h（p）值更高的点时，或者搜索到矩阵边界的时候停止，返回该搜索点。

最终得到搜索结果，如图7所示。

2.5 结果分析

从图7可以看出，在11个起始点中，数目最多的搜索结果是[3，320]，故确定在该h（p）函数下的最优结果为[3，320]。

最优点选取的特征向量个数N较少，而KNN中的K值却偏大。其原因是N影响时间复杂度的程度更大，而K值影响正确率的程度更大。所以在人脸识别的过程中，可以适当地降低N，适当地提高K，在保证正确率的同时降低花费的时间。

3 结论

本文对ORL人脸数据库进行了分类处理，并综合正确率矩阵与时间复杂度得到了较为有效的参数选取策略。

要进一步提高策略的有效性，可以通过选取其他的搜索算法来实验。所以后续的研究可以围绕不同搜索算法对参数选取策略的影响来研究。

参考文献（References）：

[1] BledsoeW W.Man-machine facial recognition[J]. Rep. PRI，1966，22

[2] Turk M， Pentland A. Eigenfaces for recognition[J].Journalof cognitive neuro science，1991，3（1）：71-86

[3] Brunelli R， PoggioT. Face recognition： features versustemplates[J]. IEEE transactions on pattem analysis and machine intelligence，1993，15（10）：1042-1052

[4] Belhumeur P N， Hespanha J P， Kriegman D J.Eigenfacesvs. fisherfaces： Recognition using class specific linear projection[J].IEEE Transaction sonpattem analysis and machine intelligence，1997，19（7）：711-720

[5] Winder S A J， Brown M， Learning Local  Image Descriptors[C]//Computer Visionand Pattem Recognition，2007.CVPR'07.IEEE Conferenceon.IEEE，2007：1-8

[6] Chen D.CaoX，WenF，etal.Blessing of dimensionality： High-dimensional feature and its efficient compression for face verification[C]//Proceedings of the IEEE Conferenceon Computer Vision and Pattern Recognition，2013：3025-3032

[7] 付氐，陈中举，杜友福.基于PCA和SVM的人脸识别研究[J].电脑知识与技术，2019（3）：209-211

[8] 平原2018.机器学习之KNN（k近邻）算法详解.CSDN，2018-07-03

[9] 鬼木士.路径规划|图搜索算法：DFS、BFS、GBFS、Dijkstra、A*.知乎，2021.2.2

[10] fengbingchun. ORL Faces Database介绍.CSDN，2018-01-09