陳雯柏，黃至鋮，劉瓊

(北京信息科技大學 自動化學院, 北京 100192)

一種基于P穩(wěn)定局部敏感哈希算法的相似人臉檢索系統(tǒng)設計

陳雯柏，黃至鋮，劉瓊

(北京信息科技大學 自動化學院, 北京 100192)

針對智能移動終端、移動機器人安防巡檢等應用需求，本文提出了一種基于P穩(wěn)定局部哈希算法的相似人臉檢索系統(tǒng)設計。首先，采用基于局部組合二值特征檢測圖像中的人臉。進而，通過深度自編碼神經網絡提取人臉特征。最后，基于所提取的圖像的人臉區(qū)域特征使用穩(wěn)定分布的局部敏感哈希算法對每幅圖像構建高效索引。實驗表明，本文所設計的相似人臉檢索系統(tǒng)處理一幅圖像的時間約400 ms，能滿足實際應用需求，且返回檢測結果的誤檢率低于經典AdaBoost算法。

人臉圖像檢索；局部敏感哈希算法；P穩(wěn)定分布；局部組合二值特征

中文引用格式：陳雯柏，黃至鋮，劉瓊.一種基于P穩(wěn)定局部敏感哈希算法的相似人臉檢索系統(tǒng)設計[J]. 智能系統(tǒng)學報， 2017, 12(3): 392-396.

英文引用格式：CHEN Wenbai, HUANG Zhicheng, LIU Qiong. A similar-face-image-retrieval system design based on aP-stable locality-sensitive Hashing algorithm[J]. CAAI transactions on intelligent systems, 2017, 12(3): 392-396.

由于人臉是一種具有高度區(qū)分度的生物特征，基于人臉圖像識別檢索的研究十分活躍[1-3]，已成為計算機視覺、模式識別和人工智能領域的重要研究課題和系統(tǒng)應用。與傳統(tǒng)的人臉識別不同，人臉圖像檢索需要在大規(guī)模人臉庫中，實現單張人臉圖片的檢測、特征提取、索引、配準等過程。大數據環(huán)境下，這種相似人臉檢索技術，在安防、軍事以及娛樂領域有著廣泛的應用價值，已成為人臉圖像研究中的一個熱點[4-6]。

相似人臉檢索本質上是一種高維結構索引，為解決“維數災難”和大規(guī)模數據的困擾[7-8]，基于內容的BOF(bag of feature)方法和LSH(locality-sensitive hashing)方法取得了不錯的效果[9]。近年來,在圖像識別檢測問題上，區(qū)別于以往的人工構造特征的方法，基于深度神經網絡的深度學習方法在特征提取和準確率等方面取得了許多驚人的成績。但深度學習對數據和計算的需求以及實現的效率是需要考慮的問題[10]。

針對智能移動終端、移動機器人安防巡檢應用需求[11]，基于對數據和計算的考慮，本文提出了一種基于P穩(wěn)定的局部敏感哈希算法的相似人臉檢索系統(tǒng)設計。首先采用基于局部組合二值特征人臉檢測算法(locally assembled binary,LAB)來完成人臉檢測，然后采用深度自編碼網絡實現人臉的特征提取,最后采用基于P穩(wěn)定的局部敏感哈希算法來完成整個系統(tǒng)的索引構建與相似人臉的檢索。

1 相似人臉檢索系統(tǒng)

1.1 人臉檢測

本文采用基于局部編碼二值特征(locally assembled binary，LAB)的人臉檢測算法[12]，具有檢測速度快、精度高等優(yōu)點。

LAB特征分類器通過級聯(lián)式檢測結構，能在預處理層中高效剔除大量非人臉樣本。針對于較為復雜的非人臉樣本，本文所設計系統(tǒng)采用實數型Adaboost(即Real AdaBoost)算法進行處理。

為了讓同一個特征在屬于不同窗口的分類器中的計算過程中提供相同的輸入特征，采用二值Haar特征，如式(1)所示：

