多特征融合匹配的霍夫森林多目标跟踪

梁付新， 刘洪彬， 常发亮

(山东大学 控制科学与工程学院， 山东 济南 250061)

多特征融合匹配的霍夫森林多目标跟踪

梁付新， 刘洪彬， 常发亮

(山东大学 控制科学与工程学院， 山东 济南 250061)

针对目标遮挡、形变等复杂环境中多目标跟踪准确性低的问题，提出了一种多特征融合匹配的霍夫森林多目标跟踪算法．首先，该算法根据目标检测响应进行初步关联，在线选取正负样本，通过融合颜色直方图、方向梯度直方图特征以及光流信息构建目标的特征模型;然后利用霍夫森林学习，形成可靠的长轨迹;最后采用多特征融合的轨迹匹配算法，引入颜色直方图的相似性度量和基于Gabor滤波器的特征点匹配两种方式，形成加权融合的概率矩阵，将长轨迹逐级关联为目标的完整轨迹．实验表明，该算法在多个复杂环境的视频序列中，可以有效解决目标形变、相互遮挡等问题，能实现多目标的鲁棒性跟踪．

多目标;霍夫森林;颜色直方图;相似性度量;特征点匹配

随着视频监控系统的普及，目标检测与跟踪的研究逐渐成为计算机视觉领域的热点研究方向，而多目标跟踪作为其重要分支，主要对目标进行定位并形成运动轨迹，进一步确认视频序列中每个目标的身份．近年来，基于数据关联思想的多目标跟踪算法得到许多学者的关注．文献[1]提出分层逐级关联的思想，通过建立高斯混合模型逐步关联轨迹片段．文献[2]引入模型在线学习机制，利用在线收集的样本，建立特定的目标外观模型，虽提高了跟踪的精度，但判别性模型有待改进．文献[3-4]将目标细化为多个局部区域，通过加权融合得到整体的关联模型，但对目标相互遮挡现象处理效果不佳．文献[5]不仅考虑目标的相似性，同时建立目标差异性模型，以关联概率比为依据，构建关联模型．文献[6]通过在线学习采集样本，使用统计方法区分不同轨迹，将短小轨迹片段分层逐级关联，但对于相似目标容易累积误差，导致跟踪准确度较低．

针对上述问题，笔者提出一种多特征融合匹配的霍夫森林多目标跟踪算法．该算法采用在线学习的霍夫森林框架，通过颜色直方图、方向梯度直方图(Histogram of Oriented Gradient，HOG)以及光流信息构建目标的特征模型，提高算法对目标外观和运动模型的描述能力; 再引入多特征融合的轨迹匹配算法，利用颜色直方图的相似性度量与Gabor特征点匹配两种方式分别对目标轨迹实现再匹配，并将两者加权融合．这样不仅解决了误差累积、跟踪精度低的问题，还提高了处理目标遮挡和形变情况的能力，实现了复杂场景下的多目标跟踪．文中算法的主要流程如图1所示．

图1 多目标跟踪算法总体框架

1 初级关联

初级关联用于关联相邻帧间的检测响应，形成短小可靠的轨迹片段．文中采用双阈值关联算法[6]，设检测器得到的检测响应集合D= {di}，i= {1，2，…，n}，检测响应di= {ti，hi，li}，其中，t代表视频序列的帧数，h代表检测响应的外观特征，l代表检测响应的位置、尺寸信息．定义检测响应之间的关联概率为

p(di|dj)=pcol(di|dj)ploc(di|dj) ，j=i+1 ,

(1)

其中，pcol(di|dj)和ploc(di|dj)分别代表检测响应基于外观和位置的关联概率．外观信息取自颜色直方图，位置信息主要依据目标面积的重叠率．当关联概率p满足

且r≠i，r≠j

(2)

时，表明两个检测响应关联成功，其中，θ1和θ2分别为上阈值和下阈值．双阈值关联将散落的检测响应关联为多个短小的轨迹片段，每个轨迹片段长度有限，文中算法限制在20帧以内，这样不仅保证了数据关联的正确性，还可以在线获取足够的训练样本．

2 基于霍夫森林的多目标跟踪

霍夫森林是一种带有位移信息的分类算法．基于霍夫森林的多目标跟踪方法利用短小可靠的轨迹片段，在线提取样本构建决策树，通过多个决策树的投票完成分类任务，并将同类轨迹片段进行关联，逐步关联为长轨迹．

2.1 特征模型

