前言
目标跟踪是计算机视觉领域中研究的热点之一，分为单目标跟踪与多目标跟踪。前者跟踪视频画面中的单个目标，后者则同时跟踪视频画面中的多个目标，得到这些目标的运动轨迹。        
基于视觉的多目标跟踪在近年来越来越多地成为计算机视觉领域的研究重点，主要是因为其在智能监控、动作与行为分析、自动驾驶、虚拟现实和娱乐互动等领域都有重要的应用。例如，在自动驾驶系统中，目标跟踪算法要对运动的车、行人、其他动物的运动进行跟踪，对它们在未来的位置、速度等信息作出预判；在虚拟现实领域里，需要根据摄像头捕捉到的人物动作和轨迹，实现人机交互的目的。
那么，跟踪算法有哪些主要分支？不同的跟踪算法是如何实现的呢？让我们带着这些问题开始多目标跟踪领域的奇幻之旅吧！
须知
多目标跟踪算法按照轨迹生成的顺序可以分为离线的多目标跟踪和在线的多目标跟踪算法。
离线方式的多目标跟踪算法通常构造为图模型。其中，设计和计算检测之间的相似度或者距离度量是决定图模型构造正确性的关键。在线方式的多目标跟踪算法根据当前检测观测，计算与已有轨迹的匹配关系。
综上，计算合适的匹配度量决定了匹配的正确性。因此，无论是离线方式的多目标跟踪还是在线方式的多目标跟踪算法，学习检测结果的特征并计算匹配相似度或者距离度量都是多目标跟踪算法的关键步骤。
基于深度学习的多目标跟踪算法的主要任务是优化检测之间相似性或距离度量的设计。根据学习特征的不同，基于深度学习的多目标跟踪可以分为基于深度表观特征学习的多目标跟踪，基于深度相似性度量学习的多目标跟踪，以及基于深度高阶特征匹配的多目标跟踪，如图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

文章目录
目标跟踪、单目标跟踪、多目标跟踪的概念
欧氏距离、马氏距离、余弦距离
欧氏距离
马氏距离
余弦距离
SORT算法原理
SORT算法中的匈牙利匹配算法
最大匹配的匈牙利算法
指派问题中的匈牙利算法
预测模型（卡尔曼滤波器）
数据关联（匈牙利匹配）
目标丢失问题的处理
SORT算法过程
deep SORT算法原理
状态估计
轨迹处理
分配问题的评价指标
级联匹配
深度表观描述子
算法总结

目标跟踪、单目标跟踪、多目标跟踪的概念
目标跟踪分为静态背景下的目标跟踪和动态背景下的目标跟踪。

静态背景下的目标跟踪:

静态背景下的目标跟踪指摄像头是固定的，其采集的视野中背景是静止的，如在十字路口的固定摄像头。

动态背景下的目标跟踪:

摄像头采集的视野中背景和目标都是在变化的。
目标跟踪又分为单目标跟踪和多目标跟踪。

单目标跟踪:

在视频的初始帧画面上框出单个目标，预测后续帧中该目标的大小与位置。典型算法有Mean shift（用卡尔曼滤波、粒子滤波进行状态预测）、TLD（基于在线学习的跟踪）、KCF（基于相关性滤波）等。

多目标追踪:

不像单目标追踪一样先在初始帧上框出单个目标，而是追踪多个目标的大小和位置，且每一帧中目标的数量和位置都可能变化。此外，多目标的追踪中还存在下列问题:

处理新目标的出现和老目标的消失；

跟踪目标的运动预测和相似度判别，即上一帧与下一帧目标的匹配；

跟踪目标之间的重叠和遮挡处理；

跟踪目标丢失一段时间后再重新出现的再识别。
欧氏距离、马氏距离、余弦距离
欧氏距离
在数学中，欧几里得距离或欧几里得度量是欧几里得空间中两点间“普通”（即直线）距离。

假设二维空间中有点（x1,y1）和（x2,y2），则这两点的欧氏距离为:

$\rho=\sqrt{\left(x_{2}-x_{1}\right)^{2}+\left(y_{2}-y_{1}\right)^{2}}$
马氏距离
马氏距离（Mahalanobis distance）数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法。与欧氏距离不同，马氏距离考虑到各种特性之间的联系，并且与测量尺度无关。

对于一个均值为:

$\mu=\left(\mu_{1}, \mu_{2}, \mu_{3}, \dots, \mu_{p}\right)^{T}$

协方差矩阵为Σ的多变量矢量:

$x=\left(x_{1}, x_{2}, x_{3}, \dots, x_{p}\right)^{T}$

其马氏距离为:

$D_{M}(x)=\sqrt{(x-\mu)^{T} \Sigma^{-1}(x-\mu)}$

马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为Σ的随机变量x与y的差异程度:

$d(\vec x, \vec y)=\sqrt{(\vec x-\vec y)^{T} \Sigma^{-1}(\vec x-\vec y)}$

如果协方差矩阵为单位矩阵（或者说去掉协方差矩阵），马氏距离就退化为欧氏距离。如果协方差矩阵为对角阵，其也可称为正规化的马氏距离:

$d(\vec x, \vec y)=\sqrt{\sum_{i=1}^{p} \frac{\left(x_{i}-y_{i}\right)^{2}}{\sigma_{i}^{2}}}$

其中σi是xi的标准差。

协方差的物理意义:

在概率论中，两个随机变量X与Y之间的相互关系有3种情况:正相关、负相关、不相关（这里的相关都是指线性相关）。

我们可以定义一个表示X, Y 相互关系的数字特征，也就是协方差:

$cov(X, Y)=E(X-E X)(Y-E Y)$

当cov（X, Y）>0时，表明X与Y正相关；当cov（X, Y）<0时，表明X与Y负相关；当cov（X, Y）=0时，表明X与Y不相关。

使用欧式距离衡量两个变量，距离近就一定相似吗？

如果两个变量的度量尺度不同，如身高和体重，身高用毫米计算，而体重用千克计算。显然差10mm的身高与差10kg的体重是完全不同的。但在普通的欧氏距离中，这将会算作相同的差距。

如果使用归一化后的欧氏距离，两个变量的欧氏距离近就一定相似吗？

