目标跟踪算法之相关滤波器（一）：MOSSE

前言
MOSSE: David S. Bolme, J. Ross Beveridge, Bruce A. Draper, Yui Man Lui. “Visual Object Tracking using Adaptive Correlation Filters.” CVPR2010

一、相关的理解

在信号处理中，有一个概念–相关性（correlation）：描述两个因素之间的联系。相关性分为cross-correlation（互相关：两个信号之间的联系）和auto-correlation（自相关：本身在不同频域的相关性）。
互相关是用来度量两个信号在某个时刻的相似程度，对于机器视觉领域来说就是指两个图像patch的互相匹配的程度。

1、相关操作
图像的相关公式：

其中h称为相关核(Kernel)，具体到每一个像素表示为：


注：Input Image为输入的图像。Kernel为相关核 ，也可以称作我们提前训练好的滤波器模板。Output image即为输出响应图像。
步骤：
（1）滑动核，使其中心位于输入图像的f(i,j)像素上
（2）利用上式求和，得到输出图像的g(i,j)像素值
（3） 重复上面操纵，直到求出输出图像的所有像素值

2、卷积操作
图像的卷积公式：

其中h称为卷积核(Kernel)，具体到每一个像素表示为：


步骤：
（1）将卷积核围绕中心旋转180度
（2）滑动核，使其中心位于输入图像的f(i,j)像素上
（3） 利用上式求和，得到输出图像的g(i,j)像素值
（4）充分上面操纵，直到求出输出图像的所有像素值

3、相关和卷积的差异
（1）卷积将核旋转了180度。
（2）物理意义：相关可以反应两个信号相似程度，卷积不可以。
（3）卷积满足交换律，相关不可以。
（4）卷积可以直接通过卷积定理（时域上的卷积等于频域上的乘积）来加速运算，相关不可以。

二、相关滤波的原理

相关滤波的原理
相关滤波跟踪器就是通过互相关(cross-correlation)来定位目标当前帧所在位置的。响应图g最大值对应的位置即为当前时刻预测的目标位置，具体流程如下：

如果我们在时域内求解响应图，运算量巨大，那么如何利用卷积定理将其转换到频域？？？
用卷积来表示相关就是：

利用卷积定理转换到频域为：

所以将我们的输入图像和滤波器通过算法变换到频域后，直接将他们相乘，然后再变换回时域（也就是图像的空域）就可以得到响应图。

几点重要的解释：
（1）输入的图像是指目标检测区域（MOSSE的检测区域就是目标所在区域），可能是像素值也可能是提取的特征（eg.Hog，CN，DeepFeatures等）。
（2）滤波器（或者叫目标模板）的大小和检测区域的大小一样。因为相同大小的矩阵在频率域才可以点乘计算。
（3）当滤波器稍微偏移就会超出输入图像的范围，则需要填充数据（这就是卷积的边界效应）。然而在实际的相关滤波跟踪算法中，因为代码中直接就写频域的计算公式，所以我们不知道是如何填充边界的。常用的有三种填充方法，补零、补边界像素、循环图像，matlab中fft默认的是第三种。

三、MOSSE算法

假设有两个信号f和g，则两个信号的相关性（correlation）为：

其中f∗表示f的复共轭。correlation的直观解释就是衡量两个函数在某个时刻相似程度。而将correlation filter应用与跟踪最简单的想法就是：两个信号越相似，其相关值越高。在跟踪中，就是找到与跟踪目标响应最大的项。
作者提出的滤波器叫做Minimum Output Sum of Squared Error filter（MOSSE）（误差最小平方和滤波器）。按照前面的思路，我们需要找到一个滤波器，使其在目标上的响应最大，则如下公式：

其中g表示响应输出，f表示输入图像，h表示滤波模板。
显然，我们要是想获得响应输出，只需确定滤波器模板h即可。上式的计算是进行卷积计算，这在计算机中的计算消耗很大，因此作者对上式进行快速傅里叶变换（FFT），这样卷积操作经过FFT后就变成了点乘操作，极大的减少了计算量。关于图像卷积和滤波的一些知识请参考【图像卷积和滤波】。上式变成如下形式：

为了方便描述，将上式写成如下形式：

有了上面的式子，那么后面跟踪的任务就是找到H∗了：

但是在实际跟踪的过程中，我们要考虑到目标外观变换等因素的影响，所以需要同时考虑目标的m个图像作为参考，从而提高滤波器模板的鲁棒性，所以作者提出了MOSSE这个模型。

MOSSE模型公式如下

因为上式的操作都是元素级别的，因此要想找到H，只要使其中的每个元素（w和v是H中每个元素的索引）的MOSSE都最小即可。因此上式可以转换为如下形式：

对上式求偏导，并使偏导为0即可。即：

以下求导都是常量，涉及到复数的求导：

解得H为：

上式就是滤波器的模板公式。

但是在跟踪中怎么得到滤波器H呢？Fi和Gi又该怎么获取？
在作者的文章中，对跟踪框（groundtruth）进行随机仿射变换（一次线性变换，y=ax+b,a控制缩放和旋转，b控制平移），获取一系列的训练样本fi，而gi是由高斯函数产生，并且其峰值位置是在fi的中心位置。获得了一系列的训练样本和结果之后，就可以计算滤波器h的值。注意：这里的f,g,h的size大小都相同。
模型更新
作者为了让滤波器对于形变、光照等外界影响具有更好的鲁棒性，采取了如下的模板更新策略：

将滤波器的模型公式分为分子和分母两个部分，每个部分都分别进行更新，更新参数为η。其中At和At−1分别表示的是当前帧和上一帧的分子。

总结
在目标跟踪中相关滤波的基本思路：在初始帧中，给定目标区域，用最小二乘法，训练得到滤波模板H；在下一帧中，通过滤波模板H与新目标F进行相关操作，得到输出响应G，G中最大值对应着目标在下一帧中的位置。（其中特征用的是原始像素）

参考文章
1、MOSSE 添加链接描述
2、相关滤波跟踪（MOSSE）添加链接描述
3、ICCV2010跟踪算法MOSSE原理及代码解析添加链接描述