«上一篇
文章快速检索     高级检索
下一篇»
  智能系统学报  2017, Vol. 12 Issue (3): 392-396  DOI: 10.11992/tis.201607005
0

引用本文  

陈雯柏, 黄至铖, 刘琼. 一种基于P稳定局部敏感哈希算法的相似人脸检索系统设计[J]. 智能系统学报, 2017, 12(3): 392-396. DOI: 10.11992/tis.201607005.
CHEN Wenbai, HUANG Zhicheng, LIU Qiong. A similar-face-image-retrieval system design based on a P-stable locality-sensitive Hashing algorithm[J]. CAAI Transactions on Intelligent Systems, 2017, 12(3): 392-396. DOI: 10.11992/tis.201607005.

基金项目

北京高等学校高水平人才交叉培养“实培计划”项目(京教高〔2015〕11号)

通信作者

陈雯柏. E-mail:chenwb03@126.com

作者简介

陈雯柏,男,1975年生,副教授,博士,中国人工智能学会理事, 主要研究方向为机器人控制与无线传感器网络;
黄至铖,男,1992年生,硕士研究生,主要研究方向为机器学习与模式识别;
刘琼,女,1984年生,副教授,主要研究方向为模式识别、认知计算、机器学习

文章历史

收稿日期:2016-07-05
网络出版日期:2017-07-05
一种基于P稳定局部敏感哈希算法的相似人脸检索系统设计
陈雯柏, 黄至铖, 刘琼    
北京信息科技大学 自动化学院, 北京 100192
摘要:针对智能移动终端、移动机器人安防巡检等应用需求,本文提出了一种基于P稳定局部哈希算法的相似人脸检索系统设计。首先,采用基于局部组合二值特征检测图像中的人脸。进而,通过深度自编码神经网络提取人脸特征。最后,基于所提取的图像的人脸区域特征使用稳定分布的局部敏感哈希算法对每幅图像构建高效索引。实验表明,本文所设计的相似人脸检索系统处理一幅图像的时间约400 ms,能满足实际应用需求,且返回检测结果的误检率低于经典AdaBoost算法。
关键词人脸图像检索    局部敏感哈希算法    P稳定分布    局部组合二值特征    
A similar-face-image-retrieval system design based on a P-stable locality-sensitive Hashing algorithm
CHEN Wenbai, HUANG Zhicheng, LIU Qiong    
School of Automation, Beijing Information Science and Technology University, Beijing 100192, China
Abstract: This paper proposes a similar-face-retrieval system based on a P-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 a P-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.
Key words: face-image retrieval    locality-sensitive Hashing algorithm    P-stable distribution    locally assembled binary feature    

由于人脸是一种具有高度区分度的生物特征,基于人脸图像识别检索的研究十分活跃[1-3],已成为计算机视觉、模式识别和人工智能领域的重要研究课题和系统应用。与传统的人脸识别不同,人脸图像检索需要在大规模人脸库中,实现单张人脸图片的检测、特征提取、索引、配准等过程。大数据环境下,这种相似人脸检索技术,在安防、军事以及娱乐领域有着广泛的应用价值,已成为人脸图像研究中的一个热点[4-6]

相似人脸检索本质上是一种高维结构索引,为解决“维数灾难”和大规模数据的困扰[7-8],基于内容的BOF(bag of feature)方法和LSH(locality-sensitive hashing)方法取得了不错的效果[9]。近年来, 在图像识别检测问题上,区别于以往的人工构造特征的方法,基于深度神经网络的深度学习方法在特征提取和准确率等方面取得了许多惊人的成绩。但深度学习对数据和计算的需求以及实现的效率是需要考虑的问题[10]

针对智能移动终端、移动机器人安防巡检应用需求[11],基于对数据和计算的考虑,本文提出了一种基于P稳定的局部敏感哈希算法的相似人脸检索系统设计。首先采用基于局部组合二值特征人脸检测算法(locally assembled binary, LAB)来完成人脸检测,然后采用深度自编码网络实现人脸的特征提取, 最后采用基于P稳定的局部敏感哈希算法来完成整个系统的索引构建与相似人脸的检索。

1 相似人脸检索系统 1.1 人脸检测

本文采用基于局部编码二值特征(locally assembled binary,LAB)的人脸检测算法[12],具有检测速度快、精度高等优点。

LAB特征分类器通过级联式检测结构,能在预处理层中高效剔除大量非人脸样本。针对于较为复杂的非人脸样本,本文所设计系统采用实数型Adaboost(即Real AdaBoost)算法进行处理。

为了让同一个特征在属于不同窗口的分类器中的计算过程中提供相同的输入特征,采用二值Haar特征,如式(1) 所示:

$ {b_j}\left( x \right) = \left\{ \begin{array}{l} 1,{\left( {{S_1}} \right)_j} - {\left( {{S_2}} \right)_j} > 0\\ 0,{\rm{其他}} \end{array} \right. $ (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) 作为一种无监督的学习方法,深度自编码网络尝试学习一个恒等函数,从而使得输出数据近似于输入数据。通过对隐层加入稀疏性限制,当隐层节点数少于输入层时,迫使网络去学习输入数据的压缩表示。

2) 累加统计是一个池化过程。每个图片块进行量化后,其像素点都关联一个K维度的编码。这些编码对位置非常敏感,为了缓解人脸图像的类内较大的变化而导致难以精确配准问题,将人脸图像划分为若干个空间区域,统计每个区域的编码信息。具体的操作就是将每个空间码字X={X1, X2, …, Xp}进行累加统计以得到一个更加抽象的紧致表达V=X1+X2+…+Xp

3) 由于传统主成分分析(principle component analysis, PCA)的方法容易受到一些高频噪声的影响,本文采用了基于WPCA的白化主成分分析来完成特征向量的降维[13]

1.3 人脸索引构建

对于高维人脸特征向量查询问题,传统线性匹配的方法在运算效率和复杂度方面都不尽人意。本文通过使用LSH算法构建大规模人脸图像数据库的索引,能以稳定的概率返回数据库中与检索样本最近邻的图像。

2 P稳定局部敏感哈希算法 2.1 LSH函数簇定义[14]

Sd维的人脸特征的数据域,pqS中任意的两点。函数H={h:SU}被称为(r, cr, P1, P2)敏感,当且仅当:

1) D(p, q)≤rh(p)=h(q),其中pq碰撞的概率至少为P1;

2) D(p, q)≥cr⇒h(p)=h(q),其中pq碰撞的概率最多为P2,并且P1>P2

当采用LSH函数簇中的功能函数进行哈希映射时,可以保证P1>P2,即距离比较近的点冲突的概率要大于距离比较远的点冲突的概率。

2.2 LSH算法框架

从LSH算法实现的原理上来看,如果在建立索引的过程中相近特征的哈希函数能放在一起,那么查询的效率也会越高。

定义    一组函数G={g:SUk},其中g(v)= h1(v), h2(v), …, hk(v), hiH,随机地从G中抽取L个哈希函数g1, g2, …, gL。对于得到的人脸特征数据集,任何一张人脸的特征向量v将其存在一个容器gi(v)中。

图 3所示,对于待查询向量q首先通过哈希函数得到其数字指纹,然后从具有相同数字指纹的容器中获得其所有的近邻点,当结果集中的近邻点与查询点的距离满足D(q, vj)≤r那么就将其放入返回列表中,当所有可能结果返回后,对其进行再次排序并返回。

图 3 LSH建立索引的过程 Fig.3 Process of LSH indexing

在创建索引的时候,使用的哈希函数由k个哈希函数串联得到,这种串联结构的使用虽然加大了P1P2之间的差值,但也引起了P1P2的值都同时降低问题。为了弥补这种情况带来的影响,我们同时使用L张表来加大P1减小P2。这种互补索引结构,能保证以较高的概率返回查询点的近邻点,同时也能以较高的概率拒绝返回距离较远点。因此,只要能设置符合数据集特征的kl,LSH就具有较高的查找效率。

2.3 基于P稳定分布的LSH算法

由上述LSH算法框架可知,不同哈希函数簇会产生不同的LSH算法。对于不同的数据集,采用不同的哈希函数簇,将会产生不同的效果。

对于实数域上的一个分布D,如果随机变量${\sum _i}{\alpha _i}{X_i}$${\left({{\sum _i}{{\left| {{\alpha _i}} \right|}^P}} \right)^{\frac{1}{P}}}X$具有相同的分布,那么就称D是一个P稳定分布。其中,P≥0,α1, α2, …, αnn个实数,X1, X2, …, Xnn个满足D分布的随机变量。对于P∈(0, 2]都存在稳定分布; 当P=1时是柯西分布,概率密度为c(x)=$\frac{1}{{\pi \left({1 + {x^2}} \right)}}$; 当P=2时是高斯分布,概率密度为g(x)=$\frac{1}{{\sqrt {2\pi } }}{{\rm{e}}^{ -{x^2}/2}}$

利用P稳定分布可以保证度量距离的同时,对人脸特征向量进行降维操作。其主要思想是, 利用服从P稳定分布的随机函数产生一个d维的随机向量a,对于一个d维的人脸特征向量v,可以用a·v来估算‖vP

基于P稳定分布的LSH函数簇中每个哈希函数定义为

$ h\left( \boldsymbol{v} \right) = \left\lfloor {\frac{{\boldsymbol{a}\cdot \boldsymbol{v} + b}}{w}} \right\rfloor $ (2)

