图像分割（Image Segmentation）的主要目的也就是将图像（image）分割成若干个特定的、具有独特性质的区域（region），然后从中提取出感兴趣的目标（object）。而图像区域之间的边界定义是图像分割算法的关键，论文给出了一种在图表示（graph-based）下图像区域之间边界的定义的判断标准（predicate），其分割算法就是利用这个判断标准（predicate）使用贪心选择（greedy decision）来产生分割（segmentation）。该算法在时间效率上，基本上与图像（Image）的图（Graph）表示的边（edge）数量成线性关系，而图像的图表示的边与像素点成正比，也就说图像分割的时间效率与图像的像素点个数成线性关系。这个算法有一个非常重要的特性，它能保持低变化（low-variability）区域（region）的细节，同时能够忽略高变化（high-variability）区域（region）的细节。
图的基本概念
1、图
由顶点集V（vertices）和边集E（edges）组成，表示为G=(V, E)，顶点v∈V，在论文即为单个的像素点，连接一对顶点的边(vi, vj)具有权重w(vi, vj)。
2、树
3、最小生成树（minimum spanning tree）
特殊的树，给定需要连接的顶点，选择边权之和最小的树。
论文中，初始化时每一个像素点都是一个顶点，然后逐渐合并得到一个区域，确切地说是连接这个区域中的像素点的一个MST。如下图，棕色圆圈为顶点，线段为边，合并棕色顶点所生成的MST，对应的就是一个分割区域。分割后的结果其实就是森林。
相似性
既然是聚类算法，那应该依据何种规则判定何时该合二为一，何时该继续划清界限呢？对于孤立的两个像素点，所不同的是灰度值，自然就用灰度的距离来衡量两点的相似性，本文中是使用RGB的距离，即
当然也可以用perceptually uniform的Luv或者Lab色彩空间，对于灰度图像就只能使用亮度值了，此外，还可以先使用纹理特征滤波，再计算距离，比如先做Census Transform再计算Hamming distance距离。
阈值
上面提到应该用亮度值之差来衡量两个像素点之间的差异性。对于两个区域（子图）或者一个区域和一个像素点的相似性，最简单的方法即只考虑连接二者的边的不相似度。如下图，已经形成了棕色和绿色两个区域，现在通过紫色边来判断这两个区域是否合并。那么我们就可以设定一个阈值，当两个像素之间的差异（即不相似度）小于该值时，合二为一。迭代合并，最终就会合并成一个个区域，效果类似于区域生长：星星之火，可以燎原。
举例说明：
对于上右图，显然应该聚成上左图所示的3类：高频区h,斜坡区s,平坦区p。
如果我们设置一个全局阈值，那么如果h区要合并成一块的话，那么该阈值要选很大，但是那样就会把p和s区域也包含进来，分割结果太粗。如果以p为参考，那么阈值应该选特别小的值，那样的话p区是会合并成一块，但是h区就会合并成特别特别多的小块，如同一面支离破碎的镜子，分割结果太细。显然，全局阈值并不合适，那么自然就得用自适应阈值。对于p区该阈值要特别小，s区稍大，h区巨大。先来两个定义，原文依据这两个附加信息来得到自适应阈值。
可以近似理解为一个区域内部最大的亮度差异值，定义是MST中不相似度最大的一条边。俩个区域的类间差异Diff(C1, C2)：
即连接两个区域所有边中，不相似度最小的边的不相似度，也就是两个区域最相似的地方的不相似度。直观的判断，两个区域应当合并，当：
算法
计算每一个像素点与其8邻域或4邻域的不相似度。
如上图，实线为只计算4领域，加上虚线就是计算8邻域，由于是无向图，按照从左到右，从上到下的顺序计算的话，只需要计算右图中灰色的线即可。
2、将边按照不相似度non-decreasing排列（从小到大）排序得到e1, e2, ..., en。
3、选择ei
4、对当前选择的边ej（vi和vj不属于一个区域）进行合并判断。设其所连接的顶点为(vi, vj)，
if 不相似度小于二者内部不相似度：
5、更新阈值以及类标号
else：
6、如果i < n，则按照排好的顺序，选择下一条边转到Step 4，否则结束。
结果
网友评论