基于在线学习判别性外观模型的多目标跟踪算法

侯建华，边群星，项 俊

(中南民族大学 电子信息工程学院，武汉 430074)

基于在线学习判别性外观模型的多目标跟踪算法

侯建华，边群星，项 俊

(中南民族大学 电子信息工程学院，武汉 430074)

在基于检测的跟踪框架下，设计了一种在线学习的判别性外观模型并应用于多目标跟踪.对检测器输出的相邻帧间检测响应做保守关联，生成短小可靠的轨迹片；利用目标轨迹时空域约束条件，从轨迹片中提取训练样本及特征；采用Adaboost算法在线生成目标外观的判别性模型，计算轨迹片之间的外观相似度；最后采用匈牙利算法，经过多次迭代得到每个目标的完整轨迹.对实验结果做了定量和定性分析，结果表明:所设计的算法提高了跟踪精度，在复杂场景下能够较好地完成多目标跟踪任务.

多目标跟踪；轨迹片；外观模型；Adaboost算法

近十年来，随着目标检测技术快速发展，基于检测的跟踪方法[1-6]已成为当前多目标跟踪领域研究热点；该方法将多目标跟踪问题转化为数据关联问题，利用目标检测响应所包含的外观、运动、位置等信息设计关联模型，以此度量迹片间的连接概率(即相似度)，实现轨迹片最优关联.Huang等人[6]提出的多级关联是一种比较流行的方法，该方法先通过初级关联得到可靠而短小的轨迹片，再通过逐级关联方式，计算轨迹片间的连接概率，应用Hungarian算法[8]得到最优关联解，逐步将短小轨迹片关联为长的目标轨迹.但文献[6]使用基于颜色直方图的外观相似度，其外观模型简单，对位置相近、外观相似的易混淆目标区分性较差，在跟踪过程中容易产生目标轨迹间隙、及身份标识混淆.

针对上述问题，本文提出了一种基于在线学习判别性外观模型的多目标跟踪算法：利用目标轨迹时空域约束条件，从短小轨迹片中采集训练样本，分别提取颜色及纹理特征；采用Adaboost在线学习算法[7]训练分类器，构建目标判别性外观模型，计算轨迹片之间的外观相似度；利用Hungarian算法[8]对轨迹片多次迭代关联，最终得到可靠的目标完整轨迹.实验结果表明在拥挤、遮挡频繁发生的背景复杂中，该算法可以较好地实现准确稳定的目标跟踪.

1 训练样本采集

为提高算法的有效性，采用滑动窗[5]处理模式，在每一个滑动窗内，从短小轨迹片中提取目标正负样本.

1.1 短小轨迹片

设R={ri}代表检测器输出的检测响应集，其中第i个响应为ri=(xi，yi，si，ti),(xi,yi)、si、ti分别表示目标的位置、大小、所在帧序号.定义相邻两帧间两个响应ri与rj的连接概率如下：

(1)

其中Aappr(rj|ri)表示两个检测响应的外观亲密度模型(即连接概率).设第k帧、k+1帧分别有m、n个响应，按照(1)式构造m×n的连接概率矩阵P.

采用文献[6]提出的双阈值关联策略，将相邻帧间的检测响应做保守关联，生成短小可靠的轨迹片(tracklet).双阈值策略如下：如果Pscore(rj|ri)大于门限θ1，并且比矩阵P的第i行、第j列中其他元素都大于门限θ2，则认为检测响应ri与rj是相互关联的，即属于同一目标.公式化描述为：

(2)

1.2 训练样本提取策略

图1 训练样本采集示意图Fig.1 The diagram of obtaining training samples

2 目标外观描述及特征表达

2.1 目标外观描述

为了构建鲁棒的外观模型，采用颜色和纹理特征，提取标准的颜色直方图、HOG特征、协方差矩阵，分别描述目标外观的颜色、形状、纹理信息.

(1)颜色直方图.采用RGB颜色空间，将每个通道设置为8Bins，将三个通道直方图串联起来，组成一个24维颜色直方图向量fRGB.

(2)HOG特征.根据文献[10]，把目标区域划分为4个单元、每单元分8个方向统计，得到32维HOG特征向量fHOG.

(3)纹理特征.采用基于协方差的纹理特征描述[11]，该方法对于图像纹理和目标分类有很好的性能.描述符C与协方差矩阵对应：

(3)

(4)

其中，μ、n分别表示检测响应区域灰度均值、像素个数，zk表示第k个像素的一阶导和二阶导.

综合以上三种特征，单个检测响应ri(即目标)的外观描述子表示为{fRGBi,fHOGi,Ci}；

(5)

2.2 特征表达

首先考察检测响应ri、rj间的相似性向量.对于颜色直方图和HOG特征，采用欧式距离进行，表示为ρ(fRGBi,fRGBj)、ρ(fHOGi,fHOGj).对于纹理特征，采用文献[11]提出的相似性距离：

