基于检测的多目标跟踪算法综述

2021-04-27李志华

物联网技术 2021年4期

李志华，于杨

（河北工程大学信息与电气工程学院，河北邯郸 075000）

0 引言

目标跟踪是计算机视觉领域研究的热点之一，可在给定第一帧图像目标处于初始状态的情况下，估计后续图像序列每一帧的目标位置[1]。目标跟踪算法可分为单目标跟踪（Single Object Tracking, SOT）与多目标跟踪（Multiple Object Tracking or Multiple Target Tracking, MOT or MTT）。对单目标跟踪而言，其主要任务为跟踪视频画面中的单个目标，研究中心通常为设计高效的运动与外观模型，解决诸如尺度变化、光照变化等问题。对于多目标跟踪，其主要任务为同时跟踪视频画面中的多个目标，为目标分配ID并维持其ID的长久有效性，得到目标的运动轨迹[2]。需解决的问题包括频繁遮挡、轨迹初始化和终止、相似的外观、多目标间的相互影响等[3]。

多目标跟踪的主要应用场景多为交通流监控[4]、自动驾驶[5]和虚拟现实[6]等，在以上场景中，多目标跟踪算法的主要任务是对众多目标同时进行跟踪，并为每个目标分配并维持一个相应的ID，记录轨迹，这是仅用目标检测算法或单目标跟踪算法无法做到的。多目标跟踪算法根据初始化方法的不同可分为Detection-Based Tracking（DBT）和Detection-Free Tracking（DFT），前者为基于检测的跟踪，即优先目标检测，再将检测结果与已存在的轨迹进行匹配链接。后者则需要在第一帧手动标记定量目标，在后续帧定位物体。DFT的跟踪模式仅能跟踪已标记目标，而DBT的跟踪模式可以自动发现新的目标，移除已消失的目标，更适应如今多目标跟踪算法的应用场景。传统的基于检测的多目标跟踪算法，如2008年提出的Nevatia算法[7]，该算法将MOT问题转化为3层逐步细化的数据关联问题：最底层通过样本和样本的关联实现简单的目标检测；中间层使用最大化后验概率方法实现轨迹初步拼接；最高层使用EM算法优化中间层检测结果得到多目标跟踪轨迹。该算法基于底层目标检测，利用层次递进的思想解决多目标跟踪问题，但检测器较为简单，且场景预设为单出入口，局限性较大。同时算法内部需设定的参数过多，如EM算法方差、最大时间差等，实现同等效果较为困难。近年来，随着深度学习的快速进步，目标检测算法的精度不断提升[8-9]，基于检测的多目标跟踪算法得到了长足的发展[10]。2016年BEWLEY等人提出的SORT算法[11]凭借其出色的跟踪性能获得了极大关注，标志着利用深度学习目标检测器的多目标跟踪方法逐渐崛起。

基于检测的多目标跟踪可以分为在线跟踪（Online）与离线跟踪（Offline）。在线多目标跟踪是一种逐帧渐进的跟踪方式，与人眼实时跟踪目标过程类似，首先要对每个运动目标进行识别确认（目标检测），然后对其下一步的行动进行预测（轨迹预测），最终根据目标的运动方向（运动模型）、外观形体（外观模型）等特征与之前的轨迹进行关联（数据关联匹配）。可以看出，在线多目标跟踪仅仅是将这一帧的信息与先前的信息或轨迹关联，且必须具备实时性，即运行速度可以达到视频正常的播放速度（通常算法速度达到20 FPS即可算作实时算法）。离线多目标跟踪的输入是一段完整的视频，并已获得了目标检测结果。与在线多目标跟踪算法逐帧渐进方式不同的是，离线多目标跟踪可获取全局信息后再进行匹配关联。可理解为将目标检测算法的结果看作一个集合，将轨迹看作集合的一种划分，多目标跟踪的任务可化为子集优化的任务。前者的优点在于可实时输出，但其易受目标遮挡和检测器漏检、误检的影响。后者的输出从理论上获得了全局最优的结果，但实时性较差。

