在技术日新月异的时代，今天的技术可能在明天就会被新的技术取代，例如现在爆火的大模型。但目前看来，大模型还不能做到无所不能。

所以这篇博客还是来考古一下，写一下传统的跟踪算法。这里不是为了怼大模型而为了写一篇传统算法而写传统算法。只是觉得这个算法有个思想非常有意思，所以记录一下。

该算法在2010年发表在ICPR上，它主要是提出了Forward-Backward errors这种跟踪点的校验思想，使得跟踪点更为可靠。但博主这里认为，这篇文章其实还有一个比较有意思的一点，就是文章后面提出的MedianFlow跟踪算法，里面利用了中位数来估计待跟踪目标的位移和缩放尺度。接下来大概按照文章结构对该跟踪算法进行详细说明。

一、Forward-Backwark errors（FB errors）

从名字上可以看出，Forward-Backwark errors其实就是根据跟踪点前向和后向的结果来计算跟踪点的偏差。如下图所示：

从上图上半部分可以看出算法流程是这样的：

1. 首先在第一帧输入的图片中定义需要跟踪的点，例如图中的点1和点2。为了这些点能够更稳定的被跟踪，通常会采用像Harris角点检测算法或者像FAST特征点检测算法来提取图片中特征明显的点
2. 利用点跟踪算法，跟踪第一帧的点在第二帧的位置。通常这里会采用Lucas-Kanade稀疏光流算法
3. 通过第2步获取到当前帧的点后，再将这些点再次利用点跟踪算法，计算出它们在前一帧的位置
4. 利用第3步获得的前一帧的点的位置和第1步初始化的点的位置计算点的偏差，这样就得到了所谓的FB errors
5. 根据FB errors就可以过滤掉位移较大的点，也就是跟踪失败的点

上图中的下半部分是采用符号的形式来表示这个流程：

假设目前有k的图片帧，用符号表示为$S=(I_t,I_{t+1}...,I_{t+k})$, $x_t$为在时刻t这一帧中待跟踪的点

1. 采用某种点跟踪算法，跟踪点$x_t$在后面k帧中的位置，这样就可以得到一条点$x_t$的移动轨迹$T_f^k=(x_t,x_{t+1},...,x_{t+k})$。这一步就称为Forward
2. 同理根据相同的跟踪算法，将t+k帧中的跟踪点$x_{t+k}$反向跟踪回第t帧，这样又可以得到一条移动轨迹$T_b^k=({\hat{x}}_t,{\hat{x}}_{t+1},...,{\hat{x}}_{t+k})$，这里${\hat{x}}_{t+k}=x_{t+k}$
3. FB errors用公式表示为$FB(T_f^k|S)=distance(T_f^k,T_b^k)$，文章为了简单定义$=distance(T_f^k,T_b^k)=||x_t-{\hat{x}}_t||$。也就是说FB errors文章采用初始点和反向跟踪到t帧的点之间的距离来表示

二、MedianFlow跟踪算法

MedianFlow算法是在利用上述提出的FB errors基础上获取可靠的跟踪点，进而来跟踪物体。MedianFlow跟踪算法如下图所示

如上图中上半部分所示，现在有两帧图片$I_t$和$I_{t+1}$，现在想利用MedianFlow算法来跟踪图中的小车。也即输入图片$I_t$和$I_{t+1}$，bounding box ${\beta }_t$，跟踪器输出${\beta }_{t+1}$。

算法流程如上图中下半部分所示

1. 根据输入的bounding box ${\beta }_t$，在框中初始化一些待跟踪点。这里的初始化方式跟第一部分所述有点不同。这里不采用角点或者特征点来初始化，而是简单的采用在框中间距相同的点作为待跟踪点
2. 利用某种跟踪点的算法，例如Lucas-Kanade稀疏光流算法跟踪在t+1帧中点的位置
3. 利用某种过滤算法将跟踪失败的点进行过滤，当然这里采用的就是FB errors将50%的误差较大的点进行过滤。文章其实还增加了一个叫NCC的方法（后面会做简单说明），也将误差较大的50%的点过滤掉。最终得到的点集就为跟踪到的点
4. 利用跟踪到的点进行t+1帧bounding box的预估

上面流程中有两点需要待解释，一个是NCC，一个是bounding box的预估。下面分别做一下介绍

2.1 Normalized Cross Correlation(NCC)

从名字可以看出这里就是去求两个图之间的归一化互相关系数。

具体的对于输入的两个图$S_1$和$S_2$，两张图的大小都为$m\times n$，它们之间的互相关系数用公式表示如下：

$\rho =\frac{\frac{1}{mn}{\sum }_{i=1}^m{\sum }_{j=1}^n(S_1(i,j)-{\overline{S}}_1)(S_2(i,j)-{\overline{S}}_2)}{\sqrt{\frac{1}{mn}{\sum }_{i=1}^m{\sum }_{j=1}^n(S_1(i,j)-{\overline{S}}_1{)}^2}\sqrt{\frac{1}{mn}{\sum }_{i=1}^m{\sum }_{j=1}^n(S_2(i,j)-{\overline{S}}_2{)}^2}}$

其中$\overline{x}$表示求平均操作。

所以NCC操作就是两图的协方差除以两图标准差的结果，又称为Pearson相关系数。在MedianFlow两个图来源于对应跟踪点周边一定大小的图片块。

2.2 bounding box的预估

要预估一个bounding box，我们只需要预估出新的bounding box的位移以及对应的缩放尺寸。

我们通过下面两步来分别预估这两个参数

1. 在得到可靠的跟踪点后，计算所有可靠的跟踪点的在x和y方向的移动位置，分别取x方向移动值的中位数和y方向移动值的中位数作为新的bounding box相对之前bounding box的位移
2. 在得到可靠的跟踪点后，计算这些跟踪点两两之间的距离以及在t帧中对应点两两之间的距离，这些距离各自相除，出所有除数的中位数作为bounding box的缩放比例。

上面第2点可能有点绕，这里举个例子来说明。假设在t+1帧中，通过过滤得到的跟踪点有n个，那么对应t帧中也有n个。计算t+1帧中n个点的两两之间的距离，得到$n\ast n$个值，同理t帧对应的点也可以得到$n\ast n$个值，对应两帧中$n\ast n$个值相除，得到$n\ast n$个除数，这$n\ast n$个除数取其中的中位数就为新的bounding box的缩放尺寸。

MedianFlow算法在opencv中是有开源代码的，可以路径https://github.com/opencv/opencv_contrib/blob/3.4/modules/tracking/src/trackerMedianFlow.cpp

参考：

1. http://kahlan.eps.surrey.ac.uk/featurespace/tld/Publications/2010_icpr.pdf
2. https://github.com/opencv/opencv_contrib/blob/3.4/modules/tracking/src/trackerMedianFlow.cpp