MST：《Real-Time Tracking of Non-Rigid Objects using Mean Shift》 mean shift
前言
无参密度估计理论，无参密度估计也叫做非参数估计，属于数理统计的一个分支，和参数密度估计共同构成了概率密度估计方法。参数密度估计方法要求特征空间服从一个已知的概率密度函数，在实际的应用中这个条件很难达到。而无参数密度估计方法对先验知识要求最少，完全依靠训练数据进行估计，并且可以用于任意形状的密度估计。所以依靠无参密度估计方法，即不事先规定概率密度函数的结构形式，在某一连续点处的密度函数值可由该点邻域中的若干样本点估计得出。常用的无参密度估计方法有：直方图法、最近邻域法和核密度估计法。
MeanShift算法正是属于核密度估计法，它不需要任何先验知识而完全依靠特征空间中样本点的计算其密度函数值。对于一组采样数据，直方图法通常把数据的值域分成若干相等的区间，数据按区间分成若干组，每组数据的个数与总参数个数的比率就是每个单元的概率值；核密度估计法的原理相似于直方图法，只是多了一个用于平滑数据的核函数。采用核函数估计法，在采样充分的情况下，能够渐进地收敛于任意的密度函数，即可以对服从任何分布的数据进行密度估计。
1.mean shift vector-均值移动向量
Mean Shift向量：偏移的均值向量。定义如下：对于给定d维空间Rd中的n个样本点xi,i=1,2,…,n在xd点的Mean Shift向量的基本形式定义为：
其中，Sh是一个半径为h的高维球区域：
，k表示在这n个样本点中有k个落入球Sh中。
直观上来看，这k个样本点在x处的偏移向量即为：对落入Sh区域中的k个样本点相对于点x的偏移向量求和然后取平均值；
几何解释为：如果样本点xi服从一个概率密度函数为f(x)的分布，由于非零的概率密度函数的梯度指向概率密度增加最大的方向，因此从平均上来说，Sh区域内的样本点更多的落在沿着概率密度梯度的方向。因此，Mean Shift向量Mh(x)应该指向概率密度梯度的方向。如图(图片来源)所示：
这里写图片描述：黄色箭头即为平均的偏移向量Mh(x)，指向样本分布最多的区域，也就是概率密度函数的梯度方向。
求解最优的概率密度最大处的mean shift 算法的迭代过程：
先算出当前点的偏移均值，移动该点到其偏移均值，然后以此为新的起始点，继续移动，直到满足一定的条件结束。结合上图，算法实施过程为：原点是选定的初始迭代点，将蓝色圆(其半径记为h)内所有向量相加，相加的结果如黄色向量所示，其终点指向上图所示的红色点，则下一次迭代以该红色点为圆心，h为半径画圆，然后求这个圆内以圆心为起点所有向量的和。如此迭代下去，圆的中心点为收敛于一个固定的点，也就是概率密度最大的地方。所以 均值漂移算法本质上是一种基于梯度的优化算法。
在这种情况下，求出的mean shift vector 向量是表示的是各个样本点位置的权重是一样的情况下，即就是没有考虑样本点距离距离当前的中心点的距离等因素，是没有加入权重的mean shift ，在image的追踪中，由于在某一个位置的时候，其周围位置的密度是一样的，那么进行密度估计之后，位置还是应该在原来的位置，但是，在实际的应用中，每个位置所占的密度权重是不一样的，所以，估算出得位置不在原处。
最为重要的是：mean shift 可以根据样本点的分布情况，也就是密度估计，然后通多迭代的方法可以求出概率密度最大的位置，此处借助的是随机变量本身的分布情况，同样，在目标追踪中，有一些列的可能的位置，一般我们是通过均匀的，但是每个样本点由于在此处决定的object 区域不一样，与原先的模板区域的相似度不一样，所以，所以所占的密度权重是不一样的，所以，对于密度估计来说，不经要考虑样本所在的位置分布，同样也要考虑样本的密度权重，这个权重会对mean shift 的迭代产生很大的影响。
在具体的tracking中，这个位置的密度分布是一样的，唯一的考量是每个位置所在的重要程度，也就是密度权重不一样，进而能够推算出密度最大的位置。
2.加入了核化以及权重的mean shift
常用的两个kernel函数：
Flat kernel:
Gaussian kernel:
此外， 在拓展Mean Shift算法的过程中，对每个样本点设定一个权重系数,使得不同的样本点对计算Mean Shift向量的重要性不一样 。引入核函数和样本点加权的Mean Shift算法具有如下形式：
其中：
, G(x)是一个单位核函数，H是一个对称正定矩阵，称之为带宽矩阵。
w(xi)≥0是采样点的权重系数。
实际应用中，带宽矩阵H常被限制为对角阵，特别地，最为常见的带宽矩阵为
。则Mean Shift向量的计算公式为：
特别地，当w(xi)=1, 核函数采用flat kernel时，上式退化为最开始的Mean Shift向量计算公式。
特别重要：在计算这个mean shift vector 的时候这个权重的计算是至关重要的，在追踪中起到了至关重要的作用。
总结：
mean shift vector 通过迭代最终找到了分布的概率密度最大的位置。因为分布，所以不同的位置的概率分布不一样，也是密度不一样，但通过这样的迭代可以找到密度最大的位置，也就是概率密度最大的位置，迭代的方式是基于梯度的方法。在目标追踪中，是在候选位置的空间中进行迭代，在候选位置的空间中存在一个分布，不知道具体的分布，只能进行的是无参密度估计，找到概率密度最大的位置；当候选位置的采样时均匀分布时，要加入样本的权重，以表示不同样本的重要程度，在追踪中，这个权重的确定是根据Bhattacharyya coefficient 来确定的，最终根据mean shift vector 迭代来确定最后的位置。
**
**
论文中算法的过程 ：《Real-Time Tracking of Non-Rigid Objects using Mean Shift》
**
**
可以看到在迭代过程中，权重的计算以及最后迭代停止的条件是非常重要的，另外进行这样迭代必须要是有益的，朝着找到最相似的位置进行下去。相似度衡量用：
用mean shift来跟踪属于确定性算法，粒子滤波器属于统计学方法。meanshift跟踪算法相对于粒子滤波器来说可能实时性更好一些，可是跟踪的准确性在理论上还是略逊于粒子滤波器的。mean shift跟踪的的实质就是通过相应的模板来确定目标的下一个位置。通过迭代找到新的中心点（即是目标的新的位置点）
思考：
为什么说是基于梯度的一种迭代方法，因为分布是一个概率密度函数，在概率密度大的区域，自然样本点集中就多，而在mean shift vector 指向了在一个区域中样本集中的区域，即概率密度大的区域，同样，梯度也是指向极值的方向，虽然求得的mean shift vector 不一定完全和梯度方向一致，但是与梯度方向的夹角是锐角，是朝着极值的方向走的。
参考博客 ：