由于值Haar特征只保留了Haar特征的符號信息，為了提高特征的描述能力，提出將多個二值特征進行組合的辦法，通過將多個二進制的二值Haar特征作為碼字進行編碼，用于提高特征的描述能力。局部組合二值特征采用圖1所示的8個特征，其中8個特征中的黑色矩形方塊指代同一個像素點，最終得到一個組合了8個特征計算所得的新特征。相比Haar特征，局部組合二值特征在簡化計算復雜度的同時，針對于光照多變等問題具有很強的魯棒性。

圖1 組合二值Haar特征Fig.1 Assembled binary Haar features

1.2 人臉特征提取

本文通過使用深度自編碼神經網絡局部描述子來進行特征提取及表征，具體流程如圖2所示。

圖2 基于稀疏自編碼的局部描述子Fig.2 Locality descriptor based on sparse auto-encoding

1)作為一種無監(jiān)督的學習方法，深度自編碼網絡嘗試學習一個恒等函數，從而使得輸出數據近似于輸入數據。通過對隱層加入稀疏性限制，當隱層節(jié)點數少于輸入層時，迫使網絡去學習輸入數據的壓縮表示。

3)由于傳統(tǒng)主成分分析(principle component analysis,PCA)的方法容易受到一些高頻噪聲的影響，本文采用了基于WPCA的白化主成分分析來完成特征向量的降維[13]。

1.3 人臉索引構建

對于高維人臉特征向量查詢問題，傳統(tǒng)線性匹配的方法在運算效率和復雜度方面都不盡人意。本文通過使用LSH算法構建大規(guī)模人臉圖像數據庫的索引，能以穩(wěn)定的概率返回數據庫中與檢索樣本最近鄰的圖像。

2 P穩(wěn)定局部敏感哈希算法

2.1 LSH函數簇定義[14]

1)D(p,q)≤r?h(p)=h(q)，其中p和q碰撞的概率至少為P1;

2)D(p,q)≥cr?h(p)=h(q)，其中p和q碰撞的概率最多為P2，并且P1>P2。

當采用LSH函數簇中的功能函數進行哈希映射時，可以保證P1>P2，即距離比較近的點沖突的概率要大于距離比較遠的點沖突的概率。

2.2LSH算法框架

從LSH算法實現的原理上來看，如果在建立索引的過程中相近特征的哈希函數能放在一起，那么查詢的效率也會越高。

圖3 LSH建立索引的過程Fig.3 Process of LSH indexing

在創(chuàng)建索引的時候，使用的哈希函數由k個哈希函數串聯(lián)得到，這種串聯(lián)結構的使用雖然加大了P1和P2之間的差值，但也引起了P1和P2的值都同時降低問題。為了彌補這種情況帶來的影響，我們同時使用L張表來加大P1減小P2。這種互補索引結構，能保證以較高的概率返回查詢點的近鄰點，同時也能以較高的概率拒絕返回距離較遠點。因此，只要能設置符合數據集特征的k和l，LSH就具有較高的查找效率。

2.3 基于P穩(wěn)定分布的LSH算法

由上述LSH算法框架可知，不同哈希函數簇會產生不同的LSH算法。對于不同的數據集，采用不同的哈希函數簇，將會產生不同的效果。

利用P穩(wěn)定分布可以保證度量距離的同時，對人臉特征向量進行降維操作。其主要思想是,利用服從P穩(wěn)定分布的隨機函數產生一個d維的隨機向量a，對于一個d維的人臉特征向量v，可以用a·v來估算‖v‖P。

基于P穩(wěn)定分布的LSH函數簇中每個哈希函數定義為

?

由此可得兩個向量碰撞的概率為

由(4)式可知在w給定的情況下，兩個向量沖突的概率隨c的增加而減小。在實際使用中為了讓w更加符合數據集特征，本文通過隨機抽樣的方法計算w。

3 相似人臉檢索系統(tǒng)設計與實現

相似人臉檢索系統(tǒng)基于BS架構開發(fā)，采用Java中的SpringMvc框架，利用Tomcat服務器實現。

3.1 系統(tǒng)架構

如圖4所示，人臉檢索系統(tǒng)共分為3個模塊，即人臉特征提取模塊、索引構建模塊和人臉圖片檢索模塊。

圖4 系統(tǒng)架構圖Fig.4 System architecture

