基于Spark平台的人脸图像检索系统

陈新荃,陈晓东,蒋林华

(1.中国科学院上海高等研究院,上海 201210; 2.中国科学院大学,北京 100049; 3.上海理工大学,上海 200093)

0 概述

网络带宽的增长和移动互联网的兴起促进了大数据时代的到来。越来越多基于图片和视频内容的应用得到普及,如Facebook、Instagram等。这类应用的发展促进了基于目标的图像检索技术[1]的发展与应用。该技术在人脸检索领域有丰富的应用场景,如公安刑侦人脸识别、失踪人口调查、相似明星脸搜索等。随着图像数据的爆炸式增长,现有人脸图像检索技术在处理海量图像数据的过程中,在实时性、扩展性、并发性和准确性等方面面临严峻的考验。

Spark[2]是一个开源的分布式大数据处理平台,算法框架基于MapReduce[3]算法实现分布式计算。不同于Hadoop[4]大数据处理系统,Spark基于内存计算,同时还提供多种数据处理接口和有向循环图(Directed Acyclic Graph,DAG)调度策略,在复杂计算场景下编码更方便,计算效率更高。

随着图像应用的迅速发展,人脸图像数据爆炸增长,因此,需要一种能够处理海量数据且具有良好可扩展性、并发性和准确率的人脸图像检索方案。本文以此为目标,提出基于Spark分布式计算平台的人脸图像检索系统。

1 相关研究

随着人脸图像检索应用的不断发展,许多研究人员针对图像检索技术进行了研究。文献[5-6]考虑了人脸在二维图像中的空间分布特点,分别通过图像分割法和特征权重法抽取人脸中的显著视觉信息,目的是降低视觉特征规模。文献[7]指出传统视觉词袋模型聚类过程缓慢的问题,考虑了局部特征之间的空间信息,运用二进制哈希与空间金字塔生成视觉词典。文献[8]采用基于签名的方法替代传统的聚类方式,利用权重组合机制计算相似图像,提高了视觉词典生成速度。文献[9]分析图像高维视觉特征的内存占用情况,提出将尺度不变特征变换(Scale-Invariant Feature Transform,SIFT)特征转换成低维汉明特征的方法,压缩视觉词袋模型的倒排索引。文献[10]提出自动检测人类语义属性的方法,构建基于语义的稀疏编码倒排索引,提高了人脸检索的离线和在线处理性能。

上述研究分别从视觉特征提取、词典生成、索引构建等方面提高图像检索的效率和准确率,但都没有考虑到处理海量图像数据时的并行化问题。为解决该问题,文献[11]提出异构计算框架CHCF处理海量图像检索,利用GPU和分布式集群提高并行处理能力。文献[12-14]采用开源的Hadoop分布式文件系统(Hadoop Distributed File System,HDFS)计算平台实现图像检索方案,将传统视觉词袋模型MapReduce化,从而提高并行程度,但图像索引直接存放于HDFS文件系统中,导致检索时产生硬盘读取,影响检索效率。文献[15]在Hadoop平台的基础上采用Hbase分布式数据库用作索引存储,解决了HDFS存取的时效性问题,但检索时需要对目标图像和所有图像计算相似度,增加了不必要的计算过程。

基于上述研究,本文考虑人脸图像的特点及检索系统的并行性能,提出基于Spark分布式计算平台的人脸图像检索技术。通过区块划分减少特征规模,结合SURF局部特征和HOG区块特征设计新的相似度算法以提高检索准确率,最后在Spark平台上实现人脸图像检索系统,以提高系统可扩展性和并行性。

2 系统架构与模型

2.1 系统架构

本文提出的分布式人脸图像检索平台系统架构如图1所示,其中,用户通过前端模块与检索系统进行交互,前端模块负责接收用户的人脸检索请求,转发给检索系统处理,并接收处理结果返回给用户。本文采用Spark并行计算集群构建人脸检索系统,其主要承担2个任务:离线索引构建和在线人脸检索,两者均基于OpenCV[16]计算机视觉库进行图像处理。离线索引构建过程中的海量图像数据采用HDFS存储。HDFS是具备高度容错性的分布式文件系统,适合大规模数据集的访问。构建过程中生成的视觉词汇表和倒排索引存储于HBase中,HBase[17]是Apache基金会开源的非结构化数据库,基于HDFS分布式文件系统实现,具备高可靠性、面向列式存储的特点,能够实现索引数据的高效存取。

图1 分布式人脸图像检索平台系统架构

2.2 离线索引构建

