基于移动平台的快速相似脸检索

邓健康，杨静，王蒙，刘青山

(南京信息工程大学 信息与控制学院，南京210044)

随着手机、平板电脑等移动设备计算与存储性能的提升，移动设备的智能化也成了学术界与工业界的研究热点.移动智能终端上图像传感器的改进也给移动平台上的视觉应用提供了更好的硬件条件支撑［1］.同时，随着人脸分析技术的进步，移动终端的人脸识别、表情识别、属性分析等移动应用在人们的生活中已经崭露头角.另外，基于内容的图像信息检索技术也逐渐成熟，各大搜索引擎也加入了“以图搜图”的功能.人脸识别技术和基于内容的信息检索技术的进步，使得自动化的相似脸检索成为可能.相似脸检索在娱乐搜索、犯罪监视等方面具有很高的应用价值.本文基于移动平台在大规模人脸数据库上实现快速的相似脸检索.然而，移动平台的计算和存储能力毕竟有限.所以，如何设计时间复杂度和空间复杂度低的算法成为解决移动平台上相似脸检索的关键问题.

基于精确的人脸配准，建立了级联形状和纹理特征的高效的相似脸检索模型，核心技术包括人脸配准、人脸特征提取与压缩、检索算法.

人脸配准是在一幅人脸图像中自动地定位出人脸各个器官的准确位置以及人脸的外轮廓，是人脸图像处理与分析的基础与前提，不精确的关键点定位往往会引起“误配准灾难”［2］.近年来，国内外学者提出了各种人脸配准方法，大体上可以分为基于参数化模型的方法［3-7］和基于回归的方法［8-12］.基于级联回归的方法在自然条件下的人脸库上配准精度高，且模型简单、速度快，备受研究者的关注.该方法主要依赖局部描述子稳健的性能，通过级联的弱回归器拟合复杂的非线性映射，能够有效定位人脸关键点的坐标.文献［10］采用快速SIFT(Scale Invariant Feature Transform)特征，通过最小二乘回归实现关键点快速定位.文献［11］通过利用二值特征，进一步提高了配准速度.文献［12］通过显式的回归遮挡信息，增强了模型在局部遮挡情况下的鲁棒性.在级联回归模型中引入稀疏约束，可以增强模型的鲁棒性，同时压缩模型的存储空间.

文献［13］指出了高维人脸特征对人脸识别的重要意义，并采用旋转稀疏投影的方式进行了高效的特征降维.基于精确的人脸配准，可以提取关键点周围的高维纹理特征，并通过稀疏投影高效降维.

高效的索引机制是图像检索的关键，图像哈希［14］作为一种优良的图像单向压缩技术，是近年来图像检索领域的研究热点，但哈希算法必须有足够的散布空间以降低冲突率.通过级联形状和局部纹理特征，可以不断缩小检索空间，进行高效的相似脸检索.由于形状和局部纹理的特征维度均较低，可以采用基于稀疏重构的方式高效地检索相似脸，最终获得脸型和五官纹理均相似的人脸图像.

对 LFW(Labeled Face in Wild)［15］进行扩展，建立了近百万级的人脸数据库，采用级联形状和纹理特征的方法实现高效的相似脸检索.该模型对移动端的计算和存储资源要求较低，具有精度高、速度快、模型小的特点.在三星Note 3智能手机上，每幅人脸图像的配准时间在10 ms左右，相似脸检索时间在1.5 s左右，整个模型大小仅 5.4 MB.

1 级联形状和纹理的相似脸检索

为了在移动平台上进行快速的相似脸检索，基于精确的人脸配准，采用级联形状和纹理的相似脸检索模型，方法流程如图1所示.

首先，通过基于稀疏约束的级联回归模型进行人脸配准，估计人脸姿态［16］，进行图像规范化以消除旋转、平移、缩放差异.稀疏约束的级联回归能够筛选鲁棒的特征，高效地压缩模型的存储空间.

然后，在对应的人脸姿态子集中进行基于稀疏形状重构的相似脸型检索.同时，提取测试人脸图像的局部纹理特征，并通过稀疏投影进行高效降维.

