MOT中改进的目标身份感知网络流量技术

梅炳夫，肖春霞

(1.广州市广播电视大学 人文与工程学院，广东 广州 510091；2.武汉大学 计算机学院，湖北 武汉 430072)

0 引 言

多目标跟踪(multiple object tracking，MOT)[1]是视频监视、行为预测、运动视频分析等多种计算机视觉领域的关键问题。近期提出的大部分算法均按照如下两个步骤来解决MOT问题[2]：目标检测和数据关联。其中，在数据关联方面，现有的算法可以分为两大类：①局部关联[3]：这类算法属于时域局部算法，在求解数据关联问题时只考虑部分帧。虽然该类算法的计算量较小，但是它们容易发生ID交换问题，并且对长期/短期遮挡、姿态变化和摄像机移动时的跟踪难度很大。②全局关联[4]：在全局关联算法中，视频帧数量有所上升，甚至为了推断出目标轨迹而一次性处理整个视频。虽然基于数据关联的跟踪算法展示了自身潜力，但仍然存在重大缺陷：算法性能严重依赖于目标检测器的性能。如果目标检测器的虚警率或漏警率较高，数据关联将会失败。为此，本文提出一种改进的多目标跟踪算法，将一种全局数据关联策略集成到结构化学习跟踪器的推理过程中，实现检测和全局数据关联的同步。总体来说，本文的贡献如下：①提出一种综合了结构化学习和全局数据关联的多目标跟踪模型；②提出一种目标身份感知网络流量技术，并通过拉格朗日松驰策略对其进行高效优化；③采用软性空间约束取代了传统目标检测算法中的非最大贪婪抑制策略[4]，进一步提升了检测结果；④验证了本文方法对高难度数据序列的性能要优于其它最新算法。

1 本文算法

假设已知前几帧中进入场景的目标初始边界框(通过标注或利用目标检测算法获得)，本文方法首先通过结构化学习为每个对象训练一个模型，并将目标跟踪问题建模为拉格朗日松驰优化问题，然后提出一种目标身份感知网络流量技术(target identity-aware network flow，TINF)进行结构化学习的推理。在学习期间，通过搜索使目标身份感知网络流量代价函数最小化的一组轨迹，确定最被违反约束和序列在下个时间段的最优轨迹，推断出视频片断中所有目标的最佳位置。具体过程如图1所示，其中，图1(a)表示本文方法对多个视频帧采用的密集候选窗口的并集；图1(b)表示传统方法[5]获得的人体检测结果的并集；图1(c)表示通过TINF发现并可用于模型更新的最被违反约束；图1(d)表示本文方法的跟踪结果。

图1 多个视频帧中某一人体的跟踪过程

2 目标模型

(1)

(2)

(3)

由于Υ中边界框的可能组合呈几何数量级，所以对式(2)中的约束进行穷尽搜索不具有可行性。然而，文献[6]已经证明，通过利用最被违反约束(即可使得分和损失函数之和最大化的一组边界框)便可在多项式时间内获得最优解。因此，本文借鉴文献[6]中寻找最被违反约束时使用的思路来对模型参数w进行学习，获得模型参数w后，接着寻找下一视频片断中所有k个目标的最优轨迹集合。

3 轨迹推断

已知模型参数w和每个视频帧的密集重叠边界框后，本文的目标是为每个目标寻找可使式(1)最大化的一个候选窗口序列(称为轨迹)。该问题属于一种全局数据关联问题，本文首先通过对连续帧中的候选施加某种时域一致性约束来降低其指数级的搜索空间，然后提出一种目标身份感知网络流量技术(target identity-aware network flow，TINF)，如图2所示，并通过拉格朗日松驰策略对TINF进行高效优化，最终实现对轨迹的准确推断。在图2中，大的圆圈表示每个帧中的所有候选位置(密集分布在整个帧内)。通过k条观察边相连的一对节点可表示各个候选位置，一条观察边对应一种身份。网络中有k个源节点和k个汇点，每个源节点或汇点属于一个目标。每个身份用一种单独颜色表示。进入各个节点的流量只能取3条观察边中的某一条，具体视其所隶属的源节点(身份)而定。与其它帧的节点相连的过渡边表示一个目标从某一位置到另一位置的可能移动，且每次移动均关联一个转移成本。在起始/汇节点和图中其它每个节点之间存在一条边，这是为了考虑人体进入或离开场景这一情况。出于简便考虑，我们只给出了部分进入/离开边。

