基于改进霍夫森林框架的多目标跟踪算法

高庆吉　霍璐　牛国臣

摘要：针对单目视觉对多个相似的目标跟踪因遮挡等因素影响而失效的问题，提出一种基于改进霍夫森林框架的多目标跟踪算法。在将多目标跟踪问题归结为基于目标检测的轨迹关联过程基础上，通过引入在线学习霍夫森林框架将轨迹关联计算转化为最大后验概率（MAP）问题。通过在线采集多目标样本、提取目标外观和运动特征构建霍夫森林，进行森林训练得到轨迹关联概率，从而关联多目标轨迹；而引入低秩逼近Hankel矩阵进行轨迹校验，修复了误匹配的轨迹，改进了在线更新训练样本算法的效能。实验表明，轨迹误匹配率显著改善，能有效提高单目摄像机对多个相似目标有遮挡情况下跟踪的准确性和鲁棒性。

关键词：多目标跟踪；在线学习；霍夫森林；轨迹关联；Hankel矩阵；相似目标

中图分类号：TP391.41

文献标志码：A

0引言

近年来，基于视觉的多目标识别和跟踪成为研究热点，但由于单摄像机视野受限，容易出现目标偶尔移出视野或被遮挡等问题，且视距较远或目标本身极为相似时跟踪容易出错，使得这方面研究尤为重要。目前广泛采用的方法是使用高质量的视觉目标识别方法逐帧检测目标，然后用在线或者离线方式将检测到的目标信息关联成轨迹以实现跟踪，其轨迹关联通常是基于外观和位置相似度进行[1-3]；另有采用多通道核相关滤波器进行样本训练的实时跟踪算法[4-5]，对目标尺寸和外观变化具有很好鲁棒性。然而，这些算法在目标外观相似度高、无先验运动模型、目标快速运动等情况下失效率较高。

文献[6]提出通过卡尔曼滤波或者粒子滤波预测目标位置，关联距离最近的目标来实现多目标跟踪；但是该方法需要有先验的目标运动模型，而实际情况中很多时候目标运动模型是随时变动或未知的，且当多个目标彼此很接近时这类算法很难对不同目标进行正确区分。文献[7]使用在线学习框架进行多目标跟踪，通过在线搜集样本，并引入目标外观特征和运动特征来构建霍夫森林，使用统计的方法区分不同轨迹，并关联成为长轨迹，以此进行跟踪；该方法运算速度快，可在线实现，对目标外观变化有一定鲁棒性，对目标位置预测能力强，但在多相似目标情况下跟踪准确度较差。文献[8]提出一种基于潜在动态模型复杂度进行轨迹关联的方法，该方法无需先验运动模型，可以有效地处理多相似目标的运动跟踪；但计算复杂，且完全不考虑目标外观因素。

针对上述问题，对在线学习算法和关联矩阵进行深入研究，提出了改进霍夫森林（Improved Hough Forest， I-HF）算法。该算法拟引入在线学习霍夫森林框架，对多目标外观和运动模型进行学习和跟踪，利用低秩逼近Hankel矩阵方法对霍夫森林学习中的错误轨迹匹配进行校验，并修复误匹配轨迹，以此来更新学习模型，提高跟踪精度，并提高对多相似目标跟踪的鲁棒性。该算法有效提高了单摄像机对多相似目标跟踪及其遮挡情况的处理能力。

1改进霍夫森林算法框架

霍夫森林[9]是随机森林的一种改进算法，由多棵互相独立的决策树组成，在树的生长过程及训练样本中加入外观和位置偏移信息，并提出了两种不确定性度量方法用于节点分裂。本文在此基础上拟使用低秩Hankel矩阵方法对霍夫森林训练输出的轨迹关联进行校验，并修复补全轨迹，更新霍夫森林以提高算法跟踪准确度。算法框图如图1所示，在线学习霍夫森林包括五部分：样本采集、特征提取、森林学习、结果修复和训练样本更新。在线采集多目标样本用于初始构建霍夫森林，读入下一帧视频进行森林训练得到轨迹关联概率，后进行轨迹校验，如关联有误则修复轨迹并重新采集样本，更新霍夫森林，否则继续下一帧目标提取和森林训练，往复直至视频终止。

