基于粒子滤波和在线随机森林分类的目标跟踪

陈 姝，彭小宁

(1.湘潭大学信息工程学院，湖南湘潭411105;2.湘潭大学智能计算与信息处理教育部重点实验室，湖南湘潭411105;3.中南大学信息科学与工程学院，湖南长沙410083;4.怀化学院计算机科学与技术系，湖南怀化418008)

粒子滤波作为目标跟踪中的一种常用方法，具有非线性非高斯系统建模功能.由于粒子滤波能够处理多模式问题，因而它相对其他单模式跟踪算法(如meanshift)鲁棒性更好［1］.粒子滤波采用状态模型及观测模型对动态系统建模，因而不精确的状态模型或观测模型对跟踪结果影响极大.在无规律运动目标跟踪或低帧率的运动目标跟踪中，目标运动的连续性被破坏，从而使得预先建立的运动模型(状态模型)预测效果变差，跟踪出现误差，随着误差积累会造成跟踪丢失.另一方面，由于光照变化、尺度变化、遮挡或背景成簇等原因，采用单一特征难以表达目标外观的多变性.为了提高观测模型的精度，目前提出了多种改进方法.Liang Dawei等［2］提出一种结合边缘与区域的观测模型，王敏等［3］提出一种基于高斯分布来近似估计未知变量的后验分布的粒子滤波算法，近年来提出的目标外观在线更新也取得了较好的效果［4-5］.

基于检测的目标跟踪作为另一类目标跟踪方法，如 Adaboost［6］、SVM［7］，其基本思想是在视频序列的每一帧中应用分类器对目标进行分类，并将每帧分类结果组合成一个运动轨迹作为最终的跟踪结果.根据训练样本产生策略不同分为在线训练及离线训练两种.离线训练采用传统的学习方法，在跟踪前使用采集的样本对分类器进行训练，跟踪时利用训练好的分类器对目标进行分类，分类结果作为跟踪结果.离线方法对于训练样本集中的目标有较好的检测效果，但是检测非样本集中的目标效果较差.在线训练方法采用半监督训练方法，将每帧的跟踪结果作为一个训练样本［8］.相比较离线训练方法，在线训练得到的分类器具有更好的鲁棒性，检测效果更好.

粒子滤波通过后验概率来估算运动目标的分布，充分利用了目标运动的连续性，在有规律运动目标跟踪中取得了较好的效果，但是运动变化剧烈则可能会出现跟踪漂移.目标检测无需知道运动目标的先验状态，完全依据当前帧信息进行分类，因而具有自启动特点，但是其跟踪结果精度较差.文中提出一种结合粒子滤波与在线随机森林分类的目标跟踪算法，充分利用这两类跟踪方法的优点来提高跟踪的精度.

1 粒子滤波原理

在传统的粒子滤波算法中，动态系统由两种模型来表示:状态模型和观测模型.状态用x向量表示，观测用z向量表示.假定上一状态已知，状态模型用来预测下一状态，其定义如下:

式中:g:Rn×Rm→Rn为状态变换函数;vk-1∈Rm为零均值独立同分布的白噪声.观测模型用来度量当前观测下某一状态的相似度，其定义为

式中:h:Rn×Rr→Rp为度量函数;nk∈Rr为另一个零均值独立同分布的白噪声.

根据贝叶斯理论，跟踪就是在假定预测值z1:k=(z1，z2，…，zk)的情况下计算后验概率密度p(xk|z1:k).在粒子滤波跟踪算法中该后验概率以一个带权的粒子集来近似，每个粒子代表目标状态的一个假设对应的权值定义为，并且满足z1:k)由观测模型(2)计算得到.因而k时刻的目标状态由下式得到:

在k+1时刻，新的粒子集根据每个粒子的权值进行重采样，重采样的粒子集再根据状态模型(1)进行系统状态传播，从而可以进行k+1时刻的目标跟踪.这样不停迭代进行粒子传播就可以完成整个系统状态跟踪.

由以上分析可知，粒子滤波跟踪的精度依赖于状态模型及观测模型的可靠性.不精确的状态模型及观测模型都可能造成跟踪精度下降及跟踪失效.

2 随机森林分类器

随机森林分类器最先由Breima提出，A.Saffari等［9］在此基础上提出在线学习算法.随机森林分类器作为集成分类器的一种，具有分类效果好、分类速度快、防过拟合等优点.一个典型的随机森林如图1所示，其基本思想是将多个弱分类器集成一个强分类器，在该森林中，共有N个弱分类器，每个弱分类器由一棵决策树组成，分类结果以森林中各棵决策树的分类结果平均最大值作为随机森林分类器的输出．

图1 随机森林示意图

