基于在线增量学习的实时人脸跟踪算法

包　芳　张炎凯,　王士同

1(江阴职业技术学院　江苏 江阴 214400)2(江苏省信息融合软件工程技术研究开发中心　江苏 江阴 214400)3(江南大学　江苏 无锡 214000)



基于在线增量学习的实时人脸跟踪算法

包芳1,2张炎凯1,2,3王士同3

1(江阴职业技术学院江苏 江阴 214400)2(江苏省信息融合软件工程技术研究开发中心江苏 江阴 214400)3(江南大学江苏 无锡 214000)

摘要提出基于在线增量式极端随机森林分类器的实时人脸跟踪算法。算法用在线极端随机森林分类器实现基于检测的跟踪，并结合动态目标框架和P-N学习矫正检测的错误。 实验结果表明，该算法能够在不确定背景下对任意人脸实现较长时间段内的稳定快速的实时跟踪，并能有效排除背景等的干扰,效果较好。

关键词在线增量学习极端随机森林P-N学习动态目标框架实时人脸跟踪

0引言

在视频监控快速普及的情况下，迫切需要远距离、用户非配合状态下的快速识别和跟踪技术。其中，人脸可以最自然的方式实现快速身份识别、预警和跟踪。因此，人脸检测、识别与跟踪是机器视觉领域的一个研究热点，国内外学者对此进行了大量的研究。

静态人脸的检测与识别技术，基本已成熟，且广泛应用于考勤、检票等应用场合中。运动人脸的检测与跟踪又分为固定背景与不确定背景两种情况。固定背景下的运动人脸检测主要采用AdaBoost系列算法[1,2]，跟踪则采用Mean-Shift算法[3]和粒子滤波算法[4]两类框架实现。固定背景下的人脸跟踪，只能是一种短期的、局限性较强的跟踪，在实际场合中应用价值并不大。在网络集成、背景变化的情况下，任意选中需跟踪人脸，进行长时间稳定跟踪，才是实际应用所需要的，可供公共交通场所、安全部门等用于特定人员的有效跟踪，具备极高的实用价值。在任意环境中长期稳定地跟踪人脸，主要存在以下挑战：人脸的各类形变；人脸在某些帧中移开，过了一个不确定阶段又出现；背景的复杂性和不确定性等。因此，传统的批量离线机器学习模式已不能解决此类问题，而需要使用在线增量学习模式。

目前，增量学习主要用基于决策树的算法来实现，特别是基于决策树的随机森林算法[5,6]。随机森林对原始训练样本进行采样替换，算法简单、快速、稳定适用于各种分类场合。但无论是应用贪婪算法还是统计算法的随机森林，在增量重构时都需要重新计算最优属性或统计值，因此需要大量数据作为样本。

Geutrs等提出的极端随机森林算法[7]，直接采用原始的训练样本，随机选择分裂阈值，在分类精度和时间开销方面，都优于一般随机森林算法，比较适合于小样本数据流分类。视频序列中的人脸跟踪，属于典型的小样本数据流中的两分类问题，适合用基于极端随机森林的在线增量学习算法来实现。

另外，P-N学习[8]经常被用于矫正分类器的错误。P-experts将那些被分类器标记为负样本，但根据约束条件应该为正样本的那些样本赋予“正”的标签，并添加到训练样本集中；而N-experts则将那些被分类器标记为正样本，但根据约束条件应该为负样本的那些样本赋予“负”的标签，并添加到训练样本集当中。这样，P-experts增加了分类器的鲁棒性，而N-experts则增加了分类器的判别能力。

近年来，基于检测的跟踪方法成为研究的热点。一般这种方法都需检测器和跟踪器并行运行，由检测结果及时重置完善跟踪，以达到持续跟踪。检测算法常用随机森林分类器，跟踪则采用光流法等。如上所述，随机森林算法在增量重构时需要大量样本，光流法算法复杂，抗噪声能力一般，均不能适应视频序列中人脸的实时跟踪场合。

因此，本文提出应用极端随机森林分类器进行在线增量式目标检测，然后应用P-N学习[8]再次提升检测性能，并构建在线动态目标框架，实时更新目标框架。最后综合应用检测和P-N学习的结果，以及距离动态目标模型的相似度，实现人脸在线跟踪。

