meanshift算法简介

1、Meanshift算法的概述及其应用Meanshift的背景 Mean Shift 这个概念最早是由Fukunaga等人于1975年在一篇关于概率密度梯度函数的估计中提出来的,其最初含义正如其名,就是偏移的均值向量。 直到20年以后,也就是1995年,Yizong Cheng发表了一篇对均值漂移算法里程碑意义的文章。对基本的Mean Shift算法在以下两个方面做了改进,首先Yizong Cheng定义了一族核函数,使得随着样本与被偏移点的距离不同,其偏移量对均值偏移向量的贡献也不同,其次Yizong Cheng还设定了一个权重系数,使得不同的样本点重要性不一样,这大大扩大了Mean Shif

2、t的适用范围.另外Yizong Cheng指出了Mean Shift可能应用的领域,并给出了具体的例子。直观描述直观描述完全相同的桌球分布感兴趣区域质心Mean Shift矢量目的：找出最密集的区域直观描述直观描述完全相同的桌球分布感兴趣区域质心Mean Shift矢量目的：找出最密集的区域直观描述直观描述Distribution of identical billiard balls感兴趣区域质心Mean Shift矢量Objective : Find the densest region直观描述直观描述完全相同的桌球分布感兴趣区域质心Mean Shift矢量目的：找出最密集的区域直观描述直

3、观描述完全相同的桌球分布感兴趣区域质心Mean Shift矢量目的：找出最密集的区域直观描述直观描述完全相同的桌球分布感兴趣区域质心Mean Shift矢量目的：找出最密集的区域直观描述直观描述完全相同的桌球分布感兴趣区域质心目的：找出最密集的区域核函数说明 对在d维欧式空间中，x表示该空间中的一个点，K (x)表示该空间的核函数，其定义为：K (x)= ck,d k（|X|） 这里：K(x)是放射对称核函数，k(x)称为K(x)的轮廓函数，具有可微性，且；标准化常量ck,d严格正，使K(x)积分为1。 一维下的无参数估计 设X1,X2, Xn是从总体中抽出的独立同分布的样本，X具有未知的密度

4、函数f（x），则f（x）的核估计为： h为核函数的带宽。常用的核函数如下：分别是单位均匀核函数和单位高斯核函数 多维空间下的无参密度估计：在d维欧式空间X中，x表示该空间中的一个点， 表示该空间中的核函数, 空间中点x的概率密度估计值为:在计算机视觉中，最常用的是放射状对称核函数。 是放射状核函数 是 的轮廓函数 标准化常量 是个正数，保证 积分为1H为带宽矩阵。 1122HKxHK HxH表示d*d维的带宽矩阵 1122HKxHK Hx在实际中常采用H为单位矩阵的比例形式，即若再考虑到这个表达式就是基于核函数 的概率密度函数的估计怎样找到数据集合中数据最密集的地方呢？怎样找到数据集合中数据最

5、密集的地方呢？数据最密集的地方，对应于概率密度最大的地方。我们可以对概率密度求梯度，梯度的方向就是概率密度增加最大的方向，从而也就是数据最密集的方向。 令 ,假设除了有限个点，轮廓函数 的梯度对所有 均存在 。将 作为轮廓函数，核函数 为： 2,212nk dih Kidicxxfxxx gnhh221,221,12niinig dk didnig diixxx ghccxxgxh cnhhxxgh Mean shift向量 基于核函数G(x)的 概率密度估计用核函数G在 x点计算得到的Mean Shift向量 正比于归一化的用核函数K估计的概率密度的函数 的梯度,归一化因子为用核函数G估计的

6、x点的概率密度.因此Mean Shift向量 总是指向概率密度增加最大的方向.Mean shift向量的物理意义的什么呢？向量的物理意义的什么呢？为了更好地理解这个式子的物理意义，假设上式中g(x)=1平均的偏移量会指向样本点最密的方向，也就是概率密度函数梯度方向下面我们看一下mean shift算法的步骤 hmx给定一个初始点x,核函数G(x), 容许误差 ,Mean Shift算法循环的执行下面三步,直至结束条件满足,计算把 赋给 . 如果 ,结束循环;若不然,继续执行(1)( )hmx( )hmxx( )hm xx 上面的步骤也就是不断的沿着概率密度的梯度方向移动,同时步长不仅与梯度的大