如今受限于多目标跟踪算法应用场景，在线多目标跟踪算法更受学者们的关注。本文介绍的算法性能参数均来自MOT16官方数据，如MOTA、IDF1、IDs、FPS。MOT16是2016年提出的多目标跟踪MOT Challenge系列的衡量多目标检测跟踪方法标准的数据集，由于目标检测算法的精度对跟踪效果影响较大，所以该数据集共有2个性能排行，分别为使用公开检测器在MOT16上的性能指标，与使用私人检测器在MOT16上的性能指标。

1 在线多目标跟踪算法

1.1 SORT算法

2016年提出的SORT（Simple Online and Realtime Tracking, SORT）算法是一种在线实时多目标跟踪算法，虽然其框架较为简单，但在算法提出的当年，其新颖的想法与出色的性能便引起了业界的广泛关注。SORT算法主要由目标检测模块与数据关联模块组成。目标检测模块的主要任务是对输入的视频进行特定类别的目标检测（如运动目标或人、车辆等）。数据关联模块主要采用卡尔曼滤波算法与匈牙利算法，主要任务是判定不同帧中所检测目标是否为同一对象。

SORT算法使用Faster R-CNN[15]进行目标检测，并为每一个检测结果的状态进行建模。该检测算法选用VOC数据集上的预训练模型，只关注置信度大于0.5的行人目标，实验结果表明，检测质量的提升可使跟踪性能提高18.9%。在数据关联方面，SORT算法将检测目标的状态模型输入卡尔曼滤波器[12]中进行预测与更新，滤波器依据当前目标检测算法所得的检测位置与上一帧滤波器输出的目标预测位置计算当前最佳位置，实现“去噪”[13]。SORT算法将检测框和跟踪框的IOU作为匈牙利算法cost矩阵（损失矩阵）的输入[14]，得到检测框和跟踪框的匹配结果后，判断检测结果与轨迹是否匹配成功。该算法复杂度低，框架结构简单，运行速度快，虽然数据关联方面模型较为简单，易受遮挡，但为后续许多优秀算法的提出做了铺垫。SORT算法框架如图1所示。

图1 SORT算法框架

1.2 DeepSORT算法

2017年提出的DeepSORT[16]算法是针对SORT算法的一次改进。在数据关联方面引入外观模型的参考，从而提高关联的鲁棒性。SORT算法对于遮挡、姿态变换未做处理，导致IDs较高。DeepSORT算法融合了运动模型与外观模型，并为2种模型分配了不同权重，综合计算目标与轨迹的匹配程度[17]。运动模型：以检测框间的马氏距离为参考，即通过计算检测位置和平均跟踪位置间的标准差对状态测量的不确定性进行考虑。外观模型：利用预先设计的CNN网络提取1个描述目标边界框（bbox）内物体外观的128维向量，利用不同bbox间特征向量的最小余弦值作为参考，并将这一向量融入损失矩阵的构造，使匈牙利算法的匹配结果更可靠。经验证，相对SORT算法而言，DeepSORT算法在MOT16数据集私人检测器的性能表现上，MOTA值提升幅度不大，但IDswitch频率降低了45%，速度接近实时要求（20 FPS）。

1.3 MOTDT算法

MOTDT[17]算法整体框架和DeepSORT相似。SORT算法及DeepSORT算法进行轨迹匹配时，从检测和跟踪的输出中收集候选项作为集合，输入到匹配机制，导致候选集合中存在冗余候选项。针对该问题，MOTDT算法通过融合对象分类器和跟踪器置信度制定了统一的轨迹评分机制，将产生的检测框和预测框的标准置信度作为非最大抑制（NMS）输入，从而获得无冗余候选项。引入轨迹评分机制，对NMS的每一个输入进行评分，利用卡尔曼滤波预测弥补漏检。

