多目标跟踪算法简介
跟踪算法的重点
SORT

是一种的在线实时多目标跟踪算法。要点为：


以 IOU 作为前后图像目标关系度量指标；


利用卡尔曼滤波器预测当前位置；


通过匈牙利算法关联检测目标；


使用 YOLO3，证明检测好跟踪可以很简单。


跟踪算法过程


将检测目标分配给现有目标时；


预测每个目标在当前图像中的新位置，估计其边界框形状；


由每个检测与现有目标的所有预测边界框之间的交并比（IoU）计算分配成本矩阵；


使用匈牙利算法对分配进行优化求解；


跟踪算法流程图
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WqQZo4ez-1588736442528)(media/dee5c95f024741ea9caf8ac927325d39.png)]
匈牙利算法
匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法。



步骤1：给定一个图：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5kUznRzu-1588736442531)(media/562018b024c49605b185216d135ef606.png)]
我们讨论的基础是二部图，而上图就是一个二部图，我们从上图的左边开始讨论，我们的目标是尽可能给x中最多的点找到配对。
刚开始，一个匹配都没有，我们随意选取一条边，（x1,

y1）这条边，构建最初的匹配出来，结果如下，已经配对的边用粗线标出：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uSduoshM-1588736442532)(media/c14c8d1503f942c97f76c5a5b9f4f094.png)]

给x2添加一个匹配，如下图的（x2, y2）边。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O7TarvUu-1588736442533)(media/31502f1e1ee5a346075317c643c61dd4.png)]
目前，我们形成了匹配M，其有（x1,  y1）, (x2,  y2 ) 两条边。

给x3匹配一条边，发现它的另一端y1已经被x1占用了，那x3就不能匹配x1，让y1离开x1。x1匹配y2，x1发现

y2 和x2 匹配，又让 y2离开 x2 （这是个递归的过程）。x2 继续匹配。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t60FFwTA-1588736442534)(media/e2bc3d0143077e6655e56aaeb959346f.png)]


总结：

匈牙利算法寻找最大匹配，就是通过不断寻找原有匹配M的增广路径，因为找到一条M匹配的增广路径，就意味着一个更大的匹配M’

, 其恰好比M 多一条边。



条M匹配的增广路径，就意味着一个更大的匹配M’

, 其恰好比M 多一条边。
2.  对于图来说，最大匹配不是唯一的，但是最大匹配的大小是唯一的。

	

