陳新義

（四川大學(xué)計算機學(xué)院，成都 610065）

0 引言

人臉識別技術(shù)是近年來被廣泛研究的熱點之一?，F(xiàn)階段人臉識別算法主要分為基于全局特征的人臉識別算法和基于局部特征的人臉識別算法，基于局部的圖像特征點的方法對人臉圖像在形變、旋轉(zhuǎn)、一定程度放射變換等條件下具有比基于全局特征的算法更好的匹配效果,是人臉識別算法的熱門發(fā)展趨勢。David Lowe在1999年提出2004年完善的尺度不變特征轉(zhuǎn)換（Scale Invariant Feature Transform）算法[1]（簡稱SIFT算法）對發(fā)生旋轉(zhuǎn)、平移、和仿射變換后的圖像有很好的匹配效果。SIFT特征是一種表示物體外觀局部區(qū)域的描述子，具有很強的穩(wěn)定性和魯棒性，與圖像中物體的大小、位置、旋轉(zhuǎn)角度的變化無關(guān)，并且對噪聲、光照以及微視角等變化的穩(wěn)定性相當高，另外，SIFT特征對于遮擋物體的檢測和分辨率也相當高[2-6]。

SIFT特征點描述子是一個128維的特征描述向量，也可以看做是一個特征直方圖。原始的SIFT特征點的匹配策略是使用歐氏距離計算特征直方圖的匹配程度,設(shè)置一個閾值作為匹配程度的標準，當圖像A中待匹配的特征點與圖像B中的最近特征點的比值（最近距離/次最近距離）小于這個閾值時，認為匹配成功,否則不成功。EMD距離[7]是一個具有感知魯棒性的直方圖距離度量方法，使用EMD距離計算兩個特征直方圖間的匹配程度更加準確,但是EMD距離的計算時間復(fù)雜度比較高，運行算法時，勢必會消耗很多時間，因此本文引入快速EMD距離[8]對兩個特征直方圖的匹配程度進行計算,該改進算法在一定程度上提高了在人臉圖像在旋轉(zhuǎn)、放射變換、部分遮擋等復(fù)雜情況下的特征匹配度[9-16]。

1 快速EMD距離的SIFT特征點匹配策略

1.1 EMD距離

EMD（Earth Mover's Distance）距離是由 Yossi Rubner等在2000年提出的，用來計算兩個直方圖之間匹配度的方法。在直方圖匹配度算法中，EMD距離在圖像發(fā)生形變、檢測器定位誤差等方面與歐氏距離相比，有更好的匹配效果和更強的魯棒性。

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

其中，s代表一類特征，m為其中心，w為屬于該類中心的數(shù)量，對于一維的直方圖，m為直方圖bin的索引，w為該bin的數(shù)量（權(quán)重）。下面介紹EMD距離的計算方法[7]：

其中，D=[dij]是距離矩陣，dij代表類 pi和qj之間的距離（在均勻的直方圖中，距離可以簡化為bin的索引的差值得絕對值）。F={fij}是類間流動矩陣，fij代表類 pi和 qj之間流（flow）的數(shù)量。約束（3）-（6）是指，約束（3）限制了P到Q的單向流動，且流（flow）不能小于0；約束（4）限制了P類供應(yīng)量不能超過它的數(shù)量，約束（5）限制了Q類接收量不能超過它們的數(shù)量；約束（6）是指最大程度的移動數(shù)，也就是總流（flow）的數(shù)量。

經(jīng)過簡化，式（6）可簡化為：

1.2 快速EMD距離

由于EMD距離的計算復(fù)雜度高,運行人臉匹配算法時，勢必會消耗很多時間。因此,本文快速EMD距離來測量特征直方圖之間的匹配度。