数据关联方面，MOTDT算法为改善拥挤场景中的类别遮挡问题，融合外观表示和空间信息，将现有轨道与所选候选项分层关联。外观表示与DeepSORT算法相似，通过深度神经网络训练行人重识别（Re-ID）数据集解决当目标重新出现时的检测问题，即使用神经网络学习得到对象外观信息，提取相应特征向量，再利用获得的特征间距离确定相似性。行人重识别（Re-ID）指在局部位置失去跟踪目标，也可在目标再次出现时将目标与之前的轨迹关联。以往行人重识别的难点在于长距离跟踪情况下，相似度高的行人仍有可能不是同一目标。经验证，在IDF1和IDs方面，Re-ID特征优于传统的手工特征。同样，通过从对应的数据集中学习外观表示，例如车辆重新识别，可以轻松将提出的跟踪框架转移到其他类别[18]。分层关联主要体现在优先将候选集和候选项基于空间信息和外观信息与现有轨迹进行关联匹配，余下的候选项和未关联的轨迹再基于IOU进行匹配。该算法在MOTA2016数据集上的结果见表1所列（各算法数据均使用公开检测器）。

表1 MOTDT算法与其他算法在数据集上运行结果对比

实验结果表明，跟踪器速度可以达到实时要求，并且在大多数指标上都优于同年现有的在线跟踪器，尤其对IDF1而言，同比其他算法有了显著提升。采用深度学习的Re-ID特征作为外观模型参考，增强了识别能力，且该算法的计算复杂度低，运行速度可达20.6 FPS。

1.4 JDE算法

当前的主流多目标跟踪系统通常是基于检测的跟踪方式。系统中存在检测模型与嵌入模型（Embedding model），如DeepSORT算法中提出的Re-ID，2个模型分开且独立，简称为SDE。2019年提出的JED算法认为这种运行方式降低了效率，于是提出了一种新的MOT系统，将检测模型和嵌入模型整合为一个模型，即JDE模型[19]。

JDE算法基于YOLOv3[20]和MOTDT开发，网络部分占比较大，需在特征图中提取一个嵌入向量。为提高时间效率，JDE算法在单个网络中同时进行检测分支与身份嵌入分支的运算。检测分支与标准的RPN相似，RPN即候选区域网络，直接作用在特征图上，用来生成候选区域。主要改进点为根据目标数量、比例和纵横比设计检测框，使其能够适应目标，同时精确前景、背景分配使用的双重阈值。嵌入模型方面，因相同ID的样本接近，而不同ID的样本相距很远，所以采用类似交叉熵的triplet loss[21]进行样本分配。为平衡损失权重，JDE算法采用自动学习损失权重方案[22]，通过学习一组辅助参数自动对非均匀损失加权。JDE算法在MOT16数据集私人检测器的性能表现较SDE方法提升不大，但速度方面提升明显，尤其在拥挤或复杂场景，JDE算法的速度优势突出。以典型SDE的DeepSORT算法为例，JDE算法在MOTA指标上较DeepSORT算法高3%，运行速度达18.8 FPS，接近实时速度，图像分辨率达1 088×608。

1.5 Fair算法

One-shot MOT的核心思想是在单个网络中同时实现目标检测和身份嵌入，通过共享大部分计算来减少推理时间，典型的算法如JDE算法与MOTS[23]算法。但One-shot MOT的跟踪精度通常低于SDE MOT的跟踪精度，2个模块结合后，精度降低的同时会导致IDs上升。

针对这一问题，2020年Y. Zhang等人提出了一种基于One-shot MOT的Fair[24]算法。该算法提出One-shot MOT系统是基于检测框的，但这种方式通常存在一个问题，即同一目标可能同时存在多个检测框，会影响跟踪结果。在Fair算法中，作者采用anchor-free的方式降低检测框对Re-ID的影响，通过在高分辨率的feature map上估计对象中心，使Re-ID特征能够更好地与对象中心对齐。在Re-ID特征维度方面，改用多尺度融合方式提高跟踪鲁棒性。该算法提出目标检测分支与身份嵌入分支并行运算来完成目标检测和Re-ID任务的集成。实验数据表明，与同作为One-shot MOT系统的JDE算法相比，Fair算法的MOTA值与速度有显著提升，同时IDs较高的问题也得以抑制，完全可满足实时性要求。