前言
目标跟踪是计算机视觉领域中研究的热点之一，分为单目标跟踪与多目标跟踪。前者跟踪视频画面中的单个目标，后者则同时跟踪视频画面中的多个目标，得到这些目标的运动轨迹。        
基于视觉的多目标跟踪在近年来越来越多地成为计算机视觉领域的研究重点，主要是因为其在智能监控、动作与行为分析、自动驾驶、虚拟现实和娱乐互动等领域都有重要的应用。例如，在自动驾驶系统中，目标跟踪算法要对运动的车、行人、其他动物的运动进行跟踪，对它们在未来的位置、速度等信息作出预判；在虚拟现实领域里，需要根据摄像头捕捉到的人物动作和轨迹，实现人机交互的目的。
那么，跟踪算法有哪些主要分支？不同的跟踪算法是如何实现的呢？让我们带着这些问题开始多目标跟踪领域的奇幻之旅吧！
须知
多目标跟踪算法按照轨迹生成的顺序可以分为离线的多目标跟踪和在线的多目标跟踪算法。
离线方式的多目标跟踪算法通常构造为图模型。其中，设计和计算检测之间的相似度或者距离度量是决定图模型构造正确性的关键。在线方式的多目标跟踪算法根据当前检测观测，计算与已有轨迹的匹配关系。
综上，计算合适的匹配度量决定了匹配的正确性。因此，无论是离线方式的多目标跟踪还是在线方式的多目标跟踪算法，学习检测结果的特征并计算匹配相似度或者距离度量都是多目标跟踪算法的关键步骤。
基于深度学习的多目标跟踪算法的主要任务是优化检测之间相似性或距离度量的设计。根据学习特征的不同，基于深度学习的多目标跟踪可以分为基于深度表观特征学习的多目标跟踪，基于深度相似性度量学习的多目标跟踪，以及基于深度高阶特征匹配的多目标跟踪，如图1所示。
图1 基于深度学习的多目标跟踪算法
深度表观特征：利用图像识别任务中学习到的深度特征直接替换现有多目标跟踪算法框架中的表观特征，或者采用深度神经网络学习光流运动特征，计算运动相关性。
深度相似性度量：学习检测之间的特征相似性，比如设计深度网络计算不同检测的距离函数，相同目标的检测距离小，不同目标的检测距离大，从而构造关于检测距离的代价函数。也可以设计二类分类代价，使相同目标的检测特征匹配类型为1，而不同目标的检测特征匹配类型为0,从而学习并输出(0,1)之间的检测匹配度。
深度高阶特征匹配：如果考虑已有轨迹与检测之间的匹配或者轨迹之间的匹配，采用深度学习方法可以用于设计并计算轨迹之间的匹配相似度，这种方法可以认为是基于深度学习的高阶特征匹配方法。采用深度学习计算高阶特征匹配可以学习多帧表观特征的高阶匹配相似性，也可以学习运动特征的匹配相关度。
下面我将对一些比较重要的基于深度学习的多目标跟踪算法进行概述，想要详细了解的小伙伴还是要多读源码、多看论文，细细体会这些算法背后的深刻含义了，文章的最后我会给出我看过的一些关键性的论文与源码传送门，莫慌！
算法
基于Siamese对称网络的多目标跟踪算法
Siamese对称卷积网络是一种检测匹配度量学习方法，如图2所示。以两个尺寸相同的检测图像块作为输入，输出为这两个图像块是否属于同一个目标的判别。
原始的检测特征包括正则化的LUV图像I1和I2，以及具有x,y方向分量的光流图像O1和O2，把这些图像缩放到121x53，并且叠加到一起构成10个通道的网络输入特征。卷积网络由三个卷积层(C1、C2、C3)、三个全连接层(F4、F5、F6)以及一个2元分类损失层(F7)组成，如图2所示。
图2 Siamese对称网络结构
学习过程采用经典的带有动量的随机梯度反向传播算法。minibatch大小选择为128，学习率初始为0.01。通过50个回合的训练，可以得到较为优化的网络参数。在Siamese网络学习完成之后，作者采用第六层全连接网络的输出作为表观特征，为了融合运动信息，作者又设计了6维运动上下文特征：尺寸相对变化，位置相对变化，以及速度相对变化。
基于Siamese对称网络的多目标跟踪算法在计算机视觉跟踪领域有着十分重要的地位，由于采用孪生的网络结构，使得其能够更好地利用一套参数来对相似的图像进行拟合，达到快速学习跟踪的目的。这种网络结构为后续的研究工作提供了一个十分有效的网络模板与思路，推动了计算机视觉领域跟踪算法的发展。
基于全连接孪生(Siamese-FC)网络的目标跟踪
Siamese-FC与之前提到的Siamese CNN都采用了孪生结构，Siamese-FC的算法结构如图3所示。
图3 Siamese-FC网络结构
图中z代表的是模板图像，算法中使用的是第一帧的groundtruth，x代表的是search region，即在后面的待跟踪帧中的候选框搜索区域，φ代表的是一种特征映射操作，将原始图像映射到特定的特征空间，文中采用的是CNN中的卷积层和pooling层，6×6×128代表z经过φ后得到的特征，是一个128通道6×6大小feature，同理，22×22×128是x经过φ后的特征，最后的*代表卷积操作，让22×22×128的feature被6×6×128的卷积核卷积，得到一个17×17×1的score map，代表着search region中各个位置与模板的相似度值。
算法本身是比较搜索区域与目标模板的相似度，最后得到搜索区域的score map。从原理上来说，这种方法和相关性滤波的方法很相似。都是在搜索区域中与目标模板进行逐点匹配，Siamese-FC算法将这种逐点平移匹配计算相似度的方法看成一种卷积操作，然后在卷积结果中找到相似度值最大的点，作为新的目标中心。
MDNet的改进网络——Real-Time MDNet
首先简单介绍MDNet, MDNet是一个纯深度的目标跟踪方法，训练时首先在每一个视频中根据目标的位置用高斯分布，均匀分布和随机分布结合的方法采样取得ROI框，提取对应图像patch；然后输入网络最后一层(全连接层)后，利用softmax输出目标和背景的概率，然后根据groundtruth计算loss反传，训练时仅最后一层FC层根据不同类的视频而不同，即仅有前面的层共享参数，目的是学习到更鲁棒的参数，检测的时候去掉最后一层，用新的FC层使用第一帧的信息finetune，MDNet的缺点是太慢，FPS~ 1。Real-TimeMDNet提升至FPS～40。
       Real-Time MDNet[12]的贡献是：
