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

陳雯柏，黃至鋮，劉瓊

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

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

陳雯柏，黃至鋮，劉瓊

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

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

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

中文引用格式：陳雯柏，黃至鋮，劉瓊.一種基于P穩(wěn)定局部敏感哈希算法的相似人臉檢索系統(tǒng)設(shè)計[J]. 智能系統(tǒng)學(xué)報， 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]，已成為計算機(jī)視覺、模式識別和人工智能領(lǐng)域的重要研究課題和系統(tǒng)應(yīng)用。與傳統(tǒng)的人臉識別不同，人臉圖像檢索需要在大規(guī)模人臉庫中，實現(xiàn)單張人臉圖片的檢測、特征提取、索引、配準(zhǔn)等過程。大數(shù)據(jù)環(huán)境下，這種相似人臉檢索技術(shù)，在安防、軍事以及娛樂領(lǐng)域有著廣泛的應(yīng)用價值，已成為人臉圖像研究中的一個熱點[4-6]。

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

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

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

1.1 人臉檢測

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

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

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

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

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

1.2 人臉特征提取

本文通過使用深度自編碼神經(jīng)網(wǎng)絡(luò)局部描述子來進(jìn)行特征提取及表征，具體流程如圖2所示。

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

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

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

1.3 人臉?biāo)饕龢?gòu)建

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

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

2.1 LSH函數(shù)簇定義[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。

當(dāng)采用LSH函數(shù)簇中的功能函數(shù)進(jìn)行哈希映射時，可以保證P1>P2，即距離比較近的點沖突的概率要大于距離比較遠(yuǎn)的點沖突的概率。

2.2LSH算法框架

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

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

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

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

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

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

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

?

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

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

3 相似人臉檢索系統(tǒng)設(shè)計與實現(xiàn)

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

3.1 系統(tǒng)架構(gòu)

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

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

1)人臉特征提取模塊

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

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

2)索引構(gòu)建模塊

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

3)人臉圖片檢索模塊

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

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

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

圖5 哈希函數(shù)個數(shù)與算法性能的關(guān)系Fig.5 Relationship between the number of Hash function and performance of the algorithm

3.2 實驗結(jié)果

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

表1 人臉檢測器性能比較

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

(a)檢索出相同人臉

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

4 結(jié)束語

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

[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]胡正平,李靜.基于低秩子空間恢復(fù)的聯(lián)合稀疏表示人臉識別算法[J].電子學(xué)報, 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]. 北京航空航天大學(xué)學(xué)報, 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. 網(wǎng)絡(luò)出版日期：2017-07-05.

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

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

TP18;TN911.22

A

1673-4785(2017)03-0392-05

陳雯柏，男，1975年生，副教授，博士，中國人工智能學(xué)會理事,主要研究方向為機(jī)器人控制與無線傳感器網(wǎng)絡(luò)。

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

劉瓊，女，1984年生，副教授，主要研究方向為模式識別、認(rèn)知計算、機(jī)器學(xué)習(xí)。