MeanShift

§5-1Mean Shift算法

Mean Shift算法是由Fukunaga和Hosteler于1975年提出的一种无监督聚类方法[109]，Mean Shift的含义是均值偏移向量，它使每一个点“漂移”到密度函数的局部极大值点。但是再提出之初，Mean Shift算法并没有得到广泛的重视，直到1995年，Cheng等人对该算法进行了进一步的研究

[110]

，提出了一般的表达形式并定义了一族核函数，从而扩展了该算法的应用

领域，此后Mean Shift算法逐步得到了人们的重视。目前，Mean Shift算法已广泛应用于目标跟踪[111~114]、图像分割与平滑[115~118]等领域，同时由于该算法具有简洁、能够处理目标变形等优点，也是目前目标跟踪领域的一个重要研究热点。 5-1-1 Mean Shift算法原理

Mean Shift算法是一种基于密度梯度的无参数估计方法，从空间任意一点，沿核密度的梯度上升方向，以自适应的步长进行搜索，最终可以收敛于核密度估计函数的局部极大值处。基本的Mean Shift算法可以描述为：设?xi??i?1,?,n?为d维空间Rd中含有n个样本点的集合，在点x处的均值偏移向量的基本形式可以由式(5.1)表示：

Mh(x)?1k?(xx?Shi?x) (5.1)

其中，Sh是Rd中满足式(5.2)的所有y点集合，其形状为一个半径为h的高维球区域。k为所有n个样本点中属于高维球区域的点的数目。(xi-x)为样本点相对于点x的偏移向量。根据式(5.1)的定义可知，点x的均值偏移向量就是所有属于Sh区域中的样本点与点x的偏移向量均值，而Sh区域中的样本点大多数是沿着概率密度梯度的方向，所以均值漂移向量的方向与概率密度梯度方向一致，图5.1为具体的示意图。

Sh(x)??y:(y?x)(y?x)?hT2? (5.2)

hShx 图5.1 Mean Shift 示意图 Fig.5.1 Mean Shift sketch map

根据式(5.1)和图5.1可以看出，所有属于区域Sh中的样本点对于点x的均值漂移向量贡献度相同，而与这些点与点x间的距离无关。然而就一般情况而言，与x点距离越小的样本点对估计点x的统计特性越有效，因此在实际计算点x的均值漂移向量时要考虑每个样本点与点x在区域Sh中的距离，所以引入核函数(Kernel Function)的概念，将式(5.1)改写为式(5.3)的形式。

f?(x)?1nhdn?i?1?x?xi?K??(5.3) ?h?其中，K(x)为核函数且为有界函数，h为核函数的带宽，同时K(x)具有以下四个特性：

(1)核函数具有规范性，即有?K(x)dx?1；

Rd(2)核函数具有指数加权衰减性，即limxx??dK(x)?0；

(3)核函数具有对称性，即有?xK(x)dx?0；

Rd(4)核函数具有单位协方差性，即?xxTK(x)dx?ckI。其中，ck为常数，ckI为为核函数

RdK(x)的协方差矩阵。

对给定的核函数K(x):Rd?R，如果有一元函数k(x):?0,???R使得K(x)?k(x)成立，同时满足以下几个条件，则称函数k(x)为核函数K(x)的剖面函数。

(1) k(x)在区间?0,??上是非负的；

(2) k(x)在区间?0,??上有界且单调递减，即有x1k(x2)； (3) k(x)在区间?0,??分段连续，并且积分?k(x)dx有界。

0?2设在d维空间Rd中，k(x)为K(x)的剖面函数，则可使用剖面函数来表示多变量的核密度估计，将式(5.3)改写为式(5.4)。

f?h,K(x)?1nhdn?i?1?x?xik??h?2????(5.4)

根据式(5.4)可以得出，Mean Shift算法本质上是将目标点附近邻域中样本点的剖面函数均值作为该目标点的概率密度估计值，同时，局部邻域的大小通过核函数的带宽h所确定。

对于Mean Shift算法，核函数的选择很重要。Mean Shift算法常用的核函数主要有Uniform Kernel， Epanechnikov Kernel和Normal Kernel三种，表5.1是这三种核函数的基本形式以及三维图形[119]。

