基于图的快速图像分割算法.pdfVIP

-

Efficientgraph-basedimagesegmentation

2.相关工作

G=(V,E)，每个节点viV对应图像中一个像素点，E是连接相邻节点的边，每

个边有对应有一个权重，这个权重与像素点的特性相关。

最后，我们将提出一类基于图的查找最小割的分割方法。这个最小割准则是最

小化那些被分开像素之间的相似度。【18】原文中叫ponent,实质上是一个MST,

单独的一个像素点也可以看成一个区域。

预备知识：

图是由顶点集〔vertices〕和边集〔edges〕组成，表示为，顶

点，在本文中即为单个的像素点，连接一对顶点的边具有权重，

本文中的意义为顶点之间的不相似度，所用的是无向图。

树：特殊的图，图中任意两个顶点，都有路径相连接，但是没有回路。如上

图中加粗的边所连接而成的图。如果看成一团乱连的珠子，只保存树中的珠子和

连线，则随便选个珠子，都能把这棵树中所有的珠子都提起来。如果，i和h这

条边也保存下来，则h,I,c,f,g就构成了一个回路。

最小生成树〔MST,minimumspanningtree〕：特殊的树，给定需要连接的

顶点，选择边权之和最小的树。上图即是一棵MST。

本文中，初始化时每一个像素点都是一个顶点，然后逐渐合并得到一个区域，

确切地说是连接这个区域中的像素点的一个MST。如图，棕色圆圈为顶点，线段

为边，合并棕色顶点所生成的MST，对应的就是一个分割区域。分割后的结果其

实就是森林。

边的权值：

对于孤立的两个像素点，所不同的是颜色，自然就用颜色的距离来衡量两点

的相似性，本文中是使用RGB的距离，即

3图割

3.1我们定义D，衡量分割区域之间是否有明显边界。D是通过测量沿着两个

区域边界元素的不相似度比照测量两个区域部各自部元素之间不相似度。

我们用C表示一个局部的在差异，是该区域最小生成树上的最大权值。

我们定义两个区域间的不同是两个区域连接边的最小权值，

如果C1，C2之间不想连，则Dif(C1,C2)=无穷大，

使用下面的阈值函数来控制两个区域之间的差异性必须大于最小在差异，我

们定义如下函数：

其中MInt是：

阈值函数控制着两个区域之间的差异性必须大于他们在差异性，以便它们

之间有明显的边界〔D为true〕。对于小的区域，Int(C)是对局部数据的特性的

一个好的估计。在一些极端情况下，如果|C|=1，Int(C)=0。因此我们的阈值函

.z

-

数为

这里的|C|是C的大小，K是*个特定常量参数。对于小的区域我们需要明显

的边界。实际上k设置为一系列值.

说明：

当二者都是孤立的像素值时，，所有像素都是零容忍只有像素值

完全一样才能合并，自然会导致过分割。所以刚开场的时候，应该给每个像素点

设定一个可以容忍的围，当生长到一定程度时，就应该去掉该初始容忍值的作用。

原文条件如下

增加项:

其中为区域所包含的像素点的个数，如此，随着区域逐渐扩大，这一项的作

用就越来越小，最后几乎可以忽略不计。则就是一个可以控制所形成的的区域

的大小，如果，则，几乎每个像素都成为了一个独立的区域，如果，

显然整图片都会聚成一块。所以，越大，分割后的图片也就越大

4算法和它的特性

定义1分得太细。

定义2分得太粗

特性1

相近的算法【6】

算法1分割算法

输入：图G(V,E)，有n个顶点和M条边。

输出：对V的分割为S(C,,C)

1