Multi-Object Tracking Survey

Multi-Object Tracking Survey

来自论文:"Deep Learning in Video Multi-Object Tracking: A Survey", 作者是来自意大利和西班牙等院校的Gioele Ciaparrone等人。论文引用[1]:Ciaparrone, Gioele et al. “Deep learning in video multi-object tracking: A survey.” Neurocomputing 381 (2019): 61-88.

总结

1. 多目标跟踪的问题是指在一个序列中跟踪不同目标的轨迹，通常是一个视频。近些年随着深度学习的兴起，算法从深度模型的表征能力中收益。本文提供了提供了用深度学习模型来解决MOT问题的全面的综述。

2. MOT问题不同于目标检测(输出一系列的bounding box)。MOT算法还将target ID和每个box(detection)进行关联，为了区分类内的目标。单目标跟踪中，目标的外观是已知的先验，在MOT中，检测这一步对于识别targets是必须的，追踪多个目标的主要困难在于多样的阻塞和目标之间的交互，有时它们还有相似的背景。因此，将单目标跟踪应用于多目标跟踪会导致目标漂移和多个ID切换，这样的模型通常在区分相似目标和类内目标的时候有困难。专门针对多目标跟踪的一系列的算法被调整出来，用于解决这个问题，还有数据benchmarks和比赛，来方便不同方法的对比。 最近，很多的算法用深度学习来做，深度学习模型的长处在于学习丰富表征和提取特征。卷积神经网络长处在于空间模式提取，循环神经网络想LSTM用于处理时序数据。

3. MOT算法介绍：MOT采用的标准方式是tracking-by-detection：从视频帧中提取一系列的detections，然后用来指导追踪过程，通常将它们进行关联，为了给包含相同目标的bounding boxes分配相同的ID。因此，很多MOT算法将这个任务视为分配问题。现代的检测器保证了很好的检测质量，大多数的MOT方法聚焦于提升association；事实上，很多MOT数据集提供了标准的detections的集合，为了能在关联算法的质量上比较它们的性能，因为检测器的性能对追踪结果有很大的影响。 MOT算法也可以分为batch和online方法。当决定特征帧中的目标的时候，Batch tracking算法允许用future information。它们利用全局信息，导致更好的追踪质量。在线tracking算法，相反，只能用现在和过去的信息来对当前帧做预测。在一些场景下有这个要求例如自动驾驶。相比于batch方法，在线方法效果会差一些，因为不能利用future information来修正过去的errors。事实上，在线方法在实际环境中跑得很慢，特别是当利用深度学习算法的时候。

   尽管文献中有各种各样的方法，大多数的MOT算法有下列的几个步骤：

   • Detection Stage：目标检测算法分析每一帧，来识别目标类别using bboxes，在MOT语境中称为Detections。
   • Feature extraction/motion prediction：一个或多个特征提取算法分析detections/tracklets来提取外观，运动或者interaction features。optionally, 一个运动预测器预测每个tracked target的下一个位置。
   • Affinity Stage：features和motion predictions用来计算detections/tracklets pairs之间的相似度/距离分数。
   • Association Stage：相似度/距离用来关联属于同一目标的detections/tracklets，通过为识别相同目标的检测结果分配相同的ID。 这些阶段可以按照上述顺序执行。有很多算法将这些步骤合并了，或者用不同的techniques多次执行。更多的是，一些方法没有直接将检测进行关联，而是用它们来refine 轨迹预测，来管理新的tracks的初始化和终结，尽管如此，这种情况下，这些步骤仍然能够被识别。