最后，将低维纹理特征在脸型相似的子集中进行基于稀疏纹理重构的相似脸检索.通过级联形状和纹理的检索，检索效率明显提升，且返回的结果在脸型和五官纹理上均具有很强的相似性.

图1 相似脸检索示意图Fig.1 Schematic of similar face retrieval

图2 基于移动平台的相似脸检索Fig.2 Similar face retrieval on mobile platform

图2展示了基于移动平台的相似脸检索的交互过程，移动端先将人脸形状发送到服务器端，接着对内部的某些关键点提取高维纹理特征，并进行基于稀疏投影的特征降维，然后将低维纹理特征发送至服务器端.在移动端进行纹理特征提取的时候，服务器端同步完成基于稀疏形状重构的相似脸型检索.服务器端基于稀疏纹理重构的相似脸检索在脸型相似的人脸子集中完成，检索效率较高，最终服务器端向移动端返回相似度最高的5个人脸图像.相似脸检索过程中移动端和服务器端的通信主要有:移动端发送136维人脸形状，500维人脸纹理特征，服务器端返回5幅相似脸图像(稀疏重构支持增量传输，稀疏系数可作为相似度指标).移动端的模型存储主要是稀疏级联回归模型(约1.56 MB)和高维纹理特征的稀疏投影矩阵(约3.80 MB).移动端的计算主要集中在特征提取、级联回归，纹理特征稀疏投影.整个交互过程在近百万级人脸数据库上进行，硬件条件为三星Note 3，Wifi环境(或者3G)，IBM 服务器(12 核，3.4 GHz，128 GB内存)，相似脸检索的时间大约1.5 s.

1.1 基于稀疏级联回归的人脸配准

级联回归模型通过级联简单的回归器不断拟合配准残差完成人脸配准.通过级联T个回归器(R1，R2，…，RT)不断拟合配准残差:

式中，Ii为人脸图像;N为训练集人脸图像的数目;Xi*为标定的人脸形状;Xit为迭代过程中的人脸形状;Rt为每步迭代的回归矩阵;Φ(Ii，Xit)为图像Ii在形状Xit位置下的SIFT特征描述，每一步回归的目标都是减少残差，该优化问题可以通过最小二乘求解，存在闭式解.迭代过程中的形状更新按照累加的形式完成:

在实际的应用过程中，迭代步数在4或5次即可收敛.由训练的目标函数可知，迭代过程中的形状实际上是在人脸形状的线性子空间中，由此，引入了隐性的人脸形状约束，这种约束相对于参数化模型灵活性较高，能够适应姿态变化和夸张表情.

从迭代过程中的形状增量RtΦ(Ii，Xit)可知，对于每个关键点迭代过程中位置的变化，都与所有关键点的特征相关，因此，参数维度较高，容易过拟合.可以对回归矩阵Rt引入稀疏约束，即假设某个关键点的位置变化仅仅与一部分关键点的特征相关.

式中，ΔXit=Xi*－Xit，该优化问题可由 Lasso［17］求解;λ1为正则系数，控制回归矩阵Rt的稀疏度.

通过交叉验证确定λ1=0.1，此时，Rt每行的非零元素约为300左右，远小于8704(68×128)，Rt可以获得5%左右的压缩率，大大缩小了模型的存储空间.同时，稀疏的回归矩阵对应着稀疏的特征选择，相对于最小二乘的求解方法，稀疏约束抑制了过拟合倾向，筛选了鲁棒的特征.基于稀疏级联回归的人脸配准过程如图3所示，配准过程迭代5次.

图3 基于稀疏级联回归的人脸配准Fig.3 Face alignment based on sparse cascade regression

1.2 人脸特征提取与压缩

基于人脸关键点的准确定位，对人脸图像进行了归一化以消除旋转、平移以及缩放的差异.如图4所示，基于每幅人脸图像构建5层的图像金字塔(瞳孔距250，100，150，100，50 像素)，并在一些人脸内部关键点位置(40像素×40像素)提取人脸的局部多尺度特征.采用LBP，HoG和Gabor特征描述子，最终形成高维的人脸纹理特征.

图4 基于稀疏投影的特征降维Fig.4 Feature dimension reduction based on sparse projection