为加强霍夫森林对目标的判别力，采用一种多种特征融合的判别模型．考虑到目标的相似性以及遮挡情况，采用颜色直方图以及HOG特征[7-8]来判别目标．颜色直方图将目标区域颜色量化，通过计算颜色落在每个区间内的像素数量反映目标特性，对目标的部分遮挡与形变具有较强的适应性;HOG特征主要描述目标局部的表象和形状信息，对图像几何与光学的形变都可以保持较好的不变性．同时采用两种特征描述目标的外观信息，可以更好地区分目标身份，加强对相似目标的判别．而对于光线较暗的运动目标，仅采用外观特征不足以体现目标的特性，可引入目标的运动模型．文中采取中值流[9]光流跟踪法作为目标的运动描述子．在相邻帧间的目标区域生成光流点，将正向与反向误差较低的点作为可靠光流点，通过直方图量化统计得到模型的运动方向与速度．通过建立特征模型，轨迹片段中的检测响应全部的特征可表示为

F={fhist，fhog，fmot} ,

(3)

其中，fhist代表颜色直方图信息，fhog代表HOG特征信息，fmot代表运动信息．

2.2 样本提取

有效样本的提取对霍夫森林的成功构建具有举足轻重的作用．样本提取需遵循以下原则:同一轨迹片段的检测响应对是同一目标;存在时序重叠的轨迹片段间的检测响应对属于不同目标;时间相近但空间距离较大的检测响应对属于不同目标．样本选取的具体流程如图2所示．T表示时间序列，以10帧为例，经过初步关联得到短小可靠的轨迹片段，并对每个轨迹赋予身份信息，如图2(b)所示，轨迹片段的颜色深浅代表不同的目标．根据上述的样本选取原则，得到正负样本集合，如图2(c)所示．

图2 样本提取过程

2.3 霍夫森林构建与轨迹关联

霍夫森林由多棵决策树组成，每棵决策树通过节点分裂以递归方式构建而成．根据样本的特征信息，采用类别不纯度与运动不确定性[6]指标划分节点，使节点中样本的外观与运动信息最大可能地达到一致．

通过正负样本构建霍夫森林，提取叶子节点样本的统计特性来估计轨迹片段的关联概率．轨迹Ti与Tj基于外观的关联概率定义为

Papp(Ti|Tj)=Q(A+)/Q(A) ,

(4)

其中，Q(A)表示样本落入叶子节点A的总数；Q(A+)代表节点A正样本个数，以正样本的比例估计两轨迹基于外观的关联概率．轨迹Ti与Tj基于运动的关联概率采用带有高斯核的Parzen窗估计法，可定义为[10]

(5)

其中，si，mot表示叶子节点A中正样本的运动量．在一棵决策树的轨迹Ti与Tj概率关联模型可定义为

P(Ti|Tj)=Papp(Ti|Tj)Pmot(Ti|Tj) ．

(6)

因此，多棵决策树经过投票得到轨迹Ti与Tj最终的关联概率为

(7)

其中，Y代表霍夫森林的决策树的数量．轨迹Ti与Tj的关联概率X越高，表明两轨迹同属一个目标的概率越大．通过霍夫森林投票决策出最相近的轨迹片段，以时间序列相互关联，初步完成目标的局部跟踪．

3 多特征融合的轨迹匹配

文中针对霍夫森林输出的多条长轨迹，采用一种多特征融合的轨迹匹配算法，既保留了霍夫森林在线训练的优越性，又有效解决了文献[6]在后期级联出现的误差积累、精度低的问题．按照时间不相交的原则，将长轨迹分为多组，每两组的多个轨迹分别提取目标的特征相互匹配．若满足匹配条件，则证明两条轨迹属于同一目标，直至多组轨迹全部匹配完毕，实现目标的全程跟踪．

3.1 颜色直方图的相似性度量

轨迹匹配实质上是求解两轨迹之间的相近程度，而颜色直方图的相似性度量法是常用的一种有效手段，具有旋转、平移和尺度不变性的优点．直方图的相似性度量，一般通过直方图之间的距离度量来实现．巴氏距离测量两个离散概率分布的可分离性效果较好，因此，用来度量颜色直方图的相似性，其定义如下:

(8)

其中，N为颜色直方图中分组区间的数目，Hk为颜色分组区间的频率．