4. Metrics：为了提供common 的实验设定，算法能够被公正地测试和比较，建立了一组metrics，用的很广泛。

   • Classical metrics：强调了MOT算法犯得一些错误，为了展示这些问题，计算了下列的值：

     • Mostly Tracked trajectories(MT)：在至少80%的帧中，正确地追踪到的ground truth的轨迹。
     • Fragments：是一个轨迹假设，覆盖了至少groundtruth 轨迹的80%。一个true trajectory至少有多个fragment。
     • Mostly Lost：groundtruth 轨迹少于20%的帧被追踪到。
     • False Positives：被追踪到的轨迹，没有ground truth对应。
     • ID swithces：目标被正确追踪的次数，但是目标关联的ID改变了。

   • CLEAR MOT metrics：CLEAR MOT metrics是在2006/2007年举办的workshop上的CLEAR开发的。这个Metrics是MOTA和MOTP。他们作为其它构成它们的简单的metrics的summary。首先会解释简单的metrics，然后构建复杂的。因为关注的是2D tracking，用的最多的metric，来决定object和prediction是否相关的是bboxes的IoU。groundtruth和hypotheses之间的mapping如下：**如果ground truth object \(o_j\)和 hypothesis \(h_j\) 在 \(t-1\) 帧 匹配，在\(t\) 帧， IoU(\(o_i,h_j\)) >= 0.5, 则 \(o_i,h_j\) 在这帧是匹配的，即使有另外一个hypothesis \(h_k\)， IoU(\(o_i,h_j\)) < IoU(\(o_i,h_k\))。匹配执行完之后，剩余的objects会和剩余的hypotheses进行匹配，仍然用0.5的IoU阈值。不能和一个hypothesis进行关联的ground truth bboxes记为false negatives(FN)，不能和一个真实的bboes进行关联的hypothesess记为false positives(FP)。每次，一个ground truth object tracking中断之后，之后又继续的，记为一个fragmentation。在追踪期间，每次一个追踪到的groundtruth object ID不正确地改变，记为 ID switch。MOTA和MOTP分别定义为：

     • FP：整个视频中的false positives的数量
     • FN：整个视频中的false negatives的数量
     • Fragm：fragmentation的数量
     • IDSW：ID switch的数量 MOTA的定义如下： \[MOTA=1-\frac{(FN+FP+IDSW)}{GT}\quad\in(-\infty,1]\] GT是ground truth boxes的数量。这个分数可以是负数，因为算法犯的错误可能大于groundtruth boxes的数量，通常，相反用MOTA，更common的是用MOTA，就是用百分比表示， MOTP计算如下：

     \(c_t\) 表示帧t中的matches的数量，\(d_{t,i}\) 是hypothesis i和分配的ground truth object之间的 bbox overlap，注意到这个metric考虑了很少的tracking，而是关注于detections的质量。

     ID scores：MOTA的主要问题考虑了tracker做的不正确的decision的次数，例如ID switch，但是在一些场合，人们更感兴趣的是奖励那些能够长时间跟踪目标的跟踪器。因此，定义了一些新的metrics，来补充信息。不是通过逐帧的匹配ground truth和detections。这个mapping是全局进行的。分配给一个给定ground truth trajectory的轨迹预测 是 最大化 正确分为ground truth的frames的数量。为了解决这个问题，构建了一个bipartite graph，这个问题的最小的成本解决思路是将其视为problem solution。对于bipartite graph，一系列的vertices定义如下：第一组的vertices，\(V_T\)，对于每个true trajectory，有一个所谓的regular node，对于每个计算的轨迹有一个false positive node。第二个set，\(V_c\)，对于每个计算的轨迹有一个regular node，对于每个true one，有一个false negative。边缘的cost are set，为了计算false negative的数量和false negative frames，防止edge were chosen。在关联之后，有四个不同的pairs，如果来自 \(V_T\) 的regular node和 \(V_C\)的一个regular node相匹配(一个true trajectory和一个计算的trajectory相匹配)，则计数一个 \(true positive ID\)，来自 \(V_T\)的每个false positive 和来自 \(V_C\)的一个regular node相匹配，计数为一个false positive ID。每个来自 \(V_T\)的regular node和来自 \(V_C\)的false negative计数为一个 false negative ID，最后，每个false positive和false negative 匹配，计数为一个true negative ID。之后，三个分数都计算了，IDTP是真正被选为true positive ID matches的边的权重之和(可以被视为整个视频中争取分配的detections的百分比)。IDFN是selected false negative ID edges的权重之和，IDFP是selected false positive ID edges的权重之和。有了这三个basic measures，其它的三个计算如下：

     • Identification precision: \(IDP=\frac{IDTP}{IDTP+IDFP}\)

     • Identification recall: \(IDR=\frac{IDTP}{IDTP+IDFN}\)

     • Identification F1: \(IDF1=2\frac{IDP*IDR}{IDP+IDR}\)

   5. Benchmark datasets：

      • MOTChallenge：MOTChallenge是用的最多的MOTbenchmark。对于每个数据集，提供了groundtruth for training split, detections for both training and tests splits，MOT数据集提供detections的原因是detection的质量对于tracker的性能有很大的影响，但是算法的检测部分通常独立于tracking part，通常用的是现有的模型；提供public detections，每个模型都能用，方便追踪算法的比较，由于检测质量从性能计算中被剔除，trackers从一个共同的基础上开始。在test dataset上的算法的评估是通过把结果提交到test server。
      • MOT15：是第一个MOTChallenge dataset，包含了22个序列的videos，11 for training和11 for testing。包含11283个不同分辨率的frames，有1221个不同的identities和101345个boxes。提供的detections是通过ACF detector得到的。
      • MOT16/17：2016年提出的新版本的数据集，共有14个videos，7 for training, 7 for testing。用DPMv5得到的public detections，共计包括11235frames，有1342个identies和292733个boxes。MOT17数据集和MOT16的视频一样，但是有更精确的ground truth，对于每个视频，有三组detections：一个是来自Faster RCNN，一个来自DPM，一个来自Scale-Dependent Pooling detector(SDP)。
      • MOT19：用在了CVPR2019 Tracking上的新版本的数据集。包含8个视频, 4 for training 4 for testing。在最拥挤的视频中，平均每帧有245个行人，数据集有13410frames，有6869个tracks和共计2259143个boxes，比之前的数据集都多。
      • KITTI：MOTChallegne主要关注于行人追踪，KITTI数据集追踪行人和车辆。这个数据集是通过开车绕着城市收集的，包含21个training videos和29个test ones，共计19000frames。包含了用DPM和RegionLets 检测器得到的detections，还有立体和laser 信息。

   6. DL in detection step：尽管许多研究使用数据集中由不同检测器生成的检测结果作为其算法的输入，例如DPM for MOT16。也有很多算法继承了定制的detection step，通过增强检测质量，提高了整体的追踪性能。很多的算法利用FasterRCNN及其变体作为custom detections。尽管很多算法用深度学习模型来提取rectangular bboxes，很少的工作用deep networks在检测阶段有不同的用途。

      • SORT算法是第一个MOT pipelines用卷积神经网络用于行人检测。它们展示了通过FasterRCNN计算的detections比ACF检测器计算的detections，能够提高MOTA，它们用了一个简单的方法，用卡尔曼滤波器预测目标运动，然后用匈牙利算法关联detections，用IoU distances来计算cost matrix，高质量的detections降低了复杂追踪算法需要。MOTA分数被false positives和false negatives严重影响。

      • 有人用SSD检测器用来查找行为和车辆，用了基于CNN的相关滤波来使得SSD能够产生更多的精确的bboxes。CCF利用PCA压缩的CNN特征，来预测后面帧的目标的位置；预测的位置然后用来crop RoI around it。作为SSD的输入。这样，网络能够用更深的layers计算小的detections。提取更多有价值的语义信息，产生更多的精确的bboxes和less false negatives。算法然后将这些detections和在fulll image上用NMS step得到的ones进行结合，然后用匈牙利算法执行tracks和detections之间的association， with a matrix that took into account geometric(IoU) and appearance(Average Peak-to-Correlation Energy-APCE) cues。APCE也用作object re-identification，来去掉occlusions。作者展示了用多尺度增强训练一个detector能够在tracking中有更好的结果。

      • 有时候MOT中的CNN用来除了计算object bboxes之外的用途。例如：CNN用来计算减小false positives

   7. DL in feature extraction and motion prediction：特征提取阶段是使用深度学习模型的首选，因为它们有很强的表征能力，使得它们擅长提取有意义的高阶features。典型的方式是用CNN 模型来提取特征。

      • 自编码器：有人提出了两层的自编码器网络，用来refine visual features。在extraction 之后，用SVM计算affinity，关联任务formulated as a minimum spanning tree problem。feature refinement极大地提升了模型性能。
      • CNN作为visual feature extractors：用的最广的特征提取是基于卷积网络的修改。有人将visual features引入了经典算法，visual features结合用卡尔曼滤波提取的spatial ones，然后计算affinity matrix； DeepSORT引入了CNN提取的visual information。CNN提供了128 features的vector 作为output，这些vectors之间的余弦距离加入到affinity scorse。实验表明这个修改克服了SORT算法的缺点(ID switch比较大)； 有人用了DeepSORT 特征提取器，用一个区别相关滤波来测量特征之间的关系，之后，matching score和时空关系score相结合，最后的score用作一个likelihood in a Gaussian Mixture Probability Hypothesis Density filter。
      • Siamese networks：另一个idea是用结合不同images信息的loss functions来训练CNNs，为了学习能够区分不同目标的features。这些网络称之为孪生网络。有人提出了孪生网络，用一个contrastive loss进行训练，网络将两个images、IoU score和area ratio作为输入，产生的contrastive loss作为输出。在网络训练之后，计算对比损失的loss被去掉，最后一层作为feature vector for the input image。相似度分数通过结合feature vectors之间的欧氏距离、bbox之间的IoU score和area ratio被计算出来。通过用一个贪心算法解决关联的步骤。有人也提出了一个Siamese network，将两个image patches，计算它们之间的相似度分数。测试时的得分是通过比较网络提取的两张图像的视觉特征，并结合时间约束信息来计算的。
      • SymTriplet loss：在训练期间，用了3个共享权重的CNNs，损失函数结合了属于同一个Object的两张图片提取的信息，和不同目标的一张图片的信息。当positive pair的feature vectors之间的distance小的时候，Symtriplet loss减小，当negative pairs features接近的时候，增加。优化这个函数导致相同物体的图像的相似的特征，不同的物体不同的vectors，它们之间有很大的distance。首先，执行帧间的关联，这种情况下affinity score是detections的feature vectors的欧氏距离和时序运动信息的结合。之后，tracklets进行连接，用一个Hierarchical Agglomerative Clustering 算法over 外观特征。

      也有人提出了Siamese CNN，接受连个image作为输入，输出两张图片都属于同一个人的概率，用这个训练网络，因此它能学到更多的表征特征来区分subjects。这之后，输出层去掉了，最后一个隐藏层提取的features和上下文信息一起作为Gradient Boosting model的输入，为了得到detections之间的affinity score。然后，用线性规划解决关联步骤。

      • CNNs用于motion prediction：相关滤波：有人研究相关滤波的employment，输出是一个追踪的物体的response map。这个map是下一帧物体的新的位置的估计。这个affinity可以进一步和光流affinity结合，用Lucas-Kanade 算法计算。motion affinity用卡尔曼滤波计算，scale affinity 通过一个设计bboxes的高和宽的ratio表示。两个detections之间的affinity是先前分数的线性组合。也有一个用SVM分类器去掉false detections的步骤，missing detections handling用作之前步骤计算的response map。如果一个目标mistakely lost，然后重新识别，这个步骤能够修正mistake，重新连接broken tracklet。也有人将相关滤波用来预测序列帧中的目标的位置，滤波器将CNN提取的外观特征作为输入，之前用PCA降过维，产生的下一帧中的目标的预测的位置作为输出，预测的位置之后用来计算相似度分数，结合预测和检测之间的IoU，和response map之间的APCE 分数。之后构建cost matrix，计算every pair of detections between frames的said score，分配的问题用匈牙利算法解决。

      还有人用了强化学习的方法，来训练一些agents，帮助特征提取，算法完全基于Motion features。不需要任何视觉信息，用卡尔曼滤波器学习motion model。它的行为有一个agent管理，用一个agentfor each tracked object。这个agent学习决定卡尔曼滤波器应该采取哪个行为between a set of actions，包括忽略预测，忽略new measure。这个作者声称他们的算法可以在即使非视觉场景下解决它们的算法，和性能深受视觉特征影响的经典算法相比。

