目标追踪DeepSort

一、卡尔曼滤波

        你可以在任何对某个动态系统有 “不确定信息” 的地方使用卡尔曼滤波器，并且可以对系统下一步的行为做出 “有根据的猜测”。即使混乱的现实干扰了你所猜测的干净运动，卡尔曼滤波器通常也能很好地确定实际发生了什么。它还可以利用你可能想不到要利用的疯狂现象之间的相关性！
        卡尔曼滤波器非常适合 “不断变化” 的系统。它们的优点是占用内存少（除了前一个状态，不需要保留任何历史记录），并且速度非常快，非常适合实时问题和嵌入式系统。
举个例子：开车时如何确定自己的位置呢？我们根据车辆的运行，可以提供以下信息：①加速度信息，②里程表信息，③GPS信息。这三种信息都存在误差（噪音），但是他们都有用，可以综合的利用它们，估计出最优的位置，这就是卡尔曼滤波，本质上是优化估计算法。

1.1一个定量的例子

下面是个定量分析的例子：一个小车的位置更新：

状态向量 $x_{t}$ ：位置和速度；小车加速度 $u_{t}$ ：

则经过 $\triangle t$ 时刻后的位置：位置和速度

根据上式可以得出状态转移矩阵：

任何状态都会受到外部环境的影响（例如压了一颗石头、例如突然猛刮大风），但是这些影响可能会促进状态，也可能抑制状态，它们的平均呈正态分布。

这里的A就是上式中的Ft，B就是Bt， $w_{k}$ 是位置误差； $y_{k}$ 就是速度， $v_{k}$ 是速度误差。这就是状态转移方程。

卡尔曼滤波的本质上就是基于估计值和观测值进行综合判断

1.2 计算公式

那么下一时刻的准确位置在哪呢？如下图， $\hat{x}_{k-1}$ 是上一时刻的预测值，它的正太分布的宽度相当于误差， $\hat{x}_{k}$ 是这一时刻的预测值，它的误差更大（因为它就是从 $\hat{x}_{k-1}$ 这个本身就是“连蒙带猜”的结果得出来的，那么它的误差就更大），而 $y_{k}$ 是测量值，也带有误差。

那么如果根据 $\hat{x}_{k}$ 和 $y_{k}$ 得出一个更加准确的值呢？科学家给出的一个方法：

$\hat{x}_{}^{-}$ 是先验估计； $\hat{x}$ 是后验估计； $y_{k}$ 是传感器； $K_{k}$ 是卡尔曼增益

1.3 两大核心模块

1.3.1 预测Prediction

车辆在运行过程中，有些量保持着一定的关系（如某个人的眼睛中，这一时刻的车辆大小和下一时刻的车辆大小存在着一定的大小关系，当一个车远离这个人时，它不会瞬间变大，也不会瞬间变小，而是慢慢的变小）

单状态协方差矩阵就是其方差：

$P_{k}^{-}$ 是协方差矩阵，它描述了一些量的关系，状态在更新（状态转移矩阵），同样的，关系也在更新，关系在更新时同样加上了噪音项Q（误差项），其实就是更新过程必然会受到外界干扰的影响。

这就是预测阶段，预测状态估计值和协方差。

1.3.2 更新Update

不建议大家看这个公式的推导，尤其是卡尔曼增益 $K_{k}$ ，推导过程及其复杂，科学家费了好大力气才推导出，已经超出了我们的学习范围了。

对于我们的目标追踪，我们要对每一帧的要预测、更新，下一帧继续再预测、再更新，因为每一帧的状态肯定会改变的。预测完根据观测值进行修正，修正后的状态值去估计下一帧。

1.4 卡尔曼增益

卡尔曼增益K：式中R是偏差，C是转换矩阵（单状态，匀速）

它的目的就是让最优估计值的方差最小（就是下图中的 $\hat{x}_{k}$ 中的方差最小），它决定了卡尔曼滤波的核心作用。

若观测过程没有一点偏差，根据推导可得： $\hat{x}_{k}=y_{k}$ ，即后验估计值就等于观测值；

若状态估计没有噪音时，根据推导可得： $\hat{x}_{k}=x_{k}^{-}$ ，即后验估计值等于先验估计值。

二、追踪问题考虑的状态

均值（Mean）：8维向量：

$x=[cx,cy,r,h,vx,vy,vr,vh]$