(6)

其中λk(Ci,Cj)是广义特征值.

检测响应ri、rj的相似性向量表示为：

h(ri,rj)=[ρ(fRGBi,fRGBj),ρ(fHOGi,fHOGj),σ(Ci,Cj)].

(7)

(8)

为方便描述，以下将h(ri,rj)记为h(xi)，其中xi代表样本(即一对检测响应).样本特征向量构成的集合记为F={h(xi)}.

3 在线学习

(9)

基于Adaboost算法的外观模型学习过程见算法1.其中，(xi,yi)为样本集第i个样本，yi∈{+1,-1)}，+1代表来自同一目标检测响应对组成的正样本，-1代表来自不同目标检测响应对组成的负样本；N为特征库F中特征的数量，T为选取的弱分类器个数，实验中T取40.

算法1：外观模型学习

1) Input：正样本集：S+=(xi,yi=1)，负样本集：S-=(xi,yi=-1)；

End for

Setαt=αn*;ht=hn*.

样本权重更新：wi=wi·exp[-αiyihi(xi)] 归一化wi

End for

此外，考虑到目标外观的变化，在每个时间滑动窗内重新获取新的样本，在线更新强分类器H(即外观判别性模型).

综合以上三节内容，图2给出了一个时间滑动窗内的多目标跟踪算法框图.

2)利用时空域约束条件，从TL集中生成训练样本，提取样本和轨迹片特征；

3)训练样本送至Adaboost分类器，在线学习强分类器H，得到判别性外观模型；

4)强分类器H计算两两轨迹片之间的相似性H(Ai,Aj)，利用Hungarian算法实现轨迹片关联；多次重复该步骤，得到该时间滑动窗内的目标轨迹.

通过移动时间滑动窗，重复上述步骤，最终得到视频序列中多目标的完整轨迹T={Tk}.

图2 时间滑动窗内多目标跟踪算法系统框架Fig.2 The system framework of muti-target tracking algorithm in time sliding window

4 实验结果与分析

实验采用TUD数据库(包含TUD-Stadtmitte、TUD-Crossing两个视频序列)和PET2009数据库中的S2L1视频序列，跟踪目标为行人.

采用文献[3,12]定义的标准来评估本文跟踪算法的性能，包含多个评估指标，如表1所示(“↑”表示其值越大、对应跟踪效果越好；“↓”表示其值越小、对应跟踪效果越好).

为了保证算法评价的公平性，检测结果(即跟踪算法的输入)均来自文献[14,15]，其中TUD数据库采用DPM检测器，PET2009数据库采用HOG+SVM检测器.参与比较的算法包括文献[13,14]中的两种方法.

表1 多目标跟踪性能指标Tab.1 Multi-target tracking performance index

表2、表3分别给出了在TUD数据库、PET2009数据库上的实验结果.实验中的3个视频序列均具有背景复杂、目标间频繁发生遮挡的特点.由表2、表3可知，本文算法在多个性能指标上都优于文献[13,14]算法，例如在FAF、Frag、IDS指标上，本文算法的优势明显.

表2 在TUD数据库上的实验结果比较Tab.2 Comparison results on TUD dataset

表3 在PET2009数据库上的实验结果比较Tab.3 Comparison results on PET2009 dataset

图3给出了本文算法在TUD-Stadtmitte上的跟踪效果图.其中第7024帧中目标4、5(图中向上箭头)并肩行走，在第7051帧目标6、7(图中向下箭头)相反方向朝目标4、5走来，被目标4、5严重遮挡，本文算法可处理此遮挡问题、实现对目标的正确跟踪；另外，4号目标从第7024帧到7068帧行走过程中，背景变化较大，本文算法也可以很好地克服.

图3 TUD-Stadtmitte跟踪踪的结果Fig.3 Tracking results on TUD-Stadtmitte

图4是本文算法在TUD-Crossing上的跟踪效果图.该视频序列中由车辆运动导致背景干扰严重.第38帧目标2、5、6、9至左向右行走(图中向上箭头)，其中目标5、9并肩行走，被从右往左迎面行走的目标8(图中向下箭头)依次遮挡，到第85帧遮挡结束；目标身份没有发生混淆(见第85帧5、6、9、8)，始终保持对目标的稳定跟踪.

图4 TUD-Crossing跟踪的结果Fig.4 Tracking results on TUD-Crossing

图5是本文算法在PET2009中S2L1视频序列上的跟踪效果图.摄像机由上向下拍摄，视频场景中目标之间身体形态和外观相似、相互遮挡，且场景中心存在路灯杆对行人的遮挡发生.在第104帧中目标1、7和10(图中向上箭头)之间发生严重遮挡，目标4和5肩并肩行走(图中向上箭头)；到137帧时目标1和7，4和5均被准确跟踪；在528帧到566帧中，目标28和29肩并肩行走、相互发生遮挡(图中向下箭头)，本文算法始终保持对其准确稳定的跟踪.图5表明本文算法对位置相近、外观相似的目标具有较好的鉴别能力.

