图像分割—基于图的图像分割（Graph-Based Image Segmentation）
图像分割—基于图的图像分割（Graph-Based Image Segmentation）
Reference:
Efficient Graph-Based Image Segmentation,IJCV 2004,MIT Code
最后一个暑假了，不打算开疆辟土了，战略中心转移到品味经典，计划把图像分割和目标追踪的经典算法都看一看，再记些笔记。
Graph-Based Segmentation 是经典的图像分割算法，作者Felzenszwalb也是提出DPM算法的大牛。该算法是基于图的贪心聚类算法，实现简单，速度比较快，精度也还行。不过，目前直接用它做分割的应该比较少，毕竟是99年的跨世纪元老，但是很多算法用它作垫脚石，比如Object Propose的开山之作《Segmentation as Selective Search for Object Recognition》就用它来产生过分割（oversegmentation）。还有的语义分割(senmatic segmentation )算法用它来产生超像素（superpixels）具体忘记了……
图的基本概念
因为该算法是将照片用加权图抽象化表示，所以补充图的一些基本概念。
图是由顶点集（vertices）和边集
（edges）组成，表示为
，顶点
，在本文中即为单个的像素点，连接一对顶点的边
具有权重
，本文中的意义为顶点之间的不相似度，所用的是无向图。
树：特殊的图，图中任意两个顶点，都有路径相连接，但是没有回路。如上图中加粗的边所连接而成的图。如果看成一团乱连的珠子，只保留树中的珠子和连线，那么随便选个珠子，都能把这棵树中所有的珠子都提起来。如果，i和h这条边也保留下来，那么顶点h,i,c,f,g就构成了一个回路。
最小生成树（MST, minimum spanning tree）：特殊的树，给定需要连接的顶点，选择边权之和最小的树。上图即是一棵MST
本文中，初始化时每一个像素点都是一个顶点，然后逐渐合并得到一个区域，确切地说是连接这个区域中的像素点的一个MST。如图，棕色圆圈为顶点，线段为边，合并棕色顶点所生成的MST，对应的就是一个分割区域。分割后的结果其实就是森林。
相似性
既然是聚类算法，那应该依据何种规则判定何时该合二为一，何时该继续划清界限呢？
对于孤立的两个像素点，所不同的是颜色，自然就用颜色的距离来衡量两点的相似性，本文中是使用RGB的距离，即
当然也可以用perceptually uniform的Luv或者Lab色彩空间，对于灰度图像就只能使用亮度值了，此外，还可以先使用纹理特征滤波，再计算距离，比如，先做Census Transform再计算Hamming distance距离。
全局阈值à自适应阈值
上面提到应该用亮度值之差来衡量两个像素点之间的差异性。对于两个区域（子图）或者一个区域和一个像素点的相似性，最简单的方法即只考虑连接二者的边的不相似度。
如图，已经形成了棕色和绿色两个区域，现在通过紫色边来判断这两个区域是否合并。那么我们就可以设定一个阈值，当两个像素之间的差异（即不相似度）小于该值时，合二为一。迭代合并，最终就会合并成一个个区域，效果类似于区域生长：星星之火，可以燎原。
显然，上面这张图应该聚成右图所思的3类，高频区h,斜坡区s,平坦区p。如果我们设置一个全局阈值，那么如果h区要合并成一块的话，那么该阈值要选很大，但是那样就会把p和s区域也包含进来，分割结果太粗。如果以p为参考，那么阈值应该选特别小的值，那样的话，p区是会合并成一块，但是，h区就会合并成特别特别多的小块，如同一面支离破碎的镜子，分割结果太细。
显然，全局阈值并不合适，那么自然就得用自适应阈值。对于p区该阈值要特别小，s区稍大，h区巨大。
对于两个区域（原文中叫Component,实质上是一个MST,单独的一个像素点也可以看成一个区域）,本文使用了非常直观，但抗干扰性并不强的方法。先来两个定义，原文依据这两个附加信息来得到自适应阈值。
一个区域的类内差异：
可以近似理解为一个区域内部最大的亮度差异值，定义是MST中不相似度最大的一条边。
两个区域的类间差异：
即连接两个区域所有边中，不相似度最小的边的不相似度，也就是两个区域最相似的地方的不相似度。
那么直观的判断是否合并的标准：
等价条件
解释： ，
分别是区域
和
所能忍受的最大差异，当二者都能忍受当前差异
时，你情我愿，一拍即合，只要有一方不愿意，就不能强求。
特殊情况，当二者都是孤立的像素值时，，所有像素都是"零容忍"只有像素值完全一样才能合并，自然会导致过分割。所以刚开始的时候，应该给每个像素点设定一个可以容忍的范围，当生长到一定程度时，就应该去掉该初始容忍值的作用。原文条件如下
增加项
:
其中为区域
所包含的像素点的个数，如此，随着区域逐渐扩大，这一项的作用就越来越小，最后几乎可以忽略不计。那么
就是一个可以控制所形成的的区域的大小，如果，
那么，几乎每个像素都成为了一个独立的区域，如果
，显然整张图片都会聚成一块。所以，
越大，分割后的图片也就越大。
当然，可以采用中位数来应对超调，不过这就变成了一个NP难问题，证明见原文
形状相似
前面提到的用颜色信息来聚类，修改相似性衡量标准，可以聚类成我们想要的特定形状。比如我们希望得到很多长条形的区域，那么可以用聚类后的所形成的区域的面积/周长 + 亮度值的差 衡量两个子图或者两个像素之间的相似度。因为长条形的面积/周长会比较小。
算法步骤
Step 1: 计算每一个像素点与其8邻域或4邻域的不相似度。
如左边所示，实线为只计算4领域，加上虚线就是计算8邻域，由于是无向图，按照从左到右，从上到下的顺序计算的话，只需要计算右图中灰色的线即可。
Step 2: 将边按照不相似度non-decreasing排列（从小到大）排序得到。
Step 3: 选择
Step 4: 对当前选择的边进行合并判断。设其所连接的顶点为
。如果满足合并条件：
（1）不属于同一个区域
；
（2）不相似度不大于二者内部的不相似度。则执行Step 5。否则执行Step
6
Step 5: 更新阈值以及类标号。
更新类标号：将的类标号统一为
的标号。
更新该类的不相似度阈值为：。
注意：由于不相似度小的边先合并，所以，即为当前合并后的区域的最大的边，即
。
Step 6: 如果，则按照排好的顺序，选择下一条边转到Step
4，否则结束。
结果
Segmentation parameters: sigma = 0.5, k= 500, min = 50.
Sigma：先对原图像进行高斯滤波去噪，sigma即为高斯核的
k: 控制合并后的区域的大小，见前文