目标跟踪之MeanShift/CamShift

meanshift（均值漂移）的基本思想是利用概率密度的梯度爬升来寻找局部最优解，漂移这个说法非常形象的形容了该算法。

opencv中有实现meanshift作目标跟踪，可以通过它来帮助理解算法思想：

移动的物体在视频每帧所处的位置都可能有位移，目标跟踪便是希望能实现在视频中跟踪移动的目标物体并标记出来。为了便于捕获目标物体，一般得先找到目标物体与背景的差异所在（当然，在镜头静止的场景下也有通过帧间像素差异对比的方式寻找运动物体的算法，但是这种方法适用面有限，特别不适合用于镜头存在运动的场景），这种差异可以是颜色、可以是纹理、也可以是边缘或者形状。opencv实现的meanshift采用HSV颜色空间中的H分量（色调）来统计目标与背景的差别，实现步骤如下：
1.将图像从RGB颜色空间转至HSV颜色空间。
2.split出HSV空间中的H分量。
3.在统计选中的目标框内的H（色调）分布直方图。
4.通过步骤3得到的直方图计算整个色调域（0-360）中各值是前景的概率，并将结果归一化至（0-255）得到色调域的前景概率分布。
5.利用4所得的前景概率分布进行H通道原图的前景概率反向投影，得到的结果中灰度值的大小代表着该点是前景的概率。

完成以上5步之后，一般反向投影图的目标处显示呈片区域的高亮。

接下来需要从上一帧目标所在的区域出发，在下一帧的反向投影图中搜索该目标所处的位置，即通过迭代的方式找寻局部最优解，如果将迭代过程一层一层显示出来可以看到代表目标的框从上一帧目标所处的位置一点一点往下一帧目标所处的位置移动，漂移之说非常形象。opencv中寻找最优解的方式是通过寻找局部区域重心，步骤如下：
1.以上一帧目标所在位置作为搜索窗的出发点，在反向映射图中计算搜索窗的一阶矩（firstMoment），并通过一阶矩计算搜索窗的重心。
2.计算步骤1所得重心与上一次迭代所得重心的欧氏距离，如果小于阈值的话即认为最优解达成，迭代结束，否则将搜索框中心移动至步骤1所得重心处，再次进行步骤1.
以上迭代的结束条件为1)重心距离小于阈值，寻找最优解达成 2)达到迭代次数上限（opencv默认的是10次）。
通过以上描述可以发现meanshift算法的两个较为显著的缺点：
1.两帧间目标框需有交集，否则搜索框可能无法迭代漂移至新帧的目标处，这就要求目标的移动速度不能太快，否则会跟丢。
2.搜索窗大小是不变的，当目标由于运动而导致显示尺寸有变化时meanshift的跟踪效果不好。

针对于缺点2，出现了camshift，camshift全称“Continuously Apaptive Mean-SHIFT”，是一种搜索窗尺寸连续自适应的meanshift算法改良，它在每次meanshift完成后又追加了一个搜索窗尺寸更新的步骤。
camshift更新搜索窗尺寸的方式是计算二阶矩（secondMoment），然后采用固定的公式得到目标的尺度和方向，然后更新搜索窗尺寸。