目标跟踪算法

一．互相关运算

给你一张我的正脸照（没有经过美颜处理的），你该如何在人群中找到我呢？一种最直观的方案就是：“谁长得最像就是谁”。但是对于计算机来说，如何衡量“长得像”，并不是个简单的问题。这就涉及一种基本的运算——互相关（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 )：表示目标位置信息的不确定性，由8×8的对角矩阵表示，矩阵中数字越大则表明不确定性越大，可以以任意值初始化。

.  卡尔曼滤波分为两个阶段：(1) 预测track在下一时刻的位置，(2) 基于detection来更新预测的位置。

下面将介绍这两个阶段用到的计算公式。（这里不涉及公式的原理推导，因为我也不清楚原理(ಥ_ಥ) ，只是说明一下各个公式的作用）