探究MeanShift算法的优化

本节主要介绍MeanShift方法。MeanShift是一种最优的寻找概率密度极大值的方法，属于无参密度估计算法，可应用于图像滤波、图像分割和目标跟踪等领域。MeanShift算法对应的是一个迭代步骤，如图2－8所示，基于MeanShift方法的目标跟踪技术采用核概率密度来描述目标的特征，然后利用MeanShift搜寻目标位置。其主要思想是先计算出当前点的偏移均值，移动该点到其偏移均值，然后以此为新的起始点，继续移动，直到满足一定的条件结束。这种方法的优点在于稳定性很高，对目标形状、大小的连续变化具有很好的适应性，具有较强的抗干扰能力，对计算资源要求不是很高，能够保证目标跟踪的实时性和稳定性。

下面对MeanShift的原理进行简单介绍：设d维空间存在n个样本点xi，i＝1，…，n，该空间内点x处的MeanShift向量的基本形式定义如下：

图2－8　MeanShift方法示意图

式中，Sh是一个半径为h的高维球区域，k代表落入Sh区域的样本点数目，（xi－x）代表样本点xi相对于点x的偏移向量，即两点之间的矢量差。上述公式很直观地说明了MeanShift的物理意义，即某点的MeanShift向量为落于该点为中心的高维球形区域内所有样本点与该点矢量差的平均值。假设xi来自于一个概率密度函数f（x）的采样，对于非零的概率密度梯度，它总是指向概率密度增加最大的方向，因此，落入Sh区域的样本点更多的分布在概率密度梯度方向。从而，MeanShift向量Mh（x）也指向概率密度方向。如图2－9所示，图中大圆代表多维球形区域Sh的投影，小圆圈代表落入该球区域的样本点，大圆中心黑色实心点代表MeanShift的基准点x，箭头线段代表球区内各样本点xi与x的矢量差。从图中可以看出，平均的偏移向量Mh（x）会指向样本最大的区域，也就是概率密度函数的梯度方向。

(www.xing528.com)

图2－9　MeanShift向量的示意图

式（2－6）中各点对MeanShift向量计算的贡献是一样的，考虑到实际情况，从常理来说，离x点越近的采样点对x的统计特性起的作用越大，因而，在实际应用中引入核函数的概念，在计算Mh（x）时对各点的作用进行加权：

式中，h为带宽系数。G（x）是一个单位核函数，常见形式为高斯核函数和常量核函数。

MeanShift算法是一个迭代过程，以G（x）为核函数，从最初始点x，不断沿着概率密度的梯度方向移动直到满足约束条件。移动时步长的大小取决于两个因素，即该点概率密度梯度大小和该点概率密度大小。在概率密度大的地方，相对来说更接近概率密度峰值，从而MeanShift算法使得移动时的步长小些，避免寻优过程发生超调产生震荡。相反，在密度小的地方，移动的步长就大一些，加快寻优速度，加速算法收敛过程。

当MeanShift算法目标跟踪时，MeanShift方法中关键的两个过程分别是目标模型和候选模型的描述。首先，目标模型描述：在初始图像帧中确定包含所有目标像素点的目标区域，在该区域中计算目标特征空间中每个特征值的概率；其次，候选模型描述：图像序列中后续图像中可能存在候选区域，计算这些候选区域中对应特征空间的每个特征值。为了检测初始目标模型和候选模型之间的相似性，需要通过计算一个相似函数来进行衡量。相似性函数最大时得到MeanShift向量，再利用MeanShift算法的收敛性，迭代计算Mean－Shift向量，最终目标收敛到一个静止点，即目标的真实位置，完成跟踪目的。

MeanShift向量总是沿着密度变化最大的方向，而对核函数进行每一轮迭代计算时的移动步长都有所变化。在一部分区域步长比较大，这说明这些区域并未包含我们所关注的特征，而在另外一些区域的步长会变小，这说明这些区域中存在我们所感兴趣的特征，而且越接近密度极值处步长就越小。换句话说，MeanShift算法本质上是一个步长自动变化的梯度上升算法，也可以称为自适应梯度上升算法，核心就是迭代以及由阈值判断迭代是否进行。