假设样本数为L，样本中的变量为M，则随机森林的训练过程如下:

1)从样本集中有放回地采样L个训练样本，使用这些样本对每棵决策树训练．

2)在决策树的每个分裂点，从M个变量中随机选择m个变量(m≪M)，将这m个变量中具有最大熵增益的变量作为当前分裂点．m值在森林训练过程中保持不变．

3)对每棵决策树进行无剪枝增长直至叶子节点为纯节点(即该节点中的样本都属于同一类)或无法再增长．

在分类过程中，以一个W类的分类问题为例，一个样本q通过每个决策树Tn有W个输出结果(输出W个置信度，c∈{1，2，…，W}，每个置信度p(n，q)(f(q)=c)表示该样本q属于第c类的概率)，最后随机森林的分类结果基于所有决策树结果的平均，如下式所示:

3 观测模型在线更新的目标跟踪

3.1 运动模型

文中以向量xk=(xk，yk，sk)T表示目标状态，其中(xk，yk)T表示上下两帧中运动目标中心点的平移值，sk为尺度变化因子表示目标缩放大小．状态迁移以自回归模型表示如下:

式中:N(0，Σ)为零向量均值多元高斯函数;Σ为对角矩阵

3.2 随机森林分类器构建

特征的选择对于分类器至关重要，文中采用文献［10］提出的2 bit BP特征作为样本特征，该特征类似harr-like特征，因而可以使用积分图进行特征快速提取．给定一个图像上的目标区域，通过改变特征模板的大小和位置，可在目标区域图像子窗口中穷举出大量的2 bit BP特征，其数目为nf，由这nf个特征构成的向量作为随机森林训练的一个样本．随机森林中的决策树数量为100，随机森林训练算法及分类算法参照第2节，其中m值设为分类算法中的置信度p(n，q)(f(q)=c)计算如下:

式中:N为属于该叶子节点的所有样本数;Nc为该叶子节点属于第c类的样本数，N及Nc由训练算法得到．由于只区分样本属于目标或者非目标，因而W=2，c=1表示样本属于目标，c=0表示样本属于非目标．本算法属于单目标跟踪，因而目标检测判定如下:

式中:Q为采用滑动窗口在整个图像中取得的侯选目标样本的集合;p1(q)为某个样本属于目标的概率，定义如下:

式中:N为森林中决策树的棵数;p(n，q)(f(q)=1)为第n棵决策树中该侯选样本属于目标的概率．

3.3 观测模型

为了计算各个粒子的权值，故需要计算某个粒子下观测值的条件概率，为了充分利用随机森林的统计分类优点，相似度综合考虑了随机森林分类器的分类结果及目标区域直方图相似度，定义如下:

式中:α，β为相似度系数，满足α+β=1，其值根据试验调整设置;q为粒子对应的图像区域生成的测试样本;p1(q)为随机森林分类器计算该样本属于目标的概率，其定义见式(8);p2(q)为测试样本直方图与目标初始直方图的归一化互相关值(NCC)，定义如下:

式中:H1为目标初始直方图列向量(由首帧初始化得到);H2为测试样本q的直方图列向量;H1(i)，H2(i)分别为H1，H2中的第i个分量.

3.4 具体实现

算法的实现如图2所示.

图2 算法整体示意图

式中:(x，y)T为选定目标区域中的像素点坐标;(xt，yt)T为变换后的区域像素点坐标;θ，s为变换参数，θ为变换角度，取值范围为［-3.141 592 6，3.141 592 6］，s为变换尺度，取值范围为［0.5，1.5］.随机选择一组(θ，s)值根据式(11)将目标模板进行变换再计算2 bit BP作为一个训练正样本.负样本集则以选定目标区域之外的图像区域作为数据源，以不同的尺度及位置从这些数据源中提取负样本.

在本算法中还设定两个阈值a1，a2，且a1＞a2，其中a1用来判定当前跟踪结果是否可靠，如果可信度超过该阈值，则将跟踪结果作为一个新的正样本，并从该区域以外的图像区域选择负样本，重新训练

算法的基本思想是在粒子滤波的框架下由随机森林在线学习目标的特征分布，粒子的权值由随机森林的分类概率及直方图相似度来表示.粒子滤波算法请参照文献［1］并结合图2理解，这里不再缀述.采用文献［11］类似方法，随机森林的初始样本集及目标初始直方图由首帧初始化得到，初始时由用户通过交互工具在图像中选定目标区域，根据区域图像信息计算目标初始直方图H1.随机森林的初始正样本集由选定目标区域根据以下变换方程得到:随机森林分类器.a2用来判定粒子滤波跟踪是否发生漂移，如果跟踪结果可信度低于该阈值，则表明跟踪器失效，需要由随机森林进行目标检测，并根据检测结果进行粒子滤波器重新初始化.