1、受Mask R-CNN的启发，提出了一种自适应的ROIAlign；
2、对损失函数进行了改进，引入了一个内嵌实例的loss。
自适应的ROIAlign:
如果把MDNet比作tracking版的R-CNN，那么RT-MDNet就可以近似的认为是tracking版的Mask R-CNN。
原始的MDNet像R-CNN一样，是先产生proposal，然后用proposal在原图上抠图提特征，这就会像R-CNN一样在提特征时产生很多冗余的部分，很自然的，可以像Faster那样，先提原图的特征，然后在featuremap上去找RoI，这样可以大大加快速度。但是普通的RoI Pooling会在两次量化的过程中积累很多误差，这些误差再积累到tracking的时序上，最后很可能会让模型漂掉。所以自然的又想到了用RoI Pooling的改进版，RoIAlign。
然而，当RoIAlign中的采样点间隔太大，会损失掉featuremap上一些有用的信息。比如，一个feature map grid上是5×5的点，但是RoIAlign在每个grid上只采2×2共4个点，这必然会导致featuremap上的信息被丢失。所以作者根据feature map grid的size自适应的调整网格里samplepoints的数量，来减少信息的损失。这就是自适应的ROIAlign。
对损失函数的改进：
对Loss的改进如图4所示，引入了内嵌实例的loss，使不同域的目标在特征空间的距离相互更远，这样能学到更有判别力的特征。MDNet仅仅是在每一个域中区分目标和背景，而当目标们有相似的外观时就不能有效判别不同域中的目标，所以作者loss中嵌入了其他视频中的目标来使相互之间更有判别力。
图4 内嵌实例的loss
基于时空域关注模型的多目标跟踪算法
除了采用解决目标重识别问题的深度网络架构学习检测匹配特征，还可以根据多目标跟踪场景的特点，设计合适的深度网络模型来学习检测匹配特征。Chu等人对行人多目标跟踪问题中跟踪算法发生漂移进行统计分析，发现不同行人发生交互时，互相遮挡是跟踪算法产生漂移的重要原因。如图5。
图5 互相遮挡导致识别不准
针对这个问题，他们提出了时空域关注模型(STAM)来学习遮挡情况，并判别可能出现的干扰目标。如图6所示，空间关注模型用于生成遮挡发生时的特征权重，对候选检测特征加权之后，通过分类器进行选择，得到估计的目标跟踪结果。时间关注模型加权历史样本和当前样本，从而得到加权的损失函数，用于在线更新目标模型。
图6 基于时空域关注模型
在这个模型中每个目标独立管理并更新自己的时空域关注模型，并选择候选检测进行跟踪，因此本质上，这种方法是对单目标跟踪算法在多目标跟踪中的扩展。为了区分不同的目标，关键的步骤是如何对遮挡状态进行建模和区分接近的不同目标。
空间注意模型用于对每个时刻的遮挡状态进行分析，空间关注模型如图7所示。主要分为三步。第一步是学习特征可见图(visibility map)；第二步是根据特征可见图，计算空间关注图(Spatial Attention)；第三步根据空间关注图加权原特征图。对生成的加权特征图进行卷积和全连接网络操作，生成二元分类器判别是否是目标自身。最后用得到分类打分，选择最优的跟踪结果。
图7 空间关注模型步骤
基于LSTM判别融合表观的多目标跟踪算法
前面介绍的几个算法采用的深度网络模型都是基于卷积网络结构，由于目标跟踪是通过历史轨迹信息来判断新的目标状态，因此，设计能够记忆历史信息并根据历史信息来学习匹配相似性的网络结构，也是比较可行的算法框架。Sadeghian等人设计了基于长短期记忆循环网络模型(LSTM)的特征融合算法来学习轨迹历史信息与当前检测之间的匹配相似度。如图8，首先，轨迹目标与检测的匹配需要用到三种特征(表观特征、运动特征、交互特征)(左)；然后，采用分层的LSTM模型(中)来实现三种特征的融合；最后，通过相似度的二部图匹配算法实现最终的匹配结果(右)。
图8 基于LSTM特征融合进行跟踪
对于表观特征，首先采用VGG-16卷积网络生成500维的特征，以这个特征作为LSTM的输入计算循环网络的输出，根据与当前时刻检测到的特征匹配的情况来学习分类器，并预训练这个网络，如图9所示。
图9 基于CNN模型和LSTM模型的轨迹与检测表观特征匹配架构
对于运动特征，取相对位移为基本输入特征，直接输入LSTM模型计算每个时刻的输出。对于下一时刻的检测，同样计算相对位移,通过全连接网络计算特征，得到500维的特征，并利用二元匹配分类器进行网络的预训练。整个过程如图10所示。
图10 基于LSTM模型的轨迹运动特征匹配架构
对于交互特征，取以目标中心位置周围矩形邻域内其他目标所占的相对位置映射图作为LSTM模型的输入特征，计算输出特征。同样通过全连接网络计算500维特征，进行分类训练，如图11所示。
图11 基于LSTM模型的目标交互特征匹配架构
当三个特征都计算之后拼接为完整的特征，输入到上层的LSTM网络，对输出的向量进行全连接计算，然后用于匹配分类，匹配正确为1，否则为0。
总结
目前的基于深度学习的多目标跟踪框架在以下两个方向取得了较好的进展：
(1)结合多目标跟踪场景对网络进行优化，这种考虑跟踪场景的网络设计对于跟踪结果有明显的提升效果。
(2)采用循环神经网络，利用历史信息来表达跟踪中的轨迹特征，这是研究跟踪问题的又一个重要的方向。
算法的发展是飞快的，目前也一直有新的优秀的跟踪算法喷涌而出，对这个方向比较感兴趣的小伙伴们加油了，大家一起来参与到多目标跟踪的领域中来吧！同时，希望这篇文章能够帮助那些对这个方向还不太了解的小伙伴尽快入门，下面是我列出的一些个人认为比较好的论文和源码。
论文
[1].C. Kim, F. Li, A. Ciptadi, andJ. Rehg. Multiple Hypothesis Tracking Revisited. In ICCV, 2015.
[2].S. Tang, B. Andres, M.Andriluka, and B. Schiele. Multi-person tracking by multicut and deep matching.In ECCV Workshops, 2016.
[3].L. Lealtaixe, C. Cantonferrer, andK. Schindler, Learning by tracking: Siamese CNN for robust targetassociation, in Proceedings of Computer Vision and Pattern Recognition. 2016.
[4].Bertinetto L,Valmadre J, Henriques, João F, et al. Fully-Convolutional Siamese Networks for Object Tracking, 2016.
[5].Q. Chu, W. Ouyang, H. Li, X.Wang, B. Liu, N. Yu. Online Multi-Object Tracking Using CNN-based SingleObject Tracker with Spatial-Temporal Attention Mechanism, ICCV 2017.
[6].Sadeghian, A. Alahi, and S.Savarese. Tracking the untrackable: Learning to track multiple cues withlong-term dependencies, ICCV2017.
[7].K. Fang, Y. Xiang, X. Li and S.Savarese, Recurrent Autoregressive Networks for Online Multi-ObjectTracking, In IEEE Winter Conference on Applications of Computer Vision2018.
[8].M. Keuper, E. Levinkov, N.Bonneel, G. Lavou´e, T. Brox, B. Andres. Efficient decomposition of imageand mesh graphs by lifted multicuts, ICCV 2015.
[9].P. Weinzaepfel, J. Revaud, Z.Harchaoui, C. Schmid. DeepFlow: large displacement optical flow with deepmatching, In ICCV 2013.
[10].S. Tang, M. Andriluka, B.Andres, and B. Schiele. Multiple People Tracking with Lifted Multi-cut andPerson Re-identification. In CVPR, 2017.
[11].C. Kim, F. Li, and J. M. Rehg,Multi-object Tracking with Neural Gating Using Bilinear LSTM, inECCV 2018.
[12].Jung I, Son J, Baek M, et al.Real-Time MDNet, European Conference on Computer Vision. 2018.
源码
http://votchallenge.net/vot2016/trackers.html
https://zhuanlan.zhihu.com/p/37856765
https://github.com/martin-danelljan/ECO
https://github.com/huanglianghua/siamrpn-pytorch
https://github.com/zkisthebest/Siamese-RPN
https://github.com/marsmarcin/Da-SiamRPN_No_vot-toolkit
https://github.com/foolwood/DaSiamRPN
https://www.cnblogs.com/wangyong/p/8523814.html
https://handong1587.github.io/deep_learning/2015/10/09/tracking.html
https://blog.csdn.net/StayFoolish_Fan/article/details/80432531
https://github.com/makalo/Siamese-RPN-tensorflow

