资源描述：
《mean-shift算法概述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、MeanShift概述MeanShift简介MeanShift这个概念最早是由Fukunaga等人[1]于1975年在一篇关于概率密度梯度函数的估计中提出来的,其最初含义正如其名,就是偏移的均值向量,在这里MeanShift是一个名词,它指代的是一个向量,但随着MeanShift理论的发展,MeanShift的含义也发生了变化,如果我们说MeanShift算法,一般是指一个迭代的步骤,即先算出当前点的偏移均值,移动该点到其偏移均值,然后以此为新的起始点,继续移动,直到满足一定的条件结束.然而在以后的很长一段时间内MeanShift并没有引起人们的注意,直到20年以后,也
2、就是1995年,另外一篇关于MeanShift的重要文献[2]才发表.在这篇重要的文献中,YizongCheng对基本的MeanShift算法在以下两个方面做了推广,首先YizongCheng定义了一族核函数,使得随着样本与被偏移点的距离不同,其偏移量对均值偏移向量的贡献也不同,其次YizongCheng还设定了一个权重系数,使得不同的样本点重要性不一样,这大大扩大了MeanShift的适用范围.另外YizongCheng指出了MeanShift可能应用的领域,并给出了具体的例子.Comaniciu等人[3][4]把MeanShift成功的运用的特征空间的分析,在图像平
3、滑和图像分割中MeanShift都得到了很好的应用.Comaniciu等在文章中证明了,MeanShift算法在满足一定条件下,一定可以收敛到最近的一个概率密度函数的稳态点,因此MeanShift算法可以用来检测概率密度函数中存在的模态.Comaniciu等人[5]还把非刚体的跟踪问题近似为一个MeanShift最优化问题,使得跟踪可以实时的进行.在后面的几节,本文将详细的说明MeanShift的基本思想及其扩展,其背后的物理含义,以及算法步骤,并给出理论证明.最后本文还将给出MeanShift在聚类,图像平滑,图像分割,物体实时跟踪这几个方面的具体应用.MeanShi
4、ft的基本思想及其扩展基本MeanShift给定d维空间中的n个样本点,i=1,…,n,在点的MeanShift向量的基本形式定义为:(1)其中,是一个半径为h的高维球区域,满足以下关系的y点的集合,(2)k表示在这n个样本点中,有k个点落入区域中.我们可以看到是样本点相对于点的偏移向量,(1)式定义的MeanShift向量就是对落入区域中的k个样本点相对于点的偏移向量求和然后再平均.从直观上看,如果样本点从一个概率密度函数中采样得到,由于非零的概率密度梯度指向概率密度增加最大的方向,因此从平均上来说,区域内的样本点更多的落在沿着概率密度梯度的方向.因此,对应的,Mea
5、nShift向量应该指向概率密度梯度的方向.图1,MeanShift示意图如上图所示,大圆圈所圈定的范围就是,小圆圈代表落入区域内的样本点,黑点就是MeanShift的基准点,箭头表示样本点相对于基准点的偏移向量,很明显的,我们可以看出,平均的偏移向量会指向样本分布最多的区域,也就是概率密度函数的梯度方向.扩展的MeanShift核函数首先我们引进核函数的概念.定义:代表一个d维的欧氏空间,是该空间中的一个点,用一列向量表示.的模.表示实数域.如果一个函数存在一个剖面函数,即(3)并且满足:(1)是非负的.(2)是非增的,即如果那么.(3)是分段连续的,并且那么,函数就
6、被称为核函数.举例:在MeanShift中,有两类核函数经常用到,他们分别是,单位均匀核函数:(4)单位高斯核函数:(5)这两类核函数如下图所示.图2,(a)单位均匀核函数(b)单位高斯核函数一个核函数可以与一个均匀核函数相乘而截尾,如一个截尾的高斯核函数为,(6)图3显示了不同的值所对应的截尾高斯核函数的示意图.图3截尾高斯核函数(a)(b)MeanShift扩展形式从(1)式我们可以看出,只要是落入的采样点,无论其离远近,对最终的计算的贡献是一样的,然而我们知道,一般的说来,离越近的采样点对估计周围的统计特性越有效,因此我们引进核函数的概念,在计算时可以考虑距离的影
7、响;同时我们也可以认为在这所有的样本点中,重要性并不一样,因此我们对每个样本都引入一个权重系数.如此以来我们就可以把基本的MeanShift形式扩展为:(7)其中:是一个单位核函数是一个正定的对称矩阵,我们一般称之为带宽矩阵是一个赋给采样点的权重在实际应用的过程中,带宽矩阵一般被限定为一个对角矩阵,甚至更简单的被取为正比于单位矩阵,即.由于后一形式只需要确定一个系数,在MeanShift中常常被采用,在本文的后面部分我们也采用这种形式,因此(7)式又可以被写为:(8)我们可以看到,如果对所有的采样点满足(1)(2)则(8)式完全退化为(1