4 试验结果

文中采用vc 6.0+opencv实现了本算法，并设计两类试验来验证算法的有效性，第1类试验用来验证跟踪精度，第2类试验用来验证抗漂移能力，试验所用计算机CPU为酷睿i3(2.1 GHz)处理器，内存容量为4 GB.试验中粒子数为100，跟踪目标由首帧手工标注得到，随机森林的初始正样本按照3.4节方法获取，在试验中由于考虑跟踪目标为长方形，因此 θ的取值范围为［-0.2，0.2］，且两样本之间的旋转角度间隔为0.005.初始负样本从目标区域外的其他区域随机获取.初始化结果如图3所示，其中红色矩形为选中的跟踪目标，绿色区域为正样本叠加结果，蓝色矩形为选取的负样本.

图3 目标初始化及随机森林正负样本选取图

粒子相似度根据式(9)计算，由于目标形变及光照变化影响，初始时计算的直方图随着时间推移越来越不能对目标进行精确表示.因此，跟踪过程中系数α值随时间逐渐增加，β逐渐减小，初始时α =0.2，β =0.8.在本文算法中，随机森林作为粒子相似度的判定依据，而非分类情况，故将随机森林中叶子节点的定义按照文献［12］作以下修正:当决策树的层数达到6层或者到达当前节点的正样本(或负样本)比例大于80%，则称此节点为叶子节点.阈值a1，a2定义为a1=0.85，a2=0.45.

第1类试验采用文献［13］项目中的视频数据库，该视频记录一个男子跳绳运动过程，视频背景复杂，人体运动剧烈且无规则.比较算法中的随机森林分类器由离线样本集训练，传统粒子滤波算法中的粒子相似度通过计算归一化直方图互相关值得到.图4为跟踪到第84帧时随机森林中的第1棵子树，其中空心圆为分裂点，圆内数字为该分裂点所对应特征在特征集中的序号，圆边括号中的数字为在该节点进行分裂时选取的特征.箭头下方括号中的数字［n:m］，其中n为某一2 bit BP特征，m为该特征值所对应的样本数，例如第2行［1，92］表示第12号特征其值为1时的样本有92个.方框为叶子节点，方框中的数字分别为正负样本的数目.

本文算法计算第84帧的粒子相似度过程如图5所示，只显示4个粒子相似度计算结果，计算所用参数为 α =0.65，β=0.35.

图4 随机森林中第1棵子树示意图

图5 粒子相似度计算过程

由图5可知归一化互相关值不能准确反映粒子真实相似性(例如白色矩形框粒子互相关值)，而本文算法综合随机森林的检测结果能提高粒子相似准确度.

图6为目标跟踪中心点轨迹图，由图可知，跟踪结果反映人体跳绳运动周期往复变化规律.图7为部分帧跟踪结果，图8为前50帧本文算法与传统粒子滤波算法及随机森林检测算法的定量比较结果，跟踪误差定义为跟踪目标中心点与目标真实值中心点的图像欧氏距离，目标中心点真实值由手动标注得到.

图6 人脸中心点跟踪轨迹图

图7 跳绳运动视频序列跟踪结果比较

图8 不同跟踪方法错误曲线图

由图8可知本文算法跟踪结果在大多数帧中都优于传统粒子滤波算法及随机森林检测结果，原因在于随机森林没有考虑上一帧目标位置的先验知识，由于光照、视点变化及目标运动使得目标外观发生变化，而传统粒子滤波算法中的粒子相似度计算单一，没有考虑这些变化量.

根据图8观察可知，在第30帧时由于目标运动幅度过大，根据运动模型生成的粒子不能较好地覆盖运动目标区域，因而粒子滤波跟踪结果误差较大.本文算法检测到跟踪结果不可靠时，由随机森林检测运动目标作为跟踪结果，从而提高了跟踪精度.同时，根据检测结果进行粒子重新初始化，可有效抵抗跟踪漂移.图9分别为第30帧时粒子集分布结果、第30帧随机森林在线检测结果以及重新初始化后的粒子集在第31帧的分布结果.

图9 随机森林检测及粒子重新初始化

表1为跟踪准确的视频帧数统计结果，跟踪准确的判定采用文献［14］所述标准.

表1 不同跟踪方法正确跟踪结果统计

第 2 类试 验 采用 MILTrack［15］(tracking with online multiple instance learning)项目中的视频数据库.在Tiger1视频中，一个玩具虎由人舞动快速移动，并不时被周围植物部分遮挡，从而造成被跟踪目标成像模糊.Tiger1跟踪结果如图10所示，其中在第110帧时由于严重遮挡使得粒子滤波跟踪出现漂移，算法应用随机森林检测运动目标并进行了粒子重新初始化.尽管运动目标存在局部遮挡及光照变化，但是在大多数帧中跟踪结果仍然比较精确.