1.6 在线多目标跟踪算法性能对比

在线多目标跟踪算法输入为视频帧，算法运行方式为逐帧进行，仅利用上一帧与当前帧的信息进行检测、预测、关联，实现跟踪任务。本文主要介绍的在线算法有目前工业界应用较为广泛的SORT、DeepSORT算法，基于这2种算法框架改进MOTDT、JDE算法，以及2020年提出的Fair算法。表2为以上在线多目标跟踪算法使用私人检测器在MOT16数据集上的实验结果。

表2 在线多目标跟踪算法性能对比

2 离线多目标跟踪算法

2.1 POI算法

POI算法[25]是一种离线多目标跟踪算法，结合了目标检测和基于深度学习的外观特征。基本思路：在每一帧的输入上，用检测算法检测行人的位置，然后利用行人检测框的外观特征进行前后帧行人框的匹配，从而实现对行人的跟踪。

该算法使用Faster R-CNN作为目标检测算法，选用随机采样动态尺度的多尺度训练策略，此外采用skip pooling和multi-region策略联合不同尺度和水平层次的特征。经验证，采用该策略可有效降低FN+FP的值（即准确率的分母）。嵌入模型训练方面，同时使用softmax loss和triplet loss。2种损失函数的设定是为了更加清晰地区分目标间的表观特征。相似度的判断以特征间的余弦距离为参考，相关为1，无关为0。POI算法中的离线跟踪器是基于H2T[26]算法改进的，虽然该算法提出时间较早，但其在MOT16数据集上的性能表现依旧良好，MOTA值可达66.1。

2.2 IOU算法

IOU算法[27]是一种离线多目标追踪算法。该算法指出，随着目标检测算法精度的不断提高，当检测精度与视频帧率较高时，可以结合简单的目标检测算法与IOU，再通过设定阈值来判断前景与背景即可完成目标跟踪任务。即在高帧率（25 FPS）、高精度的目标检测算法情况下，结合检测与时间步长间的空间重叠完成跟踪。该算法优缺点明显，但由于未引入任何帧间信息、运动模型、外观模型，漏检和错检问题难以解决，若出现频繁遮挡、目标形变的情况，会导致ID频繁切换，且极其依赖目标检测算法的性能。但该算法的优点是框架简单、速度快，若设定在某些环境简单的情况下，效果明显。该算法在MOT16数据集上速度约3 000 FPS，且该策略对于结合检测和分割有一定启发，如果能找到高速的追踪方法，将检测和追踪进行结合效果更佳。

2.3 LMP算法

LMP[28]算法的提出虽距今已有一段时间，但在MOT16数据集上表现仍出色。该算法主要针对遮挡影响及行人重识别展开。LMP算法提出一种新结构，结合深度网络中提取的整体表示特征和从最先进的姿态估计模型中抽取的身体姿态进行判断，从而提高准确率。主要创新点在于：数据关联方面，LMP算法是在最小代价多分割问题（MP）基础上改进的，将数据的关联匹配看作一种基于图的分解、聚类问题。通过设置一个基于边的目标函数来选择能最大化相同目标和不同目标概率的分量对，从而完成行人重识别的任务并改善遮挡影响，有效降低IDs。经实验验证，LMP算法在2016数据集私人检测器上性能名列前茅，MOTA可达71.0。

2.4 基于多线索的多目标跟踪算法

在实际应用系统中，短期线索跟踪的特点是基于附近帧进行预测、更新，只包含当前帧的信息，易受遮挡和相似目标影响，但表现效果较好。与之相对的，长期线索则包含轨迹的运动外观等特征，能应对一定遮挡和相似目标的影响，但表现力不及短期线索。2019年提出的基于多线索的多目标跟踪算法[29]融合了长期线索与短期线索的优点，并在一个网络结构中突出两者的优点以应对MOT场景中的复杂情况。