归一化可以消除不同变量间的度量尺度不同的问题，但是不同变量之间的方差还是不一样。第一个类别均值为0，方差为0.1，第二个类别均值为5，方差为5。那么一个值为2的点属于第一类的概率大还是第二类的概率大？距离上说应该是第一类，但是直觉上显然是第二类，因为第一类不太可能到达2这个位置。因此，在一个方差较小的维度下很小的差别就有可能成为离群点。

如果维度间不独立同分布，样本点与欧氏距离近的样本点同类的概率一定会更大吗？

如果维度间不是独立同分布的，那么两个点即使距离均值点距离相同，但显然更接近整体分布点集的点与该点集同类的概率更大。

马氏距离的几何意义:

马氏距离就是将变量按照主成分进行旋转，让维度间相互独立，然后进行标准化，使不同的维度独立同分布。由于主成分就是特征向量方向，每个方向的方差就是对应的特征值，所以只需要按照特征向量的方向旋转，然后缩放特征值的倍数。这样，离群点就被成功分离，这时候的新坐标系下的欧式距离就是马氏距离。
余弦距离
余弦距离，也称为余弦相似度，是用N维空间中两点与原点连接线段之间夹角的余弦值作为衡量两个个体间差异的大小的度量。余弦距离越大，表示夹角越小，那么两点越相似。如果余弦距离为1（最大值），那么表示两者非常相似。注意这里只能说明两点非常相似，并不一定相同。

余弦距离公式:

$sim(X, Y)=\cos \theta=\frac{\vec x \cdot \vec y}{||x|| \cdot ||y||}$

向量a和向量b点乘的公式:

$a \cdot b=a_{1} b_{1}+a_{2} b_{2}+\ldots+a_{\mathrm{n}} b_{n}$

余弦距离的意义:

当两点夹角为零时，表示两点的各个维度的值所占的比例相同。比如（2，2，2）和（6，6，6），（1，2，3）和（3，6，9）。
SORT算法原理
论文:Simple Online and Realtime Tracking

论文地址:https://arxiv.org/pdf/1602.00763.pdf 。

代码地址:https://github.com/abewley/sort 。
在sort算法中，目标检测模型的性能是影响追踪效果的一个关键因素。SORT算法全称为Simple Online And Realtime Tracking, 对于tracking-by-detection的多目标跟踪方法，更多依赖的是其目标检测模型的性能的好坏。尽管只是简单的结合了Kalman滤波追踪和匈牙利指派算法，效果却可以匹配2016年的SOTA算法。另外，由于本文的算法复杂度低，追踪器可以实现260Hz的速度，比前者快了20倍。

多目标追踪问题可以被看成是数据关联问题，目的是在视频帧序列中进行跨帧检测结果的关联。作者没有在目标追踪过程中使用任何的目标外观特征，而是仅使用检测框的位置和大小进行目标的运动估计和数据关联。另外，没有考虑遮挡问题，也没有通过目标的外观特征进行目标重识别，作者一切的核心就是围绕处理速度要快，要能够实时应用。

作者使用CNN进行目标检测，使用kalman滤波进行目标运动状态估计，使用匈牙利匹配算法进行位置匹配。文章主要关注行人目标的追踪。
SORT算法中的匈牙利匹配算法
最大匹配的匈牙利算法
该算法详细原理可以看我的另一篇专门介绍匈牙利算法最大匹配原理的博客。

我们知道一个二分图可以用矩阵的形式来表示，如:
graph_1 = [(0, 0, 0, 0, 1, 0, 1, 0),
           (0, 0, 0, 0, 1, 0, 0, 0),
           (0, 0, 0, 0, 1, 1, 0, 0),
           (0, 0, 0, 0, 0, 0, 1, 1),
           (1, 1, 1, 0, 0, 0, 0, 0),
           (0, 0, 1, 0, 0, 0, 0, 0),
           (1, 0, 0, 1, 0, 0, 0, 0),
           (0, 0, 0, 1, 0, 0, 0, 0)]

上例表示这个二分图的U集合有8个点，V集合也有8个点，当两点之间有边时对应位置的值为1，否则为0。

匈牙利算法的目标是从二分图中找出一个最大匹配，即匹配边最多的匹配方式。
指派问题中的匈牙利算法
进一步地，我们可以将二分图变成下面的形式:
     A    B    C    D
甲   2    15   13   4
乙   10   4    14   15
丙   9    14   16   13
丁   7    8    11   9

此时U集合中任意点和V集合中任意点都有边，但边的代价不同。此时我们的目标是，在矩阵中选取n个元素（即n条不同代价的边），使得每行每列各有1个元素（U集合和V集合中的每一个点都有配对点），且边的代价和最小。

我们将上述矩阵赋予一个实际问题的含义：有n项不同的任务，需要n个人分别完成其中的1项，每个人完成任务的时间不一样。于是就有一个问题，如何分配任务使得花费时间最少。

最优解性质:

若从矩阵的一行（列）各元素中分别减去该行（列）的最小元素，得到一个归约矩阵，这个规约矩阵的最优解与原矩阵的最优解相同。
指派问题的匈牙利算法的基本思路:

通过行/列变换让规约（费用）矩阵的每行和每列都出现0；
找出不同行不同列的n个0；
这些0对应的边就是最优指派（代价最少）。

指派问题的匈牙利算法的主要步骤:

先对规约（费用）矩阵先作行变换，再作列变换。行变换即费用矩阵的每一行的各个元素分别减去该行的最小元素。列变换即费用矩阵的每一列的各个元素分别减去该列的最小元素，有0的列则无需作列变换；
在经过行变换和列变换的费用矩阵中寻找n个不同行不同列的0元素。如果找到，则这n个不同行不同列的0元素位置即对应最优指派。否则，进行下一步骤。一般使用标记法来寻找n个不同行不同列的0元素：

依次检查新费用矩阵的各行，找出只有一个没有加标记的0元素的行，并将这个0元素加上标记，而与这个0元素在同一列的0元素全划去；

依次检查新费用矩阵的各列，找出只有一个没有加标记的0元素的列，并将这个0元素加上标记，而与这个0元素在同一行的0元素全划去。
对新费用矩阵进行调整：对每一个加了标记的0元素画一条横线或竖线，使得这些横线和竖线覆盖全部0元素；在这些横线和竖线没有经过的元素中找出最小的元素；未画横线的各行元素减去这个最小的数，画竖线的各列元素加上这个最小的数；重新在费用矩阵中找出n个不同行不同列的0元素，从而找出最优指派（代价最少）。