图10 Tiger1视频序列跟踪结果

5 结论

针对粒子滤波跟踪方法中的漂移问题，文中提出了一种结合在线随机森林分类的粒子滤波跟踪算法，结论如下:

1)该算法充分利用模板直方图的先验知识及随机森林的在线更新能力，通过改进粒子滤波的观测模型来提高目标跟踪精度.

2)在跟踪过程中，目标运动的快速性及无规律性使得传统粒子滤波出现跟踪漂移，而本文算法通过对跟踪结果可靠性检测来判断当前跟踪结果，当出现错误跟踪时，利用随机森林检测跟踪目标，并对粒子滤波器进行重新初始化.

3)两类试验结果表明本文算法比传统粒子滤波及随机森林的跟踪精度有一定程度提高，并且能够抵抗传统粒子滤波的跟踪漂移.

References)

［1］Yao Anbang，Lin Xinggang，Wang Guijin，et al.A compact association of particle filtering and kernel based object tracking［J］.Pattern Recognition，2012，45(7):2584-2597.

［2］Liang Dawei，Huang Qingming，Yao Hongxun，et al.Novel observation model for probabilistic object tracking［C］∥Proceedings of2010IEEE Conference on Computer Vision and Pattern Recognition.San Francisco:IEEE Computer Society，2010:1387-1394.

［3］王 敏，张 冰.基于一种改进粒子滤波算法的目标跟踪研究［J］.江苏科技大学学报:自然科学版，2008，22(1):63-67.Wang Min，Zhang Bing.Research on target tracking based on improved particle filter algorithm［J］.Journal of Jiangsu University of Science and Technology:Natural Science Edition，2008，22(1):63-67.(in Chinese)［4］Liu Baiyang，Huang Junzhou，Yang Lin，et al.Robust tracking using local sparse appearance model andK-selection［C］∥Proceedings of2011IEEE Conference on Computer Vision and Pattern Recognition.Providence:IEEE Computer Society，2011:1313-1320.

［5］Ross D A，Lim J，Lin R S，et al.Incremental learning for robust visual tracking［J］.International Journal of Computer Vision，2008，77:125-141.

［6］Yeh Y J，Hsu C T.Online selection of tracking features using AdaBoost［J］.IEEE Transactions on Circuits and Systems for Video Technology，2009，19(3):442-446.

［7］Li Xi，Anthony D，Wang Hanzi，et al.Graph modebased contextual kernels for robust SVM tracking［C］∥Proceedings of the IEEE International Conference on Computer Vision.Barcelona:IEEE Computer Society，2011:1156-1163.

［8］Zdenek K，Jiri M，Krystian M.P-N learning:bootstrapping binary classifiers by structural constraints［C］∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.San Francisco:IEEE Computer Society，2010:49-56.

［9］Saffari A，Leistner C，Santner J，et al.Online random forests［C］∥Proceedings of2009IEEE12th International Conference on Computer Vision Workshops.Kyoto:IEEE Computer Society，2009:1393-1400.

［10］Zdenek K，Jiri M，Krystian M.Online learning of robust object detectors during unstable tracking［C］∥Proceedings of2009IEEE12th International Conference on Computer Vision Workshops.Kyoto:IEEE Computer Society，2009:1417-1424.

［11］王爱平，万国伟，程志全，等.支持在线学习的增量式极端随机森林分类器［J］.软件学报，2011，22(9):2059-2074.Wang Aiping，Wan Guowei，Cheng Zhiquan，et al.Incremental learning extremely random forest classifier for online learning［J］.Journal of Software，2011，22(9):2059-2074.(in Chinese)

［12］王丽婷，丁晓青，方 驰.基于随机森林的人脸关键点精确定位方法［J］.清华大学学报:自然科学版，2009，49(4):543-546.Wang Liting，Ding Xiaoqing，Fang Chi.Accurate localization of facial feature points based on random forest classifier［J］.Journal of Tsinghua University:Science and Technology，2009，49(4):543-546.(in Chinese)

［13］Li Yuan，Ai Haizhou，Yamashita T，et al.Tracking in low frame rate video:a cascade particle filter with discriminative observers of different lifespans［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30(10):1728-1740.

［14］Everingham M，Gool L V，Williams C K I，et al.The pascal visual object classes(voc)challenge［J］.International Journal of Computer Vision，2010，88:303-338.

［15］Babenko B.Tracking with online multiple instance learning(MILTrack)project［DB/OL］.［2009］.http:∥vision.ucsd.edu/～ bbabenko/project-miltrack.shtml.