图2 本文方法对3种身份进行推理时使用的网络

网络流量是一个二元指示量，当节点为轨迹一部分时为1，否则为0。利用每个源节点推入单位流量，通过使分配给流量的成本最小化来确定所有目标的轨迹。此外，我们将稍后证明，如果为经过边界框观察边的流量设置上限，便可保证一个候选位置最多只属于一条轨迹。在下面小节中，我们首先将上述问题建模为拉格朗日松驰优化问题，然后给出用于代替目标检测算法非最大贪婪抑制策略的空间约束。

3.1 目标身份感知的网络流量(TINF)

首先构建图形G(V,E)。对帧t中的每个候选窗口，考虑通过k条不同观察边相连的一对节点，这些观察边分别对应于一种身份。对帧t中的每个节点vp以及帧t+1中的节点vq，如果vq在vp邻域内，则这两个节点间存在一条过渡边。节点vp的邻域可定义为

(4)

(5)

(6)

(7)

经过这些边的流量必须满足一定约束，才可以切实保证它可以表示真实世界中的轨迹。针对G(V,E)定义的一组约束如下

(8)

(9)

(10)

式(8)中的约束为供应/需求约束，要求到达节点的流量之和等于离开该节点的流量之和。式(10)中的约束将经过各个节点的流量之和的上限设置为1，来规定不同身份的轨迹不会共享同一节点。依据文献[7]可知，式(7)是一种典型的整数规划问题(integer programming，IP)，该问题为完全NP难题，在实践中往往采取松驰策略，将该问题转化为线性规划问题(linear programming，LP)进行求解。本文中，我们为该问题提出一种拉格朗日松驰解。我们将证明，对硬性约束松驰后，上述问题在每次迭代时将会化简成为最优目标跟踪算法问题，利用动态规划方法，可在多项式时间内获得该问题的全局解。此外，本文还通过采用兼顾了空间约束的迭代优化策略进一步提升了跟踪性能。

3.2 TINF问题的拉格朗日松驰解

本文采用的拉格朗日松驰方法的核心思想是对硬性约束进行放松，并将其放到目标函数中，进而获得一种简单近似。我们首先对式(10)中的约束条件进行松弛，引入非负拉格朗日乘子λij。λ表示拉格朗日乘子向量，向量维度等于G(V,E)中的边数量。式(10)中的约束条件松弛之后，新的目标函数可表示为

(11)

对其进一步简化后，我们有

(12)

条件为

(13)

(14)

(2)根据式(15)更新拉格朗日乘子

(15)

式中：λq表示第q次迭代时的拉格朗日乘子，θq表示以当前解为起点的步长，且[α]+=max(0,α)。

3.3 空间约束

(16)

(17)

图3 轨迹混淆现象VS空间约束

我们发现，对高度重叠的两个节点进行惩罚，有时会导致某一轨迹边界框的精度较低。因此，我们根据式(1)中的得分函数，只对轨迹得分较低的观察节点进行惩罚。综上所述，集成了空间约束的拉格朗日松驰方法如算法1所示。

算法1：TINF的拉格朗日松驰解

输入：T个帧的候选窗口；每个身份的模型参数(wk)

输出：K个身份的跟踪结果

—构建TINF图G(V,E)

—对拉格朗日乘子和空间约束乘子初始化，λ=0,ρ=0,θ=1,q=1

While未收敛时do

—求解每个身份的最小成本流量(fk)

—更新拉格朗日乘子；

—对空间约束乘子进行更新；

—对边缘成本进行更新；

—更新步长

q=q+1

End

4 仿真实验

本文采用目前常用的Parking Lot 1-2序列、TUD Crossing序列、PET序列、以及目标发生大幅关节运动的两个新型数据序列(Running序列和Dancing序列)等[9]作为测试对象，评估了本文算法的性能。初始化时，我们通过手工标注的方法对目标初始化。对进入场景的每个目标，标注4个初始边界框。同时给出目标利用预训练目标检测算法进行自动初始化的运行结果。对手动标注，目标只初始化一次，不会进行再次初始化。实验中利用方向梯度直方图(HOG)和彩色直方图作为目标的特征。HOG特征描述了目标的边缘信息，有助于将目标从背景中检测出来；而彩色直方图属于视频特征，有助于不同目标的鉴别。数据序列被划分为多个数据段，每个数据段包含20个视频帧。每次时间跨度结束时，我们将轨迹得分与预定义阈值做比较，进而确定该轨迹是否有效。如果轨迹有效，则将其用于模型更新。