式中:a是由服从P稳定分布的随机函数产生的一个d维向量; b为一个[0, w]中的一个随机实数。其原理就是, 将人脸特征向量v投影到向量a上,并且在投影的结果上加入一个偏差修正值b,然后再以w为间隔进行量化。这样就可以利用哈希函数将距离相近的点映射到相近区间中。

对于数据集中任意两个特征向量v1v2,设c=‖ v1v2PfP(t)为P稳定分布的概率密度函数的绝对值,当特征向量v1v2映射到a上时有|a·v1a·v2| < w,即|(v1v2a| < w, 由P稳定分布的特性得到

$ {\left\| {{\boldsymbol{v}_1} - {\boldsymbol{v}_2}} \right\|_P}X = \left| {cX} \right| < w $ (3)

由此可得两个向量碰撞的概率为

$ {\rm{Pr}}\left( c \right) = {\rm{Pr}}\left( {h\left( {{\boldsymbol{v}_1}} \right) = h{\rm{ }}\left( {{\boldsymbol{v}_2}} \right)} \right) = \int_0^w {\frac{1}{c}{f_P}\left( {\frac{t}{c}} \right)\left( {1 - \frac{t}{w}} \right)} {\rm{d}}t $ (4)

由(4) 式可知在w给定的情况下,两个向量冲突的概率随c的增加而减小。在实际使用中为了让w更加符合数据集特征,本文通过随机抽样的方法计算w

3 相似人脸检索系统设计与实现

相似人脸检索系统基于BS架构开发,采用Java中的SpringMvc框架,利用Tomcat服务器实现。

3.1 系统架构

图 4所示,人脸检索系统共分为3个模块,即人脸特征提取模块、索引构建模块和人脸图片检索模块。

图 4 系统架构图 Fig.4 System architecture

1) 人脸特征提取模块

为缩短特征提取的时间,采用C++实现并且加入了OpenMP(open multi-processing)的编译支持。

特征提取模块主要完成人脸检测以及校准,然后利用自编码网络来完成人脸区域的特征表征,整个过程在本系统实际测量中处理一张人脸图片的时间大约400 ms。

2) 索引构建模块

利用基于P稳定分布的LSH算法来完成人脸特征向量的映射,得到图片的数字指纹。通过数字指纹将相似度较高的人脸图像映射到一个桶内,并且利用多表互补的方法提高召回率。当对所有图像进行映射后,将每幅图像的索引进行序列化,并存储为文件。

3) 人脸图片检索模块

用户上传人脸图片后,系统首先调用人脸特征提取模块得到人脸特征向量。特征向量经过哈希表中的k个哈希函数生成一个k维的向量,然后再将该向量生成一个数字指纹。最后利用生成的数字指纹进行查找,并返回相似度最高的4张图片。为了保证待检索图片与结果之间的相似性,采用余弦距离对返回结果进行二次约束,只有当检索图片的特征向量v1和检索结果的人脸特征向量v2之间的余弦距离大于0.75才符合要求,并放入结果队列。

4) 系统参数设置模块

整个系统是否能高效地进行索引构建以及目标人脸图片的检测,在一定程度上与哈希表的数目以及每张表中哈希函数的个数都有关系。如图 5所示,兼顾正确率和查询效率,本系统设置了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 人脸检测器性能比较 Tab.1 Performance comparison of face detector

实际系统运行于PC(Intel i5-4590主频3.30 GHz内存4 GB)平台,系统基本能在1 s内返回与上传图片相似的4张图片,能满足智能移动终端、移动机器人安防巡检的实际应用需求。系统部分实际运行效果如图 6所示。

图 6 相似人脸检索 Fig.6 Similar face retrieval
4 结束语

本文给出了一种基于P稳定LSH算法的相似人脸检索系统设计,采用基于局部组合二值特征人脸检测算法来完成人脸检测,采用深度自编码网络对检测出的人脸提取特征。通过采用P稳定的局部敏感哈希算法,完成整个系统的图像索引构建。本系统的设计应用于智能移动终端和移动机器人安防巡检,达到了检索精度和检索时耗的平衡。

参考文献
[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. DOI:10.1109/TMM.2013.2242460 (0)
[2] 胡正平, 李静. 基于低秩子空间恢复的联合稀疏表示人脸识别算法[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. (0)
[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. DOI:10.1109/TIP.2010.2041397 (0)
[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. (0)
[5] BURGOS-ARTIZZU X P, PERONA P, DOLLAR P. Robust face landmark estimation under occlusion[C]//International Conference on Computer Vision, 2013:1513-1520. (0)
[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. (0)
[7] GUTTMAN A. A dynamic index structure for spatial searching[C]// Sigmod84, Proceedings of Meeting, Boston, Massachusetts, 1984: 47-57. (0)
[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. (0)
[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. (0)
[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. (0)
[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. (0)
[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. (0)
[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. DOI:10.1007/11573548 (0)
[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. (0)