目标跟踪算法
一．互相关运算
给你一张我的正脸照（没有经过美颜处理的），你该如何在人群中找到我呢？一种最直观的方案就是：“谁长得最像就是谁”。但是对于计算机来说，如何衡量“长得像”，并不是个简单的问题。这就涉及一种基本的运算——互相关（cross-correlation）。互相关运算可以用来度量两个信号之间的相似性。在离散的图像空间中，它的数学定义是这样的：
h和 f分别为核和图像，代表着要搜索的目标模版和存在要搜索的目标的图像。如果这个公式对你来说有点难以理解，那你又能否记起离散图像空间卷积运算的定义：
从公式看，它俩不就是把 h水平、垂直分别翻转一下的关系嘛！实际上，在很多机器学习库的实现中，所谓的“卷积”就是通过互相关运算来实现的——反正卷积核中的所有参数都是通过优化得到的、物理意义不明的值，它要做的仅仅是“在卷积核合适的位置学习合适的值”。严格使用卷积运算学习得到的核，等价于使用互相关运算学习到的核的180度翻转。
互相关运算让得以衡量 h与 f的相似度，互相关得到的响应图中每个像素的响应高低代表着每个位置相似度的高低。假设目标存在于新一帧图像 f中的话，那么在 h和 f对得最齐的地方就应该是目标中心的位置了！
一些难点：目标的形状、大小甚至身处的环境都是在不断发生变化的。在考虑这些变数的同时，如何学习目标不变的那些特性，从而准确地进行定位呢？或者说，如何让核 h能够通过与 f的互相关运算来最有效地得到响应呢？这也就是单目标跟踪主流方法所尝试的思路。
定义则是响应图的ground truth。因为处理的是一个连续的图像序列，所以还存在下标 i通过对上式中的 h对整个图像序列进行优化，可以让目标跟踪算法学习一个最优的相关滤波器。为了提升优化的速度，还可以把 h和f 投射到傅里叶频域。空域中的互相关运算在频域中变成了逐项相乘，优化目标也就变了。
它等价于：
那么对于整个序列而言，可以解出最优的：
但这并不一定对于每一帧图像都是最优的。为了让随着序列的进行而适应性地进行更新，可以递归式地定义不断更新中的：
二．在线跟踪（Online Tracking）和离线跟踪（Offline Tracking）
通过调整更新学习率参数 η，可以让算法学得具有高鲁棒性并且能够快速适应目标外观变化的。上述的过程就是首次在单目标跟踪问题上使用相关滤波的工作——MOSSE[1])（Minimum Output Sum of Squared Error, CVPR10, F. Henriques et al.）的基本思路。
多目标跟踪算法又可分为在线跟踪（Online Tracking）和离线跟踪（Offline Tracking）。在线跟踪要求处理每一帧时，决定当前帧的跟踪结果时只能利用当前帧和之前的帧中的信息，也不能根据当前帧的信息来修改之前帧的跟踪结果。离线跟踪则允许利用之后的帧的信息从而获得全局最优解。离线追踪的设定也不太适合实际应用场景，但是以一种“batch”的形式进行的离线跟踪（每次得到若干帧，在这些帧中求全局最优）也是可行的，只是会导致一点延迟。
按照处理方式分类。上：在线跟踪；下：离线跟踪
三．匈牙利与Kalman filter
主流的目标跟踪算法都是基于Tracking-by-Detecton策略，即基于目标检测的结果来进行目标跟踪。DeepSORT运用的就是这个策略，DeepSORT对人群进行跟踪，每个bbox左上角的数字是用来标识某个人的唯一ID号。
这里就有个问题，如果视频中不同时刻的同一个人，位置发生了变化，那么是如何关联上的呢？答案就是匈牙利算法和卡尔曼滤波。
· 匈牙利算法可以告诉当前帧的某个目标，是否与前一帧的某个目标相同。
· 卡尔曼滤波可以基于目标前一时刻的位置，来预测当前时刻的位置，并且可以比传感器（在目标跟踪中即目标检测器，比如Yolo等）更准确的估计目标的位置。
匈牙利算法（Hungarian Algorithm）
首先，先介绍一下什么是分配问题（Assignment Problem）：假设有N个人和N个任务，每个任务可以任意分配给不同的人，已知每个人完成每个任务要花费的代价不尽相同，那么如何分配可以使得总的代价最小。
举个例子，假设现在有3个任务，要分别分配给3个人，每个人完成各个任务所需代价矩阵（cost matrix）如下所示（这个代价可以是金钱、时间等等）：
怎样才能找到一个最优分配，使得完成所有任务花费的代价最小呢？
匈牙利算法（又叫KM算法）就是用来解决分配问题的一种方法，它基于定理：
如果代价矩阵的某一行或某一列同时加上或减去某个数，则这个新的代价矩阵的最优分配仍然是原代价矩阵的最优分配。
算法步骤（假设矩阵为NxN方阵）：
1. 对于矩阵的每一行，减去其中最小的元素
2. 对于矩阵的每一列，减去其中最小的元素
3. 用最少的水平线或垂直线覆盖矩阵中所有的0
4. 如果线的数量等于N，则找到了最优分配，算法结束，否则进入步骤5
5. 找到没有被任何线覆盖的最小元素，每个没被线覆盖的行减去这个元素，每个被线覆盖的列加上这个元素，返回步骤3
卡尔曼滤波（Kalman Filter）
卡尔曼滤波被广泛应用于无人机、自动驾驶、卫星导航等领域，简单来说，其作用就是基于传感器的测量值来更新预测值，以达到更精确的估计。
假设要跟踪小车的位置变化，如下图所示，蓝色的分布是卡尔曼滤波预测值，棕色的分布是传感器的测量值，灰色的分布就是预测值基于测量值更新后的最优估计。
· 协方差(Covariance )：表示目标位置信息的不确定性，由8x8的对角矩阵表示，矩阵中数字越大则表明不确定性越大，可以以任意值初始化。
· 卡尔曼滤波分为两个阶段：(1) 预测track在下一时刻的位置，(2) 基于detection来更新预测的位置。
下面将介绍这两个阶段用到的计算公式。（这里不涉及公式的原理推导，因为我也不清楚原理(ಥ_ಥ) ，只是说明一下各个公式的作用）