5. DL in affinity computation：很多工作通过用一些distance measure over features extracted by a CNN，计算tracklets和detections之间的affinity，也有一些算法用深度学习模型来直接输出affinity score，不需要显示地计算features之间的distance metric。

   • CNNs for affinity computation：有人用4个不同的CNNs来计算图中点之间的affinity score，关联任务视为最小化成本的对切口问：它可以被视为graph clustering 问题，每个输出的cluster表示单个tracked object。与边关联的代价考虑了两个检测之间的相似性。这相似性是person re-id置信度，深度一致匹配和时空关联匹配的结合。为了计算person-reid affinity，用了多种的架构。Siamese CNNs也是一种用于affinity 计算的常用的方式，

6. DL in Association/Tracking step：有一些工作用深度学习模型，来提高通常由经典算法例如匈牙利算法执行的关联过程。有人用一个双向GRU RNN来决定在哪split tracklets，算法在三个方面进行：一个tracklet generation step，包含一个NMS步骤，来去掉冗余的检测，用外观和运动affinity的匈牙利算法来形成高置信度的tracklets；然后，是一个tracklet cleaving步骤；因为occlusions，一个tracklet可能包含一个ID switch error。这个步骤旨在分离ID switch发生的点，为了得到包含相同identity的两个分离的tracklets，最后用了一个tracklet 重连步骤，用一个customized关联算法，用来Siamese 双向GRU提取的特征。GRU为每一帧输出一组feature vectors。计算这些feature vectors之间的距离。

   也有一些工作用深度强化学习agents在跟踪阶段做决定。用多个deep RL agents来manage 多个tracked targents，决定tracks什么时候开始和结束。这个agent是用3层的MLP建模的。 有人用了3个不同的CNN。第一个称之为PafNet，用来从tracked objects中区分背景。第二个称之为PartNet，用来区分不同的目标。第三个CNN，有一个卷积和FC层构成，用来决定是否更新tracking model。整个的算法流程是这样的：对于之前帧的中每个追踪到的目标，在当前帧中用PafNet和PartNet计算score maps。然后，用核相关滤波器tracker，预测目标的新的位置。更多的是，在特定帧之后，执行一个检测验证的步骤；检测器输出的结果通过解决一个graph multicut 问题，分配给tracked targets。没有和一定数量的帧的detection关联的targets会被终结。然后，第三个CNN用来检查关联的detection box是否比预测的更好，如果是，KCF模型参数会更新，反应目标特性的变化。这样的CNN用PafNet提取的maps，用强化学习进行训练。没有关联的detections用SVM分类器和匈牙利算法用来恢复target occlusion；最后，剩余的没有关联的detections用来初始化新的targets。

7. 分析：用public detections在降低FNs方面有很有限的提升，最有效的方式是构建和训练一个custom 检测器，降低了FNs的数量是private detectors有更好的tracking效果的主要原因，能够识别之前uncovered targets。SORT算法对丢失的detections很敏感，当相关的检测丢失的时候，不能检测一个target。 为了避免这个问题，很多新的算法用了新的策略来解决这个问题。事实上，执行插值的方法能够在occlusion期间恢复missing boxes，对于检测没有被single detection cover的目标来说这是不够的。深度学习算法在检测和特征提取上扮演了重要的角色，用深度网络来学习affinity 函数没有那么普遍，对于MOT来说还没有被证实是一个重要的算法。很多算法依赖于在深度和非深度特征上的手工distance metrics的结合。然而，这些工作展示了用affinity 网络能够产生top-performing的算法，从用Siamese CNNs到循环神经网络。特别地，有人提出了自适应的Siamese 网络，能够产生可靠的相似度测量，帮助在occlusions之后的行人重识别，使得算法达到了最高的MOTA。body part information的集成对于StackNetPose CNN也是重要的。作为一个attention 机制，允许网络关注输入图像的相关部分，能够产生更精确的similarity measures。这个算法用private detections在MOT16上达到了最高的性能。很少的工作用深度学习模型来指导association 过程，这个是未来研究的一个方向。

8. 基于SOT的MOT方法必须小心，不要保持由不可避免的大量的false positive detections造成的虚假的轨迹。当前的方法仍然倾向于用detection overlap(detection cover了多少最近的帧)来理解一个轨迹在long run中是tru or false positive，但是更好的解决方法应该是用来避免detections中多余的reliance。很多方法将关联视为一个图优化问题，batch方法从中收益，因为它们能够执行全局优化；例如，最小成本lifted multicut problem在MOT16上取得了很好的表现，然而heterogeneous association graph fusion和correlation clustering用在了top MOT17方法中。 最终，bboxes的精度影响了最终的算法性能。MOT15撒谎给你的top ranked tracker用了一个deep RL agent在之前的算法上进行了一个bbox 回归的步骤。开发一个有效的bbox回归器用在MOT上也是一个有趣的研究方向。