2.2.1 构建流程

在基于视觉词袋模型的搜索引擎技术中,倒排索引构建过程是离线训练的主要内容。本文针对人脸图像空间分布特点,提出局部区块划分方法构建倒排索引,具体过程如图2所示。

图2 离线索引构建过程

传统图像检索系统对整幅图片进行局部视觉特征提取,未考虑人脸在二维图像中的空间分布特点,在相似人脸检索中并不适用。本文针对人脸场景,首先利用Haar[18]算法检测图像中的人脸,去除大部分和人脸无关的背景信息并对齐,再检测人脸上的五官局部区块。由于耳朵在人脸图像中经常受到拍摄角度和发型的影响,容易产生不稳定的视觉特征噪点,因此本文划分出左眼、右眼、鼻子、左嘴角、右嘴角5个局部区块,这些区块包含了人脸图像的显著特征信息,且划分后的5个区块各自特征空间相互独立,容易进行并行处理操作。

在索引构建过程中,本文结合MapReduce编程模型,首先从HDFS文件系统读取人脸图像,将图像数据分片后分发到不同的Spark执行器中,再利用Spark框架的map转换算子完成人脸图像处理任务,包括人脸检测、局部区域划分及视觉特征提取。因此,每个执行器只负责处理一部分图像数据,实现多个执行器的并行处理操作。

2.2.2 视觉特征计算

执行人脸视觉特征提取任务时,本文共提取2种视觉特征,分别是SURF局部特征和HOG区块特征。加速稳健特征(Speeded Up Robust Features,SURF)特征[19]属于局部视觉特征,具有良好的旋转不变性和尺度不变性。文献[20]指出,在去除和人脸无关的背景噪声后,SURF特征能够应用于人脸识别领域。本文通过区块划分方法约束SURF特征的提取范围,去除了无关噪点。考虑到从海量图像中提取的视觉特征规模巨大,为缩减倒排索引规模,本文基于视觉词袋模型,利用SURF特征生成视觉单词,通过视觉单词表示人脸图像,建立倒排索引,从而降低海量人脸图像的索引规模。但SURF特征的提取仅基于人脸图像中关键点周围的信息,其视觉特征丢失了关键点以外的图像信息,缺乏对人脸图像空间结构信息的整体描述。因此,本文针对人脸图像局部区块提取方向梯度直方图(Histogram of Oriented Gradient,HOG)特征[21]。该特征将图像均匀地分为多个图像单元,通过统计每个单元的梯度直方图作为视觉特征,属于全局视觉特征。HOG特征能够对人脸的光照、旋转和部分遮挡保持良好的不变性,描述出人脸图像的局部区块特点,弥补SURF特征所缺少的空间结构视觉信息。本文中每张人脸图像5个局部区块对应5个HOG特征,而所有HOG特征组成的区块特征表通过HBase进行存储,在人脸检索过程中结合SURF特征进行候选图像的相似得分计算。

2.2.3 索引构建

本文通过K-Means算法对SURF特征向量进行聚类,生成具有代表性的特征,即视觉单词。K-Means算法时间复杂度为O(nkt),其中,n为全部视觉特征数量,t为迭代次数,k为视觉词汇数。如果将整张人脸图像的SURF特征放在同一空间进行聚类,会导致非常高的时间复杂度,并造成不同人脸部位的特征向量被归于同一类的情况。因此,本文基于人脸区域划分方法划分人脸图像得到5种局部区块,并通过Spark的reduceByKey算子重新分配特征向量描述符,将属于同一人脸区域的SURF特征分配到同一集合,获得5个独立的视觉特征子空间,聚类操作在每个特征子空间内分别执行,最后生成5张视觉特征词汇表,以此降低n和k的值,从而提高整体聚类速度,解决错分类问题。

本文根据视觉特征词汇表对每个特征子空间中的特征向量进行归类和统计,生成倒排索引表。倒排索引表在HBase分布式数据库中以Key-Value的形式存储。其中Key的形式为<子区域ID_视觉单词ID>,Value包含2个部分:一部分是特征单词的逆文档频率值idf;另一部分是该特征单词在每个人脸图像中的词频权重集合。特征单词t的逆文档频率计算公式如式(1)所示。

(1)

其中:N是人脸库中所有人脸的总数;dft是具有该特征单词的人脸图像数量。式(1)对于罕见的特征单词权重较高,而普遍在所有人脸图像中出现的特征单词则权重较低。

特征单词t在人脸图像d中的词频权重可描述为:

