mean shift 图像分割 (二): 3 算法原理，4 延伸

mean shift 图像分割 (三): 5 非参数密度估计

图像分割—mean shift(OpenCV源码注解)

3 算法原理

3.1 密度估计

    关于密度估计，这里直接使用结论，具体原理，参见第5部分:非参数密度估计。

某一点的密度估计值：

    为核函数，一般我们会使用径向对称（radially symmetric）核函数。即：

    其中为标准化常数，使得

    称为的profile,原文介绍了两种，对应两种核，这里再补充一种。

    （1）Epanechnikov Kernel

    它的profile如下：

可视化效果

    （2）Normal Kernel

    它的profile如下：

可视化效果

    （3）Uniform Kernel

    它的profile如下：

可视化效果

    3.2密度梯度估计

    3.2.1 梯度方向

    处的密度估计：

    则密度梯度估计：

    令，即这一部分又可以看成是一个核密度估计。

    物理意义：梯度方向是各个数据点的方向向量的加权求平均，即上式可以看成

蓝色圈圈—>到黄色圈圈

    例如，我们使用的是Normal Kernel，则

    想象一下几十匹马同时拉一辆车的恢宏场面，每匹马都往自己的方向拉，不过，距离越近的马，其力量越大，初中物理告诉我们，结果是合力的方向，如上图的黄色箭头。

    注意：Epanechnikov Kernel求导后实质上就是Uniform Kernel。

    3.2.2 漫漫爬坡路

    虽然，往哪个方向移动知道了，但是移动的步长并不好确定，下面转化一下形式，可以得到自适应步长:

    看起来有点复杂，实际上只是简单的替换。其中类比, 类比

    中间项的物理意义：处的核的密度估计,是求导所得，如果用Normal Kernel，则的形式和相同。

    中间项只是一个数，而最后一项就是所谓的mean shift向量，是一个方向向量，对应的就是我们的梯度方向。

    对于某一点往梯度方向移动到，则新坐标：

    物理意义：很直观，以为权值计算重心。

    当时，我们就到达了模点，由于，所以只能是。不过想要一步登天，很难，除非你出生很好，就落在模点，大多数数据点，还是得老老实实，一步一个脚印爬上去。还是设爬过的脚印依次，，则脚印公式：

    3.3.3 自适应步长

    可以看出步长与成反比，还是以Normal Kernel为例，越靠近模点，步长越小，反之越大。

    原文证明了，只要是凸函数，单调递减（可以不是哦），那么就能保证它总能收敛到模点，并且是单调递增的（我没看……）。只要步履不停，我们总会遇见，多么美好的世界啊，求遇见。

    3.3 图像分割领域的具体化

    本质上，mean shift解决任何问题，都是转化成密度估计问题。但具体问题还得具体分析。对于图像它有两种信息，坐标和颜色，前者为spatial 空间后者为range空间，对于单通道图片即灰度值，对于彩色图片即或者效果更好的等。二者是截然不同的属性，决定了不能等同视之。因此，我们使用多元核密度估计（multivariate kernel）。设spatial有2维，range空间，设为维。

    一元核：

    即

    图像分割中使用的多元核：

滤波的结果

    物理意义：分别为坐标空间核和颜色空间核的带宽（bandwidth）/尺度，我说不清，看结果吧。

    3.4回首OpenCV实现

    第二步，重心计算公式

    我们是对以为中心为边长的区域求重心，其实本应该是：

    用的是Uniform Kernel，也就是说用的是Epanechnikov Kernel

    此时，距离筛选是由核函数实现的，因此我们是对图像中所有的数据点计算重心，而不是落在为中心，为边长的区域内的点求重心。

    OpenCV的实现中， 并不是圆形的，为了循环时程序实现的方便，就用方形近似，但是严格的球体。

    不过方形的也可以写成核函数形式：

    此外，Normal Kernel 的平滑效果固然好，但是计算量大，所以主要还是用Uniform Kernel。原文说大部分场合，Uniform Kernel和Normal Kernel就能取得很好的效果。

    4延伸

    不写了，已经写得太多了……这次就只挖个坑，日后再跳

    Camshift

能够自动调整窗口的大小，能适应目标尺度变化的情况，比如人脸跟踪时，人与摄像头的距离动态变化的情况。

    带宽选择

    图像分割的带宽一般是自己调整看效果，最优带宽也能也求出来？不过，我倒想看看自适应带宽。最优带宽值看原文吧。

    Mode prune

    对于鞍点等会产生一些虚假的模点，如上图，红色线上的点可能就跑到鞍点去了，去除办法：将模点的坐标稍作移动，再从移动后的位置继续爬，如果还能爬到原来模点的位置，那就保留，否则踢掉。恩，是你的跑不了，不是你的撒手就跑。

    与双边滤波的关联

    可以看做死板的mean shift 参见[4]的5.2.1

    与分水岭分割

    逆过程，从山峰开始找山谷，参见[4]的Sec5.2.1

    补充阅读

    图像分割加速：原文提到了一种加速方法，先随机选取一部分点作为先头部队，让它们去找模点，找的过程中就会开辟出很多到模点的道路，然后呢，让其余的点插到离它最近的路走过去就好了。此外，还有层级分割的方法，OpenCV的实现应该就是其中一种实现。

    A topological approach to hierarchical segmentation using mean shift. CVPR 2007

    目标跟踪：Kernel-Based Object Tracking, PAMI 03