采用颜色直方图的相似性度量描述两轨迹之间的关联程度，首先将匹配轨迹的目标区域转换到色度-饱和度-纯度色彩模型(Hue-Saturation-Value，HSV)空间，多通道提取颜色直方图．通过不同轨迹颜色直方图的度量返回相关系数，作为相似概率．多个目标长轨迹两两进行相似性度量，形成匹配的概率矩阵．

3.2 多尺度Gabor滤波器的特征点匹配

在进行后续的轨迹匹配时，考虑到相似目标以及目标遮挡的情况，引入特征点匹配的方式对多组轨迹进行再匹配．受文献[11]的启发，对多条轨迹进行目标提取，根据各目标区域的特征点匹配情况，确定轨迹是否为同一目标．常用的匹配方法有尺度不变特征转换(Scale Invariant Feature Transform，SIFT)算法、加速稳健特征(Speeded Up Robust Features，SURF)算法等．文中采用多尺度Gabor滤波器的特征点匹配算法．该算法通过改进的环形Gabor滤波器生成目标图像，采用实部响应作为图像的多尺度特征，利用FAST和BRIEF算法对图像进行特征点提取与描述，最后进行暴力匹配并提纯，达到了很好的匹配效果．

图3展示了不同数据库不同算法的匹配效果．如图3(a)，TUD数据库行人色彩较暗，遮挡严重，相邻帧间目标区域的特征点匹配准确性较低，而SIFT算法的匹配点对数不足文中算法的一半，SURF算法匹配效果最差; 如图3(b)，DukeMTMC数据库是校园实地场景拍摄，色彩鲜亮，由于检测器误差以及霍夫森林对轨迹片段的预估，使行人不能完整出现在有效区域，但文中算法的匹配效果仍比SIFT算法和SURF算法的匹配效果好．

图3 不同匹配算法的效果对比

采用多尺度Gabor滤波器的特征点匹配算法，将霍夫森林输出的多条长轨迹两两匹配，形成特征点矩阵，再将矩阵中匹配点数进一步转化为相似概率，矩阵中每一数值表示两轨迹为同一目标的概率．

3.3 匹配概率模型

颜色直方图的相似性度量法和多尺度Gabor滤波器的特征点匹配法是两种完全不同的匹配方式，为了提高轨迹匹配的准确性，引入权重系数，重新定义匹配概率模型

H(Ti|Tj)=ωhhist(Ti|Tj)+(1-ω)hfeature(Ti|Tj)， 0

(9)

其中，hhist(Ti|Tj)和hfeature(Ti|Tj)分别代表两轨迹基于颜色直方图的相似性度量和Gabor特征点匹配的关联概率，ω为权重系数，Tθ为两轨迹的时间阈值．当两轨迹满足该阈值时，通过加权得到最终的概率矩阵，找出行与列的最大值．若此概率满足式(2)，则证明两轨迹属于同一目标，利用牛顿插值法填补轨迹间隙，得到新的长轨迹．若所有轨迹均存在时间交叉或匹配概率均不满足式(2)，则表明轨迹匹配完毕．

4 实验结果

为验证文中算法对多目标跟踪的有效性，选取3个视频序列分别进行对比实验．检测结果均来自DPM检测器，部分参数设置如下: 初级关联的阈值θ1= 0.75，θ2= 0.10，霍夫森林决策树数量Y= 10，每棵决策树最大深度为15; 在轨迹匹配时，多条轨迹匹配的时间阈值Tθ=10，20，30; 匹配概率模型的权重系数ω= 0.7，可根据视频场景适度调节．为了方便与其他算法进行客观对比，采用文献[8]定义的标准评估算法的性能．

实验1 主要验证文中算法对多目标跟踪的可行性．视频序列选自DukeMTMC数据库carema5的某段序列[12]，共218帧，部分目标之间存在遮挡与形变情况．将文中算法(HF-HG)分别与文中仅采用颜色直方图相似性度量匹配的跟踪算法(HF-H)、文献[6]提出的在线学习多目标跟踪算法(HF)进行性能比较．

图4展示了文中算法对DukeMTMC数据库的跟踪结果．从图4中可知，目标5与目标1、目标2均存在部分遮挡的情况，而HF-HG算法仍可以准确地完成多目标跟踪．不同算法跟踪性能的对比结果如表1所示．表1中，Rcll表示成功匹配的检测响应占所有检测响应的百分比，Prcn表示成功匹配的检测响应占真值的百分比，FAF表示平均每帧错误跟踪的目标数，GT表示视频序列跟踪的总目标数，MT表示超过80%成功跟踪的目标数，IDs表示目标被误判的次数，MOTA表示从漏检、误检和误判等多方面评估跟踪正确的百分比，MOTP表示输出轨迹位置的准确性．HF-HG算法的性能指标基本上优于HF和HF-H算法的，有效解决了轨迹关联的累积误差、准确性低的问题．其中，HF算法的MOTP最高，是因为在后期匹配的过程中，HF-HG算法仅使用牛顿插值法填补空隙，降低了目标位置的精确性，虽使MOTP在HF-H算法的基础上有所提升，但仍略低于HF算法的．

