【原创】刘龙坡转载请注明出处
【CSDN】http://blog.csdn.net/llp1992
最近，我非常关注跟踪这个块的算法。 关于meanshift的知识也来自论文和博客。 本博客总结了均值偏移算法，包括均值偏移算法的原理和公式推导，以及在图解、图像聚类、目标跟踪中的应用和优缺点总结。
算法原理meanshift算法实际上从名称上可以看到算法的核心、mean (平均)、shift )偏移。 简单地说，有一个点，它周围有很多点，计算点移动到每个点所需的偏移量之和，求平均，就可以得到平均偏移量。 (该偏移量的方向是周围点分布密集的方向)该偏移量是包含大小和方向的方向。 然后，点向平均偏移方向移动，并以此作为新的起点继续反复，直到满足一定的条件为止。
图解如下：
中心点是上面提到的周围的红点是黄色箭头，是我们求出的平均偏移矢量。 那么，图中的“大圆”是什么呢？ 我们上面说的周围的点周围是什么概念？ 总是限制点什么吧。 那个“圆”是我们的限制条件，或者在图像处理中，是我们检索迭代时的窗口大小。 但在opencv中，我们一般使用矩形窗口，而且是图像，是二维的。 这里其实不是圆，而是高维的球。
第一步，首先设定起点。 我之前说过，因为是球，所以有半径。 球内的所有点都是计算出黑色箭头的向量。 将所有向量相加并平均，即可获得均值shift向量，即图中的黄色向量。
然后，以meanshift向量的重点为圆心，制作高维球体。 如下图所示，重复上述步骤，最终收敛到点分布中密度最高的地方
最终结果如下
用数学方法推导
给定d维空间Rd的n个样本点i=1，n，并且在空间中选择给定点x时，均值shift向量的基本定义如下：
其中有半径为的高维区域。 定义如下。
表示该n个采样点xi中，k个点落入区域.
然后，如果升级meanshift向量并添加内核函数(如ckdxmf内核)，则meanshift算法为：
k )解释核函数，h是半径，是单位密度。 为了使上式f最大，最容易考虑求出上式，确实meanshift是求出上式。
命令的话，我们可以做以下事情。
因为我们使用的是ckdxmf核，所以第一项是
第二项相当于一个meanshift向量的式：
上述公式可以表示为：
图解式的结构如下。
当然，在求出meanshift矢量时，其密度最大是极值点处，此时梯度为0，即
而且，只有在那个时候成立，这个时候我们才能得到新的原点坐标：
以上是公式的推导。 我建议你读一遍理解。 自我参照
33558 www.cn blogs.com/liqizhou/archive/2012/05/12/2497220.html
在实际项目中，meanshift的算法流程如下。
1、选择中心点，用半径制作高维球体(如果我们正在处理图像或视频，可以是二维窗口中的矩形，不限于球)，标记落在窗口中的所有点
2、计算，如果的值小于阈值或迭代次数达到某个阈值，停止算法，否则用上述求圆心的公式更新点，进入步骤1
正如meanshift在图像处理中的聚类、跟踪中的应用，meanshift算法的每一步其实都在向密度最大的方向发展，空间中点分布的密度正好可以应用于meanshift算法，但一幅图像紧密配合
首先考虑的还是距离。 距离越近，越有可能被分为同一种类。 所以我们决定点的概率密度，即
定义为越接近点像素的点，其概率密度越高
然后，由于分类为同一类型的颜色通常被认为很接近，因此定义颜色的概率密度：
越是与点的颜色相似的点，概率越高
然后，各点的概率密度分布由下式得到。
这里，表示空间位置的信息，越接近距离的点其值越大，表示颜色信息，颜色越类似其值越大。
接下来可以运送meanshift
算法进行聚类。 meanshift算法目标跟踪在opencv中已经有库函数可以调用了：
int cvMeanShift(const CvArr* prob_image,CvRect window,CvTermCriteria criteria,CvConnectedComp* comp );查看API可以知道，调用该函数时，需要输入的图像是反向投影图，什么是反向投影图，简单介绍一下：
图像的反向投影图是用输入图像的某一位置上像素值（多维或灰度）对应在直方图的一个gldhj上的值来代替该像素值，所以得到的反向投影图是单通的。用统计学术语，输出图像象素点的值是观测数组在某个分布（直方图）下的概率。
不懂？用例子说明一下：
Image=
0 1 2 3
4 5 6 7
8 9 10 11
8 9 14 15
(2)该灰度图的直方图为（gldhj指定的区间为[0,3)，[4,7)，[8,11)，[12,16)）Histogram=
4 4 6 2
(3)反向投影图Back_Projection=
4 4 4 4
4 4 4 4
6 6 6 6
6 6 2 2
例如位置(0,0)上的像素值为0，对应的gldhj为[0,3)，所以反向直方图在该位置上的值这个gldhj的值4。
这下懂了吧，其实就是一张图像的像素密度分布图，而我们的meanshift算法本身就是依靠密度分布进行工作的，找到密度分布最大的地方。所以就很容易理解这个输入参数了。
半自动跟踪思路：输入视频，用画笔圈出要跟踪的目标，然后对物体跟踪。
用过opencv的都知道，这其实是camshiftdemo的工作过程。
第一步：选中物体，记录你输入的方框和物体。
第二步：求出视频中有关物体的反向投影图。
第三步：根据反向投影图和输入的方框进行meanshift迭代，由于它是向重心移动，即向反向投影图中概率大的地方移动，所以始终会移动到目标上。
第四步：然后下一帧图像时用上一帧输出的方框来迭代即可。
全自动跟踪思路：输入视频，对运动物体进行跟踪。
第一步：运用运动检测算法将运动的物体与背景分割开来。
第二步：提取运动物体的轮廓，并从原图中获取运动图像的信息。
第三步：对这个信息进行反向投影，获取反向投影图。
第四步：根据反向投影图和物体的轮廓（也就是输入的方框）进行meanshift迭代，由于它是向重心移 动，即向反向投影图中概率大的地方移动，所以始终会移动到物体上。
第五步：然后下一帧图像时用上一帧输出的方框来迭代即可。
meanShift算法用于视频目标跟踪时，其实就是采用目标的颜色直方图作为搜索特征，通过不断迭代meanShift向量使得算法收敛于目标的真实位置，从而达到跟踪的目的。
在目标跟踪中：meanshift有以下几个优势：
（1）算法计算量不大，在目标区域已知的情况下完全可以做到实时跟踪；
（2）采用核函数直方图模型，对边缘遮挡、目标旋转、变形和背景运动不敏感。
同时，meanShift算法也存在着以下一些缺点：
（1）缺乏必要的模板更新；
（2）跟踪过程中由于窗口宽度大小保持不变，当目标尺度有所变化时，跟踪就会失败；
（3）当目标速度较快时，跟踪效果不好；
（4）直方图特征在目标颜色特征描述方面略显匮乏，缺少空间信息；
由于其计算速度快，对目标变形和遮挡有一定的鲁棒性，其中一些在工程实际中也可以对其作出一些改进和调整如下：
（1）引入一定的目标位置变化的预测机制，从而更进一步减少meanShift跟踪的搜索时间，降低计算量；
（2）可以采用一定的方式来增加用于目标匹配的“特征”；
（3）将传统meanShift算法中的核函数固定带宽改为动态变化的带宽；
（4）采用一定的方式对整体模板进行学习和更新；