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 shitf的故事说来挺励的，早在1975年就诞生了，接着就是漫长的黑暗岁月，黑暗到几乎淡出了人们的视野，不过，命运总是善良的，95年又重新焕发生机，各种应用喷薄而出，包括目标跟踪，边缘检测，非极大值抑制等。这次就只介绍在图像分割中的应用吧，其它的我也没看。Mean shitf过程也充满正能量，描绘的是如何通过自己的努力，一步一步爬上顶峰的故事。
1 总体思想
图 1 特征空间映射：RGB图片 -> L-u特征空间
首先meanshift是一种特征空间分析方法，要利用此方法来解决特定问题，需要将该问题映射到特征空间。对于图像分割，我们可以映射到颜色特征空间，比如将RGB图片，映射到Luv特征空间，图1是L-u二维可视化的效果。
图像分割就是求每一个像素点的类标号。类标号取决于它在特征空间所属的cluster。对于每一个cluster，首先得有个类中心，它深深地吸引着一些点，就形成了一个类，即类中心对类中的点构成一个basin of attraction ，好比咱们的太阳系。如此，图像分割问题，就可以看成对每个像素点，找它的类中心问题，因为找到类中心就知道它是属于那一类啦，即类中心一样的点就是一类。
图2标准化后的概率密度可视化效果 -> 聚类分割结果
密度估计的思路需要解决两个问题，what:中心是什么？how：怎么找？mean shift认为中心是概率密度（probalility density function ）的极大值点，如图2中的红色点，原文称之为mode，我这暂且用模点吧（某篇论文是如此称呼）。对于每个点怎样找到它的类中心呢？只要沿着梯度方向一步一步慢慢爬，就总能爬到极值点，图2中黑色的线，就是爬坡的轨迹。这种迭代搜索的策略在最优化中称之为 multiple restart gradient descent。不过，一般的gradient descent并不能保证收敛到局部极值，但mean shift 可以做到，因为它的步长是自适应调整的，越靠近极值点步长越小。
也就是说meanshift的核心就两点，密度估计(Density Estimation) 和mode 搜索。对于图像数据，其分布无固定模式可循，所以密度估计必须用非参数估计，选用的是具有平滑效果的核密度估计（Kernel density estimation，KDE）。
2 算法步骤
截取这一块可视化
（a）灰度图可视化à（b）mean shift模点路径à（c）滤波后效果à（d）分割结果
分三步走：模点搜索/图像平滑、模点聚类/合并相似区域、兼并小区域（可选）。模点搜索是为了找到每个数据点的到类中心，以中心的颜色代替自己的颜色，从而平滑图像。但模点搜索得到的模点太多，并且很多模点挨得很近，若果将每个模点都作为一类的话，类别太多，容易产生过分割，即分割太细，所以要合并掉一些模点，也就是合并相似区域。模点聚类后所得到的分割区域中，有些区域所包含的像素点太少，这些小区域也不是我们想要的，需要再次合并。
2.1 模点搜索/图像平滑
建议先看[2]中的演示（P4-12）
图像中的点包括两类信息：坐标空间（spatial，
，
），颜色空间（range ，
，
）。这些就构成了特征空间。
模点搜索（OpenCV）：某一个点，它在联合特征空间
中迭代搜索它的mode/模点
；
图像平滑: 将模点的颜色值赋给它自己，即.对应原文中的图像平滑，实质上是通过模点搜索，达到图像平滑的效果, 所以我合并为以一步。
设点依次爬过的脚印为：
出发时，它所收敛到的模点为
，c代表convergence。
第一步：如果迭代次数超过最大值（默认最多爬5次），结束搜索跳到第四步，否则，在坐标空间，筛选靠近的数据点进入下一步计算。
OpenCV是以的坐标
为中心，边长为
的方形区域
内的数据点。
其实，本应用为中心，
为半径的圆形区域，那样效果更好，但是循环计算时并不方便，所以用方形区域近似。
第二步：使用第一步幸存下来的点计算重心，并向重心移动。
写得有点复杂了，下面解释下。是某种核函数，比如高斯分布，
是颜色空间的核平滑尺度。OpenCV使用的是最简单的均匀分布：
二维可视化效果
是一个以
（第
步位置的颜色值）为球心，半径为
的球体，球体内部值为1，球体外部值为0。对于经过上一步筛选后幸存的数据点
，如果其颜色值
满足
，也就是颜色值落也在球内，那么求重心
时，就要算上
，否则落在球外，算重心时，就不带上它。实际上，上一步是依据坐标空间距离筛选数据点，
是依据颜色距离进一步筛选数据点，上一步的筛子是矩形，这一步是球体。
简而言之，设满足的点依次为
，那么重心计算公式可以进一步化简为：
是不是很简单呢，初中知识吧。
注意：上文中的两个参数，是Mean shift最核心的两个参数（还有一个可选的M），具有直观的意义，分别代表坐标空间和颜色空间的核函数带宽。
第三步：判断是否到模点了，到了就停止。
如果，移动后颜色或者位置变化很小，则结束搜索，跳到第四步，否则重返第一步，从继续爬。
OpenCV停止搜索的条件：
（1）坐标距离不变
（2）颜色变化值很小。
满足一条就可以功成身退，否则继续努力。
第四步：将模点的颜色
赋给出发点
/
，即
。
注意：原文这一步，不仅将模点的颜色值赋给，顺带把坐标值也赋给了
，也就是说
。
2.2 合并相似区域/模点聚类
合并上一步平滑后的图像。OpenCV采用flood fill函数实现，原理很简单，看下wiki的动画就知道了，模拟洪水浸满峡谷的效果。基本上就是区域生长，从某一点出发，如果和它附近的点（4/8邻域）的颜色值相似就合并，同时再从新合并的点出发继续合并下去，直到碰到不相似的点或者该点已经属于另一类了，此时，就退回来，直到退无可退（所有的4/8邻域搜索空间都已经搜索完毕）。
虽然很简单，但是不同的方法还是有很多需要注意的细节问题。这里假设滤波后的图像用表示。
滤波后的两个像素点和
，是否合并，可以使用颜色相似度和空间位置相似性判定。
OpenCV只考虑颜色相似性，而忽略模点的坐标是否相似。而原算法综合了二者的信息。如果像素点，满足
或者
, 则这两个像素点就合并。不过OpenCV也是有考虑坐标位置的，它是只考虑原空间的4/8邻域，而原文是考虑特征空间模点的
，相当于说OpenCV的
（原空间）。
此外，floodfill有一个特点，它不能越过已经被分类的区域，再加上没有第三步，使得OpenCV的结果，真的是惨不忍睹。原文的合并算法，具体怎么合并的还得看源代码。不过，应该不是用flood fill。
《Computer Vision A Modern Approach》中是使用类平均距离判定是否合并。比如，，
能否合并成
，取决于类平均距离：
这样做我觉得效果会更好，因为它不是单独依据边界上的两个点来判定是否合并，它是依据两个区域内部所有的点的信息综合判断。所以，它能合并两个区域，而原算法和OpenCV只能是两个点合并成一个区域，该区域又不断地合并点，一旦一个区域已经完成生长，那么它就不会和别的区域合并了。可以反证。假设先形成,区域
生长的时候把
给合并了，那么必定有两个点满足相似关系，连接了二者，假设这两个点为
，
相似，那么
生长的时候就肯定已经把
点合并进来了，接着把
所拥有的区域全盘接收，根本不会让
区域自成一类。
当然考虑Outlier，使用中值更好。
假设合并之后得到m类。对于原文的算法，每个像素点
的标号
就是其模点
所属的模点集合的类标号，比如
。不过，OpenCV是
所属集合的类标号。
不过，从原文结果来看，得到的结果并不是类标号，因为类标号一般都是序号，比如1，2，……，然后显示分割结果的时候，就给每一类随机分配一种独有的颜色。但原文的分割结果貌似是这一类的总体颜色值，我猜测原算法可能是用（加权）求平均的方式得到类的颜色值，然后属于这一类的像素点就用这个颜色代替。
注意：这一步实现的是合并相似区域，但本质上还是而是合并模点，或者说模点聚类，因为每个像素点的值，就是它所属模点的颜色值/模点的联合信息
。
2.3 兼并小区域
OpenCV的分割结果
上一步合并了一些模点，但是，对于一些小区域，如果它和周围的颜色差异特别大，那么它们也会自成一类，这些小家伙让需要进一步合并。不过，OpenCV的实现中，并没有包含这一步，所以分割出的结果中包含了太多芝麻大点的区域，本人很不满意，有时间再加进去，还得优化下代码，这个实现实在是太慢了。怎么兼并小的区域呢？原文没说，我也没看他的源代码，我们可以直接将包含像素点少于的区域与它最相似的区域合并，实际中，小区域往往是被大区域兼并了。