锐客网

  1. 首页 > it技术 > >

mean shift 图像分割（二）

图像分割

Reference:
[1] Mean shift: A robust approach toward feature space analysis, PAMI, 2002
[2] mean shift,非常好的ppt ，百度文库链接
[3] Pattern Recognition and Machine Learning, Bishop, 2006，Sec 2.5
[4] Computer Vision Algorithms and Applications, Richard Szeliski, 2010, Sec 5.3
[5] Kernel smoothing,MP Wand, MC Jones ,1994, Chapter 4

mean shift 图像分割 (一): 1 总体思想，2 算法步骤
mean shift 图像分割 (二): 3 算法原理，4 延伸

mean shift 图像分割 (三): 5 非参数密度估计
图像分割—mean shift(OpenCV源码注解)




3 算法原理 3.1 密度估计
关于密度估计，这里直接使用结论，具体原理，参见第5部分:非参数密度估计。
某一点的密度估计值：
mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片
为核函数，一般我们会使用径向对称（radially symmetric）核函数。即：
mean shift 图像分割（二）
文章图片

其中mean shift 图像分割（二）
文章图片
为标准化常数，使得
mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片
称为mean shift 图像分割（二）
文章图片
的profile,原文介绍了两种mean shift 图像分割（二）
文章图片
，对应两种核，这里再补充一种。
（1）Epanechnikov Kernel
它的profile如下：
mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片

可视化效果
（2）Normal Kernel
它的profile如下：
mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片

可视化效果
（3）Uniform Kernel
它的profile如下：
mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片

可视化效果
3.2密度梯度估计
3.2.1 梯度方向
mean shift 图像分割（二）
文章图片
处的密度估计：
mean shift 图像分割（二）
文章图片

则密度梯度估计：
mean shift 图像分割（二）
文章图片

令mean shift 图像分割（二）
文章图片
，即这一部分又可以看成是一个核密度估计。
物理意义：梯度方向是各个数据点的方向向量的加权求平均，即上式可以看成
mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片

蓝色圈圈—>到黄色圈圈
例如，我们使用的是Normal Kernel，则
mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片

想象一下几十匹马同时拉一辆车的恢宏场面，每匹马mean shift 图像分割（二）
文章图片
都往自己的方向mean shift 图像分割（二）
文章图片
拉，不过，距离越mean shift 图像分割（二）
文章图片
近的马，其力量mean shift 图像分割（二）
文章图片
越大，初中物理告诉我们，结果是合力的方向，如上图的黄色箭头。
注意：Epanechnikov Kernel求导后实质上就是Uniform Kernel。
3.2.2 漫漫爬坡路
虽然，往哪个方向移动知道了，但是移动的步长并不好确定，下面转化一下形式，可以得到自适应步长:
mean shift 图像分割（二）
文章图片

看起来有点复杂，实际上只是简单的替换。其中mean shift 图像分割（二）
文章图片
类比mean shift 图像分割（二）
文章图片
, mean shift 图像分割（二）
文章图片
类比mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片

中间项的物理意义：mean shift 图像分割（二）
文章图片
处的核mean shift 图像分割（二）
文章图片
的密度估计,mean shift 图像分割（二）
文章图片
是mean shift 图像分割（二）
文章图片
求导所得，如果mean shift 图像分割（二）
文章图片
用Normal Kernel，则mean shift 图像分割（二）
文章图片
的形式和mean shift 图像分割（二）
文章图片
相同。
中间项只是一个数，而最后一项mean shift 图像分割（二）
文章图片
就是所谓的mean shift向量，是一个方向向量，对应的就是我们的梯度方向。
对于某一点mean shift 图像分割（二）
文章图片
往梯度方向移动到mean shift 图像分割（二）
文章图片
，则新坐标：
mean shift 图像分割（二）
文章图片

物理意义：很直观，以mean shift 图像分割（二）
文章图片
为权值计算重心。
当mean shift 图像分割（二）
文章图片
时，我们就到达了模点，由于mean shift 图像分割（二）
文章图片
，所以只能是mean shift 图像分割（二）
文章图片
。不过想要一步登天，很难，除非你出生很好，就落在模点，大多数数据点，还是得老老实实，一步一个脚印爬上去。还是设mean shift 图像分割（二）
文章图片
爬过的脚印依次mean shift 图像分割（二）
文章图片
，mean shift 图像分割（二）
文章图片
，则脚印公式：
mean shift 图像分割（二）
文章图片