1人脸建模和动态目标框架

1.1人脸建模

本文采用2bitBP特征进行人脸建模。这是一种类Harr特征[9]，通过量化，只有4种可能的编码。因此比较适合于在线监测的场合。

建模过程包括特征类型的确定以及相应的特征取值。假定需要判断一个Patch块是否为检测目标。所谓特征类型，是指在这个Patch在(x,y)坐标，取一个长width，高height的框，这个组合(x,y,width,height)即为相应的特征类型。在已经选定特征类型的情况下，把框左右分成相等的两部分，分别计算左右两部分灰度和的大小，会有两种情况。同样的，把框分成上下相等的两部分，也会有两种情况。于是在分了上下左右后，总共会有4种情况，可以用2 bit来描述这4种情况，即可得到相应的特征取值。

2bitBP特征对外界环境的光照等变化具有良好的鲁棒性，但对于人脸自身形态的变化有较高的漏检率，而基于人脸肤色的模型则对自身形变有很好的鲁棒性。因此，本文在后续的P-N学习的约束条件中，利用基于YCgCr颜色空间[10]的肤色检测模型，保证对形变的鲁棒问题。

1.2动态目标框架

本文提出一种动态目标框架，它是归一化后的正样本和负样本的集合，即为本文的训练集合。设pi+为第i个被添加进去的正样本，同理pi-为第i个被添加进去的负样本。

给定任意一个图像片p和动态目标框架M，定义以下概念：

(1) Patch 块相似度：采用归一化积相关算法NCC[11](Normalized Cross-Correlation)计算两个图像块之间的相似度：

S(pi,j)=0.5×(NCC(pi,pj)+1)

(1)

(2) 正样本相似度：

(2)

(3) 负样本相似度：

(3)

(4) 最近邻正样本相似度：

(4)

由于本文涉及的是任意人脸的跟踪问题，因此，在第1帧，正样本为需跟踪的人脸。然后，在离其最近的扫描窗口内，在1%的范围内，进行旋转、偏移等20次几何变换，这样就产生了共20个正样本。负样本则在所有Patch块的外部随机生成。这些带标记的样本构成原始的动态目标框架，可以用来训练原始的极端随机森林分类器。在后续跟踪过程中，正负样本被标记后再依据P-N学习被陆续添加进来。

2基于在线增量式极端随机森林分类器的人脸检测

极端随机森林是由多棵决策树集成的分类器，它直接采用原始数据作为训练样本，并且在每棵树的决策节点上，随机选择分裂阈值。Geutrs等提出的极端随机森林并不支持在线增量学习，因此，王爱平等提出了支持在线学习的增量式极端随机森林算法，称为IERF(Incremental Extremely Random Forest)算法[12]。

IERF算法将新增的在线样本存储到叶节点，并通过Gini系数来决定是否需对当前叶节点进行分裂扩展。算法中的每棵决策树被称为增量超树，设输入为训练样本p和树索引i，输出为增量超树ti，其构造步骤如下：

步骤1：

if ti的根节点不存在

//返回根节点

返回一个根节点为R的增量超树ti，其标记值为p的标记值；

else

//需要分裂

训练样本p经分类后落到叶节点L；

将p存储到L的样本列表中；

更新L上样本类别的数量；

if Gini(L)>分裂阈值

构造一个子增量超树T(见步骤2)；

if L是根节点

将T作为新的根节点；

else

用T替换L成为原父节点的子节点；

endif

删除叶节点L；

返回增量超树 ti;

endif

endif

其中，Gini系数是用来衡量样本集合纯度的，设样本集D共有k个类别，pi为类别i的样本所占比率。Gini系数计算表达式为：

(5)

当某叶节点上的Gini系数超过一定阈值，则认为此节点上的混乱程度过高，需要继续分裂，利用当前存储的样本构造子增量超树。

(6)

当用当前存储的样本构造子增量超树时，设输入的是样本集合S，输出的是子增量超树T。其算法见步骤2。

步骤2：

if |S|

//生成叶节点

生成1个新的叶节点T；

将S中所有样本存储在T上；

统计S中所有类别标记的数量分布，也存储在T上；

返回叶节点T，T的标记值由S的类别标记数量确定；

Else

//生成子树

将S划分成2个子集Sl和Sr，决策属性和分裂测试s*采用Geutrs在文献[11]中的方法；