9. 总结：MOT pipeline的几个主要的步骤如下：Detection, feature extraction, affinity computation, association。在每个步骤上用深度学习都被探索过了，然而大多数的方法聚焦于前两个，一些用深度学习来学习affinity functions也展示了，但是只有少数的方法直接用深度学习来指导关联过程。在MOT挑战上的结果表明，尽管有很多不同的方法，现有方法也有一些共同点：

   • 检测的质量很重要：false negative的数量主导着MOTA的分数，用高质量的detections仍然是减小false negatives的最有效的方式。因此，好好在检测阶段用上深度学习能够提高追踪算法的性能。
   • CNNs在特征提取上很重要：外观特征对于一个好的tracker是重要的，CNNs在提取这个上很有效。更多的是，strong trackers倾向于和motion features联合起来用，可以通过LSTMs，卡尔曼滤波器或者贝叶斯滤波器进行计算。
   • SOT trackers和全局图优化：SOT trackers适配到MOT任务，用深度学习，可以得到很好的online trackers；batch 方法受益于深度学习模型在全局图优化算法上。 一些promising 的研究方向：
   • 研究更多的策略来减小检测误差：尽管现在的检测器实现了很好的性能，但是仍然倾向于产生一些false negatives和false positives in complex scenarios，一些算法提供了解决方式通过将它们和从其它sources提取到的信息结合起来，来降低exclusive reliance on detections。
   • 用DL来追踪不同的targets：大多数的基于DL的MOT算法聚焦于行人追踪，一些不同的targets提出了不同的挑战
   • 研究当前算法的稳健性：在不同的场景下对当前的算法提出了挑战
   • 将DL用于指导关联：将DL用于指导association 算法，直接执行tracking仍然是研究得比较少的问题；这个方向需要更多的研究，来理解DL算法是否有用。
   • 将SOT tracker和private detections结合：一个可能的方式减小lost tracks的数量，降低false negatives，将SOT tracker和private detections结合特别是batch setting，有可能恢复之前丢失的detections
   • 研究bbox回归：用bbox 回归展示了一个promising的步骤，但是还没有被仔细的explored，有很大的提升空间，用过去和将来的信息来指导回归
   • 研究post-tracking处理：在batch contexts中，有可能在tracker的输出上用一些correction 算法来提高它的性能。

Multiple Object Tracking in Recent Times: A Literature Review^[2]

作者是来自Islamic University of Technology的Mk Bashar等人，论文引用[2]:Bashar, Mk et al. “Multiple Object Tracking in Recent Times: A Literature Review.” ArXiv abs/2209.04796 (2022): n. pag.

Time

• 2022.Sep

总结：

1. MOT是重要的视觉任务，像是拥挤场景中的occlusion，相似背景，小目标检测，ID switching等，为了解决这些挑战，研究人员用注意力机制，图卷积神经网络的tracklets的interrelation，用siamese 网络的在不同帧的目标相似性，它们也尝试基于CNN网络简单的IOU匹配，用LSTM的motion prediction，为了把这些分散的技术弄到一个框架下，研究了过去3年超过100篇论文，尝试提取研究人员用来解决MOT问题的techniques。

2. 为了完成追踪的任务，首先需要定位帧中的目标，然后，每个目标分配一个ID，连续帧的每个相同目标会有轨迹，这里的目标可以是行人，车辆等。如果我们想追踪帧里的多个目标，就称之为MOT，可以追踪同类的所有目标或者上述类别的所有目标。如果我们直追踪单个目标，则称之为SOT，MOT比SOT更具有挑战性。因此研究人员提出了很多基于深度学习的架构来解决MOT相关的问题。之前也有一些MOT的review的paper，但是它们只包含基于深度学习的数据关联的方法，只分析problem statement，对paper的分类没有做好，实际中的应用也是缺失的。 这篇MOT的组织如下：

   • MOT的主要的挑战
   • 列出MOT的经常用的路径
   • 写下MOT benchmark数据集的总结
   • MOT metrics的总结
   • 一些应用

3. MOT有很多挑战：

   • Occlusion：当我们想要看的东西被部分或者全部遮挡时，occlusion发生了，大多数的MOT方法只基于cameras，没有sensor的数据，这是为什么对于一个tracker来说，当目标模糊了之后，tracker很难追踪它的位置。另外，在拥挤场景中，occlusion更严重，一段时间以来，用bboxes来定位目标在MOT中很流行。但是在拥挤场景中，occlusions很难处理因为bboxes是重叠的，这个问题通过联合tracking和segmentation来解决。In literature，可以用外观信息和图信息来找到global attributes来解决occlusion。然而，频繁的occlusion在MOT问题上又很低的精度。研究人员尝试去解决这个问题
   • 轻量化架构的挑战：尽管最近的解决方案依赖于heavy-weight 架构，这很消耗资源。
   • 一些常见的挑战：MOT会受到目标检测的影响，如果目标没有正确检测到，整个的追踪努力就会白费。由于相机和目标的运动，运动模糊使MOT更具有挑战性。主要的一个挑战就是detection和tracklet之间的关联。不正确或者不精确的object detection是低精度的结果。还有一些挑战，例如相似的外观特征会混淆模型，tracks的初始化和结束也很重要。还有小目标的追踪。