指派问题的匈牙利算法求解举例:

原始矩阵如下，该矩阵U集合的点为甲、乙、丙、丁，V集合的点为A、B、C、D。矩阵中每个值是每条边的代价。
    A    B    C    D
甲  90   75   75   80
乙  35   85   55   65
丙  125  95   90   105
丁  45   110  95   115

首先每行减去每行的最小值，矩阵变为:
    A    B    C    D
甲  15   0    0    5
乙  0    50   20   30
丙  35   5    0    15
丁  0    65   50   70

然后每列减去每列的最小值，矩阵变为:
    A    B    C    D
甲  15   0    0    0
乙  0    50   20   25
丙  35   5    0    10
丁  0    65   50   65

现在查找行或列中含有元素0的行或列，用最少数量的水平+垂直线覆盖所有的0。发现只要第一行、第一列、第三列就可以覆盖所有的0，线数量为3，小于U集合中点个数4。没有被覆盖的元素有50，5，65，25，10，65，其中最小元素为5。那么我们让没有被覆盖的每行减去最小值5，被覆盖的每列加上最小值5，然后继续寻找用最少数量的水平+垂直线覆盖所有的0。

第二、三、四行没有被覆盖，每行减去最小值5。
    A    B    C    D
甲  15   0    0    0
乙  -5   45   15   20
丙  30   0    -5   5
丁  -5   60   45   60

第一、三列被覆盖，每行加上最小值5。
    A    B    C    D
甲  20   0    5    0
乙  0    45   20   20
丙  35   0    0    5
丁  0    60   50   60

现在我们可以用第一行、第三行、第一列覆盖所有的0，线数量为3，仍小于U集合中点个数4。没被覆盖的元素有45，20，20，60，50，60，最小值元素为20。那么我们让没有被覆盖的每行减去最小值20，被覆盖的每列加上最小值20，然后继续寻找用最少数量的水平+垂直线覆盖所有的0。

第二、四行没有被覆盖，每行减去最小值20。
    A    B    C    D
甲  20   0    5    0
乙  -20  25   0    0
丙  35   0    0    5
丁  -20  40   30   40

第一列被覆盖，每行加上最小值20。
    A    B    C    D
甲  40   0    5    0
乙  0    25   0    0
丙  55   0    0    5
丁  0    40   30   40

现在我们用第一行、第二行、第三行、第四行可以覆盖所有的0。线数量为4等于U集合中点个数4。找到不同行不同列的n个0。即丁A、丙B、乙C、D甲位置的4个0。

上面矩阵找到的最优解和原始矩阵的最优解等同。原始矩阵的最优指派（最小代价）就是这四个位置上的代价之和，即45，95，55，80。
在SORT算法中，二分图的边权值即前一帧的M个目标与后一帧的N个目标中，两两目标之间的IOU。
预测模型（卡尔曼滤波器）
作者近似地认为目标的不同帧间地运动是和其他物体及相机运动无关的线性运动。每一个目标的状态可以表示为：

$x=[u, v, s, r, \dot{u}, \dot{v}, \dot{s}]^{T}$

其中u和v分别代表目标的中心坐标，而s和r分别代表目标边界框的比例（面积）和长宽比，长宽比被认为是常数，需要保持不变。

当进行目标关联时，使用卡尔曼滤波器，用上一帧中目标的位置信息预测下一帧中这个目标的位置。若上一帧中没有检测到下一帧中的某个目标，则对于这个目标，重新初始化一个新的卡尔曼滤波器。关联完成后，使用新关联的下一帧中该目标的位置来更新卡尔曼滤波器。
数据关联（匈牙利匹配）
SORT中匈牙利匹配的原理见上面指派问题中的匈牙利匹配算法。SORT算法中的代价矩阵为上一帧的M个目标与下一帧的N个目标两两目标之间的IOU。当然，小于指定IOU阈值的指派结果是无效的（源码中阈值设置为0.3）。

此外，作者发现使用IOU能够解决目标的短时被遮挡问题。这是因为目标被遮挡时，检测到了遮挡物，没有检测到原有目标，假设把遮挡物和原有目标进行了关联。那么在遮挡结束后，因为在相近大小的目标IOU往往较大，因此很快就可以恢复正确的关联。这是建立在遮挡物面积大于目标的基础上的。
目标丢失问题的处理
如果连续Tlost帧没有实现已追踪目标预测位置和检测框的IOU匹配，则认为目标消失。实验中设置 Tlost=1，文中指出是因为没有匹配的目标所使用的均速运动假设模型效果很差，并且帧数过多的re-id问题超出了本文讨论的范围（作者主要关注逐帧的目标追踪，而不关注长时间的目标丢失再重识别问题）。另外，尽早删除已丢失的目标有助于提升追踪效率。但是这样容易导致目标ID会频繁切换，造成跟踪计数的不准确。
SORT算法过程
对第一帧使用目标检测模型进行目标检测，得到第一帧中所有目标的分类和位置（假设有M个目标），并标注一个独有id。对每个目标初始化卡尔曼滤波跟踪器，预测每个目标在下一帧的位置；

对第二帧使用目标检测模型进行目标检测，得到第二帧中所有目标的分类和位置（假设有N个目标），求第一帧M个目标和第二帧N个目标两两目标之间的IOU，建立代价矩阵，使用匈牙利匹配算法得到IOU最大的唯一匹配（数据关联部分），再去掉匹配值小于iou_threshold的匹配对；

用第二帧中匹配到的目标的位置去更新卡尔曼跟踪器，计算第二帧时的卡尔曼增益Kk，状态估计值xk，估计误差协方差Pk。并输出状态估计值xk用来计算下一帧中的预测位置。对于本帧中没有匹配到的目标重新初始化卡尔曼滤波跟踪器；

后面每一帧图像都按第一帧和第二帧的做法进行类似处理即可。
deep SORT算法原理
论文:Simple Online and Realtime Tracking With a Deep Association Metric

论文地址:https://arxiv.org/pdf/1703.07402.pdf 。

代码地址:https://github.com/nwojke/deep_sort 。
状态估计
使用一个8维空间去刻画轨迹在某时刻的状态：

$(u, v, \gamma, h, \dot{x}, \dot{y}, \dot{\gamma}, \dot{h})$

