Mean shift和CamShift在目标追踪的应用
2014309030113
王宗贤 2015.6.10
Mean shift和CamShift在目标追踪的应用
Mean Shift 简介
Mean Shift 这个概念最早是由Fukunaga等人[1]于1975年在一篇关于概率密度梯度函数的估计中提出来的，其最初含义正如其名，就是偏移的均值向量，在这里Mean Shift是一个名词，它指代的是一个向量，但随着Mean Shift理论的发展，Mean Shift的含义也发生了变化，如果我们说Mean Shift算法，一般是指一个迭代的步骤，即先算出当前点的偏移均值，移动该点到其偏移均值，然后以此为新的起始点，继续移动，直到满足一定的条件结束。
然而在以后的很长一段时间内Mean Shift并没有引起人们的注意，直到20年以后，也就是1995年，另外一篇关于Mean Shift的重要文献[2]才发表。在这篇重要的文献中。Yizong Cheng对基本的Mean Shift算法在以下两个方面做了推广，首先Yizong Cheng定义了一族核函数，使得随着样本与被偏移点的距离不同，其偏移量对均值偏移向量的贡献也不同，其次Yizong Cheng还设定了一个权重系数，使得不同的样本点重要性不一样，这大大扩大了Mean Shift的适用范围。另外Yizong Cheng指出了Mean Shift可能应用的领域，并给出了具体的例子。
Comaniciu等人[5]还把非刚体的跟踪问题近似为一个Mean Shift最优化问题。使得跟踪可以实时的进行。
在后面的几节，本文将详细的说明Mean Shift的基本思想及其扩展，其背后的物理含义，以及算法步骤，并给出理论证明。最后本文还将给出Mean Shift在聚类。图像平滑，图像分割，物体实时跟踪这几个方面的具体应用。 Bradski根据Mean Shift算法的不足，提出了Cam Shift算法。Cam Shift算法，即Continuously Adaptive Mean Shift算法，即连续的自适应Mean Shift。
基本思想:就是对视频图像的多帧进行Mean Shift运算，将上一帧结果作为下一帧的初始值，迭代下去。
Mean Shift 的基本思想及其扩展
基本Mean Shift
给定d维空间R中的n个样本点xi，i=1，…，n，在x点的Mean Shift向量的基本形式定义为:
dMh?x??1?xi?x? ?kxi?Sh (1)
其中，Sh是一个半径为h的高维球区域，满足以下关系的y点的集合，
Sh?x??y:?y?x??T?y?x??h2? (2)
k表示在这n个样本点xi中，有k个点落入Sh区域中。
我们可以看到?xi?x?是样本点xi相对于点x的偏移向量，(1)式定义的Mean Shift向量
Mh(x)就是对落入区域Sh中的k个样本点相对于点x的偏移向量求和然后再平均。从直观
上看，如果样本点xi从一个概率密度函数f?x?中采样得到，由于非零的概率密度梯度指向概率密度增加最大的方向，因此从平均上来说， Sh区域内的样本点更多的落在沿着概率密度梯度的方向。因此，对应的， Mean Shift向量Mh(x)应该指向概率密度梯度的方向
。
图1，Mean Shift示意图
如上图所示， 大圆圈所圈定的范围就是Sh，小圆圈代表落入Sh区域内的样本点
xi?Sh，黑点就是Mean Shift的基准点x，箭头表示样本点相对于基准点x的偏移向量，
很明显的，我们可以看出，平均的偏移向量Mh(x)会指向样本分布最多的区域，也就是概率密度函数的梯度方向。
扩展的Mean Shift
核函数
首先我们引进核函数的概念。
定义:X代表一个d维的欧氏空间，x是该空间中的一个点，用一列向量表示。 x的模
x?xTx。R表示实数域。如果一个函数K:X?R存在一个剖面函数k:?0,???R，
2即
K(x)?k?x2?
并且满足:
(1) k是非负的。
(2) k是非增的，即如果a?b那么k(a)?k(b)。 (3) k是分段连续的，并且
??0k(r)dr??
那么，函数K(x)就被称为核函数。
举例:在Mean Shift中，有两类核函数经常用到，他们分别是， 单位均匀核函数:
F(x)????1 if x?1? ?0 if x?1 单位高斯核函数:
N(x)?e?x2 这两类核函数如下图所示。
图2， (a) 单位均匀核函数 (b) 单位高斯核函数
一个核函数可以与一个均匀核函数相乘而截尾，如一个截尾的高斯核函数为，
2?N?F??e??x if x????(x)?? ??0 if x?? 图 3 显示了不同的?,?值所对应的截尾高斯核函数的示意图。
(3)
(4)
(5)
(6)
图3 截尾高斯核函数 (a) N1F1 (b) N0.1F1
Mean Shift扩展形式
从(1)式我们可以看出，只要是落入Sh的采样点，无论其离x远近，对最终的Mh(x)计算的贡献是一样的，然而我们知道，一般的说来，离x越近的采样点对估计x周围的统计特性越有效，因此我们引进核函数的概念，在计算Mh(x)时可以考虑距离的影响;同时我们也可以认为在这所有的样本点xi中，重要性并不一样，因此我们对每个样本都引入一个权重系数。
如此以来我们就可以把基本的Mean Shift形式扩展为:
M?x???Gi?1nH(xi?x)w(xi)(xi?x) (7)
H?Gi?1?1/2n(xi?x)w(xi)其中:
GH(xi?x)?HG?H?1/2?xi?x??
G(x)是一个单位核函数
H是一个正定的对称d?d矩阵，我们一般称之为带宽矩阵
w(xi)?0是一个赋给采样点xi的权重
22?h,...,h在实际应用的过程中，带宽矩阵H一般被限定为一个对角矩阵H?diag?1d??，甚至
更简单的被取为正比于单位矩阵，即H?hI。由于后一形式只需要确定一个系数h，在Mean Shift中常常被采用，在本文的后面部分我们也采用这种形式，因此(7)式又可以被写为:
2