4. MOT的方法：tracking主要有两个步骤：目标检测和目标关联。一些工作聚焦于目标检测，一些聚焦于数据关联。对于这两步，有很多不同的方法，这些方法不管是检测阶段还是关联阶段，都是不可differentiable的，有时候能看到方法的有重叠，大多数的papers，用了MOT component的多种的组合。

   • Transformer：Transformer的注意力机制帮助记住上下文for long term。基于query key fashion，transformer用来预测输出。视觉研究人员聚焦于利用它来做上下文的记忆。在大多数情况下，MOT去基于之前的信息预测目标在下一帧中的位置，这里认为transformer是最好的，因为transformer能够处理时序信息。TransTrack用Transformer从object query和track query中来预测两组bboxes。通过简单的IoU匹配，找到最后的目标的tracking box，和tracking by detection范式一样。

   • Graph Model：图卷积网络是一种特殊的卷积网络，卷积网络是图的形式而不是线性的。从连续帧中检测到的目标视为一个node，两个node之间的连接视为一个edge。通过匈牙利算法实现数据关联。

   • 检测和目标关联：检测是通过深度学习模型来做的，但是主要的挑战是关联目标，为了追踪感兴趣目标的轨迹，有很多不同的方法。有人采用了自下而上和自上而下的方法。在自下而上的方法中，现决定点的轨迹。但是在自上而下的方法中，先决定box的轨迹。通过结合两者，得到完整的目标的轨迹。为了解决关联的问题，有人简单地检测目标，然后用匈牙利算法进行关联。TrackRCNN是RCNN的扩展，是一个3D的卷积网络，能够同时进行检测和追踪。 在2020年，有人将目标检测和reid用两个分支来做，两个分支在架构上相似，都用center来提取特征，分别进行检测和re-id。他们声称在两个任务上focused equally，这就是为什么它们称之为FairMOT。在2021年，有两篇文章用LSTM来提高数据关联。有人提出了Detection Refinement for Tracking(DRT)，通过半监督学习来产生heatmap来更精确地定位物体，实现检测。这个架构有两个分支，第二个分支能够恢复遮挡的物体，同时，这篇文章也通过LSTM解决了数据关联的问题。也有人提出了CorrTracker，是一个关联网络，能够通过关联传播信息。通过自监督学习来实现检测。有人也基于FairMOT引入了D2LA网络，来保持精度和复杂度的平衡。为了避免遮挡，它们采用了称之为strip attention module的measure；另一方面，有人评估每个检测到的目标，将每个目标mapping到对应的pose，因此它们能够在occlusion之后识别object。有人提出了它们自己的数据集，用称之为HeadHunter的架构for detection还有HeadHunter-T for tracking。HeadHunter有两个阶段，在第一个阶段，用FPN和Resnet-50来提取特征。在第二阶段，用FasterRCNN和RPN来产生object proposals。Jialian等人提出了两个modules：基于association module的cost volume和motion-guided feature warper(MFW) module，来分别提取目标位置的偏置信息和将信息在帧与帧之间传播，将整个过程称为TraDeS。Changzhi等人提出了ParalleMOT，有两个不同的分支用于detection和re-id。

     有人做目标追踪的同时做object forecasting。用FairMOT检测bboxes，然后stack预测网络，做了一个Joint Learning Architecture。有人提取每一帧的新的特征，来得到全局信息，积累partial features用于occlusion handling。他们将两种类型的features融合，来检测行人。

     Hong等人用Non-Maskable Suppression在tracking phase，来降低重要的bboxes被去掉的概率。Jian等人用NMS来去掉检测器中冗余的bboxes，他们通过比较features和重新识别bboxes with the help of IoU，来重新检测轨迹的位置。最终的输出是joint re-detection和re-id tracker。

   • 注意力机制：为了重新识别occluded 目标，注意力是需要的，注意力意味着仅考虑消除背景的objects of interest，因此features能够被记住很长时间，即使在occlusion之后。Yaoye等人引入了strip attention module来重新识别被遮挡的行人，这个module实际上是一个pooling layer，包括max和mean pooling，能够从行人中提取更丰富的信息，所以当被blocked的时候，模型能够记住。Tianyi提出了spatial-attention 机制，通过执行Spaital Transformation Network(STN) in an appearance model，来强制模型仅关注于前景，在另一方面，Lei等人首次提出了Prototypical Cross-Attention Module(PCAM) 来从过去的帧中提取相关的特征。他们用Prototypical Cross-Attention Network(PCAN)在整个网络中传递前景和背景的对比特征。

   Huiyuan等人提出自注意力机制来检测车辆。Jiaxu等人用了交叉和自注意力，自注意力用于提取robust features。然后数据给到cross-attention用于instance 关联。

   • Motion Model：motion是目标不可避免的一个特性。因此这个特征可以用在MOT中，无论是检测还是关联。目标的motion可以通过物体在两帧之间的位置差来进行计算。基于这个measure，有不同的方法。 Hasith等人用motion来计算dissimilarity cost，通过实际位置和预测位置的差来计算Motion。为了预测occlude object的位置，Bisheng等人用基于LSTM的motion model。Wenyuan等人将Deep Affinity Network和motion model结合，通过去掉目标不可能的位置来优化数据关联。

     Qian等人通过用Multi-frame differencing和Low-rank matrix completion，从连续的satellite frames中measue distance，来计算motion。形成了一个motion model的baseline，来检测和降低虚警的数量。Shoudong用motion model通过Motion-Aware Tracker用于运动估计和关联。Zhibo提出了compensation tracker可以得到丢失的目标。

   • Siamese Network：两帧之间的相似性信息在目标追踪中有很大的帮助。这个Siamese网络能够学习相似性，对输入做差分。这个网络有两个平行的subnetworks，共享权重和参数空间，最后，两个twin 网络的参数are tied up，然后在一个特定的损失函数上进行训练，来测量它们之间的语义相似。Bing通过引入motion model，提升了MOT网络。他们将Siamese network trackign嵌入到FasterRCNN中，实现了快速的tracking。Cong等人提出了一个Cleaving Network，用Siamese Bi-directional GRU(SiaBiGRU) in post-processing the trajectories，来消除损坏的tracklets。然后他们建立了re-connection 网络，来连接tracklets，形成轨迹。 在一个典型的MOT网络中，有预测和检测模块，预测模块来预测下一帧中的物体的外观，检测模块检测物体。两个模块的结果用于匹配特征和更新目标的轨迹。Xinwen等人提出了Siamese RPN结构作为预测器，他们也提出了一个自适应的阈值方法用于数据关联。Philippe等人将高效的Transformer引入到一个Siamese Tracking network。他们用transformer layer替换卷积层。

   • Tracklet 关联：一组连续的感兴趣目标的帧称为tracklet。在检测和追踪目标的时候，tracklets首先用不同的算法被识别，它们关联到一块构建一个轨迹。Tracklet关联是一个有挑战性的问题。

     Jinlong等人提出了Tracklet-Plane Matching，从检测的目标中构建短的tracklets，然后再tracklet-plane中对齐，根据每个trackelt的开始和结束的时间，每个tracklet分配了一个超平面。然后形成了大的轨迹。这个过程能够处理非相邻的和重叠的tracklets。Duy等人通过3D的几何算法构建轨迹，它们是从多相机来做的，通过formulating 空间和时序信息，来全局优化关联。

     Cong提出了Position Projection网络，将轨迹从局部转换到全局。Daniel通过将new-coming object分配给之前发现的occluded object来实现re-id occluded objects。

\(Fig.1^{[1]}\) MOT算法的工作流，给定一个适配的raw frame，用一个目标检测器来得到objects的bboes；然后，对于每个检测到的objects，计算不同的features，通常是visual和motion；在这之后，affinity这个步骤计算两个objects属于同一个target的概率；最后，一个关联步骤给每个object配一个ID。

\(Fig.2^{[2]}\) 最近的MOT方法的组织

Multiple Object Tracking: A Literature Review^[3]

作者是来自腾讯、自动化所等单位的Mk Bashar等人，论文引用[3]:Luo, Wenhan et al. “Multiple object tracking: A literature review.” Artif. Intell. 293 (2014): 103448.

总结

1. 尽管有很多不同的方法来解决这个问题，它仍然是具有挑战性的，因为有外观改变、严重的遮挡等因素。MOT这个任务是在给定输入视频的条件下，主要划分为定位多个物体、保持身份ID、产生各自的轨迹。作为计算机视觉的一个中级任务，多目标追踪是姿态估计、行为识别/分析等的基础。它有多个应用。MOT可以被视为一个多变量估计 问题。给定一张图像，用 \(s^i_t\) 表示在第 t 帧的第 i个物体。