由于移动平台计算和存储能力有限，需要对高维特征进行压缩.然而，传统的特征降维方法对计算和存储要求较高.例如，采用主成分分析法将10万维的高维特征降到1000维，每次投影需要1亿次浮点乘法运算，投影矩阵占用存储空间400MB.通过学习稀疏投影矩阵，能够对高维的人脸纹理特征进行高效降维.如图4所示，X是高维特征，即每幅人脸图像每个关键点的多尺度联合特征.通过PCA将原始高维特征降维，为了降低计算和存储复杂度，采用稀疏投影矩阵拟合该降维过程.

考虑到子空间对旋转具有不变性，通过在最终的低维特征Y前引入旋转矩阵R，可以近一步提升投影矩阵B的稀疏度.

上述优化问题在给定R的情况下，可以通过Lasso［17］求解，并且B的每列求解可以并行加速.在给定B的情况下，R存在闭式解，R=UVT，其中UVT来自YXTB的SVD分解UσVT.最终通过迭代求解得到稀疏投影矩阵B，在测试过程中，降维过程就是BTX.

1.3 基于分层匹配的相似脸检索

在百万级的人脸数据库上直接进行相似脸检索往往效率较低，可以结合人脸形状和局部纹理进行分层匹配，整个过程如图1所示.

首先，通过人脸关键点估计人脸姿态［16］，进行人脸的规范化，人脸侧转的角度用来选择相应的人脸检索库的子集.同时也可以通过性别、年龄、种族等属性对检索库进行分组进一步缩小检索空间.

然后，将测试图片的人脸形状向量在样本的形状字典上进行稀疏重构，获取脸型相似的人脸样本.

最后，将测试图片的低维纹理向量在样本的纹理字典上进行稀疏重构，获取脸型和五官纹理均相似的人脸图像.

式中，T(X，β)为将测试的人脸形状X与字典中的人脸形状D消除旋转、平移、缩放的相似变换;α为稀疏重构系数.

同理进行稀疏纹理重构，差异仅仅在于纹理特征向量不需要进行相似变换.

2 人脸配准的实验结果

2.1 实验数据与定位结果评价

采用300-W人脸配准比赛［18］的标注数据进行训练和测试，其中包括AFW(337)，iBug(135)，XM2VTS(2 360)，LFPW(811+224)，HELEN(2000+330)，关键点的定义如图5所示.LFPW和Helen的测试集用来进行测试，其余图像都用于训练.为了进一步扩充数据集，对训练数据进行镜像操作，对初始化的平均形状进行扰动以产生更多的训练数据，最终获得了112860(5643×2×10)的训练数据.

图5 关键点的定义Fig.5 Definition of landmarks

在人脸关键点定位的精度评价方面，关键点的平均定位误差定义为

2.2 LFPW和Helen实验结果

LFPW和Helen都是自然场景下的人脸数据库，其中姿态、光照、表情变化比较大，并且存在一定程度的遮挡.作为对比的方法是4层级联回归的SDM［10］模型.测试结果如图6所示，本文的方法比SDM略好一些，主要是因为稀疏约束可以提取鲁棒的特征，对局部遮挡适应性更强.图6同时显示了每个关键点的定位误差，每个关键点上圆的半径代表平均定位误差的大小，由图可知，眼睛上的关键点定位比较准确，而人脸外轮廓和眉毛上的关键点定位误差较大.表1、表2给出了各种级联回归方法在LFPW和Helen上的平均定位误差，其他方法的平均定位误差来自文献［11］.表3给出了稀疏度与模型大小的关系，图7给出了Android平台人脸配准示意图.

图6 LFPW和Helen配准结果Fig.6 Alignment results on LFPW and Helen

表1 LFPW归一化平均误差Table1 Normalized mean error on LFPW

表2 Helen归一化平均误差Table2 Normalized mean error on Helen

表3 稀疏度与模型大小的关系Table3 Relationship between sparsity and model size

图7 Android平台人脸配准结果Fig.7 Results of face alignment on Android platform

3 相似脸检索的实验结果

3.1 实验数据