1.1霍夫森林样本采集

基于可靠的目标检测信息，将相邻帧的多目标信息进行低层关联[3]，形成短轨迹。样本采集利用时间滑窗及轨迹的时空约束进行。轨迹时空约束基于两个假设[6]：1）同一轨迹线上检测到的目标是同一目标；2）同一时间两个不同轨迹上

的检测属于不同目标。同一短轨迹链上的不同检测目标之间

为正关联，样本采集示意图如图2所示，（a）为连续十帧图像检测结果，进行低层关联后如（b）所示，同一轨迹链上的检测目标1与检测目标3属于正关联；邻近或同一时间T不同轨迹上的关联属于负关联，如检测目标3与检测目标5，检测目标1与检测目标7的关联为负关联，以此类推采集正负样本如图（c）所示，其中+1表示正样本，-1表示负样本。

1.2目标特征提取

采样后需要提取出样本的外观特征和运动特征，以此作为霍夫森林的样本输入。这里使用文献[10]提出的时空关联方法进行运动特征提取，即假设相邻两帧间目标的运动为线性运动，将检测到的目标全局位置与线性模型估计出的全局位置作差，以此来度量运动轨迹间的一致性。在霍夫森林训练阶段，运动特征是由同一轨迹上不同时刻检测目标的位置补偿来描述的；在霍夫森林测试阶段，运动特征由可能的匹配对间的位置补偿来定义。

2轨迹修复

由于当前训练样本是基于前一阶段状态，则可能引入误差，造成错误关联轨迹，而在此基础上继续跟踪，之后的目标跟踪都将出错，就造成了轨迹漂移问题。为解决这一问题，需要对已匹配轨迹进行轨迹校验和修复。本文采用Hankel矩阵方法来识别前一阶段的链接错误，然后基于修正后的轨迹重新采集训练样本。

在无噪声情况下，Hankel矩阵的秩可以很好地反映一个模型的复杂度，但如有噪声存在，则会大大增加矩阵的秩甚至始终满秩，因此一个主要挑战是必须估计噪声的秩和不完备结构矩阵的秩。根据文献[11] 的Hankel矩阵秩最优化可以精确地解决轨迹缝合问题；文献[8]对其进行了改进，使用牛顿迭代法求解Hankel矩阵的低秩逼近，并引入数据失效指示矩阵来修复丢失轨迹数据。基于此，本文使用Hankel低秩逼近方法来校验已完成的轨迹匹配。

3实验及结果分析

3.1实验数据和评价值指标

为验证本文提出方法的可行性，实验采用两个视频进行验证，第一个视频来自国际空中机器人大赛第七代任务，第二个视频是文献[8]中用到的数据集。视频中目标有相似外形、遮挡、高速运动等情况。为评价跟踪性能，目标特征采用文献[12]标记，算法参数设置为10棵最大深度为15的树，每个最优分裂进行200次随机分裂测试。实验平台为Matlab，采用中心位置偏差（Center Position Error， CPE）来度量跟踪算法精确度。计算公式如（11）：

基于以上两个视频，分别对比了本文提出的改进霍夫森林（I-HF）算法和传统霍夫森林（Hough Forest， HF）算法的CPE，结果如图5、6所示。由图5可知，视频一中，在第200帧之前HF算法与I-HF算法得到中心位置偏差基本接近，表明两算法进度相近，而在第300帧之后，HF算法跟踪偏差越来越大，而I-HF算法只存在较小偏差波动，但仍然能正确跟踪目标；由图6可知，视频二中，在第20帧、50帧、80帧左右HF跟踪方法的位置偏差有较大波动，目标轨迹关联错误率较高，而I-HF由于引入了低秩Hankel矩阵方法进行轨迹修复，位置偏差波动小。

