一种基于P稳定局部敏感哈希算法的相似人脸检索系统设计

陈雯柏，黄至铖，刘琼

(北京信息科技大学 自动化学院, 北京 100192)

一种基于P稳定局部敏感哈希算法的相似人脸检索系统设计

陈雯柏，黄至铖，刘琼

(北京信息科技大学 自动化学院, 北京 100192)

针对智能移动终端、移动机器人安防巡检等应用需求，本文提出了一种基于P稳定局部哈希算法的相似人脸检索系统设计。首先，采用基于局部组合二值特征检测图像中的人脸。进而，通过深度自编码神经网络提取人脸特征。最后，基于所提取的图像的人脸区域特征使用稳定分布的局部敏感哈希算法对每幅图像构建高效索引。实验表明，本文所设计的相似人脸检索系统处理一幅图像的时间约400 ms，能满足实际应用需求，且返回检测结果的误检率低于经典AdaBoost算法。

人脸图像检索；局部敏感哈希算法；P稳定分布；局部组合二值特征

中文引用格式：陈雯柏，黄至铖，刘琼.一种基于P稳定局部敏感哈希算法的相似人脸检索系统设计[J]. 智能系统学报， 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.

由于人脸是一种具有高度区分度的生物特征，基于人脸图像识别检索的研究十分活跃[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)所示：

由于值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)作为一种无监督的学习方法，深度自编码网络尝试学习一个恒等函数，从而使得输出数据近似于输入数据。通过对隐层加入稀疏性限制，当隐层节点数少于输入层时，迫使网络去学习输入数据的压缩表示。

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

1.3 人脸索引构建

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

2 P稳定局部敏感哈希算法

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

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

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

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

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

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

⎣

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

由(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 人脸检测器性能比较

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

(a)检索出相同人脸

(b)检索出相近人脸图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.

[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.

[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.

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

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

TP18;TN911.22

A

1673-4785(2017)03-0392-05

陈雯柏，男，1975年生，副教授，博士，中国人工智能学会理事,主要研究方向为机器人控制与无线传感器网络。

黄至铖，男，1992年生，硕士研究生，2015年入选北京高等学校与中国科学院高水平人才交叉培养“实培计划”，主要研究方向为机器学习与模式识别。

刘琼，女，1984年生，副教授，主要研究方向为模式识别、认知计算、机器学习。