假設(shè)有P、Q兩個特征直方圖，P={(p1,wp1)，其中 pi為特征點wpi為其權(quán)重，qi為特征點wqi為其權(quán)重（這里假設(shè)n=m=4）。則EMD距離與快速EMD距離對比如圖1所示。

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

若m=n，經(jīng)過簡化，式（8）可簡化為：

圖1 EMD距離和快速EMD比較

EMD距離與快速EMD距離相比，在尋找最佳運量時算法復(fù)雜度從O（n2）級降低為O（n）級，運算速度提升了一個數(shù)量級。Ofir Pele和Michacl Werman在論文中證明，在P、Q兩個直方圖的總量一致時，EMD距離與快速EMD距離是等價的，在P,Q兩個直方圖的總量不相等時，快速EMD距離擁有更好的區(qū)分力[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。顯然，當直方圖的總量更為重要時更具有區(qū)分度。

2）令 P=（1,0），Q=（1,7）。使用 L1范式作為地面距離（ground distance），α=1時，計算 EMD距離得：EMD（P，Q）=0，而快速 EMD 距離為因此，當P、Q總量不等時，快速EMD距離更有區(qū)分度。

1.3 結(jié)合快速EMD距離的SIFT特征直方圖匹配

本文使用快速EMD距離代替原SIFT算法中使用的歐氏距離來計算特征直方圖間的匹配程度。使用快速EMD距離的SIFT特征直方圖匹配策略如下：

令P和Q來代表任意空間尺度上的兩個特征點的特征直方圖?？梢缘玫剑?/p>

2 實驗驗證與分析

YALE人臉庫由耶魯大學(xué)計算視覺與控制中心創(chuàng)建,包含15位志愿者的165張圖片,每副圖像的大小是243×320像素，包含光照,表情和姿態(tài)的變化，其中的姿態(tài)和光照變化的圖像都是在嚴格控制的條件下采集的。本文將結(jié)合快速EMD距離的SIFT人臉識別算法應(yīng)用到Y(jié)ALE人臉庫中,進行實驗驗證，并與原SIFT算法進行對比,對實驗結(jié)果進行分析,并展示改進后算法在識別率及魯棒性上的提升。實驗所用的機器是Intel Core i5 6400 CPU，8G內(nèi)存。仿真程序用MATLAB2012編寫。

2.1 改進算法的識別準確率

實驗1本次實驗分為訓(xùn)練組和測試組，訓(xùn)練組包含4張人臉圖像，作為算法的訓(xùn)練輸入,測試組包含剩余的7張人臉圖片，作為算法的測試輸入。對每一組訓(xùn)練組測試組測試6次，取平均值作為最后的識別率結(jié)果。如表1所示（表中第一行數(shù)據(jù)為原始SIFT算法，命名為SIFT；表中第二行數(shù)據(jù)為改進算法命名為FEMD-SIFT）。

由表1可得FEMD-SIFT人臉識別算法比原始SIFT算法具有更好的識別效果。說明使用快速EMD距離度量兩個特征直方圖間的匹配度,可以有效避免歐氏距離在人臉圖像發(fā)生旋轉(zhuǎn)、放射變換、遮擋時造成的匹配度下降問題,可以在一定程度上提升人臉識別算法的識別率。

表1 SIFT人臉識別算法和結(jié)合快速EMD距離的SIFT人臉識別算法的識別率對比

2.2 改進算法的魯棒性

實驗2將YALE人臉庫中每個人的一部分的人臉圖像進行噪聲，旋轉(zhuǎn)，放射變換以及部分遮擋等操作。將每一個人的沒有改變的圖像作為訓(xùn)練組，改變后的圖像作為測試組，對每一組訓(xùn)練租測試組測試5次，取匹配數(shù)的平均值作為結(jié)果。

圖2展示的是原始SIFT算法與FEMD-SIFT算法對有遮擋的人臉特征點匹配對比圖，其中SIFT即表示使用原始SIFT算法的特征點匹配個數(shù)，F(xiàn)EMD-SIFT表示使用FEMD-SIFT算法的特征點匹配個數(shù)。

由圖2可以看到使用快速EMD距離的FEMDSIFT人臉識別算法特征點的匹配對數(shù)相比使用歐氏距離的原始SIFT人臉識別算法在噪聲、旋轉(zhuǎn)、仿射變換以及遮擋等方面的匹配數(shù)量都有一定的提升，可以得出FEMD-SIFT人臉識別算法相比原始SIFT人臉識別算法在人臉圖像發(fā)生仿射變換或遮擋時具有更好的魯棒性。

圖2 原始SIFT算法與FEMD-SIFT算法特征點匹配對比圖

3 結(jié)語

本文提出了一種基于SIFT改進的人臉識別算法,通過使用快速EMD距離而不是歐氏距離計算人臉圖像特征直方圖間的匹配度。實驗表明,改進的人臉識別算法比原有算法具有更高的識別率及對人臉圖像在旋轉(zhuǎn)、放射變換以及遮擋等方面有更好的魯棒性。但算法使用128維SIFT描述子，計算的復(fù)雜度仍較大，下一步可以考慮對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.