文章目录
多目标跟踪算法
一、多目标跟踪任务
1.1 数据集
1.2 评价指标
二、多目标跟踪算法分类
三、基于目标检测的多目标跟踪
2.1 基于轨迹预测的目标跟踪算法
2.2 基于目标特征建模
四、多目标跟踪算法
4.1 DeepSort
4.2 Motdt
4.3 Towards Real-Time Multi-Object Tracking

多目标跟踪算法
一、多目标跟踪任务
1.1 数据集

MOT Challenge

2015年、2016年、2017年数据，包括行人和车辆

1.2 评价指标

所有出现的目标都要及时能够找到；
目标位置要尽可能与真实目标位置一致；
每个目标都应该被分配一个独一无二的ID，并且该目标分配的这个ID在整个序列中保持不变。





二、多目标跟踪算法分类


DBT(Detection Based  Tracking)（如上图左层所示）是指在跟踪之前每一幅图像中的目标信息都事先经过检测算法得到。它首先检测目标，然后链接到已有的轨迹中。这种策略也通常被称为“tracking -by- detection”。跟踪目标的数量，跟踪目标的类型全部由检测算法的结果来决定，无法预知。也就是说MOT过程包含一个独立的detection 过程。这种方法性能比较依赖于检测算法的好坏。
DFT(Detection Free Tracking )(如上图右层所示）需要人工标定第一帧图像中的目标，之后边检测边跟踪目标。DBT 和DFT相比较，DBT使用的更多。原因在于DFT 目标需要人工标定，对于非第一帧出现的目标或者中间帧消失的目标没办法处理。
三、基于目标检测的多目标跟踪

跟踪成功：在上一帧中的N个目标轨迹中找到了本次检测到的目标。
新目标出现：在上一帧中的N个目标轨迹中没有找到本次检测到的目标
目标消失：在上一帧中存在某个目标，但这一帧并没有与之关联的目标

2.1 基于轨迹预测的目标跟踪算法
先预测目标的下一帧会出现的位置，然后让真实的检测结果与预测的位置进行对比关联。

跟踪预测方法

卡尔曼滤波

粒子滤波

均值漂移算法
数据关联算法

多假设跟踪方法

关联滤波器方法

匈牙利算法

马尔可夫链蒙特卡罗方法

贪婪关联算法

2.2 基于目标特征建模
对于每帧，每个检测到的目标，先利用卷积神经网络提取表观特征（可以理解为该目标的一种特征编码），然后计算每个目标特征之间的余弦距离，进行关联匹配。



流程



四、多目标跟踪算法
4.1 DeepSort
deepsort是一种在检测的基础上，将检测框与跟踪器关联匹配的方式实现跟踪。

三个重要模块：

（1）运动状态估计：(u,v,r,h;x,y,r,h)，u,v为坐标点，r为宽高比，h为高度；后面四个分量分别对应前四个变量的改变量。

（2）跟踪器的创建与移除：如果连续三帧跟踪匹配成功，则认为是新目标，新建跟踪器。如果未匹配成功帧数大于一定帧数，则认为目标丢失，删除跟踪器。

（3）指派问题（多目标匹配）：卡尔曼预测结果与检测结果的距离。特征关联，前几帧与当前帧特征的距离。两个距离加权得到最终距离。距离最小的检测框与跟踪框匹配。
级联匹配的流程：


跟踪算法流程：

（1）检测器（Yolov3等）检测当前帧目标，得到目标的bounding-box和conference。

（2）利用conference抑制部分检测框，得到滤除后的检测框。并利用深度神经网络提取各个检测目标的特征。

（3）利用上一帧跟踪器的跟踪框，使用kalman滤波，预测当前帧目标的位置，这里称为预测框。其中每个跟踪器中保存了各自目标的历史特征。

（4）级联匹配，将会得到，检测器和跟踪器匹配上的$M$，未匹配上的检测框$U$，未匹配上的跟踪器。

（5）匹配上的检测器和跟踪器，用检测器得到的新坐标值更新卡尔曼滤波器的参数；未匹配上的检测框，先建立一个虚拟的跟踪器，保存检测框的坐标以及特征，如果连续三帧这个跟踪器均跟上，才认为是新的目标；未匹配上的跟踪器，则age+1，如果age>Amax，则删除跟踪器。

4.2 Motdt
MOTDT主要利用将检测和跟踪框作为候选框的方法，解决了检测不可靠的问题。其有几个重要的结构与公式：

实时目标分类------R-FCN



（1）网络输入：图片，输出为：Score maps。

（2）将检测框和卡尔曼滤波预测的跟踪框作为候选框，在score maps中切出ROI区域。并将这个ROI区域划分为k*k个区域，通过下式计算类别概率。



训练阶段，是目标的区域标签为1，非目标区域标签为0。测试阶段，选择奖ROI划分为k*k个框的作用为防止当ROI为目标的一部分时，得分很高，导致错误分类。


跟踪置信度和得分函数

跟踪轨迹的候选是通过卡尔曼滤波预测得到的，但是如果连续很多帧没有匹配到检测框的话，跟踪的结果可靠程度就会下降，因此引入一个跟踪置信度。



$L_{det}$​表示与跟踪器相关联的的检测框个数，$L_{trk}$表示距离上次匹配上检测框，已经使用了多少次跟踪预测。

得分函数：




外观表示和REID特征

使用REID网络来进行外观表示，网络的骨架使用GoogLeNet，接上k个分支全连接层。训练时构建一个triplet，$T={⟨I_i,I_j,I_k⟩}$，其中$⟨I_i​,I_j​⟩$是同一人正确配对，$⟨I_i​,I_k​⟩$是来自不同人的错误配对，通过训练使得正确配对的欧式距离小于错误配对：




数据关联

1、首先使用检测的候选进行数据关联，只取REID特征欧式距离小于阈值$τ_d​$的。

2、利用IOU进行关联，配对剩下的检测候选和跟踪候选里面，阈值小于$τ_{IOU​}$的；只有当跟踪轨迹匹配上了检测候选，才更新外观表示。

3、将剩下的未配对的检测候选，生成新的跟踪轨迹。


算法步骤：



（1）使用R-FCN得到Score map，初始化$C_{det} = D_k$,$C_{trk} = \phi$.

（2）利用上一帧的坐标，通过卡尔曼滤波得到预测框，更新$C_{trk}$。

（3）将更新后的$C_{det}$和$C_{trk}$作为候选框，计算候选框和跟踪框的得分$S$，然后，使用非极大值抑制，并滤掉$s$小于阈值的$C_{det}$和$C_{trk}$。

（4）利用REID训练的网络提取更新后的$C_{det}$检测框的特征$F_{det}$。

（5）数据匹配：1)利用特征计算跟踪器特征$F_{trk}$与检测器特征$F_{det}$间的距离；2)将剩下的检测器$F_{trk}$和跟踪器$F_{det}$使用IoU关联；3)将剩下的没有匹配上的检测器生成新的跟踪轨迹。将最终剩下的跟踪器赋给最终的跟踪结果，并把相应的特征保留。


4.3 Towards Real-Time Multi-Object Tracking
传统的Tracking by detection一般是先检测，再关联，关联过程提取特征与检测过程提取特征重复。作者针对这个问题提出了一种将检测和关联任务重的外观表示作为多任务学习。JDE模型：



目标检测有两个loss，前景和背景分类的$L_{\alpha}$，边界框回归$L_{\beta}$。
跟踪的外观表示的loss则采用度量学习，同一目标尽量接近，不同目标尽量远离，采用triplet loss：


总的Loss：


算法步骤：

（1）当前帧图像输入JDE，得到输出边框和相应的外观嵌入。

（2）卡尔曼滤波根据轨迹预测当前帧的位置。

（3）计算观测值的嵌入与之前存在的轨迹池中的嵌入之间的关联矩阵。 使用匈牙利算法将观测分配给轨迹。

（4）分配到各个轨迹的观测值与卡尔曼预测的位置比较，当观测值在空间上与预测位置相距太远，则拒绝分配。

（5）分配到观测值的跟踪器，更新kalman参数，未分配到观测值的跟踪器如果超过一定时间，删除该跟踪器。