图4 文中算法对DukeMTMC数据库跟踪效果图

方法Rcll(↑)/%Prcn(↑)/%FAF(↓)GTMT(↑)IDs(↓)MOTA(↑)/%MOTP(↑)/%HF92.295.20.2465287.374.7HF-H92.495.30.2466287.574.1HF-HG95.096.30.1966091.374.4

注:↑代表该参数值越大，跟踪效果越好; ↓代表该参数值越小，跟踪效果越好．

实验2 主要验证文中算法在目标相似与遮挡情况下对多目标跟踪的有效性．分别采取TUD-Stadtmitte和TUD-Crossing两个视频序列进行对比实验，总帧数分别为179帧和201帧．两个数据库均采用低摄像头拍摄，存在严重的目标遮挡，而且相同目标远近的尺寸差异较大，对后期的轨迹匹配是一个挑战．

图5分别展示了算法在TUD-Stadtmitte和TUD-Crossing数据库上的跟踪效果．从图5可以看出，目标均能实现跟踪，且保持身份信息不变．如表2所示，ML表示低于20%成功跟踪的目标数，Frag表示跟踪目标轨迹断裂的次数，其余参数同表1．文中算法在TUD-Stadtmitte数据库上取得了Prcn为99.5%，MT为7，IDs为零的最好结果，Rcll为81.6%，仅次于文献[4]的结果，FAF为0.03，略低于文献[2]的结果．相比文献[6]的算法，文中算法的Rcll、Prcn、FAF、Frag均有提升，而且效果明显，但在Frag上仍低于文献[2，6]的算法结果，由于目标6、8遮挡严重，且目标8在视频中多次停留，霍夫森林对于轨迹估计存在误差，而在后期的轨迹匹配中，该误差没有进行矫正．因此，在与真实轨迹对比分析中，误差部分判断为轨迹断裂，该点在后期有待提高．

表2 不同算法对TUD-Stadtmitte数据库的跟踪性能对比

注:↑代表该参数值越大，跟踪效果越好;↓代表该参数值越小，跟踪效果越好．

表3给出各算法在TUD-Crossing数据库上的实验结果．与其他算法相比，文中算法在FAF、IDs性能上均为最优，且MT为10，ML为0，与文献[2]的最好结果持平．该数据库目标紧凑，相互遮挡与目标形变都是影响跟踪性能的关键因素．如图5的TUD-Crossing跟踪效果图，由于遮挡严重，再加上DPM检测器的误差，第1帧到40帧，目标2、4区域实际上均包含两个行人．算法在Frag指标上表现较差，低于文献[2，8]的算法结果．其主要原因在于，文中算法仅通过一级轨迹预估，对目标运动轨迹的估计略有不足; 后期进行轨迹匹配仅通过轨迹插值法填补空隙，这样虽加强了目标跟踪的准确性，却增大了Frag; 而文献[8]以时间滑动窗为基本关联单位，根据Adaboost学习对目标进行分层多级关联，有效减少了Frag．

表3 不同算法对TUD-Crossing数据库的跟踪性能对比

注:↑代表该参数值越大，跟踪效果越好;↓代表该参数值越小，跟踪效果越好．

5 结 束 语

为提高复杂环境下多目标跟踪的准确性，文中提出一种多特征融合匹配的霍夫森林多目标跟踪算法．通过融合颜色直方图、HOG特征以及光流信息建立判别式特征模型，在霍夫森林训练的基础上，输出可靠的长轨迹，再根据颜色相似性度量和Gabor特征点匹配的加权融合处理方式进行轨迹再匹配，实现多目标的全程跟踪．实验表明，改进算法的跟踪精度显著提高，有效解决了目标形变和目标遮挡带来的影响．后续工作将考虑如何提高模型的轨迹预估能力，进一步加强算法的跟踪精度．

参考文献：

