目标跟踪、单目标跟踪、多目标跟踪的概念
目标跟踪分为静态背景下的目标跟踪和动态背景下的目标跟踪。
静态背景下的目标跟踪:
静态背景下的目标跟踪指摄像头是固定的，其采集的视野中背景是静止的，如在十字路口的固定摄像头。
动态背景下的目标跟踪:
摄像头采集的视野中背景和目标都是在变化的。
目标跟踪又分为单目标跟踪和多目标跟踪。
单目标跟踪:
在视频的初始帧画面上框出单个目标，预测后续帧中该目标的大小与位置。典型算法有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%, 在高速率视频流中也达到了很好的水准。该模型的速度主要取决于目标检测模型的速度，在匹配上面耗时很短。