(2)

其中,tft,d表示视觉单词t在人脸图像d中出现的次数,出现次数越多,权重越大。如果某一特征单词在图像中出现30次,那么其所携带视觉信息重要性不应该是只出现1次单词的30倍,为避免词频权重随着次数的成倍增减而骤增或者骤减,采用log函数削减其权重值数量级。

2.3 在线人脸检索

2.3.1 检索流程

人脸图像检索属于在线服务,用户最主要关注的是检索性能和结果质量,本文人脸检索具体过程如图3所示。

图3 人脸图像检索过程

检索过程中首先对目标人脸图像进行局部区块检测,分别提取出5个区块的SURF视觉特征。通过视觉特征词汇表对SURF特征向量进行分类,得到目标视觉单词集合。为提高视觉特征分类效率,避免线性匹配分类,本文系统在启动时已从HBase数据库中载入了视觉特征词汇表,以Spark RDD(Resilient Distributed Dataset)的形式存储于集群的内存中。在执行特征分类时,首先利用Spark的broadcast算子将目标人脸区块的所有SURF特征向量广播分发到不同worker节点上,接着采用flatMap算子在多个执行器内并行计算特征向量和视觉单词之间的距离,然后通过reduceByKeyLocally算子过滤出每个RDD数据分片中与特征向量距离最短的特征单词,并合并多个分区的过滤结果,以HashMap形式的数据结构返回每个特征向量对应的目标视觉单词ID,从而以并行计算的方式完成SURF特征向量的归类。最后根据目标视觉单词集合从HBase中的倒排索引表查找出候选人脸集合,再根据候选人脸集合从HOG区块特征表中查找出对应的HOG特征,通过结合SURF特征和HOG特征的相似度算法计算候选图像相似得分,排序后得到最终的相似人脸检索结果。

2.3.2 相似度算法

为提高人脸检索的准确率,本文在计算候选图像相似度时将SURF特征和HOG特征进行结合,提出基于特征词频维度和区块匹配维度的相似度算法。该算法考虑了SURF特征词汇的频率,计算公式如式(3)和式(4)所示。

(3)

wt,q=wft,q·idf(t)

(4)

其中:S(q,d)表示目标脸q和候选脸d在特征词频维度上的相似度;D是目标脸q中的所有特征单词向量;wft,d是特征单词t在相似脸d中的词频权重,在倒排索引构建阶段统计得到;wt,q表示特征单词t在目标脸q中的词频权重;wft,d和wt,q均采用欧式归一化方式。

基于区块匹配维度的相似度算法考虑了人脸区块HOG特征的相似程度,计算公式如式(5)所示。

(5)

其中:P(q,d)表示目标脸q与候选脸d在区块匹配维度上的相似度;F是面部的所有局部区块集合,本文中即左眼、右眼、鼻子、左嘴角、右嘴角5个区块;Hp,q表示目标脸q在局部区块p上的HOG特征直方图,本文采用巴氏距离(Bhattacharyya,BC)[22]算法计算目标脸和相似脸在区块p上的HOG特征直方图相似度;N是区块总数,即N=5。对所有对应区块的巴氏距离求平均,得到基于区块匹配维度的相似度。

本文采用权重系数λ将SURF特征词频算法和HOG特征区块匹配算法结合,得到最终的相似度得分算法,计算公式如式(6)所示。

score(q,d)=λ·S(q,d)+(1-λ)·P(q,d)

(6)

其中:权重系数λ作用是平衡SURF特征词频和HOG区块特征对相似得分的贡献程度,λ∈[0,1]。λ值越大,词频权重相似度越重要,反之则区块匹配相似度越重要。通过离线训练获得合适的λ取值,以此对候选人脸计算相似度得分,再根据得分排序,获得检索结果。

3 实验与结果分析

3.1 实验环境

本文Spark人脸检索集群部署在5台物理服务器上,包括1个Master节点和4个Worker节点,每台物理机配置为24核2.3 GHz处理器、32 GB内存。本文通过网络爬虫从互联网上获取80万张人脸图像作为基础人脸库,并从LFW[23](Labeled Face in Wild)数据集中抽取200张(20个人,每人10张)有标注人脸图像作为验证集加入基础人脸库中。为面向不同的人脸库规模评估系统的检索性能和准确率,本文分别构造4个不同规模的人脸库进行实验,分别有1×104张、4×104张、2×105张、8×105张人脸图像。

3.2 结果分析

3.2.1 视觉特征数

