基于SIFT的改进人脸识别算法

陈新义

（四川大学计算机学院，成都 610065）

0 引言

人脸识别技术是近年来被广泛研究的热点之一。现阶段人脸识别算法主要分为基于全局特征的人脸识别算法和基于局部特征的人脸识别算法，基于局部的图像特征点的方法对人脸图像在形变、旋转、一定程度放射变换等条件下具有比基于全局特征的算法更好的匹配效果,是人脸识别算法的热门发展趋势。David Lowe在1999年提出2004年完善的尺度不变特征转换（Scale Invariant Feature Transform）算法[1]（简称SIFT算法）对发生旋转、平移、和仿射变换后的图像有很好的匹配效果。SIFT特征是一种表示物体外观局部区域的描述子，具有很强的稳定性和鲁棒性，与图像中物体的大小、位置、旋转角度的变化无关，并且对噪声、光照以及微视角等变化的稳定性相当高，另外，SIFT特征对于遮挡物体的检测和分辨率也相当高[2-6]。

SIFT特征点描述子是一个128维的特征描述向量，也可以看做是一个特征直方图。原始的SIFT特征点的匹配策略是使用欧氏距离计算特征直方图的匹配程度,设置一个阈值作为匹配程度的标准，当图像A中待匹配的特征点与图像B中的最近特征点的比值（最近距离/次最近距离）小于这个阈值时，认为匹配成功,否则不成功。EMD距离[7]是一个具有感知鲁棒性的直方图距离度量方法，使用EMD距离计算两个特征直方图间的匹配程度更加准确,但是EMD距离的计算时间复杂度比较高，运行算法时，势必会消耗很多时间，因此本文引入快速EMD距离[8]对两个特征直方图的匹配程度进行计算,该改进算法在一定程度上提高了在人脸图像在旋转、放射变换、部分遮挡等复杂情况下的特征匹配度[9-16]。

1 快速EMD距离的SIFT特征点匹配策略

1.1 EMD距离

EMD（Earth Mover's Distance）距离是由 Yossi Rubner等在2000年提出的，用来计算两个直方图之间匹配度的方法。在直方图匹配度算法中，EMD距离在图像发生形变、检测器定位误差等方面与欧氏距离相比，有更好的匹配效果和更强的鲁棒性。

在Yossi Rubner的论文中提出了signature的概念，signature的定义如下：

其中，s代表一类特征，m为其中心，w为属于该类中心的数量，对于一维的直方图，m为直方图bin的索引，w为该bin的数量（权重）。下面介绍EMD距离的计算方法[7]：

其中，D=[dij]是距离矩阵，dij代表类 pi和qj之间的距离（在均匀的直方图中，距离可以简化为bin的索引的差值得绝对值）。F={fij}是类间流动矩阵，fij代表类 pi和 qj之间流（flow）的数量。约束（3）-（6）是指，约束（3）限制了P到Q的单向流动，且流（flow）不能小于0；约束（4）限制了P类供应量不能超过它的数量，约束（5）限制了Q类接收量不能超过它们的数量；约束（6）是指最大程度的移动数，也就是总流（flow）的数量。

经过简化，式（6）可简化为：

1.2 快速EMD距离

由于EMD距离的计算复杂度高,运行人脸匹配算法时，势必会消耗很多时间。因此,本文快速EMD距离来测量特征直方图之间的匹配度。