1)人臉特征提取模塊

為縮短特征提取的時間，采用C++實現并且加入了OpenMP(open multi-processing)的編譯支持。

特征提取模塊主要完成人臉檢測以及校準，然后利用自編碼網絡來完成人臉區(qū)域的特征表征，整個過程在本系統(tǒng)實際測量中處理一張人臉圖片的時間大約400 ms。

2)索引構建模塊

利用基于P穩(wěn)定分布的LSH算法來完成人臉特征向量的映射，得到圖片的數字指紋。通過數字指紋將相似度較高的人臉圖像映射到一個桶內，并且利用多表互補的方法提高召回率。當對所有圖像進行映射后，將每幅圖像的索引進行序列化，并存儲為文件。

3)人臉圖片檢索模塊

用戶上傳人臉圖片后，系統(tǒng)首先調用人臉特征提取模塊得到人臉特征向量。特征向量經過哈希表中的k個哈希函數生成一個k維的向量，然后再將該向量生成一個數字指紋。最后利用生成的數字指紋進行查找，并返回相似度最高的4張圖片。為了保證待檢索圖片與結果之間的相似性，采用余弦距離對返回結果進行二次約束，只有當檢索圖片的特征向量v1和檢索結果的人臉特征向量v2之間的余弦距離大于0.75才符合要求，并放入結果隊列。

4)系統(tǒng)參數設置模塊

整個系統(tǒng)是否能高效地進行索引構建以及目標人臉圖片的檢測，在一定程度上與哈希表的數目以及每張表中哈希函數的個數都有關系。如圖5所示，兼顧正確率和查詢效率，本系統(tǒng)設置了11張哈希表，每張哈希表中包含20個哈希函數。

圖5 哈希函數個數與算法性能的關系Fig.5 Relationship between the number of Hash function and performance of the algorithm

3.2 實驗結果

為了對人臉檢測模塊的性能進行定量分析，從FDDB(face detection data set and benchmark)數據庫中隨機抽取50張人臉圖像共計80個人臉，本文提出的方法與OpenCV自帶的AdaBoost人臉檢測器相比，具有較高的檢測精度和性能，結果如表1所示。

表1 人臉檢測器性能比較

實際系統(tǒng)運行于PC(Intel i5-4590 主頻3.30 GHz內存4 GB)平臺，系統(tǒng)基本能在1 s內返回與上傳圖片相似的4張圖片，能滿足智能移動終端、移動機器人安防巡檢的實際應用需求。系統(tǒng)部分實際運行效果如圖6所示。

(a)檢索出相同人臉

(b)檢索出相近人臉圖6 相似人臉檢索Fig.6 Similar face retrieval

4 結束語

本文給出了一種基于P穩(wěn)定LSH算法的相似人臉檢索系統(tǒng)設計，采用基于局部組合二值特征人臉檢測算法來完成人臉檢測，采用深度自編碼網絡對檢測出的人臉提取特征。通過采用P穩(wěn)定的局部敏感哈希算法，完成整個系統(tǒng)的圖像索引構建。本系統(tǒng)的設計應用于智能移動終端和移動機器人安防巡檢，達到了檢索精度和檢索時耗的平衡。

[1]CHEN B C, CHEN Y Y, KUO Y H, et al. Scalable face image retrieval using attribute-enhanced sparse code words [J]. IEEE transactions on multimedia, 2013,15 (5) :1163-1173.

[2]胡正平,李靜.基于低秩子空間恢復的聯(lián)合稀疏表示人臉識別算法[J].電子學報, 2013, 41(5): 987-991. HU Zhengping, LI Jing. Face recognition of joint sparse representation based on lowmark subspace recovery [J]. Chinese journal of electronics, 2013, 41(5): 987-991.

[3]XIE S F, SHAN S G, CHEN X L, et al. Fusing local patterns of gabor magnitude and phase for face recognition[J]. IEEE trans on image processing, 2010,19(5):1349-1361.

[4]LI Y, WANG R, LIU H, et al. Two birds, one stone: jointly learning binary code for large-scale face image retrieval and attributes prediction[C]// IEEE International Conference on Computer Vision. IEEE Computer Society, 2015:3819-3827.