使用一个kalman滤波器预测更新轨迹，该卡尔曼滤波器采用匀速模型和线性观测模型。通过卡尔曼估计对(u, v, r, h)进行估计，u，v是物体中心点的位置，r是长宽比，h是高。运动估计对于运动状态变化不是很剧烈和频繁的物体能取得比较好的效果。

其观测变量为:

$(u, v, \gamma, h)$
轨迹处理
对于每一个追踪目标，都有一个阈值ak用于记录轨迹从上一次成功匹配到当前时刻的时间（即连续没有匹配的帧数），我们称之为轨迹。当该值大于提前设定的阈值Amax则认为该轨迹终止，直观上说就是长时间匹配不上的轨迹则认为该轨迹已经结束。

在匹配时，对于没有匹配成功的目标都认为可能产生新的轨迹。但由于这些检测结果可能是一些错误警告，所以对这种情形新生成的轨迹标注状态’tentative’，然后观查在接下来的连续若干帧（论文中是3帧）中是否连续匹配成功，是的话则认为是新轨迹产生，标注为’confirmed’，否则则认为是假性轨迹,状态标注为’deleted’。
分配问题的评价指标
在位置度量上，使用马氏距离（Mahalanobis distance）来评价卡尔曼滤波预测的状态和实际状态的匹配程度（运动匹配程度）:

$d^{(1)}(i, j)=\left(d_{j}-y_{i}\right)^{T} S_{i}^{-1}\left(d_{j}-y_{i}\right)$

上式左边表示第j个检测到的目标和第i条轨迹之间的运动匹配度，其中Si是第i条轨迹由kalman滤波器预测得到的在当前时刻观测空间的协方差矩阵，yi是轨迹在当前时刻的预测观测量，dj是第j个目标的实际状态（u,v,r,h）。

考虑到运动的连续性，可以通过该马氏距离对目标进行筛选，文中使用卡方分布的0.95分位点作为阈值 t^{(1)} =0.4877,我们可以定义一个门限函数：

$b_{i j}^{(1)}=\mathbf{1}\left[d^{(1)(i, j)} \leq t^{(1)}\right]$

当目标运动不确定性较低时，马氏距离是一个很好的关联度量。但在实际中，如相机运动时会造成马氏距离大量不能匹配，也就会使这个度量失效。因此，我们整合第二个度量标准，对每一个BBox检测框dj我们计算一个表面特征描述子：

$r_{j},\left|r_{j}\right|=1$

我们保存最新的Lk=100个轨迹的描述子，然后我们计算使用第i个轨迹和第j个轨迹的最小余弦距离（cosine distance）来衡量检测和轨迹之间的外观相似程度：

$d^{(2)}(i, j)=\min \left(1-r_{j}^{T} r_{k}^{(i)} | r_{k}^{(i)} \in R_{i}\right)$

同样的，该度量同样可以确定一个门限函数:

$b_{i, j}^{(2)}=\mathbb{1}\left[d^{(2)}(i, j) \leq t^{(2)}\right]$

最后的评价指标是上面两种距离的加权和:

$c_{i, j}=\lambda d^{(1)}(i, j)+(1-\lambda) d^{(2)}(i, j)$

$b_{i, j}=\prod_{m=1}^{2} b_{i, j}^{(m)}$

其中是λ是超参数，用于调整不同项的权重。

总之，马氏距离对于短期的预测和匹配效果很好，而最小余弦距离对于长时间丢失的轨迹而言，匹配度度量的比较有效。超参数的选择要看具体的数据集，比如文中说对于相机运动幅度较大的数据集，直接不考虑运动匹配程度。
级联匹配
如果一条轨迹被遮挡了一段较长的时间，那么在kalman滤波器的不断预测中就会导致概率弥散。那么假设现在有两条轨迹竞争同一个目标，那么那条遮挡时间长的往往得到马氏距离更小，使目标倾向于匹配给丢失时间更长的轨迹，但是直观上，该目标应该匹配给时间上最近的轨迹。

导致这种现象的原因正是由于kalman滤波器连续预测没法更新导致的概率弥散。假设本来协方差矩阵是一个正态分布，那么连续的预测不更新就会导致这个正态分布的方差越来越大，那么离均值欧氏距离远的点可能和之前分布中离得较近的点获得同样的马氏距离值。

所以本文中才引入了级联匹配的策略将遮挡时间按等级分层，遮挡时间越小的匹配等级更高，即更容易被匹配。

首先是得到追踪框集合T和检测框集合D，设置最大的Amax为轨迹最大允许丢失匹配的帧数。通过计算上面的评价指标（两种度量的加权和）得到成本矩阵，再通过级联条件，设定阈值分别对外观和位置因素进行计算，满足条件则返回1，否则返回0。然后初始化匹配矩阵为空，初始化未匹配矩阵等于D。通过匈牙利算法，对于每个属于追踪框集合的元素T，在检测框里面查找成本最低且满足阈值过滤条件的检测框作为匹配结果，同时更新匹配矩阵和非匹配矩阵。

在匹配的最后阶段还对unconfirmed和age=1的未匹配轨迹进行基于IOU的匹配。这可以缓解因为表观突变或者部分遮挡导致的较大变化。当然有好处就有坏处，这样做也有可能导致一些新产生的轨迹被连接到了一些旧的轨迹上。但这种情况较少。
深度表观描述子
预训练的网络时一个在大规模ReID数据集上训练得到的，这个ReID数据集包含1261个人的1100000幅图像，使得学到的特征很适合行人跟踪。

然后使用该预训练网络作为基础网络，构建wide ResNet，用来提取bounding box的表观特征。该网络在Nvidia GeForce GTX 1050 mobile GPU下提取出32个bounding boxes大约花费30ms，可以满足实时性要求。
算法总结
使用wide ResNet提取的特征进行匹配，大大减少了SORT中的ID switches, 经作者实验证明减少了大约45%, 在高速率视频流中也达到了很好的水准。该模型的速度主要取决于目标检测模型的速度，在匹配上面耗时很短。

简介
FairMOT是今年很火的一个多目标跟踪算法，前不久也开放了最新版本的论文，并于最近重构了开源代码，我也在实际工程视频上进行了测试，效果是很不错的。不过，官方源码没有提高实时摄像头跟踪的编程接口，我在源码的基础上进行了修改，增加了实时跟踪模块。本文介绍如何进行环境配置和脚本修改，实现摄像头跟踪（本文均采用Ubuntu16.04进行环境配置，使用Windows在安装DCN等包的时候会有很多问题，不建议使用）。
环境配置