假设有P、Q两个特征直方图，P={(p1,wp1)，其中 pi为特征点wpi为其权重，qi为特征点wqi为其权重（这里假设n=m=4）。则EMD距离与快速EMD距离对比如图1所示。

Ofir Pele等提出的快速EMD距离的计算方法如下[8]：

若m=n，经过简化，式（8）可简化为：

图1 EMD距离和快速EMD比较

EMD距离与快速EMD距离相比，在寻找最佳运量时算法复杂度从O（n2）级降低为O（n）级，运算速度提升了一个数量级。Ofir Pele和Michacl Werman在论文中证明，在P、Q两个直方图的总量一致时，EMD距离与快速EMD距离是等价的，在P,Q两个直方图的总量不相等时，快速EMD距离拥有更好的区分力[8]。下面给出两个示例来说明：

1）令 P=（1,0），Q=（0,1），P'=（9,0），Q'=（0,9）。使用 L1范式作为地面距离（ground distance），α=1，对 P、Q 计算 EMD 距离得：EMD（P，Q）=1、EMD（P'，Q'）=1，计算快速EMD距离的：9。显然，当直方图的总量更为重要时更具有区分度。

2）令 P=（1,0），Q=（1,7）。使用 L1范式作为地面距离（ground distance），α=1时，计算 EMD距离得：EMD（P，Q）=0，而快速 EMD 距离为因此，当P、Q总量不等时，快速EMD距离更有区分度。

1.3 结合快速EMD距离的SIFT特征直方图匹配

本文使用快速EMD距离代替原SIFT算法中使用的欧氏距离来计算特征直方图间的匹配程度。使用快速EMD距离的SIFT特征直方图匹配策略如下：

令P和Q来代表任意空间尺度上的两个特征点的特征直方图。可以得到：

2 实验验证与分析

YALE人脸库由耶鲁大学计算视觉与控制中心创建,包含15位志愿者的165张图片,每副图像的大小是243×320像素，包含光照,表情和姿态的变化，其中的姿态和光照变化的图像都是在严格控制的条件下采集的。本文将结合快速EMD距离的SIFT人脸识别算法应用到YALE人脸库中,进行实验验证，并与原SIFT算法进行对比,对实验结果进行分析,并展示改进后算法在识别率及鲁棒性上的提升。实验所用的机器是Intel Core i5 6400 CPU，8G内存。仿真程序用MATLAB2012编写。

2.1 改进算法的识别准确率

实验1本次实验分为训练组和测试组，训练组包含4张人脸图像，作为算法的训练输入,测试组包含剩余的7张人脸图片，作为算法的测试输入。对每一组训练组测试组测试6次，取平均值作为最后的识别率结果。如表1所示（表中第一行数据为原始SIFT算法，命名为SIFT；表中第二行数据为改进算法命名为FEMD-SIFT）。

由表1可得FEMD-SIFT人脸识别算法比原始SIFT算法具有更好的识别效果。说明使用快速EMD距离度量两个特征直方图间的匹配度,可以有效避免欧氏距离在人脸图像发生旋转、放射变换、遮挡时造成的匹配度下降问题,可以在一定程度上提升人脸识别算法的识别率。

表1 SIFT人脸识别算法和结合快速EMD距离的SIFT人脸识别算法的识别率对比

2.2 改进算法的鲁棒性

实验2将YALE人脸库中每个人的一部分的人脸图像进行噪声，旋转，放射变换以及部分遮挡等操作。将每一个人的没有改变的图像作为训练组，改变后的图像作为测试组，对每一组训练租测试组测试5次，取匹配数的平均值作为结果。

图2展示的是原始SIFT算法与FEMD-SIFT算法对有遮挡的人脸特征点匹配对比图，其中SIFT即表示使用原始SIFT算法的特征点匹配个数，FEMD-SIFT表示使用FEMD-SIFT算法的特征点匹配个数。

由图2可以看到使用快速EMD距离的FEMDSIFT人脸识别算法特征点的匹配对数相比使用欧氏距离的原始SIFT人脸识别算法在噪声、旋转、仿射变换以及遮挡等方面的匹配数量都有一定的提升，可以得出FEMD-SIFT人脸识别算法相比原始SIFT人脸识别算法在人脸图像发生仿射变换或遮挡时具有更好的鲁棒性。

图2 原始SIFT算法与FEMD-SIFT算法特征点匹配对比图

3 结语

本文提出了一种基于SIFT改进的人脸识别算法,通过使用快速EMD距离而不是欧氏距离计算人脸图像特征直方图间的匹配度。实验表明,改进的人脸识别算法比原有算法具有更高的识别率及对人脸图像在旋转、放射变换以及遮挡等方面有更好的鲁棒性。但算法使用128维SIFT描述子，计算的复杂度仍较大，下一步可以考虑对SIFT描述子进行降维处理。

参考文献：

[1]David G Lowe.Distinctive Image Features from Scale-invariant Keypoints.IEEE International Journal of Computer,vol 60：91-110,2004.

[2]Jun Luo,Yong Ma,Erina Takikawa,Shihong Lao,Masato Kawade,Bao-Liang Lu.Person-Specific SIFT Features for Face Recognition,ICASSP，2007.

[3]Ke Y,Sukthankar R.PCA-SIFT:A More Distinctive Representation for Local Image Descriptors.Proceedings of the 2004 IEEE Computer Society Conference on IEEE,vol.2,2004：506-513.

[4]Z.Zhou,S.Cheng and Z.Li,MDS-SIFT:An Improved SIFT Matching Algorithm Based on MDS Dimensionality Reduction,2016 3rd International Conference on Systems and Informatics（ICSAI）,Shanghai,2016：896-900.

[5]X.Zhou,K.Wang and J.Fu.A Method of SIFT Simplifying and Matching Algorithm Improvement,2016 International Conference on Industrial Informatics-Computing Technology,Intelligent Technology,Industrial Information Integration（ICIICII）,Wuhan,2016：73-77.

[6]W.Hu,W.Zhou and J.Guan.A Modified M-SIFT Algorithm for Matching Images with Different Viewing Angle,2016 IEEE International Conference on Signal and Image Processing（ICSIP）,Beijing,2016：247-250.

[7]Yossi Rubner,Carlo Tomasi,Leonidas J.Guibas.The Earth Mover's Distance as a Metric for Image Retrieval,vol 40,2000：99-121.

[8]Ofir Pele，Michael Werman.Fast and Robust Earth Mover's Distances.2009 IEEE 12th International Conference on Computer Vision，2009：460-467.

[9]O.Pele，M.Werman.Robust Real Time Pattern Matching Using Bayesian Sequential Hypothesis Testing.PAMI,2008.

[10]O.Pele,M.Werman.A Linear Time Histogram Metric For Improved Sift Matching.In ECCV,2008.

[11]Shungang Hua1,Guopeng Chen,Honglei Wei，Qiuxin Jiang.Similarity Measure for Image Resizing Using SIFT Feature,EURASIP Journal on Image and Video Processing,2012：1687-5281.

[12]Dong Xu,Tat-Jen Cham,Shuicheng Yan,Shih-Fu Chang.Near Duplicate Image Identification with Spatially Aligned Pyramid Matching.IEEE Transactions on Circuits And Systems for Video Technology,Vol.20,NO.8,August 2010.

[13]Cong Geng,Xudong Jiang.Face Recognition Using Sift Features.Image Processing（ICIP）,2009,10.1109/ICIP.2009.5413956.

[14]Cheng-yuan Tang,Yi-leh Wu,Maw-kae Hor,Wen-hung Wang,Modified Sift Descriptor for Image Matching Under Interference,Proceedings of the Seventh International Conference on Machine Learning and Cybernetics,Kunming,12-15 July 2008.

[15]Fan Wang and Leonidas J.Guibas,Supervised Earth Mover's Distance Learning and Its Computer Vision Applications,in ECCV 2012,Part I,LNCS 7572,2012：442-455

[16]J.Gudmundsson,O.Klein,C.Knauer,M.Smid.Small Manhattan Networks and Algorithmic Applications for the Earth Movers Distance.In EWCG,2007.

[17]http://cvc.cs.yale.edu/cvc/projects/yalefaces/yalefaces.html.