[1] HUANG C, LI Y, NEVATIA R. Multiple Target Tracking by Learning-based Hierarchical Association of Detection Responses[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(4): 898-910.

[2] KUO C H, NEVATIA R. How Does Person Identity Recognition Help Multi-person Tracking?[C]//Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2011: 1217-1224.

[3] YANG B, NEVATIA R. Online Learned Discriminative Part-based Appearance Models for Multi-human Tracking[C]//Lecture Notes in Computer Science: 7572. Heidelberg: Springer Verlag, 2012: 484-498.

[4] YANG B, NEVATIA R. Multi-target Tracking by Online Learning a CRF Model of Appearance and Motion Patterns[J]. International Journal of Computer Vision, 2014, 107(2): 203-217.

[6] XIANG J, SANG N, HOU J. An Online Learned Hough Forest Model for Multi-target Tracking[C]//Proceedings of the 2015 IEEE International Conference on Image Processing. Piscataway: IEEE, 2015: 2398-2402.

[7] 别秀德, 刘洪彬, 常发亮, 等. 自适应分块的多特征融合多目标跟踪[J]. 西安电子科技大学学报, 2017, 44(2): 163-168.

BIU Xiude, LIU Hongbin, CHANG Faliang, et al. Multi-target Tracking Method Based on Adaptive Fragment and Multi-feature Fusion[J]. Journal of Xidian University, 2017, 44(2): 163-168.

[8] 黄奇, 项俊, 侯建华, 等. 联合特征融合和判别性外观模型的多目标跟踪[J]. 中国图象图形学报, 2015, 20(9): 1188-1198.

HUANG Qi, XIANG Jun, HOU Jianhua, et al. Multi-target Tracking Algorithm Based on Feature Fusion and Discriminative Appearance Model[J]. Journal of Image and Graphics, 2015, 20(9): 1188-1198.

[9] KALAL Z, MIKOLAJCZYK K, MATAS J. Forward-backward Error: Automatic Detection of Tracking Failures[C]//Proceedings of the International Conference on Pattern Recognition. Piscataway: IEEE, 2010: 2756-2759.

[10] XIANG J, SANG N, HOU J, et al. Hough Forest-based Association Framework with Occlusion Handling for Multi-target Tracking[J]. IEEE Signal Processing Letters, 2016, 23(2): 257-261.

[11] 彭志勇, 常发亮, 刘洪彬, 等. 基于HSV模型和特征点匹配的行人重识别算法[J]. 光电子·激光, 2015, 26(8): 1575-1582.

PENG Zhiyong, CHANG Faliang, LIU Hongbin, et al. Person Re-identification Algorithm Based on HSV Model and Key-points Matching[J]. Journal of Optoelectronics·Laser, 2015, 26(8): 1575-1582.

[12] RISTANI E, SOLERA F, ZOU R, et al. Performance Measures and a Data Set for Multi-target, Multi-camera Tracking[C]//Lecture Notes in Computer Science: 9914. Heidelberg: Springer Verlag, 2016: 17-35.

Multi-targettrackingalgorithmbasedonthemulti-featurefusionmatchingandHoughforest

LIANGFuxin，LIUHongbin，CHANGFaliang

(School of Control Science and Engineering, Shandong Univ., Ji’nan 250061, China)

In order to solve the problem of low accuracy due to target occlusion and deformation in multi-target tracking, this paper proposes a multi-target tracking algorithm based on the multi-feature fusion matching and Hough forest. First, we select positive and negative samples online according to primary association among detection responses and construct the feature model of the target with color histogram, histogram of oriented gradient (HOG) and optical flow information. Then, longer trajectory associations are generated based on the online learned Hough forest framework. Finally, a trajectory matching algorithm based on multi-feature fusion is proposed, and we introduce two methods of similarity measure in color histogram and feature points matching based on the Gabor filter to generate the probability matrix with the weighted factor. Therefore, it can further form the complete trajectories of the targets by associating them gradually. Experimental results show that the proposed algorithm can effectively solve the problems of target deformation and mutual occlusion in the video sequences of complex environments, and realize the robust tracking of multiple targets.

multiple targets; Hough forest; color histogram; similarity measure; feature point matching

2017-01-21

时间：2017-06-29

国家自然科学基金资助项目(61673244)

梁付新(1992-)，男，山东大学硕士研究生，E-mail: lfx1173473041@163.com．

http://kns.cnki.net/kcms/detail/61.1076.TN.20170629.1735.046.html

10.3969/j.issn.1001-2400.2018.01.023

TP391

A

1001-2400(2018)01-0129-06

(编辑： 齐淑娟)