根据Sl和Sr，分别构造子增量超树Tl和Tr;

根据分裂测试s*，生成决策节点T，Tl和Tr分别是其左子树和右子树；

返回子增量超树T；

endif

其中nmin为设定的最小样本数。

本文对于极端随机森林的初始化训练，由第1帧生成的带标记的目标框架完成。然后，随着新帧的进入，用扫描窗口处理每帧，扫描窗口的大小同原始框定的人脸，归一化后构成1个新的图像块。每个新图像块就是在线增量样本，由以上算法对其进行标记。最后，极端随机森林的判决结果由所有增量超树的结果取概率平均，从而判断其是否人脸样本。为了提高检测速度，在后续过程中，扫描只在每帧的肤色区域内进行，大大提高了检测速度。

3P-N学习

当按以上算法检测出人脸样本后，就应该将其作为正样本加入动态目标框架。但检测有可能存在误检，因此，在算法中加入了P-N学习模块，对检测错误进行再次矫正。

P-N学习利用带标记和不带标记的样本之间存在的结构性特征，来逐步训练并改善分类器分类性能。P-N学习的过程如下：

(1) 准备一个数量较少的训练样本集和一个数量很大的测试样本集。

(2) 利用训练样本训练一个初始分类器，并对先验约束条件进行相应的设置。

(3) 利用训练好的初始分类器对测试样本赋予标记，并找出分类器赋予的标记同约束条件相矛盾的那些样本。

(4) 根据约束条件，为上述相矛盾的样本重新赋予标记，将其加入训练样本，重新训练分类器。其中， P-experts将那些被分类器标记为负样本，但根据约束条件应该为正样本的那些样本赋予“正”的标签，并添加到训练样本集中；而N-experts则将那些被分类器标记为正样本，但根据约束条件应该为负样本的那些样本赋予“负”的标签，并添加到训练样本集当中。这样，P-experts增加了分类器的鲁棒性，而N-experts则增加了分类器的判别能力。

本文对于经分类器标记的新样本，需要确定恰当的约束条件，找出分类器赋予的标记同约束条件相矛盾的那些，加入动态目标框架。从而近一步保障检测效果。

根据本文涉及的具体领域，首先设置的约束条件为：YCgCr颜色空间中的肤色模型。目前公认YCgCr颜色空间对于肤色的聚类性能是最好的，从视频序列中图像的RGB空间向YCgCr空间转换的公式为：

(7)

其中属于肤色的范围，也即为本文的约束条件1为：

(8)

当一个样本中绝大多数像素满足以上范围，而被分类器标注为负，则该样本被改为正样本进入动态目标框架。同理，当一个样本中绝大多数像素不满足以上范围，而被分类器标注为正，则该样本被改为负样本进入动态目标框架。

其次，人脸的跟踪有其空间域上的特性，就是目标在一个视频帧中只可能出现在一个位置。因此，当分类器和约束条件都认可某目标为正，剩余的图像块就被认为是负样本，即本文的约束条件2。

综上所述，本文的人脸跟踪算法总结如下：

(1) 在第1帧，手工框定需跟踪的任意人脸，并以此确定原始的正负样本集并加入动态目标框架，再利用其训练原始的极端随机森林分类器。

(2) 在后续帧，在肤色区域内利用扫描窗口获取新样本，并应用在线增量极端随机森林对其进行标记。然后进入P-N学习模块，再次确定此样本的最终标记，并加入动态目标框架。

(3) 在每帧扫描结束后，若有符合约束条件2的样本，则此样本的当前位置既为跟踪的位置。否则，按式(4)计算所有正样本的最近邻正样本相似度，选取值最大的样本位置作为跟踪位置，即实现了在线跟踪。

4实验结果及分析

根据以上基本的算法思路，在实验过程中，增加肤色区域搜索、三级变框等实用技巧，获得了较好的跟踪准确性和速度。实验环境为Intel i5-33i7U CPU，4 GB内存，64位操作系统。

具体的实验步骤如下：