下述环境配置需要保证用户已经安装了git和conda，否则配置pytorch和cuda会诸多不便。

首先，通过下面的git命令从Github克隆源码到本地并进入该项目。访问链接（提取码uouv）下载训练好的模型，在项目根目录下新建models目录（和已有的assets、src等目录同级），将刚刚下载好的模型文件fairmot_dla34.pth放到这个models目录下。
git clone git@github.com:ifzhang/FairMOT.git
cd FairMOT

下面，通过conda创建适用于该项目的虚拟环境（环境隔离），国内用户速度慢可以参考我conda的文章配置国内源。创建之后通过activate激活环境（该命令出错将conda换为source）。然后在当前虚拟环境下（后续关于该项目的操作都需要在该虚拟环境下）安装pytorch和cuda（这里也建议配置国内源后安装conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/cloud/pytorch）。最后，通过pip命令安装所需d的Python包（国内建议配置清华源），注意先安装cython。
conda create -n fairmot python=3.6
conda activate fairmot
conda install pytorch==1.2.0 torchvision==0.4.0 cudatoolkit=10.0
pip install cython
pip install -r requirements.txt
pip install -U opencv-python==4.1.1.26

同时，用于项目使用了DCNv2所以需要安装该包，该包只能通过源码安装，依次执行下述命令即可（安装过程报warning是正常情况，不报error就行）。
git clone https://github.com/CharlesShang/DCNv2
cd DCNv2
./make.sh
cd ../

至此，所有的环境配置已经完成，由于这里还需要使用到ffmpeg来生成视频文件，所以系统需要安装ffmpeg（Ubuntu采用apt安装即可），教程很多，不多赘述。
想要试试项目是否正常工作，可以使用下面的命令在demo视频上进行跟踪测试（初次允许需要下载dla34模型，这个模型国内下载速度还可以，我就直接通过允许代码下载的）。
cd src
python demo.py mot --input-video ../videos/MOT16-03.mp4 --load_model ../models/fairmot_dla34.pth --conf_thres 0.4

默认文件输出在项目根目录的demos文件夹下，包括每一帧的检测结果以及组合成的视频。


实时跟踪
实时跟踪主要在两个方面进行修改，一是数据加载器，二是跟踪器。首先，我们在src目录下新建一个类似于demo.py的脚本文件名为camera.py，写入和demo.py类似的内容，不过，我们把视频路径换位摄像机编号（这是考虑到JDE采用opencv进行视频读取，而opencv视频读取和摄像机视频流读取是一个接口）。具体camera.py内容如下。
import os

import _init_paths
from opts import opts
from tracking_utils.utils import mkdir_if_missing
import datasets.dataset.jde as datasets
from track import eval_seq


def recogniton():
    result_root = opt.output_root if opt.output_root != '' else '.'
    mkdir_if_missing(result_root)
    print("start tracking")
    dataloader = datasets.LoadVideo(0, opt.img_size)
    result_filename = os.path.join(result_root, 'results.txt')
    frame_rate = dataloader.frame_rate

    frame_dir = None if opt.output_format == 'text' else os.path.join(result_root, 'frame')
    eval_seq(opt, dataloader, 'mot', result_filename,
             save_dir=frame_dir, show_image=False, frame_rate=frame_rate)


if __name__ == '__main__':
    os.environ['CUDA_VISIBLE_DEVICES'] = '0'
    opt = opts().init()
    recogniton()

接着，原来JDE关于视频加载是针对真正的视频的，对于摄像头这种无限视频流，修改其帧数为无限大（很大很大的整数值即可），也就是将src/lib/datasets/dataset/jde.py中LoadVideo修改如下。
class LoadVideo:
    def __init__(self, path, img_size=(1088, 608)):
        self.cap = cv2.VideoCapture(path)
        self.frame_rate = int(round(self.cap.get(cv2.CAP_PROP_FPS)))
        self.vw = int(self.cap.get(cv2.CAP_PROP_FRAME_WIDTH))
        self.vh = int(self.cap.get(cv2.CAP_PROP_FRAME_HEIGHT))
        if type(path) == type(0):
            self.vn = 2 ** 32
        else:
            self.vn = int(self.cap.get(cv2.CAP_PROP_FRAME_COUNT))

        self.width = img_size[0]
        self.height = img_size[1]
        self.count = 0

        self.w, self.h = 1920, 1080
        print('Lenth of the video: {:d} frames'.format(self.vn))

    def get_size(self, vw, vh, dw, dh):
        wa, ha = float(dw) / vw, float(dh) / vh
        a = min(wa, ha)
        return int(vw * a), int(vh * a)

    def __iter__(self):
        self.count = -1
        return self

    def __next__(self):
        self.count += 1
        if self.count == len(self):
            raise StopIteration
        # Read image
        res, img0 = self.cap.read()  # BGR
        assert img0 is not None, 'Failed to load frame {:d}'.format(self.count)
        img0 = cv2.resize(img0, (self.w, self.h))

        # Padded resize
        img, _, _, _ = letterbox(img0, height=self.height, width=self.width)

        # Normalize RGB
        img = img[:, :, ::-1].transpose(2, 0, 1)
        img = np.ascontiguousarray(img, dtype=np.float32)
        img /= 255.0

        return self.count, img, img0

    def __len__(self):
        return self.vn  # number of frames

至此，读取视频流也通过一个粗暴的方式实现了，然后就是窗口显示了，原来项目中跟踪器只会一帧一帧写入跟踪后的结果图像，然后通过ffmpeg将这些图像组合为视频。不过，原项目已经设计了实时显示跟踪结果窗口的接口了，只需要调用track.py中的eval_seq函数时，参数show_image设置为True即可。不过，也许作者并没有测试过这个模块，这里显示会有些问题，务必将eval_seq中下述代码段进行如下修改。
if show_image:
    cv2.imshow('online_im', online_im)
    cv2.waitKey(1)

调整完成后，输入下面的命令运行跟踪脚本（命令行Ctrl+C停止跟踪，跟踪的每一帧存放在指定的output-root目录下的frame目录中）。
python camera.py mot --load_model ../models/fairmot_dla34.pth --output-root ../results