本文的局部区块划分方法记为Block,对整张人脸进行处理的无区块划分方法记为Non-Block。如图4所示,在提取SURF视觉特征阶段,同样的人脸图像规模下,区块划分方法提取的视觉特征数不到无划分方法的一半,表明该方法能够通过减少SURF特征数降低倒排索引规模,提高索引构建效率和检索效率。

图4 SURF特征数对比

3.2.2 系统性能

Hadoop具有和Spark类似的MapReduce分布式计算思想,为进行性能比较,本文在相同的物理配置下搭建了Hadoop分布式集群,包括1个Master节点和4个Slave节点,并采用Hadoop自带的MapReduce接口实现了同样的倒排索引构建流程和人脸检索流程。如表1和表2所示,本文Spark集群运行索引构建过程比Hadoop集群更高效,且图像规模越大差距越显著。运行人脸检索流程也表现出相同的趋势,并发请求数越大,Spark集群性能优势越明显。上述结果表明本文系统能够发挥Spark框架在内存计算和DAG调度机制等方面的优势,提供更快的海量人脸图像处理性能。

表1 Spark对Hadoop索引构建加速比

表2 Spark对Hadoop人脸检索加速比

本文以加速比作为系统在海量数据环境下扩展能力的衡量指标,以数据分片数代表运行的并行程度。如图5所示,以数据拆分为8个分片时的运行时间作为加速比基准,随着并行度提高,本文系统进行离线索引构建的效率越高,加速比越大。80万人脸数据采用64个数据分片时加速比达到了6.4倍,体现出良好的可扩展性。

图5 离线索引构建加速比

在线人脸检索的运行加速比如图6所示,以请求拆分为8个分片时的运行时间作为加速比基准,检索请求为100并发时,数据分片数增加没有显著提高加速比,是由于Spark集群需要耗费一定的资源进行节点间数据传输及网络通信。随着并发请求量的扩大,传输和通信所需时间占比越小,数据并行处理效果越显著,当请求达到6 400、数据分片为64时,检索加速比达到6.8倍,体现出良好的并发性。

图6 在线并发检索请求加速比

3.2.3 检索准确率

本文基于1×104张人脸库对相似度权重系数λ进行实验,采用mAP(mean Average Precision)作为系统的人脸检索指标,该指标基于多次检索结果中的准确率和召回率来计算平均检索精度。实验结果如图7所示,λ=0,即只采用HOG区块匹配相似算法,λ=1,即只采用SURF视觉词频相似算法,两者准确率均低于0.59,而当λ处于0到1之间,即2种相似算法结合,各占一定比例的权重,HOG特征补充了SURF特征丢失的部分人脸区块相似信息,在λ=0.2时mAP值达到最大。

图7 不同权重系数下的mAP值对比

本文相似得分算法记为SP-Sim,基于SURF特征词频维度的相似度算法记为S-Sim。实验结果如图8所示。对比Block+S-Sim和Non-Block+S-Sim算法,前者采用区块划分方法,在不同人脸库规模下准确率比后者平均提高了30%左右。对比Block+SP-Sim和Block+S-Sim算法,前者采用基于视觉词频和区块匹配结合的相似算法,准确率平均达到了后者的2.7倍左右。对比Block+SP-Sim和Non-Block+S-Sim算法,前者为本文综合的改进算法,后者为视觉词袋原型算法,本文算法准确率平均比后者高了2.4倍左右,表明本文提出的区块划分方法和相似度算法能够有效提升检索准确率。

图8 不同检索算法的mAP值对比

4 结束语

本文提出基于Spark分布式计算平台的人脸图像检索系统。首先针对人脸图像空间分布特点设计局部区块划分方法,缩小特征规模,增加流程并行度;然后提出基于SURF特征词频维度和HOG特征区块匹配维度的相似度算法,提高检索准确率;最后基于Spark框架实现人脸检索系统处理海量数据和检索请求。实验结果表明,本文系统较基于Hadoop的检索系统运行效率更高,并具有良好的可扩展性和并发性。由于本文只针对静态人脸图像检索进行研究,未结合视频图像中的人脸数据进行处理,因此下一阶段将对此进行研究,实现对视频图像数据的高效检索。

[1] 赵永威,李弼程,彭天强,等.一种基于随机化视觉词典组和查询扩展的目标检索方法[J].电子与信息学报,2012,34(5):1154-1161.

[2] Apache SparkTM-Lightning-fast Cluster Computing[EB/OL].[2016-12-16].http://spark.apache.org/.

