meanshift算法简介

1、Meanshift算法的概述及其应用直观描述直观描述完全相同的桌球分布完全相同的桌球分布感兴趣区域感兴趣区域质心质心Mean Shift矢量矢量目的：找出最密集的区域Meanshift介绍 Meanshift算法是Fukunaga于1975年提出的。直到1995年， Yizong Cheng针对离x越近的采样点对x周围的统计特性越有效，定义了一族核函数。同时他认为所有的样本点重要性不同，设定了一个权重系数，扩大了Meanshift的使用范围。其思想概括起来就是：利用概率密度的梯度爬升来寻找局部最优。输入一个在图像的范围，然后Meanshift算法迭代（朝着重心迭代）直到满足要求为止。 Mean

2、shift的基本形式为： 是一个半径为h的高维球区域，k表示n个样本点有k个落入Sh中。hihSxiMxxkx)(1)(hS4核函数说明 对在d维欧式空间中，x表示该空间中的一个点，用一列向量x表示，K(x)表示该空间的核函数，其定义为： 这里：K(X) 称核函数，k(x)为非增的分段连续剖面函数，标准化常量c,d,为正，且k(x)积分为1。2|)(|c)(xdkXK平均的偏移量会指向样本点最密的方向，也就是概率密度函数梯度方向，引入核函数和权重系数后得到：nixixnxhM1)(1)(niixwxixhGnixixxwxixhGxhMi1)()(1)()()()(G(x)是一个单位核函数，H

3、是一个正定dxd的对称矩阵，又称带宽矩阵。w(xi)是采样点xi的权重)(2/ 1(2/ 1)(xixHGHxxhGi通常H取为正比于单位矩阵的对角阵即 ;h为核函数的带宽,为一确定在系数，常用的单位核函数G（x）如下：分别是单位均匀核函数和单位高斯核函数；前面公式可写为：这里可以看到若W(xi)=1, G(x)=1时，就转化成了meanshift基本形式。 EhH2niiiniixihxwhxxGxxwhxxGxMi11)()()()()()(多维空间下的无参密度估计（以下是证明Meanshift向量Mh(x)总是向密度增加的方向漂移）：在d维欧式空间X中，x表示该空间中的一个点， 表示该空

4、间中的核函数, f(x)的概率密度函数为:核函数K(X)的剖面函数为k(x),且K(x)的负倒数为g(x),即 其对应的核函数为2|)(|)(xkXK )(xkxgniidniiixwhxwhxxKxf11)()()()(2|)(|)(xgXG上式对x求导，得到概率密度函数的梯度函数 fK(x):niidniiiiKxwhxwhxxGxxxf1212)()()()(2)()()(2)()()()()()()(22112122xMxfhxwhxxGxwhxxGxxxwhxwhxxGhhGniiiniiiiniidniii以G(x)为核函数的概率密度函数用核函数G在x点的Meanshift向量该式

5、表明用核函数G在x点得到的Meanshift向量正比于归一化的用核函数K估计的概率密度梯度(归一化因子即分母为用核函数G估计的x点概率密度)。数据最密集的地方，对应于概率密度最大的地方。对概率密度求梯度，梯度的方向就是概率密度增加的方向，从而也就是向最密集的方向漂移。由上式可得：)()(21)(2xfxfhxMGKh 对目标进行跟踪时，可以把图片想象成一张概率密度图。图像输入后是一个目标图像的直方图（也可以认为是目标图像），还一个输入是当前图像就是你要跟踪的全图，输出大小与全图一样大，它上像素点表征着一种概率，就是全图上这个点是目标图像一部分的概率。如果这个点越亮，就说明这个点属于物体的概率越

6、大。现在我们明白了这原来是一张概率图了。当用meanshift跟踪时，输入的原来是这样一幅图像，如此可以实现对目标的跟踪。 关键：反向投影关键：反向投影 如果一幅图像的区域中显示如果一幅图像的区域中显示的是一种结构纹理或者一个独特的物体，那么这个区域的的是一种结构纹理或者一个独特的物体，那么这个区域的直方图可以看作一个概率函数，给出的是某个像素属于该直方图可以看作一个概率函数，给出的是某个像素属于该纹理或物体的概率。所谓反向投影就是首先计算某一特征纹理或物体的概率。所谓反向投影就是首先计算某一特征的直方图模型，然后使用模型去寻找测试图像中存在的该的直方图模型，然后使用模型去寻找测试图像中存在的

7、该特征特征。下面我们看一下mean shift算法的步骤 hmx给定一个初始点x,核函数G(x), 容许误差 ,Mean Shift算法循环的执行下面三步,直至结束条件满足,计算把 赋给 . 如果 , 结束循环;若不然,循环执行( )hmx( )hmxx( )hm xx 上面的步骤也就是不断的沿着概率密度的梯度方向移动,同时步长不仅与梯度的大小有关,也与该点的概率密度有关,在密度大的地方,更接近我们要找的概率密度的峰值,Mean Shift算法使得移动的步长小一些；相反,在密度小的地方,移动的步长就大一些.在满足一定条件下,Mean Shift算法一定会漂移到该点附近的峰值。均值漂移在目标跟踪

8、中应用1：目标模型叙述2：候选目标叙述3: 相似型函数比较4：目标定位5：整个算法流程u在起始帧，通过鼠标确定一个包含所有目标特征的矩形，称为被跟踪目标的目标区域，这个目标区域也是核函数作用的区域，区域的大小等于核函数的带宽。u对目标区域进行描述，常用的方法是按照直方图的方式将图像像素的值域等分成k个区间，每个区间按照值域的大小对应一个特征值。然后求出图像的像素值取每个特征值的概率。u对在初始帧图像中目标区域内所有的象素点，计算每个特征值的概率，我们称为目标模型的描述。目标模型的描述目标模型的描述目标区域的中心为 ，假设其中有n个象素用 表示，特征值的个数为m个 ,则目标模型的特征值 的概率密

9、度估计为： 为核函数的轮廓函数，由于遮挡或者背景的影响，目标模型中心附近的象素比外物象素更可靠， 对中心的象素给一个大的权值，而远离中心的象素一个小的权值 总得作用是判断目标区域中象素的值是否属于第u个特征值。b(xi)是灰度值索引函数。属于该特征则值为1，否则为0(pdf)。 C是一个标准化的常量系数，使得 于是我们得到了基于图像灰度特征的颜色直方图。 1.11muuumuqqq运动目标在第二帧及以后的每帧中可能包含目标的区域称为候选区域，其中心坐标为y，也是核函数的中心坐标。该区域中的象素用 表示。对候选区域的描述我们成为目标候选模型，候选模型的特征值 的概率密度为： 其中 是标准化常量候

10、选模型的描述 1.11muuumup ypyp相似性函数的比较相似性函数的比较 1,mp ypypy1,mqqq模板区域模板区域:候选区域候选区域:相似性函数相似性函数: ,?fyfp yq 1,mpypypy1,mqqq q pyy11 Bhattacharyya 系数 1cosTmyuuupyqfypy qpyq相似性函数描述目标模型和候选模型之间的相似程度，在理想情况下两个模型的概率分布是完全一样的。我们使用Bhattacharyya系数作为相似性函数其值在0到1之间。 的值越大，表示两个模型越相似，在当前帧中不同的候选区域计算得到的候选模型，使得 最大候选区域即是在本帧中目标的位置。目

11、标定位为使 最大，将当前帧的目标中心先定位为前一帧中目标中的位置 ，从这一点开始寻找最优匹配的目标，其中心为y。先计算目标候选模型 ，对 在 处进行泰勒级数展开，Bhattachcyarya系数可近似为：其中：类似于核函数密度估计，不过多了一个权值wi。使 式最大，就是要求 式最大，可以计算 的Mean Shift向量，这样我们就可以得到候选区域中心 移向真实目标区域y的向量:=值得注意的是，一般在一帧中找到目标的位置，需要Mean Shift算法从开始若干次迭代才能得到。其中算法过程 (1).初始化搜索窗 (2).计算搜索窗的颜色概率分布（反向投影） (3).运行meanshift算法，获得搜索窗新的大小和位置。 (4).在下一帧视频图像中重新搜索窗的大小和位置， 进行相似度匹配， 再跳转到(2)继续进行，直 到 。( )hm xxMeanshift优缺点：优点1.算法计算量不大，在目标区域已知的情况下完全可以做到实时跟踪2.采用核函数直方图模型，对边缘遮挡、目标旋转、变形和背景运动不敏感缺点：1.缺乏必要的模板更新2.跟踪过程中由