介绍CAMshift之前,必须得先介绍一下MeanShift。因为CAMshift的全称是Continuously Adaptive Meanshift,其中就包含了MeanShift。
Meanshift[1]
直观地看,Meanshift非常容易理解。假设你有一堆点,然后给你一个小窗,你需要做的是通过移动这个小窗,使得窗里的点数尽可能得多。如下图所示:
初始给定一个蓝色圈圈,叫C1,其中心用蓝色方框表示,叫C1_o。那么,你计算一下蓝色圆圈的重心,你会得到C1_r(由一个小蓝圈表示),它是这个蓝色圈圈的实际重心。很显然,两者并不一样。接下来,你需要移动你的圈圈,使两者重合。然后计算新圈圈的质心,大概率的,新的质心和中心还不重合。那么,你就再移动你的圈圈,重复这个过程,直到两者基本重合(或小于给定的误差)。最终,你会得到一个包含最多点的圈圈,在图中被标记为绿色,命名为C2。这个过程可以由以下的GIF动画,形象地展示出来:
通常情况下,我们是在histogram backprojection image上做的。当目标发生运动时,在histogram backprojection image很容易看到。那么,meanshift通过移动窗口就能定位到目标的新位置上。 下图是用meanshift追踪一辆汽车的结果:
Camshift[2]
如果你仔细观察这个结果,很容易发现问题:我们的窗口大小是固定的,不管汽车离我们远,还是离我们近。这显然是不够好,我们需要让我们的窗口自适应:不仅仅是大小,还有方向。这个解决方案来自OpenCV Labs,并叫做CAMShift(Continuously Adaptive Meanshift)。文章的作者是Gary Bradsky,发表在1998年。
首先他用的是meanshift,一旦meanshift收敛了,他就更新窗口的大小,。同时还进行椭圆拟合得到最佳的方向。在新的scale下,再应用meanshift,如此迭代直到达到一定的准确率。 结果如下所示:
这个过程可以由以下的GIF动画,形象地展示出来:
参考文献
[1] Cheng Y. Mean shift, mode seeking, and clustering[J]. IEEE transactions on pattern analysis and machine intelligence, 1995, 17(8): 790-799.
[2] Allen J G, Xu R Y D, Jin J S. Object tracking using camshift algorithm and multiple quantized feature spaces[C]//ACM International Conference Proceeding Series. 2004, 100: 3-7.