表5.1 常见的核函数 Table 5.1 Common kernel functions

核函数名称

函数原型

多元表达形式

三维图

Uniform Kernel

??c,x?1 KU(x)????0,其它?1?,x?1KU(x)??Vd

?0,其它?2?d?2(1?x),x?1?KE(x)??2Vd?0,其它?

Epanechnikov Kernel

2??c(1?x),x?1KE(x)??其它??0,

Normal Kernel

KN(x)?e

x?12,x?0

KN(x)?(2?)?d2e?12x2,x?0

表5.1中d为空间维数，Vd为d维空间Rd中单位球的体积。

通常，如果希望得到数据集中密度最大数据的分布位置，可以对标准密度梯度进行估计。则利用核函数的可微性，对式(5.4)两边取梯度，可以得到式(5.5)：

?f(x)??f?(x)??h,Kh,K2nhd?2n?i?1?x?xi(x?xi)k???h?2???? (5.5)

若核函数的剖面函数k(x)在x??0,??上除了有限个点外均连续，那么定义剖面函数的负微分函数。

g(x)??k?(x) (5.6)

根据g(x)可推导出一个新的归一化核函数，如式(5.7)所示：

G(x)?Cg,dg?x2? (5.7)

其中，Cg,d

是归一化因子，核函数K(x)称为核函数G(x)的阴影函数，使用该核的多变量核

密度估计为：

f?G?x??Cg,dnhd??x?xig??h?2????(5.8)

将式(5.6)带入式(5.5)则有式(5.9)：

?f(x)??f?(x)??h,Kh,K2nh2nhd?2d?2n?i?1n?x?xi(x?xi)k???h?22??????i?1?x?xi(xi?x)g??h?????2

????x?????????????2nhd?2?n?x?xi??g??h??i?1?2??x?xi??xig??h???i?1?????n?x?x2????ig???i?1?h??n (5.9)

n假设式(5.9)中的?i?1?x?xig??h?2????项不为零，则将式(5.9)中的第二项定义为均值漂移向量

Mh,G(x)，如式(5.10)所示：

n?Mh,G?x??i?1n?x?xixig??h??x?xig??h?22?????i?1?????x?mh,G(x)?x(5.10)

其中，mh,G(x)称为采样均值，由式(5.11)给出：

n?mh,G?x??i?1n?x?xixig??h??x?xig??h?22?????i?1????(5.11)

根据式(5.8)和式(5.10)，可将式(5.9)进一步简化，得到式(5.12)：

??x??f?x??f?h,Kh,G2Cg,dh2Mh,G?x?(5.12)

式(5.12)变形可得：

Mh,G?x??12hCg,d2?f?x?h,K?f?h,G?x?(5.13)

式(5.13)表明，在目标点x处利用核函数G(x)计算得到的均值漂移向量与利用核函数K(x)估计得到的归一化概率密度梯度成正比。因此，均值漂移向量总是指向密度增大的最大方向，即“局部平均值向着大多数点所在区域移动”。

在实际应用中，对于一个给定给的目标点x，G(x)为对应的核函数，?为核函数G(x)的容许误差，则Mean Shift算法可按照以下三个步骤进行循环：

(1)计算均值漂移向量Mh,G?x?； (2)将均值漂移向量的计算结果赋给x;

(3) 如果Mh,G(x)??，则结束循环，否则从步骤(1)继续执行循环。

由上述三个步骤可知，Mean Shift算法的循环迭代步骤就是沿着概率密度梯度的方向不断移动，同时移动的步长不仅与目标点的概率密度有关，也与梯度的大小有关。在概率密度较大的局部极大值附近，算法移动的步长较小，反之，对于概率密度较低的区域算法移动步长较大，这就说明了Mean Shift算法实质上是一种自适应的梯度上升算法。在满足一定条件下，该算法会逐渐收敛到目标点附近的峰值。

对于Mean Shift算法的收敛性，利用如下内容进行证明。若核函数K(x)的剖面函数k(x)是单调递减的凸函数，算法收敛过程的精确数学表述如下。