(1) 在出现需跟踪人脸的时候，框选目标人脸，对框选人脸进行随机拉伸，旋转，获得20个正样本。在框选区域以外随机框选20个矩形区域，作为负样本。将这40个正负样本RGB图标准化转化为20×20的标准像素灰度图，然后将这些图转化为19×19的2 bit特征图(每2×2个像素组合产生一个2 bit，因此少一维)，以获得的40个2 bit特征图为基本数据，建立极端随机森林分类器。

(2) 从截取人脸的那一帧开始逐帧搜索人脸，每获取一帧，进行如下操作：

① 肤色区域搜索、三级变框等将RGB图压缩为100×100的RGB图，然后转化成YCgCr图，找出Cr∈[Cr0-5,Cr0+5]、Cg∈[Cg0-5,Cg0+5]的所有联通区域作为肤色区域(下面所有图中左上角黑白图区)。按比例还原后，按照每个肤色区域的最边缘产生方框，作为人脸的搜索区域，有效减少了搜索区域，提高了处理速度。

② 考虑人脸形变和放大缩小，设置三级变框比[1,1;0.8,1;1.3,1;1,0.8;1,1.3]，分别表示不变、长度变窄、长度变宽、宽度变窄、宽度变宽。用上一帧的人脸框的长宽乘以一种边框比，然后用这个框在所有肤色区域依次扫描获取框选图像。用极端随机森林对每张变框图像进行快速判断。每个人脸框，保留其判断“截图”，共5个。

③ 对比5个“截图”，将极端随机森林判断最好的截图作为“当前最好截图”，并将其2 bit特征图与之前加入到动态目标框架中的所有样本进行NCC比较，判断是否为目标。如果“当前最好截图”不是目标人脸，则认定没有检测到类似人脸区域。若是人脸，再进行如下判断(含P-N学习和实用技巧)：

a) 由于搜索区域并非完全肤色，因此重新判断“当前最好截图”是否依旧符合肤色模型。如不符合，则其作为负样本，加入增量极端随机森林，并跳过b)、c)、d)，开始分析下一帧(肤色约束条件，虚线框)。

b) 比较5个“截图”中NCC判定为正的截图与“当前最好截图”的边框距离。如果超过半个人脸框的距离，则其作为负样本，加入增量极端随机森林(唯一性约束条件，虚线框)。

c) 对依旧没被否定的“截图”，以其随机森林判断结果作为权重，对其截图位置进行加权平均，得到最终的“加权截图”。“加权截图”应该比“当前最好截图”更好。

d) 如果之前“当前最好截图”的随机森林判断结果中不满95%的树同意为人脸，则将“加权截图”转化成标准2 bit特征图，并作为正样本加入增量极端随机森林。并且，确定其为当前唯一跟踪目标位置(实线框)。超过95%同意，则表示“当前最好截图”跟踪稳定，也作为当前唯一跟踪目标位置，但不用加入样本集。

图1中各子图为按照完整算法对单人脸跟踪的结果，从人脸进入到离开的整个过程中，跟踪稳定快速。

图1　完整算法单人脸跟踪效果图集

图2中各子图为减去P-N学习后的跟踪结果。可见，缺少了肤色和唯一性两个约束后，跟踪基本是不正确和不稳定的。

图2　无P-N学习的单人脸跟踪效果图集

图3中各子图为不在动态目标框架进行NCC比较的跟踪结果，不引入NCC比较，跟踪速度略有提高，但跟踪稳定性在总体上不如完整算法。

图3　无NCC比较的单人脸跟踪效果图集

图4中各子图为不使用三级边框时的跟踪结果，不使用三级变框，会造成跟踪人脸目标的局部性。

图4　无三级变框的单人脸跟踪效果图集

图5中各子图为在学习过程中途，增加其他人脸时，本算法对需跟踪人脸的跟踪效果，并且该人脸为侧脸，本算法的跟踪十分稳定。

图5　完整算法在多人脸中对跟踪人脸的跟踪效果图集

表1为使用完整算法、无P-N学习、无NCC比较、无三级变框和全图搜索(不是仅在肤色区域搜索)，这五种情况下，视频中每帧平均处理时间和正确跟踪率的比较。

表1　五种情况下的帧平均处理速度与正确跟踪率比较表

综合考虑跟踪正确率和速度，本文的完整算法是最优的。在实际应用过程中，一般的实时处理速度要求达到每秒25帧。在用户认可的误差范围内，在本文的完整算法中去掉3级变框或者NCC比较，或者使用更好的处理硬件，可以轻松达到实时跟踪要求。无P-N学习和全图搜索的算法则是不能实现跟踪要求的。可见，本文算法有良好的稳定性和鲁棒性。