3.3.3 自适应步长
mean shift 图像分割（二）
文章图片

可以看出步长mean shift 图像分割（二）
文章图片
与mean shift 图像分割（二）
文章图片
成反比，还是以Normal Kernel为例，越靠近模点，步长越小，反之越大。
原文证明了，只要mean shift 图像分割（二）
文章图片
是凸函数，mean shift 图像分割（二）
文章图片
单调递减（mean shift 图像分割（二）
文章图片
可以不是哦），那么就能保证它总能收敛到模点，并且mean shift 图像分割（二）
文章图片
是单调递增的（我没看……）。只要步履不停，我们总会遇见，多么美好的世界啊，求遇见。
3.3 图像分割领域的具体化
本质上，mean shift解决任何问题，都是转化成密度估计问题。但具体问题还得具体分析。对于图像它有两种信息，坐标和颜色，前者为spatial 空间mean shift 图像分割（二）
文章图片
后者为range空间，对于单通道图片即灰度值，对于彩色图片即mean shift 图像分割（二）
文章图片
或者效果更好的mean shift 图像分割（二）
文章图片
等。二者是截然不同的属性，决定了不能等同视之。因此，我们使用多元核密度估计（multivariate kernel）。设spatial有2维，range空间，设为mean shift 图像分割（二）
文章图片
维。
一元核：
mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片

即mean shift 图像分割（二）
文章图片

图像分割中使用的多元核：
mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片
mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片

滤波的结果
物理意义：mean shift 图像分割（二）
文章图片
分别为坐标空间核和颜色空间核的带宽（bandwidth）/尺度，我说不清，看结果吧。
3.4回首OpenCV实现
第二步，重心计算公式
mean shift 图像分割（二）
文章图片

我们是对以mean shift 图像分割（二）
文章图片
为中心mean shift 图像分割（二）
文章图片
为边长的区域求重心，其实本应该是：
mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片
用的是Uniform Kernel，也就是说mean shift 图像分割（二）
文章图片
用的是Epanechnikov Kernel
mean shift 图像分割（二）
文章图片

此时，距离筛选是由核函数实现的，因此我们是对图像中所有的数据点mean shift 图像分割（二）
文章图片
计算重心，而不是落在mean shift 图像分割（二）
文章图片
为中心，mean shift 图像分割（二）
文章图片
为边长的区域内的点求重心。
OpenCV的实现中， mean shift 图像分割（二）
文章图片
并不是圆形的，为了循环时程序实现的方便，就用方形近似，但mean shift 图像分割（二）
文章图片
是严格的球体。
不过方形的也可以写成核函数形式：
mean shift 图像分割（二）
文章图片

mean shift 图像分割（二）
文章图片

此外，Normal Kernel 的平滑效果固然好，但是计算量大，所以主要还是用Uniform Kernel。原文说大部分场合，Uniform Kernel和Normal Kernel就能取得很好的效果。
4延伸
不写了，已经写得太多了……这次就只挖个坑，日后再跳
Camshift
能够自动调整窗口的大小，能适应目标尺度变化的情况，比如人脸跟踪时，人与摄像头的距离动态变化的情况。
带宽选择
图像分割的带宽一般是自己调整看效果，最优带宽也能也求出来？不过，我倒想看看自适应带宽。最优带宽值看原文吧。
Mode prune
mean shift 图像分割（二）
文章图片

对于鞍点等会产生一些虚假的模点，如上图，红色线上的点可能就跑到鞍点去了，去除办法：将模点的坐标稍作移动，再从移动后的位置继续爬，如果还能爬到原来模点的位置，那就保留，否则踢掉。恩，是你的跑不了，不是你的撒手就跑。
与双边滤波的关联
可以看做死板的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
【mean shift 图像分割（二）】 mean shift 图像分割（二）
文章图片

    推荐阅读


    上一篇：Computer|sobel算子

    下一篇：Qunee|Qunee for HTML5 V1.8新版本发布