上图是我实际测试得到的运行结果，摄像头分辨率比较低并且我做了一些隐私模糊处理，不过，整个算法的实用性还是非常强的，平均FPS也有18左右（单卡2080Ti）。
补充说明
本文对FairMOT源码进行了简单粗暴的修改以实现了一个摄像头视频实时跟踪系统，只是研究FairMOT代码闲暇之余的小demo，具体代码可以在我的Github找到。

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

以 IoU 作为前后帧间目标关系度量指标；
利用卡尔曼滤波器预测当前位置；
通过匈牙利算法关联检测框到目标；
应用试探期甄别虚检；
使用 Faster R-CNN，证明检测好跟踪可以很简单。

技术方案
SORT  算法以检测作为关键组件，传播目标状态到未来帧中，将当前检测与现有目标相关联，并管理跟踪目标的生命周期。
检测
跟踪框架使用 Faster R-CNN  并应用其在 PASCAL VOC 挑战中的默认参数，只输出概率大于50%的行人检测结果而忽略其他类。

文章在实验中替换  MDP 和所提方法的检测，发现检测质量对跟踪性能有显著影响。
估计模型
目标模型，即用于将目标身份传播到下一帧的表示和运动模型。SORT  算法用一个独立于其他物体和相机运动的线性等速模型来近似每个物体的帧间位移。每个目标的状态建模为：
$\mathbf{x} = [u,v,s,r,\dot{u},\dot{v},\dot{s}]^T,$
其中 $u$ 和 $v$ 分别代表目标中心的水平和垂直像素位置，而 $s$ 和 $r$ 分别代表目标边界框的比例（面积）和纵横比。注意，纵横比被认为是常数。关联检测到目标后，用检测到的边界框更新目标状态，其中速度分量通过卡尔曼滤波器框架进行优化求解。如果没有与目标相关的检测，则使用线性速度模型简单地预测其状态而不进行校正。
数据关联
在将检测分配给现有目标时：

预测每个目标在当前帧中的新位置，估计其边界框形状；
由每个检测与现有目标的所有预测边界框之间的交并比（IoU）计算分配成本矩阵；
使用匈牙利算法对分配进行优化求解；
拒绝检测与目标重叠小于 $IOU_{min}$ 的分配。

文章发现边界框的 IoU 距离隐式处理由目标经过引起的短时遮挡。具体地说，当遮挡物盖过目标时，只检测到遮挡物。尽管隐藏目标离检测框中心更近，但 IoU 距离更倾向于具有相似比例的检测。这使得可以在不影响覆盖目标的情况下，通过检测对遮挡目标进行校正。
创建和删除轨迹标识
当目标进入和离开图像时，需要相应地创建或销毁唯一标识。对于创建跟踪程序，文中认为任何重叠小于 $IoU_{min}$ 的检测都表示存在未跟踪的目标。使用速度设置为零的边界框信息初始化跟踪器。由于此时无法观测到速度，因此速度分量的协方差用较大的值初始化，反映出这种不确定性。此外，新的跟踪器将经历一个试用期，其中目标需要与检测相关联以积累足够的证据以防止误报的跟踪。
如果 $T_{Lost}$ 帧未检测到，则终止轨迹。这可以防止跟踪器数量的无限增长以及由于无检测校正下预测时间过长而导致的定位错误。在所有实验中，$T_{Lost}$ 设为1有以下原因：

首先，等速模型对真实动力学的预测能力较差；
其次，我们主要关注逐帧跟踪，目标重识别超出本工作范畴；
此外，早期删除丢失的目标有助于提高效率。如果目标重新出现，跟踪将在新标识下隐式恢复。

sort.py
算法和程序都比较简单。程序依赖 scikit-learn 所提供的 linear_assignment 实现匈牙利匹配。KalmanFilter 由 FilterPy 提供。
matplotlib.pyplot.ion() 打开交互模式。
  # all train
  sequences = ['PETS09-S2L1','TUD-Campus','TUD-Stadtmitte','ETH-Bahnhof','ETH-Sunnyday','ETH-Pedcross2','KITTI-13','KITTI-17','ADL-Rundle-6','ADL-Rundle-8','Venice-2']
  args = parse_args()
  display = args.display
  phase = 'train'
  total_time = 0.0
  total_frames = 0
  colours = np.random.rand(32,3) #used only for display
  if(display):
    if not os.path.exists('mot_benchmark'):
      print('\n\tERROR: mot_benchmark link not found!\n\n    Create a symbolic link to the MOT benchmark\n    (https://motchallenge.net/data/2D_MOT_2015/#download). E.g.:\n\n    $ ln -s /path/to/MOT2015_challenge/2DMOT2015 mot_benchmark\n\n')
      exit()
    plt.ion()
    fig = plt.figure() 
  
  if not os.path.exists('output'):
    os.makedirs('output')

对于每个序列，创建一个 SORT 跟踪器实例。

加载序列的检测数据。检测框格式为[x1,y1,w,h]。
  for seq in sequences:
    mot_tracker = Sort() #create instance of the SORT tracker
    seq_dets = np.loadtxt('data/%s/det.txt'%(seq),delimiter=',') #load detections
    with open('output/%s.txt'%(seq),'w') as out_file:
      print("Processing %s."%(seq))
      for frame in range(int(seq_dets[:,0].max())):
        frame += 1 #detection and frame numbers begin at 1
        dets = seq_dets[seq_dets[:,0]==frame,2:7]
        dets[:,2:4] += dets[:,0:2] #convert to [x1,y1,w,h] to [x1,y1,x2,y2]
        total_frames += 1

skimage.io.imread 从文件加载图像。
        if(display):
          ax1 = fig.add_subplot(111, aspect='equal')
          fn = 'mot_benchmark/%s/%s/img1/%06d.jpg'%(phase,seq,frame)
          im =io.imread(fn)
          ax1.imshow(im)
          plt.title(seq+' Tracked Targets')

update 由检测框更新轨迹。trackers命名有问题。
        start_time = time.time()
        trackers = mot_tracker.update(dets)
        cycle_time = time.time() - start_time
        total_time += cycle_time

matplotlib.axes.Axes.add_patch 将补丁p添加到轴补丁列表中；剪辑框将设置为 Axes 剪切框。 如果未设置变换，则将其设置为 transData。返回补丁。

