陳雯柏，黃至鋮，劉瓊

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

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

陳雯柏，黃至鋮，劉瓊

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

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

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

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

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

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

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

1.1 人臉檢測(cè)

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

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

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

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

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

1.2 人臉特征提取

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

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

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

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

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

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

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)行哈希映射時(shí)，可以保證P1>P2，即距離比較近的點(diǎn)沖突的概率要大于距離比較遠(yuǎn)的點(diǎn)沖突的概率。

2.2LSH算法框架

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

圖3 LSH建立索引的過(guò)程Fig.3 Process of LSH indexing

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

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

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

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

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

?

由此可得兩個(gè)向量碰撞的概率為

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

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

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

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

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

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

1)人臉特征提取模塊

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

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

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

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

3)人臉圖片檢索模塊

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

表1 人臉檢測(cè)器性能比較

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

(a)檢索出相同人臉

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

4 結(jié)束語(yǔ)

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

[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)合稀疏表示人臉識(shí)別算法[J].電子學(xué)報(bào), 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]鄧健康，楊靜,王蒙，等. 基于移動(dòng)平臺(tái)的快速相似臉檢索[J]. 北京航空航天大學(xué)學(xué)報(bào), 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)“實(shí)培計(jì)劃”項(xiàng)目(京教高〔2015〕11號(hào)).

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

TP18;TN911.22

A

1673-4785(2017)03-0392-05

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

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

劉瓊，女，1984年生，副教授，主要研究方向?yàn)槟Ｊ阶R(shí)別、認(rèn)知計(jì)算、機(jī)器學(xué)習(xí)。