[3] DEAN J,GHEMAWAT S.MapReduce:Simplified Data Processing on Large Clusters[J].Communications of the ACM,2008,51(1):107-113.

[4] SHVACHKO K,KUANG H,RADIA S,et al.The Hadoop Distributed File System[C]//Proceedings of the 26th Symposium on Mass Storage Systems and Technologies.Washington D.C.,USA:IEEE Press,2010:1-10.

[5] KAMENCAY P,BREZNAN M,JELSOVKA D,et al.Improved Face Recognition Method Based on Segmentation Algorithm Using SIFT-PCA[C]//Proceedings of the 35th International Conference on Telecommunications and Signal Processing.Washington D.C.,USA:IEEE Press,2012:758-762.

[6] PARUA S,DAS A,MAZUMDAR D,et al.Deter-mination of Feature Hierarchy from Gabor and SIFT Features for Face Recognition[C]//Proceedings of the 2nd International Conference on Emerging Applications of Information Technology.Washington D.C.,USA:IEEE Press,2011:257-260.

[7] 彭天强,栗 芳.基于二进制哈希与空间金字塔的视觉词袋模型生成方法[J].计算机工程,2016,42(12):164-170.

[8] dos SANTOS J M,de MOURA E S,da SILVA A S,et al.A Signature-based Bag of Visual Words Method for Image Indexing and Search[J].Pattern Recognition Letters,2015,65(C):1-7.

[9] LU Guoyu,HU Yingjie,SEBE N.Weighted SIFT Feature Learning with Hamming Distance for Face Recognition[C]//Proceedings of 2014 International Conference on Computer Vision Theory and Applications.Washington D.C.,USA:IEEE Press,2014:691-699.

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

[11] WANG Hanli,XIAO Bo,WANG Lei,et al.CHCF:A Cloud-based Heterogeneous Computing Framework for Large-scale Image Retrieval[J].IEEE Transactions on Circuits and Systems for Video Technology,2015,25(12):1900-1913.

[12] 朱为盛,王 鹏.基于 Hadoop 云计算平台的大规模图像检索方案[J].计算机应用,2014,34(3):695-699.

[13] GRACE R K,MANIMEGALAI R,KUMAR S S.Medical Image Retrieval System in Grid Using Hadoop Framework[C]//Proceedings of 2014 International Conference on Computational Science and Computa-tional Intelligence.Washington D.C.,USA:IEEE Press,2014:144-148.

[14] RAJU U S N,GEORGE S,PRANEETH V S,et al.Content Based Image Retrieval on Hadoop Framework[C]//Proceedings of 2015 IEEE International Congress on Big Data.Washington D.C.,USA:IEEE Press,2015:661-664.

[15] CHENG Wenchen,QIAN Jiang,ZHAO Zhicheng,et al.Large Scale Cross-media Data Retrieval Based on Hadoop[C]//Proceedings of the 11th International Con-ference on Heterogeneous Networking for Quality,Reliabi-lity,Security and Robustness.Washington D.C.,USA:IEEE Press,2015:133-138.

[16] BRADSKI G.The Opencv Library[J].Dr. Dobb’s Journal,2000,25(11):120-126.

[17] Apache HBaseTM[EB/OL].[2016-12-16].http://hbase.apache.org/.

[18] LIENHART R,MAYDT J.An Extended Set of Haar-like Features for Rapid Object Detection[C]//Proceedings of 2002 International Conference on Image Processing.Washington D.C.,USA:IEEE Press,2002:900-903.

[19] BAY H,TUYTELAARS T,van GOOL L.Surf:Speeded up Robust Features[C]//Proceedings of European Con-ference on Computer Vision.Berlin,Germany:Springer,2006:404-417.

[20] DREUW P,STEINGRUBE P,HANSELMANN H,et al.SURF-Face:Face Recognition Under Viewpoint Con-sistency Constraints[C]//Proceedings of British Machine Vision Conference.London,UK:[s.n.],2009:1-11.

[21] DALAL N,TRIGGS B.Histograms of Oriented Gradients for Human Detection[C]//Proceedings of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington D.C.,USA:IEEE Press,2005:886-893.

[22] CHOI E,LEE C.Feature Extraction Based on the Bhattacharyya Distance[J].Pattern Recognition,2003,36(8):1703-1709.

[23] HUANG G B,RAMESH M,BERG T,et al.Labeled Faces in the Wild:A Database for Studying Face Recognition in Unconstrained Environments:07-49[R].Amherst,USA:University of Massachusetts,Amherst,2007.