2. 接着常用的tracking-by-detection或者Detection base Tracking(DBT)范式，用 \(o^i_t\) 表示第t帧的第i个观测。MOT的目标是找到所有目标的最优的序列状态，给定的所有观测中，通过从序列状态的条件分布，执行MAP(Maximum a posteriori,最大后验)估计： \[\widehat{\mathbf{S}}_{1:t}=\underset{\mathbf{S}_{1:t}}{\operatorname*{\arg\max}}P\left(\mathbf{S}_{1:t}|\mathbf{O}_{1:t}\right). (1)\]

   之前的不同的MOT算法，可以被认为是设计不同的方法来解决MAP问题，或是概率推理的角度，或是确定性优化的角度。基于概率推理的方法，通常用等式(1)进行推理，用如下的两步进行迭代：

   \[\begin{aligned} & \mathbf{Predict:}P(\mathbf{S}_{t}|\mathbf{O}_{1:t-1})=\int P(\mathbf{S}_{t}|\mathbf{S}_{t-1})P(\mathbf{S}_{t-1}|\mathbf{O}_{1:t-1})d\mathbf{S}_{t-1}, \\ & \mathbf{Update:}P(\mathbf{S}_{t}|\mathbf{O}_{1:t})\propto P(\mathbf{O}_{t}|\mathbf{S}_{t})P(\mathbf{S}_{t}|\mathbf{O}_{1:t-1}). \end{aligned}\]

   这里的 \(P\left(\mathbf{S}_{t}|\mathbf{S}_{t-1}\right)\) 和 \(P\left(\mathbf{O}_{t}|\mathbf{S}_{t}\right)\) 分别是动态模型和观测模型，这个基于确定性优化的方法直接最大化概率函数， \[\widehat{\mathbf{S}}_{1:t}=\arg\max_{\mathbf{S}_{1:t}}P\left(\mathbf{S}_{1:t}|\mathbf{O}_{1:t}\right)=\arg\max_{\mathbf{S}_{1:t}}L\left(\mathbf{O}_{1:t}|\mathbf{S}_{1:t}\right)=\arg\max_{\mathbf{S}_{1:t}}\prod_{n}P\left(\hat{\mathbf{O}}_{1:t}^{n}|\mathbf{S}_{1:t}\right), (2)\] 或者相反，最小化能量函数：\(E\left(\mathbf{S}_{1:t}|\mathbf{O}_{1:t}\right):\)

   \[\widehat{\mathbf{S}}_{1:t}=\arg\max_{\mathbf{S}_{1:t}}P\left(\mathbf{S}_{1:t}|\mathbf{O}_{1:t}\right)=\arg\max_{\mathbf{S}_{1:t}}\exp\left(-E\left(\mathbf{S}_{1:t}|\mathbf{O}_{1:t}\right)\right)/Z=\arg\min_{\mathbf{S}_{1:t}}E\left(\mathbf{S}_{1:t}|\mathbf{O}_{1:t}\right),\]

   \(Z\) 是一个归一化因子，确保 \(P\left(\mathbf{S}_{1:t}|\mathbf{O}_{1:t}\right)\) 是一个概率分布。

3. 很难通过一个通用的标准，将一个MOT方法分类到一个类别中。因此，对MOT进行分类有多个标准。这里有三个标准：1)初始化方法；2)处理模式；3)输出的类型。

   • 初始化：大多数的MOT可以分为两类：依赖于目标是如何初始化的：Detection-based Tracking(DBT) 和 Detection-Free Tracking(DFT)。
     • Detection-Based Tracking：首先检测到目标，然后连接成轨迹。这个方法通常也称为“tracking-by-detection"。**给定一个序列，在每一帧上进行目标检测或者运动检测，来得到object hypotheses，然后进行tracking，将detection hypotheses连接成轨迹。这里有两个问题：1）目标检测器是提前训练了，大多数的DBT方法聚焦于特定类型的目标，例如行人。2)DBT的性能依赖于采用的目标检测器的性能。
     • Detection-Free Tracking：DFT方法需要人为的在第一帧中初始化固定数量的目标，然后在后面的帧中定位这些目标。DBT更受欢迎，因为这些新的目标发现了，消失的目标终止了。DFT不能处理目标消失的情况。然而，它不许哟啊训练好的目标检测器。
   • 处理模式：MOT方法可以进一步分为在线和离线。区别在于当处理当前帧的时候，来自future frames的观测是否被利用。在线方法，也成为因果,tracking，仅依赖于过去的信息；离线方法，batch tracking，能利用所有的信息。
     • online tracking：在线方法中，图像序列是step-wise handled manner。
     • offline tracking：离线方法中，用一个batch的frames来处理数据。从所有帧中得到的观测，一起用来估计最后的输出。注意到，由于计算和存储的限制，通常不能一次处理所有帧；另外一个方式是将数据分成更短的video clips，对每个batch进行推理。
   • 输出类型：将MOT方法分为确定性的和概率性的标准，依赖于输出的随机性。两类方法的不同主要来自于优化方法。
     • stochastic tracking：stochastic tracking的输出结果因时间不同而不同。例如，在DFT的中，如果用粒子滤波进行推理，bboxes的结果是不同的；不同的结果来自于处理过程中的粒子产生的随机性。即使在DBT的中，一些研究也用SOT来对检测框进行修正，这种类型的方法在不同的运行时间导致不同的追踪结果。
     • Deterministic Tracking：当多次运行的时候，确定性跟踪的输出是不变的，例如，在tracking-by-detection中，用匈牙利算法进行数据关联会产生确定性的追踪结果，确定性的跟踪通常和用于推导最终结果的确定性优化想关联。
   • 讨论：DBT和DFT之间的不同之处是在于是否采用了检测模型。区分在线和离线追踪的关键是处理观测的方式。