以这名足球员为例，解释上述8个量。 cx，cy就是这个检测框的中心点位置；r=h/w即宽高比，是这个检测框的长宽比例（这个值表明这个检测框不能瞬间变大或变小），h就是长度； vx，vy，vr，vh就是该方向（分别是x，y，r，h）上的速度变化。协方差矩阵：表示目标位置信息的不确定性，由8*8的矩阵表示

追踪过程也分为两个阶段，每个track都要预测下一时刻的状态，并基于检测到的结果进行修正（匀速、线性、追踪通常是一帧一帧进行处理的）。

三、匈牙利匹配算法

利用匈牙利匹配完成匹配的同时最小化代价矩阵（代价矩阵后面解释）即当前帧检测到的目标应该匹配到前面的哪个track呢？但是很多时候并不是最优匹配，而是尽可能的多匹配。

3.1 例子

匈牙利匹配的例子：给三个人分配三个任务，哪个人做哪个任务代价矩阵（时间）最小呢？

时间：分钟	task1	task2	task3
Person1	15	40	45
Person2	20	60	35
Person3	20	40	24

特点：

方法：

上述过程了解即可，我们一般直接使用Python中的内置函数：用之前得有一个代价矩阵。

sklearn：linear_assignment(); scipy:linear_sum_assignment()直接做上述过程

3.2 代价矩阵的构建

得到代价矩阵即可完成这个任务。那么在追踪任务中，如何构建这个代价矩阵呢？这也是这个任务的难点。

运动信息的匹配：卡尔曼估计出8个状态量，是下一帧的预测值，我们同时还有下一帧的检测值，即下一帧估计的结果和下一帧实际的结果，可以构建一个代价矩阵。

外观匹配（ReID）：这是deepsort中最重要的，就是提供了外观信息

IOU匹配（BBOX）：BoundingBox的匹配，即预测的新位置框和检测到的实际位置框进行匹配，哪个IOU大，那就是IOU损失小。

匈牙利匹配会根据这三项分别构造代价矩阵。

ReID特征：追踪人所用到了ReID，如果追踪其他目标需要自己训练。ReID是一个很简单的网络（因为我们想实时检测，就不能构造复杂的网络），对输入的bbox进行特征提取，返回128维特征：

在实际运用时，他的每一帧的检测框都会存在一个list中，每个是128维向量，而下一帧会有检测框，也会有128维向量，他会和前面的每一帧进行计算余弦相似度，看哪个是最大的，把他们俩当作距离。track的list数量是有上线的，默认是100个。

四、追踪任务的基本流程

目标检测+追踪（对检测到的bbox提取各项特征后进行匹配）

4.1 Sort算法（是deepsort的前身）

卡尔曼预测与更新
匈牙利匹配返回结果
将预测后的tracks和当前帧中的detections进行匹配（IOU匹配）

注意：没有ReID等深度学习特征

4.2 DeepSORT算法

与Sort算法最大的区别在于，多了MatchingCascade过程。它代码写的挺难理解的，论文写的也十分抽象，但原理非常简单，是这样的：　　　　　　　　　　　　　　　　　　　　　　　　假如某个人因为某些原因在某些帧中没被检测到（如守门员扑球时形态会发生剧烈变化，此时很难被检测到，但是他会很快恢复原来状态），这些人并不是被“干掉”，他可能在下面帧会被检测到，原论文提出一个值MaxAge，就是最大尝试次数，论文给的默认值是70帧，即从检测框消失，到70帧以后也没有找到能匹配上的，就会删除该tracks。　　　　　　　　　　　　　　　 MatchingCascade，假设现在有track1，track2，track3，．．．，track10，假如track1全部匹配到100帧，丢失0帧，track2因为种种原因（如遮挡、匹配错误等）丢失5帧，tracks3丢失10帧，tracks10丢失60帧。现在第101帧来了，它含有10个bbox，而 MatchingCascade就会让这10个bbox优先匹配track1，即优先匹配丢失最少的（如果假如前５个都没有丢失，那么同时匹配这前５个）循环执行70次。在MatchingCascade匹配完成后，再进行IOU匹配。但是并不是所有的track能进入MatchingCascade匹配，只有连续3帧能匹配上的，才进行MatchingCascade匹配（图中的左边的Confirmed），然后其他的就是Unconfirmed。MatchingCascade匹配也包含了卡尔曼估计以及ReID特征。 其它的Unconfirmed进行IOU Match，看能不能找到，不能的就是Unmatched Tracks然后看是否是Confirmed，不是的话（Unconfirmed）直接删除，是Confirmed就看是否大于MaxAge（70帧）