matplotlib.axes.Axes.set_adjustable 定义 Axes 将更改哪个参数以实现给定面。
        for d in trackers:
          print('%d,%d,%.2f,%.2f,%.2f,%.2f,1,-1,-1,-1'%(frame,d[4],d[0],d[1],d[2]-d[0],d[3]-d[1]),file=out_file)
          if(display):
            d = d.astype(np.int32)
            ax1.add_patch(patches.Rectangle((d[0],d[1]),d[2]-d[0],d[3]-d[1],fill=False,lw=3,ec=colours[d[4]%32,:]))
            ax1.set_adjustable('box-forced')

        if(display):
          fig.canvas.flush_events()
          plt.draw()
          ax1.cla()

  print("Total Tracking took: %.3f for %d frames or %.1f FPS"%(total_time,total_frames,total_frames/total_time))
  if(display):
    print("Note: to get real runtime results run without the option: --display")

Sort
Sort 是一个多目标跟踪器，管理多个 KalmanBoxTracker 对象。
  def __init__(self,max_age=1,min_hits=3):
    """
    Sets key parameters for SORT
    """
    self.max_age = max_age
    self.min_hits = min_hits
    self.trackers = []
    self.frame_count = 0

update
参数dets：格式为[[x1,y1,x2,y2,score],[x1,y1,x2,y2,score],...]的 numpy 检测数组。

要求：即使空检测，也必须为每个帧调用此方法一次。返回一个类似的数组，其中最后一列是对象 ID。

注意：返回的对象数可能与提供的检测数不同。

update 的输入参数dets为 numpy.array，然而 KalmanBoxTracker 要求的输入为列表。

从现有跟踪器获取预测位置。

predict 推进状态向量并返回预测的边界框估计。
在当前帧逐个预测轨迹位置，记录状态异常的跟踪器索引。trks存储跟踪器的预测，不幸与下面的跟踪器重名。
    self.frame_count += 1
    #get predicted locations from existing trackers.
    trks = np.zeros((len(self.trackers),5))
    to_del = []
    ret = []
    for t,trk in enumerate(trks):
      pos = self.trackers[t].predict()[0]
      trk[:] = [pos[0], pos[1], pos[2], pos[3], 0]
      if(np.any(np.isnan(pos))):
        to_del.append(t)

numpy.ma.masked_invalid 屏蔽出现无效值的数组（NaN 或 inf）。

numpy.ma.compress_rows 压缩包含掩码值的2-D 数组的整行。这相当于np.ma.compress_rowcols(a, 0)，有关详细信息，请参阅 extras.compress_rowcols。

reversed 返回反向 iterator. seq 必须是具有 __reversed__() 方法的对象，或者支持序列协议（__len__() 方法和 __getitem__() 方法，整数参数从0开始）。
逆向删除异常的跟踪器，防止破坏索引。压缩能够保证在数组中的位置不变。

associate_detections_to_trackers 将检测分配给跟踪对象（均以边界框表示）。返回3个列表：matches，unmatched_detections和unmatched_trackers。
    trks = np.ma.compress_rows(np.ma.masked_invalid(trks))
    for t in reversed(to_del):
      self.trackers.pop(t)
    matched, unmatched_dets, unmatched_trks = associate_detections_to_trackers(dets,trks)

使用分配的检测更新匹配的跟踪器。为什么不通过matched存储的索引选择跟踪器？

update 使用观测边界框更新状态向量。
    #update matched trackers with assigned detections
    for t,trk in enumerate(self.trackers):
      if(t not in unmatched_trks):
        d = matched[np.where(matched[:,1]==t)[0],0]
        trk.update(dets[d,:][0])

由未匹配的检测创建和初始化新的跟踪器。
    #create and initialise new trackers for unmatched detections
    for i in unmatched_dets:
        trk = KalmanBoxTracker(dets[i,:]) 
        self.trackers.append(trk)

get_state 返回当前边界框估计值。

ret格式为[[x1,y1,x2,y2,score],[x1,y1,x2,y2,score],...]。
自后向前遍历，仅返回在当前帧出现且命中周期大于self.min_hits（除非跟踪刚开始）的跟踪结果；如果未命中时间大于self.max_age则删除跟踪器。

hit_streak忽略目标初始的若干帧。
    i = len(self.trackers)
    for trk in reversed(self.trackers):
        d = trk.get_state()[0]
        if((trk.time_since_update < 1) and (trk.hit_streak >= self.min_hits or self.frame_count <= self.min_hits)):
          ret.append(np.concatenate((d,[trk.id+1])).reshape(1,-1)) # +1 as MOT benchmark requires positive
        i -= 1
        #remove dead tracklet
        if(trk.time_since_update > self.max_age):
          self.trackers.pop(i)

    if(len(ret)>0):
      return np.concatenate(ret)
    return np.empty((0,5))

associate_detections_to_trackers
这里命名不准确，应该是将检测框关联到跟踪目标（objects）或者轨迹（tracks），而不是跟踪器（trackers）。

跟踪器数量为0则直接构造结果。
  if(len(trackers)==0):
    return np.empty((0,2),dtype=int), np.arange(len(detections)), np.empty((0,5),dtype=int)
  iou_matrix = np.zeros((len(detections),len(trackers)),dtype=np.float32)

iou 不支持数组计算。

逐个计算两两间的交并比，调用 linear_assignment 进行匹配。
  for d,det in enumerate(detections):
    for t,trk in enumerate(trackers):
      iou_matrix[d,t] = iou(det,trk)
  matched_indices = linear_assignment(-iou_matrix)

记录未匹配的检测框及轨迹。
  unmatched_detections = []
  for d,det in enumerate(detections):
    if(d not in matched_indices[:,0]):
      unmatched_detections.append(d)
  unmatched_trackers = []
  for t,trk in enumerate(trackers):
    if(t not in matched_indices[:,1]):
      unmatched_trackers.append(t)

过滤掉 IoU 低的匹配。
  #filter out matched with low IOU
  matches = []
  for m in matched_indices:
    if(iou_matrix[m[0],m[1]]<iou_threshold):
      unmatched_detections.append(m[0])
      unmatched_trackers.append(m[1])
    else:
      matches.append(m.reshape(1,2))

初始化用列表，返回值用 Numpy.array。
  if(len(matches)==0):
    matches = np.empty((0,2),dtype=int)
  else:
    matches = np.concatenate(matches,axis=0)

  return matches, np.array(unmatched_detections), np.array(unmatched_trackers)

