MedianFlow 跟踪算法详解

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

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

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

一、Forward-Backwark errors（FB errors）

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

1.png

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

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^{k}{f}=(x_t, x{t+1}, ..., x_{t+k})。这一步就称为Forward

2. 同理根据相同的跟踪算法，将t+k帧中的跟踪点x_{t+k}反向跟踪回第t帧，这样又可以得到一条移动轨迹T^{k}{b}=(\hat{x}t, \hat{x}{t+1},...,\hat{x}{t+k})，这里\hat{x}{t+k}=x{t+k}

3. FB errors用公式表示为FB(T^{{k}_{f}|S)=distance(T}{k}{f}, T^{k}{b})，文章为了简单定义=distance(T^{k}{f}, T^{k}{b})=||x_t-\hat{x}_t||。也就是说FB errors文章采用初始点和反向跟踪到t帧的点之间的距离来表示

二、MedianFlow跟踪算法

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

2.png

如上图中上半部分所示，现在有两帧图片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^m_{i=1}\sum{n}{j=1}(S_1(i,j)-\overline{S}1)(S_2(i,j)-\overline{S}2)}{\sqrt{\frac{1}{mn}\sum^m{i=1}\sum^{n}{j=1}(S_1(i,j)-\overline{S}1)^{2}\sqrt{\frac{1}{mn}\sum}m{i=1}\sum^{n}{j=1}(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个点的两两之间的距离，得到nn个值，同理t帧对应的点也可以得到nn个值，对应两帧中nn个值相除，得到nn个除数，这n*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