原始的LFW［15］数据库包含5 749个公众人物的13233张人脸图像，通过这5749个人名，在搜索引擎上整理得到617430张人脸图像，每个人对应的人脸图像数目从200到2000不等.同时整理出包含1 540人的中国名人列表，并相应地搜索得到186985张人脸图像.数据库整理时的人脸检测方法来自文献［19］，大约10%左右漏检的人脸图像采用手工方式标注人脸框，人脸配准采用稀疏级联回归，姿态估计方法来自文献［16］.相似脸检索库的规模大约是75万，每个人的人脸图像集大约包括3%～5%的其他人脸.对库中的人脸按性别(男/女)、种族(黑人/白人/黄种人)、姿态(侧角)进行分组，按树的形式重新整理了数据库.

为了比较基于分层匹配的相似脸检索方法和基于哈希的相似脸检索方法，从每个名人库中抽出5张人脸图像，一共36445(7289×5)张人脸图像.对这些人脸图像进行配准规范化，提取LBP，HoG和 Gabor联合特征，通过 k-means聚成1000类.然后，通过人工筛选的方式，将每一类中视觉上不相似的人脸图像删除，最终形成相似脸检索测试库.

3.2 高维特征的稀疏投影

在原始的LFW数据库上确定最佳的特征提取方式、关键点数目、图像金字塔层数、特征投影的稀疏度.原始高维人脸特征通过PCA降维到500维，稀疏投影拟合该降维过程，低维特征用来进行基于最近邻的人脸识别.如图8所示，通过控制变量法逐一调节参数，最终权衡速度与精度，选取LBP特征，关键点的数目为13(不包括人脸外轮廓和眉毛上的关键点)，图像金字塔层数为5层，特征投影的稀疏度为99%，在LFW数据库上的识别精度为81.42%.

图8 关键点数目、金字塔层数、投影矩阵稀疏度对识别精度的影响Fig.8 Effects of number of landmarks，layer of pyramids and sparsity of projection matrixes on recognition accuracy

3.3 相似脸检索

首先，在相似脸检索测试库上比较基于分层匹配的相似脸检索和基于哈希的相似脸检索.基于哈希的相似脸检索在原始高维人脸特征上进行，哈希编码的方式参考了文献［20］.实验结果如表4所示，基于哈希的相似脸检索方式在速度上有一定的优势，然而，基于分层匹配的方式能够在保证实时的情况下，准确率高出很多.

表4 速度和准确率的比较Table4 Comparison of speed and accuracy

然后，在扩展的LFW数据库上进行大规模相似脸检索测试.对于用户输入的人脸图像，首先进行快速人脸配准，给出性别、种族信息.当服务器端接收到这些信息的时候，在相应的子库中进行基于稀疏形状重构的相似脸型检索，稀疏重构的正则参数设为0.01.当服务器端完成相似脸型的检索，客户端的人脸低维纹理特征也发送到服务器端，于是服务器端继续完成基于稀疏纹理重构的相似脸检索，稀疏重构的正则参数设为0.1，最后稀疏系数最大的5个人脸图像作为相似度最高的图像返回给客户端.图9分析了整个算法的效率，通常在1.3～1.5s之间即可返回与输入人脸图像最相似的5个相似脸，图10展示了检索返回的相似脸.

图9 基于移动平台的相似脸检索耗时分析Fig.9 Time consuming analysis of similar face retrieval based on mobile platform

图10 级联形状和纹理的相似脸检索结果Fig.10 Results of similar face retrieval based on cascade shape and appearance

4 结论

主要研究了基于移动平台的快速相似脸检索问题，基于精确的人脸配准，建立了级联形状和纹理的相似脸检索模型.

1)在人脸检测的基础上进行基于稀疏约束的级联回归配准，回归器的训练通过引入稀疏约束，增强了模型的鲁棒性，同时可以将模型的大小压缩到原来的5%左右.提出的配准模型在LFPW和Helen等自然场景的人脸数据库上取得了很好的配准结果，具有速度快、精度高、模型小的特点.