5 结语

本文设计并实现了一种基于在线学习判别性外观模的多目标跟踪算法，该算法以时间滑动窗为基本关联单位，首先通过初级关联生成短小可靠的轨迹片；利用目标轨迹时空域约束条件从中提取训练样本及特征；采用Adaboost算法在线生成目标外观的判别性模型，计算轨迹片之间的外观相似度；最后采用匈牙利算法、经过多次迭代得到每个目标的完整轨迹.实验结果表明，针对复杂场景中的背景干扰、目标遮挡、位置相近、外观相似的易混淆目标等，该算法均具有较好的处理能力.然而，本文算法未考虑长时间多目标之间的遮挡，后期可以引入多个目标间的遮挡处理机制，进一步提高跟踪性能.

图5 PET2009中S2L1视频序列跟踪的结果Fig.5 Tracking results of S2L1 video sequence in PET2009.

[1] 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, 2(107):203-217.

[2] Yang B, Nevatia R.Online learned discriminative part-based appearance models for multi-human tracking [C]// ECCV.Proceedings of European Conference on Computer Vision.Firenze: ECCV, 2012:1-14.

[3] Yang B，Nevatia R.Multi-target tracking by online learning of non-linear motion patterns and robust appearance models [C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.Washington D C: CVPR, 2012:1918-1925.

[4] Yang B, Huang C, Nevatia R.Learning affinities and dependencies for multi-target tracking using a CRF model[C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.Piscataway: CVPR, 2011: 1233-1240.

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

[6] Huang C, Wu B, Nevatia R.Robust object tracking by hierarchical association of detection responses [C]// ECCV.Proceedings of European Conference on Computer Vision.Marseille: ECCV, 2008: 788-801.

[7] Schapire R E, Singer Y.Improved Boosting Algorithms Using Confidence-rated Predictions [J].Machine Learning, 1999, 37 (3):297-336.

[8] Kuhn H W.The Hungarian method for the assignment problem [J].Naval Research Logistics Quarterly, 1955, 2(1):83-97.

[9] Anton M, Stefan R, Konrad S.Stefan R, Konrad Schindler.Continuous Energy Minimization for Multitarget Tracking [J].IEEE Transactions on Pattern Analysis and Machine Interlligence, 2014, 36(1):58-72.

[10] Dalal N, Triggs B.Histograms of oriented gradients for human detection [C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.San Diego: CVPR, 2005: 886-893.

[11] Tuzel O, Porikli F, Meer P.Region covariance: A fast descriptor for detection and classification [C]//ECCV.Proceedings of European Conference on Computer Vision.Graz: ECCV, 2006: 589-600.

[12] Li Y, Huang C, Nevatia R.Learning to associate: HybridBoosted multi-target tracker for crowded scene [C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.Piscataway: CVPR, 2009:2953-2960.

[13] Andriyenko A, Schindler K , Roth S.Discrete-continuous optimization for multi-target tracking [C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.Washington D C: CVPR, 2012:1926-1933.

[14] Andriyenko A, Schindler K.Multi-target tracking by continuous energy minimization [C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.Piscataway: CVPR, 2011:1265-1272.

[15] Yang B, Nevatia R.An online learned CRF model for multi-target tracking[C]// CVPR.Proceedings of Computer Vision and Pattern Recognition.Washington D C:CVPR, 2012:2034-2041.

Multi-Object Tracking Algorithm Based on Online Learned Discriminative Appearance Model

HouJianhua,BianQunxing,XiangJun

(College of Electronic Information Engineering, South-Central University for Nationalities, Wuhan 430074)

An online learned discriminative appearance models is designed for multi-object tracking (MOT) under the tracking by detection framework.Firstly, by low level association strategy, short yet reliable tracklets are generated among detection responses which are produced by a pre-trained detector.Then, the training samples are collected by using spatial-temporal constraints of target trajectory, and features are extracted for representation of the appearance model.We adopt online Adaboost algorithm to train the discriminative appearance model, by which the appearance similarity between tracklets can be calculated.Finally, the Hungarian algorithm is used via several iterations to obtain the complete trajectory for each target.Experiments are conducted quantitatively and qualitatively.The results show that the proposed method has improved the tracking accuracy, and has satisfactory performance in complex scene.

multi-object tracking;tracklets;appearance model;Adaboost algorithm

2017-01-16

侯建华( 1964-)，男，教授，博士，研究方向: 计算机视觉、模式识别，E-mail: hou8781@126.com

国家自然科学基金资助项目( 61671484);中南民族大学中央高校基本科研业务费专项资金( CZW15013)

TP391.41

A

1672-4321(2017)01-0081-06