4. MOT的组件：在这个部分，MOT的目标是发现每一帧中的多个目标，通过连续帧恢复id信息。开发MOT方法的时候，两个主要的问题：一个是如何测量帧中的目标的相似性；另一个问题是如何基于跨帧对象之间的相似性度量来恢复身份信息。第一个问题涉及外观、运动、交互、exlusion和occlusion的建模；第二个涉及推理的问题。

   • 外观模型：外观在MOT中是一个重要的用于匹配计算的线索。然而，不同于SOT(主要关注于构建复杂的外观模型，来区分背景和目标)，大多数的MOT方法，不考虑外观模型作为核心的组件。外观模型通常包含两个组件：视觉表征(visual representation)和统计测量(statistical measuring)。视觉表征用一些特征描述目标的视觉特性；或是single cue或是multiple cues。统计测量，是不同观测之间的相似度计算。两个观测i和j之间的相似度如下：

   \(O_i\) 和 \(O_j\) 是不同观测的视觉表征，\(F(.,.)\) 是一个函数，计算它们之间的相似度。 - 视觉表征：根据不同类型的特征来描述一个目标，将特征分为以下几类： - 局部特征：KLT是一个搜索好的局部特征和tracking的粒子。用在了SOT和MOT中。如果将图像像素视为finest local range的话，光流也可以视为局部特征。一些MOT的思路是在数据关联之前用光流将detection连接成short tracklets。因为它和运动相关联，因此用来编码运动信息。光流的一个应用是发现拥挤场景下的crowd motion patterns，这种情况下一般的特征不可靠。 - Region Features：相比于local features，region features是从wider range中得到的(例如bbox)：有三种类型：1)zero-order类型;2)first-order类型;3)up-to-second-order类型。这里的order是指计算表征的时候的order of discrepancy。例如：zero-order一位置像素值没有进行比较，one-order意味着计算了一次像素之间的差异。zero-order：这是用的最多的MOT的表征。颜色直方图和raw pixel template是两种典型的例子。first-order：基于梯度的表征例如HOG和level-set formulation用的比较多。up-to-second-order：Region covariance matrix，计算了up-to-second order discrepancy。 - others：除了local和region features，也有一些其他类型的表征，例如depth，用来修正检测假设。Probabilistic Occupancy Map(POM)用来估计一个目标有多大的可能出现在一个grid cell中。另一个例子是gait feature，对每个人是唯一的。DCNN扮演者类似bag-of-words中的密码本的角色。ColorNames描述器用在了外观表征上。来自CNN的特征用在了视觉表征上。还有用点云的特征，用于特征融合。 - Discussion：通常，颜色直方图是研究得很多的相似度测量，但是它忽略了目标区域的spatial layout。局部特征是高效的，但是对遮挡、out-of-plane rotation是敏感的，基于梯度的特征例如HOG，能够描述目标的外形，对于一些变换也很鲁棒，但是它们不能处理遮挡和形变。region covariance matrix特征更加鲁棒，因为它们考虑了更多的信息，但是需要更多的计算。depth features使得匹配计算更加精确，但是它们需要多视角或者额外的算法来得到。 - 统计测量：这个步骤和上面紧密相连。基于视觉表征，统计测量计算两个观测之间的相似度。一些方法只依赖于一种类型的cue，其他的依赖于多个cues。 - single cue：用single cue进行外观建模要么将距离转换成相似度，要么直接计算affinity。例如Normalized Cross Correlation(NCC)经常用于计算基于raw pixel template的表征的两个counterparts之间的affinity。说到颜色直方图，Bhattacharyya距离B(.,.)用于计算连个直方图之间的距离，这个距离转换成相似度S，或者将距离拟合到高斯分布。非相似度转换到likelihood，也用在了covariance matrix表征上。来自神经网络的深度特征之间的余弦相似度也被使用过。除了这些典型的模型，bag-of-words模型用在了基于point features representation上。 - multiple cues：不同类型的cues能够互补，使得外观模型更加鲁棒。然而，如何融合这些cues的信息很重要，基于此，根据5中不同类型的融合策略，总结了基于外观模型的multi-cue：Boosting, Concatenating, Summation, Product, Cascading。 - Boosting：Boosting通过基于boosting的算法，从feature pool中选择一定的features。例如，从颜色直方图中，HOG和covariance matrix descriptor, AdaBoost, RealBoost和一个HybridBoost算法分别用来选择最具有表征的features将同一目标的轨迹和其他目标的区分开。 - Concatenation：不同类型的特征通过concatenated用于计算，color,HOG,光流等进行concatenation，用于外观建模。 - Summation：将不同特征的affinity values进行加权计算。 - Product：将不同特征的affinity values进行乘积计算，得到integrated affinity。注意到，当用这个策略的时候，通常进行独立假设。 - Cascading：用不同类型的视觉表征，用cascade 的方式，要么narrow the search space，要么对外观以coarse-to-fine的方式进行建模。

   • 运动模型：运动模型得到目标的动态行为，在future frames中估计目标的潜在位置，因此降低了搜索空间，在大多数情况下，目标假设move smoothly，因此在图像空间中。讨论线性运动模型和非线性运动模型。
     • 线性运动模型：这是用的最多的模型。模型假设速度恒定。基于这个假设，有3种不同的方式构建模型：

       • velocity smoothness：目标在连续帧中的速度变化是smoothly。

       • Position smoothness：直接force 观测的位置和估计的位置discrepancy。将估计的位置拟合到以观测的位置为中心的高斯分布中。在估计的时候，forward motion和backward motion都考虑了，公式如下：

         F和B意味着forward 和backbward方向，观测的位置和估计的位置之间的位移 \(\Delta p\) 拟合到zero-center的高斯分布中。

       • Acceleration smoothness：除了考虑位置和速度smoothness，加速度也考虑了。在时刻k的一个状态的运动的概率分布如下：

     • 非线性运动模型：线性运动模型通过用来解释目标的dynamics。然而，也有一些线性模型无法处理的情况。非线性模型用来产生不同tracklets之间的更精确的motion affinity。例如，有人用了非线性运动模型来处理targets may move freely的情况。给定属于同一个目标的两个tracklets \(T_1\) 和 \(T_2\)，线性运动模型会产生比较低的概率来连接它们。alternatively，用一个非线性运动模型，tracklet \(T_1\) 的尾巴和tracklet \(T_2\)的头之间的gap可以合理地被tracklet \(T_0\)解释，如图所示，\(T_0\) 匹配 \(T_1\)的尾巴和\(T_2\)的头。这个连接 \(T_1\) 和 \(T_2\) 之间的真实Path是通过基于 \(T_0\) 估计得到的。\(T_1\) 和 \(T_2\) 之间的 affinity的计算和之前的相似。
   • interaction model：交互模型，也称之为mutual motion model，捕获一个目标对另一个目标的影响。在拥挤的场合，一个目标可能经历一些来自其他目标的"force"。例如，当行人在街上走的时候，他会调整他的速度、方向和目的地，为了避免和其他相碰。另一个例子是：当一群人在街上走的时候，每个人都同时跟着他人，实际上，有两个典型的交互模型：social force model 和 crowd motion pattern models。

     • Social Force Models：social force模型也称之为group models。在这些模型当中，每个物体都被认为和其他物体和环境因素有依赖。这种类型的信息可以缓解拥挤场景下的性能下降。在social force模型中，目标被视为agents，基于其他物体和环境，决定它们的速度、加速度和目的地。在social force 模型中，目标行为基于individual force 和group force进行建模。Individual force：对于多个目标中的每个个体，两种类型的forces被考虑：fidelity(不会改变目的地)；constancy(不会突然改变动量/速度/方向)。Group force：三种类型的forces被考虑：attraction(个体一起移动，group靠的近)；repulsion(个体会一起移动，当group和其他保持距离的时候)；coherence(个体和group移动的时候保持相似的速度)。 目前主要的对物体和social force进行建模的方法是对一个energy objective最小化，包含反应个体force和group force的项。

     • Crowd Motion Pattern Models：受crowd simulation literature的启发，引入了motion patterns来缓解拥挤场景下追踪个体目标的困难，通常情况下，这个类型的模型用在了over-crowded 场景，这种情况下，目标相当小，cues例如外观和个体运动是模糊的。这种情况下，来自crowd的motion是一个比较可靠的cue for this problem。

       粗略地说，这里有两种类型的motion patterns，structured 和 unstructured 两种，structured motion patterns展示了collective 时空结构，unstructured motion patterns展示了多样的motion的模态，通常情况下，motion patterns通过多种方式进行学习(包括ND tensor voting, 隐马尔科夫模型等)，用一些先验知识来帮助目标跟踪。

   • Exclusion model：Exclusion是constraint，来避免physical collisions。他来自于这样一个事实：两个不同的物体不能占据真实世界中的相同的物理空间。给定多个detection responses和多个轨迹假设，通常有两个constraints：一个称之为detection-level exclusion，例如同一帧中的两个不同的detection responses不能给到同一个物体；第二个称之为trajectory-level exclusion，例如两个轨迹不能无限接近。
     • detection-level exclusion modeling：不同的方法用来对detection-level exclusion进行建模，这里有soft和hard models。Soft modeling：通过最小化cost term惩罚violation的情况，例如如果两个同时发生的detection responses被分配给相同的轨迹，它们之间的距离也足够远，则定义一个penalty。为了建模exclusion，构建一个exclusion graph，来得到constraint，给定所有的detection，定义一个graph，其中nodes表示detection，每个node之连接到和同时存在的node。在构建完这个graph之后，最大化label assignment，使连接的nodes有不同的labels。Hard modeling，通过用explicit constraint来对detection-level exclusion进行hard modeling。例如，为了建模detection-level exclusion，如果两个tracklets在它们的time span上有重叠，它们不能分配到同一个cluster，属于同一个trajectory。用non-negative discretization来将检测设置为非重叠的组，服从互斥约束。
     • trajectory-level exclusion modeling：trajectory-level exclusion通过惩罚两个相近的、有不同的trajectory labels的detection进行建模，这会抑制其中一个轨迹label。例如，惩罚项和两个detection responses之间的距离成反比。如果两个detection responses太近了，它会导致相当大的cost；也有方法，它的penalty和两个轨迹的时空overlap成正比。两个轨迹越近，惩罚越大。
   • occlusion handling：遮挡或许是MOT中最重要的挑战，它是ID切换的主要原因
     • part-to-whole：这个策略使建立在当遮挡发生的时候，物体的一部分还可见的时候，这个假设在大多数情况下成立。基于这个假设，采用这个策略的方法利用可见的部分推测整个物体的状态。流行的方式是将整个物体划分为多个parts，基于individual parts计算affinity。如果遮挡发生了，遮挡部分的affinities会比较低。Tracker会意识到这个，然后采用没有遮挡部分用于估计。基于这些individual parts，遮挡部分的观测被忽略了。例如，part-wise 外观模型被构建，重建损失用来决定哪些parts被遮挡还是没有。整个物体的外观模型通过仅更新未这遮挡的部分进行更新。part-to-whole策略也用于基于feature point clustering的追踪。假设有相似motion的feature points属于同一个object。只要一个object的一些parts是可见的，clustering of feature point trajectories会work。
     • hypothesize-and-test：这个策略通过假设proposals和testing proposals according to observations at hand，回避了遮挡的挑战。这个策略有两个步骤：hypothesize和test。Hypothesize：张等人基于occludable pair of observations，产生occlusion hypotheses，它们相近且有相似的scale。假设 \(o_i\)被 \(o_j\)遮挡，一个corresponding occlusion假设是，\(p_j\) 和 \(t_j\) 是 \(o_j\)的位置和时间戳。 \(s_i\)和 \(f_i\) 是 \(o_i\) 的尺寸和外观特征。这个方法将遮挡视为distraction，在其他的工作中，occlusion patterns被用来辅助检测。不同的detection hypotheses通过结合不同level和patterns of occlusion来生成。Test：假设的观测和原始的一起给到cost-flow framework作为输入，执行MAP来得到最优的方案。一个multi-person检测器基于detection hypotheses进行训练，这个检测器降低了检测的困难。
     • buffer-and-recover：这个策略会缓存observations，当遮挡发生的时候，记住遮挡发生之前的状态。当遮挡结束的时候，基于遮挡之前的缓存的observation和状态，恢复object states。有人提出了当遮挡发生的时候，keep trajectory alive for up to 15 frames。通过遮挡推断出休眠轨迹的位置。以防物体再次出现，再次触发track，保持identity。只要得到了足够的observations，产生hypotheses来解释observations
     • others：上述的策略可能不能覆盖所有的策略。例如，有人将targets表示为图像空间中的高斯分布，显式地对所有目标之间的pair-wise occlusion ratios进行建模。
   • 推理：
     • 概率推理：基于概率推理的方法将目标的状态表示为不确定的分布。跟踪算法的目标是估计目标状态的概率分布，通过基于已有的观测的多种概率推理方式。这种类型的方法需要the existing，例如过去和现在的观测。很自然地将马尔可夫假设用在目标状态序列上。这个假设包括两个方面。首先，当前的目标状态仅依赖于之前的状态；如果一阶马尔可夫特性应用了的话，仅依赖于最近的状态；另外，目标的观测只和对应于这个观测的状态有关。换句话说：观测是条件独立的。这两个方面分别和<font color=red dynamic model和<font color=red observation model有关。dynamic model对应于跟踪策略，观测model提供关于目标状态的观测measurements。预测阶段是基于过去所有的观测对当前状态的估计，更具体地，当前状态的后验概率分布是通过dynamic model在最后一个目标空间里进行集成，进行估计的。更新阶段是基于观测模型得到的测量，来更新状态的后验分布。 根据公式，目标的状态可以通过iteratively执行预测和更新阶段来估计。然而，在实际中，不简化假设的时候，目标的状态分布无法表示。因此计算状态分布的积分没有解析解。另外，对于多目标，状态的集合的维度是很大的，使得integration比较困难，需要对近似解进行推导。
     有很多的概率推理模型用于多目标跟踪，例如KF,EKF和粒子滤波。 - 卡尔曼滤波器：在线性系统和高斯分布的目标状态下，KF被证明是最优的估计器； - 扩展卡尔曼滤波器：未了包含非线性情况，扩展卡尔曼滤波器是一个可能的方式，通过泰勒展开近似一个非线性系统。 - 粒子滤波：基于蒙特卡洛采样的模型在跟踪中也很流行，这个策略通过一组加权的particles，对潜在的分布进行建模
     • deterministic 优化：不同于概率推理模型，基于确定性优化的方法旨在找到MOT的最大后验方法，为了这个目的，推理数据关联、目标状态的任务被视为一个优化问题。这个框架下的方法更适合离线跟踪，因为所有帧的观测都能得到。给定所有帧的观测，这些方法能够将属于通过一个目标的观测进行全局关联成轨迹。这个关键的问题是找到最优的关联。有以下方法：
       • Bipartite graph matching：通过将MOT问题建模为bipartite graph matching，两个不相交的graph nodes可以是在线跟踪中的现有的轨迹和新的检测，或者离线跟踪中的两组tracklets。nodes之间的权重被建模为轨迹和检测之间的affinity。然后用贪心的bipartite 分配算法或者匈牙利算法来决定两组nodes之间的匹配。
       • 动态规划：扩展动态规划、线性规划等用来解决detections或tracklets之间的关联问题。
       • Min-cost max-flow network flow：network flow是一个directed graph，每个边都有一个确定的容量。对于MOT，图中的nodes是detection responses或者tracklets，flow被建模为一个indicator，来连接两个nodes。为了满足flow balance要求，一个源节点，sink 节点(汇聚节点)对应于轨迹的开始和结束。在一个graph中，一个轨迹对应于一个flow graph，从源节点到汇聚节点的总的flow等于轨迹的数量；transition的成本是关联假设的负log-likelihood。
       • conditional random field：顶一个graph G=(V,E)，V是node的集合，E是边的集合。low-level tracklets作为graph的输入，图中的每个node表示观测或者pairs of tracklets，预测label，表示观测属于哪个track或者是否连接tracklets。
       • MWIS：最大权重独立set是heaviest subset of non-adjacent nodes.如上所述的CRF模型，属性图中的节点表示连续帧中的轨迹对，节点的权重表示轨迹对的关联度，如果两个轨迹共享相同的检测，则边缘连接。给定此图，将数据关联建模为MWIS问题

$Fig.3^{[3]} Components of MOT

\(Fig.4^{[3]}\) (a)Image showing optical flow;(b)image showing covariance matrix;(c)image showing point feature;(d)image showing gradient based features;(e)image showing depth;(f)image showing color feature.