7、小有关,也与该点的概率密度有关,在密度大的地方,更接近我们要找的概率密度的峰值,Mean Shift算法使得移动的步长小一些,相反,在密度小的地方,移动的步长就大一些.在满足一定条件下,Mean Shift算法一定会收敛到该点附近的峰值,Meanshift的应用Mean Shift可以应用在很多领域，比如聚类，图像平滑，图像分割。尤其是应用在目标跟踪领域，其跟踪算法是通过计算候选目标与目标模板之间相似度的概率密度分布，然后利用概率密度梯度下降的方向来获取匹配搜索的最佳路径，加速运动目标的定位和降低搜索的时间，因此在目标实时跟踪领域有着很高的应用价值。该算法由于采用了统计特征，因此对噪声有很强的

8、鲁棒性；由于是一个单参数算法，容易作为一个模块和别的算法集成；采用核函数直方图建模，对边缘阻挡、目标的旋转、变形以及背景运动都不敏感；同时该算法构造了一个可以用Mean Shift算法进行寻优的相似度函数。由于Mean Shift本质上是最陡下降法，因此其寻优过程收敛速度快，使得该算法具有很好的实时性。均值漂移在目标跟踪中应用1：目标模型叙述2：候选目标叙述3: 相似型函数比较4：目标定位5：整个算法流程u在起始帧，通过鼠标确定一个包含所有目标特征的椭圆，称为被跟踪目标的目标区域，这个目标区域也是核函数作用的区域，区域的大小等于核函数的带宽。u对目标区域进行描述，常用的方法是按照直方图的方式将

9、图像像素的值域等分成k个区间，每个区间按照值域的大小对应一个特征值。然后求出图像的像素值取每个特征值的概率。u对在初始帧图像中目标区域内所有的象素点，计算每个特征值的概率，我们称为目标模型的描述。目标模型的描述目标模型的描述目标区域的中心为 ，假设其中有n个象素用 表示，特征值的个数为m个 ,则目标模型的特征值 的概率密度估计为：u 为核函数的轮廓函数，由于遮挡或者背景的影响，目标模型中心附近的象素比外物象素更可靠， 对中心的象素给一个大的权值，而远离中心的象素一个小的权值u 总得作用是判断目标区域中象素的值是否属于第u个特征值。b(xi)是灰度值索引函数。属于该特征则值为1，否则为0(pdf

10、)。uC是一个标准化的常量系数，使得u于是我们得到了基于图像灰度特征的颜色直方图。 1.11muuumuqqq运动目标在第二帧及以后的每帧中可能包含目标的区域称为候选区域，其中心坐标为y，也是核函数的中心坐标。该区域中的象素用 表示。对候选区域的描述我们成为目标候选模型，候选模型的特征值 的概率密度为： 其中 是标准化常量候选模型的描述 1.11muuumup ypyp相似性函数的比较相似性函数的比较 1,mp ypypy1,mqqq模板区域:候选区域:相似性函数: ,?fyfp yq 1,mpypypy1,mqqq q pyy11 Bhattacharyya 系数 1cosTmyuuupyq

11、fypy qpyq相似性函数描述目标模型和候选模型之间的相似程度，在理想情况下两个模型的概率分布是完全一样的。我们使用Bhattacharyya系数作为相似性函数其值在0到1之间。 的值越大，表示两个模型越相似，在当前帧中不同的候选区域计算得到的候选模型，使得 最大候选区域即是在本帧中目标的位置。目标定位为使 最大，将当前帧的目标中心先定位为前一帧中目标中的位置 ，从这一点开始寻找最优匹配的目标，其中心为y。先计算目标候选模型 ，对 在 处进行泰勒级数展开，Bhattachcyarya系数可近似为：其中：类似于核函数密度估计，不过多了一个权值wi。使 式最大，就是要求 式最大，可以计算 的Mean Shift向量，这样我们就可以得到候选区域中心 移向真实目标区域y的向量:=值得注意的是，一般在一帧中找到目标的位置，需要Mean Shift算法从开始若干次迭代才能得到。其中 整个算法流程在当前帧以y0为起点，计算候选目标的特征pu(y0)u=1，2.m;计算候选目标与目标的相似度：计算权值wii=1，2.m利用Mean-Shift算法，计算目标新位置 (5)若 ，则停止；否则y0y1转步骤。 限制条件：新目标中心需位于原目标中心附近。Meanshift跟踪结果 转word文档。 Meanshift优缺点： 优点 算法复杂度小； 是无参数算法