5结语

本文应用在线的增量式极端随机森林分类器进行基于检测的实时跟踪，在算法中加入了P-N学习提升检测性能，并提出了动态目标框架的概念。算法综合应用分类器和P-N学习的结果，以及距离动态目标模型的相似度，确定跟踪位置，实现任意人脸在线跟踪。并在算法中加入了应用肤色联通区域缩小搜索区域、人脸三级变框、加权平均定位等技巧。实验结果表明，本文算法能够在不确定背景下对任意人脸实现较长时间段内的稳定快速的实时跟踪，能够排除背景和其他人脸的干扰。

本文对目标消失一段时间后再度出现的情况，当目标再次出现后能进行检测定位，但在目标没在的时间段内有一定比率的误测，检测稳定性不够。在后续工作中将针对这一应用需求，进一步完善跟踪处理的算法。

参考文献

[1] Paul Viola,Micheal Jones.Rapid Object Detection using a Boosted Cascade of Simple Features[C]//Kauai Marriott,Hawaii,Proc of CVPR,2001:511-518.

[2] 邓亚峰,苏广大,傅博.一种基于Adaboost的快速动态人脸检测算法[J].计算机工程,2006,32(11):222-224.

[3] 王娟,刘教民,孟军英,等.改进的均值漂移算法在运动目标跟踪中的研究[J].系统仿真学报,2012,24(9):1896-1899.

[4] 姚海涛,朱福喜,陈海强.一种自适应的PSO粒子滤波人脸视频跟踪算法[J].武汉大学学报,2012,37(4):492-495.

[5] Leo Breiman.Random Forests[J].Machine Learning,2001,45(1):5-32.

[6] 刘足华,熊惠霖.基于随机森林的目标检测与定位[J].计算机工程,2012,38(13):5-8.

[7] Pierre Geurts,Damien Ernst,Louis Wehenkel.Extremely Randomized Trees[J].Machine Learning,2006,63(2):3-42.

[8] Zdenek Kalal,Tiri Matas,Krystian Mikolajczyk.P-N Learning:Boosrapping Binary Classifiers y Structural Constraints[C]//VCPR2010 proceedings,2010:49-56.

[9] 陈勇飞,刘新民.基于肤色和类Harr特征的人脸图像的人眼检测[J].计算机工程与应用,2008,44(33):174-176.

[10] 丁友东,杜晓凤,李晓强.基于聚类肤色模型的人脸检测[J].上海大学学报,2007,13(5):511-515.

[11] Rachid Belaroussi,Maurice Milgram.A Comparative Study on Face Detection and Tracking Algorithm[J].Expert System with Applications,2012,39(12):7158-7164.

[12] 王爱平,万国伟,程志全,等.支持在线学习的增量式极端随机森林分类器[J].软件学报,2011,22(9):2059-2074.

REAL-TIME FACE TRACKING ALGORITHM BASED ON ONLINE INCREMENTAL LEARNING

Bao Fang1,2Zhang Yankai1,2,3Wang Shitong3

1(JiangyinPolytechnicCollege,Jiangyin214400,Jiangsu,China)2(InformationIntelligenceFusionResearchEngineeringCenterofJiangsu,Jiangyin214400,Jiangsu,China)3(JiangnanUniversity,Wuxi214000,Jiangsu,China)

AbstractThe paper proposes a real-time face tracking algorithm, which is based on online incremental extremely random forests classifier. The algorithm achieves detection-based real-time tracking using online incremental extremely random forests classifier, and combines dynamic target framework and P-N learning to correct detection errors. Experimental results show, the proposed algorithm can realise fast and stable real-time tracking for any face in a longer period under uncertain background, and can effectively overcome interferences such as background with preferable effect.

KeywordsOnline incremental learningExtremely random forestsP-N learningDynamic target frameworkReal-time face tracking

收稿日期：2014-10-16。江苏省自然科学基金项目(BK2012128)。包芳，教授，主研领域：人工智能模式识别，神经网络，模糊系统，在线学习。张炎凯，硕士生。王士同，教授。

中图分类号TP391.4

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.067