[5]BURGOS-ARTIZZU X P, PERONA P, DOLLAR P. Robust face landmark estimation under occlusion[C]//International Conference on Computer Vision, 2013:1513-1520.[6]SHAN S G, CHANG Y Z, GAO W, et al. Curse of misalignment in face recognition: problem and a novel mis alignment learning solution[C]// Proceeding of the 6th International Conference on Face and Gesture Recognition, Jeju, Korea, 2004, 314-320.

[7]GUTTMAN A. A dynamic index structure for spatial searching[C]// Sigmod’84, Proceedings of Meeting, Boston, Massachusetts, 1984: 47-57.

[8]CHEN D, CAO X, WEN F, et al．Blessing of dimensionality: high-dimensional feature and its efficient compression for face verification[C]//Proceeding of the Computer Vision and Pattern Recognition. Piscataway, 2013: 3025-3032.

[9]GIONIS A, INDYK P, MOTWANI R. Similarity Search in High Dimensions via Hashing[C]//International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc, 2000: 518-529.

[10]SUN Y, WANG X G, TANG X O. Deep convolutional network cascade for facial point detection[C]//Proceeding of the Computer Vision and Pattern Recognition, 2013: 121-125.

[11]鄧健康，楊靜,王蒙，等. 基于移動平臺的快速相似臉檢索[J]. 北京航空航天大學學報, 2015, 41(2): 323-330. DENG Jiankang，YANG Jing，WANG Meng，et al. Fast similar face retrieval based on mobile platform [J]. Journal of Beijing university of aeronautics and astronautics, 2015, 41(2): 323-330.

[12]YAN S, SHAN S, Chen X, et al. Locally Assembled Binary (LAB) feature with feature-centric cascade for fast and accurate face detection[C]// IEEE Conference on Computer Vision and Pattern Recognition, 2008: 1-7.

[13]LIU F, WANG Z L, WANG L, et al. Facial expression recognition using HLAC features and WPCA[J]. Lecture notes in computer science, 2005, 3784:88-94.

[14]DATAR M, IMMORLICA N, INDYK P, et al. Locality-sensitive hashing scheme based on p-stable distributions[C]// Twentieth Symposium on Computational Geometry. ACM, 2004: 253-262.

A similar-face-image-retrieval system design based on aP-stable locality-sensitive Hashing algorithm

CHEN Wenbai, HUANG Zhicheng, LIU Qiong

(School of Automation, Beijing Information Science and Technology University, Beijing 100192, China)

This paper proposes a similar-face-retrieval system based on aP-stable local hashing algorithm to meet the requirements of intelligent mobile terminals and mobile-robot-security inspection applications. First, our system extracts a locally assembled binary feature to detect a human face in a particular image. Subsequently, a deep auto-encoding network is used to compute the subject’s facial features. Finally, a locality-sensitive hashing algorithm based on aP-stable distribution is employed to construct an efficient index for each image according to the facial features. Our test results show that the proposed similar-face-image-retrieval system can process images within approximately 400 ms, thereby meeting the requirements of practical biometric applications. In addition, the false detection rate of the proposed method is considerably low than that of the classical AdaBoost algorithm.

face-image retrieval; locality-sensitive Hashing algorithm;P-stable distribution; locally assembled binary feature

DOI:10.11992/tis. 201607005

http://kns.cnki.net/kcms/detail/23.1538.TP.20170705.1703.014.html

2016-07-05. 網絡出版日期：2017-07-05.

北京高等學校高水平人才交叉培養(yǎng)“實培計劃”項目(京教高〔2015〕11號).

陳雯柏. E-mail：chenwb03@126.com.

TP18;TN911.22

A

1673-4785(2017)03-0392-05

陳雯柏，男，1975年生，副教授，博士，中國人工智能學會理事,主要研究方向為機器人控制與無線傳感器網絡。

黃至鋮，男，1992年生，碩士研究生，2015年入選北京高等學校與中國科學院高水平人才交叉培養(yǎng)“實培計劃”，主要研究方向為機器學習與模式識別。

劉瓊，女，1984年生，副教授，主要研究方向為模式識別、認知計算、機器學習。