该系统创新点在于分别设立SOT网络与Re-ID网络来承载短期线索与长期线索。设定切换感知分类器（SAC）以提升匹配效率，该分类器可利用目标的短期和长期线索、检测结果和切换器来预测检测结果是否与目标匹配。SOT网络的搭建基于单目标跟踪器SiamRPN，使用私有行人数据调整网络，根据匹配情况计算跟踪质量，该网络具备部分发现和识别功能，以弥补其他组件产生的纰漏。该算法在MOT16数据集上无论采用公开检测器还是私人检测器，结果都比较理想，采用私人检测器时MOTA值可达71.2。

2.5 离线多目标跟踪算法性能对比

不同于在线多目标跟踪算法的逐帧关联策略，离线多目标跟踪算法输入通常为整段视频，在全局搜索最佳匹配，所以相较于在线方式，离线多目标跟踪在跟踪准确度方面具有优势。通常，在MOT数据集的性能排名中，名列前茅的多为离线方法。表3为本文所阐述离线算法在MOT16数据集上的实验结果，检测器均为私人检测器。

表3 离线多目标跟踪算法性能对比

3 总结与展望

基于检测的多目标跟踪是通过目标检测算法获取一个目标集合，然后将集合内的目标进行数据关联，从而判定不同帧中多个目标是否为同一对象来进行跟踪。影响多目标跟踪算法优劣的最大因素是数据关联。无论在线模式还是离线模式，提高数据关联的效率都可有效提升跟踪准确度。运动模型、外观模型等可看作是辅助解决关联问题的元件。

基于当前目标检测算法在多目标跟踪算法中的应用，未来向以下几个方向倾斜：

（1）性能更加优越的目标检测算法：当前大多数优秀的多目标跟踪算法都是基于检测的多目标追踪，如本文提出的IOU算法，若未来出现了性能更优越的检测算法，则多目标跟踪任务完全可以转化为目标检测任务与分割任务。

（2）更有效的特征：MOT系统中所需提取的特征通常可以分为两类，一类是传统方法，通过手工设计法提取特征，比较有代表性的是KLT[30]算法；另一类是深度学习出现后，基于CNN进行特征提取，本文叙述的Re-ID模块均基于深度学习的特征提取。对MOT系统而言，良好的特征会凸显不同目标匹配时的差异，简化数据关联，降低设定参数的难度，还可以进一步融合多种特征，提高跟踪质量。

（3）场景适应性：利用深度强化学习来学习跟踪场景的适应性，例如高峰时期的地铁车站、商场等，大多数目标体积较小或被大面积遮挡，因此难以跟踪。场景理解的分析结果可以提供上下文信息和场景结构，如果将其更好地融入MOT算法中，将有助于解决跟踪问题。

（4）用深度学习指导关联问题：基于检测的多目标跟踪算法与Re-ID模块利用深度学习方法提取有效特征，而最核心的数据关联模块目前需要进行更多的研究才可以判断深度学习在数据关联方面是否有效。

现如今，利用深度学习解决数据关联的方法通常是端到端方式[31]，即数据关联的流程并不进行人为的子问题划分，而是完全交给深度学习模型学习从原始数据到期望输出的映射。在MOT系统中表现为向端到端网络中输入2张图片，查看输出是否匹配，特征提取等步骤完全由网络完成。

总而言之，性能出色的目标检测算法会优化目标样本集，有效的特征会简化关联问题与调参问题，跟踪场景的适应性算法可以适应多种环境变化，而单独的数据关联阶段是否也可以采用深度学习的方法则需要进一步探讨。目前，针对在线基于检测的多目标跟踪算法，进步的难点在于如何在保证运算速度的同时提升精度。无论是利用多任务学习的Oneshot MOT，还是检测与嵌入模块分开运行的SDE MOT，都具备明显的优点与不足，而作为2种MOT系统的交叉任务，Re-ID模块必定是未来发展的重中之重。