利用目前典型的CLEAR MOT指标(MOTA-MOTP)[10]和轨迹指标(MT，ML，IDS)[11]作为评价标准。其中，MOTP(multiple object tracking precision)指多目标跟踪的精确度，体现在确定目标位置上的精确度；MOTA(multiple object tracking accuracy)指多目标跟踪的准确度，体现在确定目标的个数，以及有关目标的相关属性方面的准确度；MT指成功跟踪率高于80%的未丢失轨迹的比例；ML指成功跟踪率低于20%的严重丢失轨迹的比例；IDS指跟踪轨迹的匹配ID的变换次数。CLEAR指标(MOTA-MOTP)将整个视频看成一个整体，而TBM指标将每个轨迹的行为分开对待。这些指标描述了跟踪算法的不同方面，因此有必要在比较跟踪算法性能时将这些指标同时考虑，以便全面掌握各个跟踪算法的优缺点。表1给出了本文方法与目前较为典型的目标检测与跟踪算法(LPD[12],LDA[13],DLP[14],H2T[15],GMCP[16],PF[17],CET[18],DCT[19],GOG[20],STRUCK[21]和SPOT[22]等)的定量比较结果。其中，所有其它算法的设置均为算法作者给出的默认设置。从表1可以看到，本文算法的5种性能指标在大多数情况下都要优于其它的算法。仔细分析其原因可知，这是由于本文算法可在检测和数据关联并行化框架下实现多目标跟踪，通过采用结构化学习策略，总是能推断出视频片断中所有目标的最佳位置，因此性能更好。

表1 不同方法的定量比较结果

为了明确展示本文空间约束的影响，我们分别对包含空间约束和不包含空间约束的数据集运行本文算法，实验结果见表2。从表2可以看到，当包含空间约束时，本文算法在几种数据集中的性能都有不同程度地提升。对于目标发生重叠的数据序列，算法增益更为明显。

表2 支持空间约束和不支持空间约束时本文方法的性能

在初始化时，除了人工标注外，我们还可以采用文献[8]中的预训练人体检测算法进行目标的自动初始化。对每个视频段，如果连续视频帧中发生至少4次严重重叠的高置信度检测并且未与任何其它轨迹相关联，则对新轨迹初始化。我们采用人体检测效果显著的Parking Lot 1-2序列和TUD Crossing序列测试了目标自动初始化情况下的本文算法性能，实验结果见表3。从表3可以看到，采用自动初始化策略时，本文方法的性能并没有显著变化，MOTA、MOTP和MT等性能反而略有下降。这主要是因为，与人工标注方法相比，部分序列的部分轨迹起始时间较晚，由于虚警现象增加，MOTA等性能出现下降。

表3 目标进行自动初始化和手动初始化时本文方法的性能

最后，为了比较采用IP或LP时本文拉格朗日松驰方法的复杂性，我们分别部署了本文方法的IP和LP版本。采用文献[3]中的CPLEX作为优化工具箱，选用Parking Lot 2序列作为实验对象(采用其它数据序列可得类似结果)。图4给出了本文方法的3种版本的运行时间比较结果(纵坐标采用对数标度)。从图4中可以看到，本文优化方法的效率远高于IP和LP方法。随着目标数量的增加，3种方法的运行时间都有所上升，但本文拉格朗日松驰方法的运行时间要远低于IP和LP版本的运行时间。此外，拉格朗日松驰方法的运行时间增长趋势趋于稳定，这表明本文方法具有较好的鲁棒性，能够在目标数量动态变化的情况下快速地实现目标跟踪。

图4 不同方法的运行时间比较

5 结束语

针对现有的目标跟踪算法的不足，本文提出了一种综合了结构化学习和全局数据关联的跟踪算法。本文方法的核心是为每个目标学习一个模型的结构化学习过程。将推理过程看成全局数据关联问题，并给出一种目标身份感知网络流量方法进行求解。实验结果表明，本文方法在多种场景下的性能均优于传统的目标跟踪算法。在下一步研究工作中，我们将对复杂背景下的分层关联多目标跟踪问题展开研究，以MOTA为优化目标，拟采用图分割、边着色等技术来实现多目标的快速可靠跟踪。