基于以上两个视频，分别对比了本文的I-HF算法和文献[10]提出的基于条件随机场（Conditional Random Field， CRF）的跟踪算法，结果如表3所示。观察指标MMR，视频一中I-HF算法比基于CRF的跟踪算法小1.4，视频二中比基于CRF的跟踪算法小6.3，两实验中I-HF的平均轨迹误匹配率仅为基于CRF的跟踪算法的25.5%左右，可见在不同数据集中，I-HF的轨迹匹配性能都明显优于基于CRF的跟踪算法。对比两个视频中同一算法数据发现，由于视频二中目标相似度更高，使得基于CRF的跟踪算法轨迹误匹配率MMR明显增高，而I-HF在两个视频中表现则相对稳定。观察指标FNR，视频一中本文的I-HF算法FNR值上比CRF小0.37，视频二中小0.1，表明I-HF漏跟踪略率优于基于CRF的跟踪算法。两算法FPR值相当。

综上，实验结果表明I-HF算法比HF算法的跟踪精度高，与基于CRF的跟踪算法相比能有效提高多目标跟踪准确度，对多相似目标、遮挡等挑战有良好的表现，具有较高鲁棒性。

4结语

针对单目视觉对多个相似目标的跟踪问题，研究了基于改进霍夫森林框架的算法。以多个相似目标外观和运动信息的估计为基础，首先计算轨迹间关联度。针对霍夫森林框架跟踪中目标轨迹误匹配现象，引入了低秩逼近Hankel矩阵改进校验轨迹关联准确性，可降低检测噪声、平滑轨迹、并更新在线学习训练样本。改进算法跟踪精度和准确程度比传统的基于霍夫森林框架算法有明显提升，对多相似目标遮挡、光照变化等情况有很好的鲁棒性。

参考文献：

[1]BENFOLD B， REID I. Stable multi-target tracking in real-time surveillance video [C]// CVPR 11： Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2011： 3457-3464.

[2]COLLINS R T. Multitarget data association with higher-order motion models [C]// CVPR 12： Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2012： 1744-1751.

[3]HUANG C， WU B， NEVATIA R. Robust object tracking by hierarchical association of detection responses [C]// ECCV 08： Proceedings of the 10th European Conference on Computer Vision， LNCS 5303. Berlin： Springer-Verlag， 2008： 788-801.

[4]胡昭华，邢卫国，何军，等.多通道核相关滤波的实时跟踪方法[J].计算机应用，2015，35（12）：3544-3549. （HU Z H， XING W G， HE J， et al. Real-time object tracking method based on multi-channel kernel correlation filter [J]. Journal of Computer Applications， 2015， 35（12）： 3544-3549.）

[5]余礼杨，范春晓，明悦.改进的核相关滤波器目标跟踪算法[J].计算机应用，2015，35（12）：3550-3554. （YU L Y， FAN C X， MING Y. Improved target tracking algorithm based on kernelized correlation filter [J]. Journal of Computer Applications， 2015， 35（12）： 3550-3554.）

[6]KUO C-H， HUANG C， NEVATIA R. Multi-target tracking by on-line learned discriminative appearance models [C]// CVPR 10： Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2010： 685-692.

[7]XIANG J， SANG N， HOU J. An online learned Hough forest model for multi-target tracking [C]// ICIP 2014： Proceedings of the 2014 IEEE International Conference on Image Processing. Piscataway， NJ： IEEE， 2014： 2398-2402.

[8]

DICLE C， CAMPS O I， SZNAIER M. The way they move： tracking multiple targets with similar appearance [C]// ICCV 13： Proceedings of the 2013 IEEE International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2013： 2304-2311

[9]GALL J， LEMPITSKY V. Class-specific Hough forests for object detection [C]// CVPR 2009： Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2009： 1022-1029.

[10]NEVATIA R. An online learned CRF model for multi-target tracking [C]// CVPR 12： Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2012：2034-2041.

[11]DING T， SZNAIER M， CAMPS O. Fast track matching and event detection [C]// CVPR 08： Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2008： 1-8.

[12]DOLLR P， WOJEK C， SCHIELE B， et al. Pedestrian detection： an evaluation of the state of the art [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（4）： 743-761.