2)在人脸配准的基础上，级联人脸形状和局部纹理特征进行基于稀疏重构的高效的相似脸检索，其中局部纹理特征采用稀疏投影的方式压缩高维特征.提出的相似脸检索方法在接近百万级的数据库上能够实时检索相似脸，且脸型结合五官纹理的相似度衡量标准符合人们的视觉感受.

3)目前的配准算法对于夸张表情、严重遮挡等情况的配准精度还有待提高，服务器端的相似脸检索效率也可以继续提升.在今后的工作中，将进一步提高配准精度，融合图像哈希等方法进一步加速检索.

References)

［1］ Hua G，Fu Y，Turk M，et al.Introduction to the special issue on mobile vision［J］.International Journal of Computer Vision，2012，96(3):277-279.

［2］ 山世光，高文，唱轶钲，等.人脸识别中的“误配准灾难”问题研究［J］.计算机学报，2005，28(5):783-791.Shan S G，Gao W，Chang Y Z，et al.“Curse of Mis-alignment”problem in face recognition［J］.Chinese Journal of Computers，2005，28(5):783-791(in Chinese).

［3］ Cootes T F，Taylor C J，Cooper D H，et al.Active shape modelstheir training and application［J］.Computer Vision and Image Understanding，1995，61(1):38-59.

［4］ Cootes T F，Edwards G J，Taylor C J.Active appearance models［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23(6):681-685.

［5］ Cristinacce D，Cootes T.Automatic feature localisation with constrained local models［J］.Pattern Recognition，2008，41(10):3054-3067.

［6］ Zhu X X，Ramanan D.Face detection，pose estimation，and landmark localization in the wild［C］//Proceeding of the Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2012:2879-2886.

［7］ Zhou F，Brandt J，Lin Z.Exemplar-based graph matching for robust facial landmark localization［C］//Proceedings of the IEEE International Conference on Computer Vision.Piscataway，NJ:IEEE，2013:1025-1032.

［8］ 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.Washington:IEEE Computer Society，2013:3476-3483.

［9］ Cao X D，Wei Y C，Wen F，et al.Face alignment by explicit shape regression［C］//Proceeding of the Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2012:2887-2894.

［10］ Xiong X H，De la Torre F.Supervised descent method and its applications to face alignment［C］//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington:IEEE Computer Society，2013:532-539.

［11］ Ren S Q，Cao X D，Wei Y C，et al.Face alignment at 3000 FPS via regressing local binary features［C］//Proceeding of the Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2014:1232-1240.

［12］ Burgos-Artizzu X P，Perona P，Dollar P.Robust face landmark estimation under occlusion［C］//Proceeding of the International Conference on Computer Vision.Piscataway，NJ:IEEE，2013:1513-1520.

［13］ Chen D，Cao X，Wen F，et al.Blessing of dimensionality:highdimensional feature and its efficient compression for face verification［C］//Proceeding of the Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2013:3025-3032.

［14］ Gionis A，Indyk P，Motwani R.Similarity search in high dimensions via hashing［J］.VLDB，1999，99(6):518-529.

［15］ Huang G B，Mattar M，Berg T，et al.Labeled faces in the wild:a database for studying face recognition in unconstrained environments［J］.International Journal of Computer Vision，2007，96(3):277-279.

［16］ Asthana A，Zafeiriou S，Cheng S，et al.Robust discriminative response map fitting with constrained local models［C］//Proceeding of the Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2013:3444-3451.

［17］ Tibshirani R.Regression shrinkage and selection via the lasso［J］.Journal of the Royal Statistical Society，1996，24(3):267-288.

［18］ Sagonas C，Tzimiropoulos G，Zafeiriou S，et al.300 faces in-thewild challenge:the first facial landmark localization challenge［C］//Proceedings of the IEEE International Conference on Computer Vision.Piscataway，NJ:IEEE，2013:397-403.

［19］ Yan J J，Zhang X C，Lei Z，et al.Structural models for face detection［C］//Proceeding of the Automatic Face and Gesture Recognition.Washington:IEEE Computer Society，2013:1-6.

［20］ Cheng J，Leng C，Wu J X，et al.Fast and accurate image matching with cascade hashing for 3D reconstruction［C］//Proceeding of the Computer Vision and Pattern Recognition.Piscataway，NJ:IEEE，2014:1-8.