参考文献：

[1]JIANG Mingxin,WANG Peichang,WANG Hongyu.Height estimation algorithm based on visual multi-object tracking[J].Acta Electronica Sinica,2015,43(3):591-596(in Chinese).[姜明新,王培昌,王洪玉.基于视频多目标跟踪的高度测量算法[J].电子学报,2015,43(3):591-596.]

[2]LU Hong,LI Hongsheng,FEI Shumin,et al.Block-level saliency centroid representation and multi-level association based multi-target tracking[J].Systems Engineering and Electro-nics,2015,37(9):2182-2190(in Chinese).[路红,李宏胜,费树岷,等.融合块显著质心描述和多级关联的多目标跟踪[J].系统工程与电子技术,2015,37(9):2182-2190.]

[3]Shu G,Dehghan A,Oreifej O,et al.Part-based multiple-person tracking with partial occlusion handling[C]//IEEE Conference on Computer Vision and Pattern Recognition.USA:IEEE Press,2016:1815-1821.

[4]Pirsiavash H,Ramanan D,Fowlkes CC.Globally-optimal greedy algorithms for tracking a variable number of objects[C]//IEEE Conference on Computer Vision and Pattern Recognition.USA:IEEE Press,2016:1201-1208.

[6]Sun C,Wang D,Lu H.Person re-identification via distance metric learning with latent variables[J].IEEE Transactions on Image Processing,2016,26(1):23-34.

[7]Türetken E,Benmansour F,Andres B,et al.Reconstructing curvilinear networks using path classifiers and integer programming[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2016,38(12):2515-2530.

[8]Girshick R,Donahue J,Darrell T,et al.Region-based convolutional networks for accurate object detection and segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2016,38(1):142-158.

[9]Kalogeiton V,Ferrari V,Schmid C.Analysing domain shift factors between videos and images for object detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2016,38(11):2327-2334.

[11]Wang X,Türetken E,Fleuret F,et al.Tracking interacting objects using intertwined flows[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2016,38(11):2312-2326.

[12]Tang S,Andriluka M,Milan A,et al.Learning people detectors for tracking in crowded scenes[C]//Proceedings of the IEEE International Conference on Computer Vision.Australia:IEEE Press,2013:1049-1056.

[13]Segal AV,Reid I.Latent data association:Bayesian model selection for multi-target tracking[C]//Proceedings of the IEEE International Conference on Computer Vision.France:IEEE Press,2016:2904-2911.

[14]Amit Kumar KC,De Vleeschouwer C.Discriminative label propagation for multi-object tracking with sporadic appearance features[C]//Proceedings of the IEEE International Confe-rence on Computer Vision.France:IEEE Press,2016:2000-2007.

[15]Wen L,Li W,Yan J,et al.Multiple target tracking based on undirected hierarchical relation hypergraph[C]//Procee-dings of the IEEE Conference on Computer Vision and Pattern Recognition.France:IEEE Press,2016:1282-1289.

[16]Zamir AR,Dehghan A,Shah M.Gmcp-tracker:Global multi-object tracking using generalized minimum clique graphs[C]//IEEE International Conference on Computer Vision.Chile:IEEE Press,2015:343-356.

[17]Breitenstein MD,Reichlin F,Leibe B,et al.Robust trac-king-by-detection using a detector confidence particle filter[C]//Proceedings of the IEEE International Conference on Computer Vision.France:IEEE Press,2016:1515-1522.

[18]Vo BN,Vo BT,Phung D.Labeled random finite sets and the Bayes multi-target tracking filter[J].IEEE Transactions on Signal Processing,2014,62(24):6554-6567.

[19]Andriyenko A,Schindler K,Roth S.Discrete-continuous optimization for multi-target tracking[C]//IEEE Conference on Computer Vision and Pattern Recognition.USA:IEEE Press,2012:1926-1933.

[20]Milan A,Roth S,Schindler K.Continuous energy minimization for multitarget tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2014,36(1):58-72.

[21]Hare S,Saffari A,Torr PHS.Struck:Structured output tracking with kernels[C]//Proceedings of the IEEE International Conference on Computer Vision.France:IEEE Press,2016:263-270.

[22]Zhang L,Laurens VDM.Structure preserving object tracking[C]//IEEE Conference on Computer Vision and Pattern Re-cognition.USA:IEEE Press,2013:1838-1845.