KalmanBoxTracker
此类表示观测目标框所对应跟踪对象的内部状态。

定义等速模型。

内部使用 KalmanFilter，7个状态变量，4个观测输入。

F是状态变换模型，H是观测函数，R为测量噪声矩阵，P为协方差矩阵，Q为过程噪声矩阵。

状态转移矩阵A根据运动学公式确定

$\mathbf{x} = [u,v,s,r,\dot{u},\dot{v},\dot{s}]^T,$

$F=\begin{bmatrix}
   1 &amp; 0 &amp; 0 &amp; 0 &amp; \Delta u &amp; 0 &amp; 0 \\
   0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; \Delta v &amp; 0 \\
   0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; \Delta s \\
   0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 \\  
   0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 \\
   0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \\
   0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1
\end{bmatrix}$
$H=\begin{bmatrix}
   1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
   0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
   0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
   0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0
\end{bmatrix}$
  count = 0
  def __init__(self,bbox):
    """
    Initialises a tracker using initial bounding box.
    """
    #define constant velocity model
    self.kf = KalmanFilter(dim_x=7, dim_z=4)
    self.kf.F = np.array([
    [1,0,0,0,1,0,0],
    [0,1,0,0,0,1,0],
    [0,0,1,0,0,0,1],
    [0,0,0,1,0,0,0],  
    [0,0,0,0,1,0,0],
    [0,0,0,0,0,1,0],
    [0,0,0,0,0,0,1]])
    self.kf.H = np.array([
    [1,0,0,0,0,0,0],
    [0,1,0,0,0,0,0],
    [0,0,1,0,0,0,0],
    [0,0,0,1,0,0,0]])

    self.kf.R[2:,2:] *= 10.
    self.kf.P[4:,4:] *= 1000. #give high uncertainty to the unobservable initial velocities
    self.kf.P *= 10.
    self.kf.Q[-1,-1] *= 0.01
    self.kf.Q[4:,4:] *= 0.01

    self.kf.x[:4] = convert_bbox_to_z(bbox)
    self.time_since_update = 0
    self.id = KalmanBoxTracker.count
    KalmanBoxTracker.count += 1
    self.history = []
    self.hits = 0
    self.hit_streak = 0
    self.age = 0

update
使用观察到的目标框更新状态向量。filterpy.kalman.KalmanFilter.update 会根据观测修改内部状态估计self.kf.x。

重置self.time_since_update，清空self.history。
    self.time_since_update = 0
    self.history = []
    self.hits += 1
    self.hit_streak += 1
    self.kf.update(convert_bbox_to_z(bbox))

predict
推进状态向量并返回预测的边界框估计。

将预测结果追加到self.history。由于 get_state 直接访问 self.kf.x，所以self.history没有用到。
    if((self.kf.x[6]+self.kf.x[2])<=0):
      self.kf.x[6] *= 0.0
    self.kf.predict()
    self.age += 1
    if(self.time_since_update>0):
      self.hit_streak = 0
    self.time_since_update += 1
    self.history.append(convert_x_to_bbox(self.kf.x))
    return self.history[-1]

get_state

返回当前边界框估计值。
    return convert_x_to_bbox(self.kf.x)

iou
@numba.jit 即时编译修饰函数以生成高效的机器代码。所有参数都是可选的。
@jit
def iou(bb_test,bb_gt):
  """
  Computes IUO between two bboxes in the form [x1,y1,x2,y2]
  """
  xx1 = np.maximum(bb_test[0], bb_gt[0])
  yy1 = np.maximum(bb_test[1], bb_gt[1])
  xx2 = np.minimum(bb_test[2], bb_gt[2])
  yy2 = np.minimum(bb_test[3], bb_gt[3])
  w = np.maximum(0., xx2 - xx1)
  h = np.maximum(0., yy2 - yy1)
  wh = w * h
  o = wh / ((bb_test[2]-bb_test[0])*(bb_test[3]-bb_test[1])
    + (bb_gt[2]-bb_gt[0])*(bb_gt[3]-bb_gt[1]) - wh)
  return(o)


convert_bbox_to_z
将[x1,y1,x2,y2]形式的检测框转为滤波器的状态表示形式[x,y,s,r]。其中x，y是框的中心，s是比例/区域，r是宽高比。
  w = bbox[2]-bbox[0]
  h = bbox[3]-bbox[1]
  x = bbox[0]+w/2.
  y = bbox[1]+h/2.
  s = w*h    #scale is just area
  r = w/float(h)
  return np.array([x,y,s,r]).reshape((4,1))

convert_x_to_bbox
将[cx，cy，s，r]的目标框表示转为[x_min，y_min，x_max，y_max]的形式。
  w = np.sqrt(x[2]*x[3])
  h = x[2]/w
  if(score==None):
    return np.array([x[0]-w/2.,x[1]-h/2.,x[0]+w/2.,x[1]+h/2.]).reshape((1,4))
  else:
    return np.array([x[0]-w/2.,x[1]-h/2.,x[0]+w/2.,x[1]+h/2.,score]).reshape((1,5))

改进思路
Sort 算法受限于在线的定位，直接忽略了所有目标的考察期输出。这未免有些因噎废食。对于目标的甄别期较短，可以考虑延时判断后再行输出。
参考资料：

【算法分析】SORT/Deep SORT 物体跟踪算法解析
人脸跟踪：deepsort代码解读
二分图的最大匹配、完美匹配和匈牙利算法
The Optimal Assignment Problem
assignment-problem-and-hungarian-algorithm
The Hungarian Algorithm for Weighted Bipartite Graphs
匈牙利算法详解（含时间复杂度）
srianant/kalman_filter_multi_object_tracking
[Tutorial OpenCV] “Ball Tracker” using Kalman filter
SORT:SIMPLE ONLINE AND REALTIME TRACKING
多目标跟踪(MOT)论文随笔-SIMPLE ONLINE AND REALTIME TRACKING (SORT)
多目标跟踪方法：deep-sort
卡尔曼滤波的理解以及参数调整
图说卡尔曼滤波，一份通俗易懂的教程
Kalman滤波器从原理到实现
The Hungarian algorithm: Kuhn-Munkres theorem
How to save a list as numpy array in python?
How to delete items from a dictionary while iterating over it?