Efficient graph-based image segmentation 2.相关工作 G=(V,E)，每个节点V

iv对应图像中一个像素点，E是连接相邻节点的边，每

个边有对应有一个权重，这个权重与像素点的特性相关。 最后，我们将提出一类基于图的查找最小割的分割方法。这个最小割准则是最小化那些被分开像素之间的相似度。【18】原文中叫Component,实质上是一个MST,单独的一个像素点也可以看成一个区域。

预备知识： 图是由顶点集（vertices）和边集（edges）组成，表示为，顶点，在本文中即为单个的像素点，连接一对顶点的边具有权重，本文中的意义为顶点之间的不相似度，所用的是无向图。

树：特殊的图，图中任意两个顶点，都有路径相连接，但是没有回路。如上图中加粗的边所连接而成的图。如果看成一团乱连的珠子，只保留树中的珠子和连线，那么随便选个珠子，都能把这棵树中所有的珠子都提起来。如果，i和h这条边也保留下来，那么h,I,c,f,g就构成了一个回路。 最小生成树（MST, minimum spanning tree）：特殊的树，给定需要连接的顶点，选择边权之和最小的树。上图即是一棵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。因此我们的阈值函数为 ||/)(CkC 这里的|C|是C的大小，K是某个特定常量参数。对于小的区域我们需要明显的边界。实际上k设置为一系列值. 说明： 当二者都是孤立的像素值时，，所有像素都是"零容忍"只有像素值完全一样才能合并，自然会导致过分割。所以刚开始的时候，应该给每个像素点设定一个可以容忍的围，当生长到一定程度时，就应该去掉该初始容忍值的作用。原文条件如下

增加项: ||/)(CkC 其中为区域所包含的像素点的个数，如此，随着区域逐渐扩大，这一项的作用就越来越小，最后几乎可以忽略不计。那么就是一个可以控制所形成的的区域的大小，如果，那么，几乎每个像素都成为了一个独立的区域，如果，显然整图片都会聚成一块。所以，越大，分割后的图片也就越大 4算法和它的特性 定义1 分得太细。 定义2 分得太粗

特性1 相近的算法【6】 算法1 分割算法 输入：图 ),(EVG，有n个顶点和M条边。 输出：对V的分割为 ),......,(

1rCCS

0. 首先将边E按照权重大小由小到大排列为)...,(

,1moo；

1. 开始一个分割0S，每一个顶点iv是它自己的区域；

2. 重复步骤3，q=1,....,m 3. 按照如下方法，通过1-qS构建qS：按顺序，iv和jv表示第q次相连的两个顶

点，比如，),(oqjivv。如果iv和jv在1-qS的不相交的两个区域中，并且)(wqo是

较小的相对于这些区域的在差异性，那么合并这两个区域除非什么也不做。1q

iC

包含iv成为1-qS的一部分，让1qjC包含jv成为一部分（let Ci q−1 be the

component of Sq−1 containing vi and Cj q−1 the component containing vj）。如果),()(1111iqjqiqqjqCCMIntowandCC，将1qiC和1qjC合并到1-qS中

成为qS。否则qS=1-qS

4. 返回 mSS 算法分析：具有全局特性，既不会分得太细也不会分得太粗。该算法是贪心决策 引理1 上述算法中的步骤3，如果iv和jv没有合并，那么1qiC和1qjC中至少有

一个最后会在分类的区域中。证明见paper

4.1 实施问题和运行时间 实施主要是包括并查集结合排序和路径压缩（a disjoint-set forest with union by rank and path compression），参考《算法导论》（Introduction to Algorithms. The MIT Press（麻省理工）, McGraw-Hill Book Company, 1990.）。运行时间分为两个部分：1.按照从小到大给权值排序。整数权重使用计数排序（counting sort）可在线性时间完成。

blog.csdn.net/dm_vincent/article/details/7655764 .cnblogs./TonyNeal/p/bingchaji.html dongxicheng.org/structure/union-find-set/ .mamicode./info-detail-610308.html 说明：并查集+排序+路径压缩 动态联通性 假设我们输入了一组整数对，即上图中的(4, 3) (3, 8)等等，每对整数代表这两个points/sites是连通的。那么随着数据的不断输入，整个图的连通性也会发生变化，从上图中可以很清晰的发现这一点。同时，对于已经处于连通状态的points/sites，直接忽略，比如上图中的(8, 9)。 在对问题进行建模的时候，我们应该尽量想清楚需要解决的问题是什么。因为模型中选择的数据结构和算法显然会根据问题的不同而不同，就动态连通性这个场景而言，我们需要解决的问题可能是： 给出两个节点，判断它们是否连通，如果连通，不需要给出具体的路径 给出两个节点，判断它们是否连通，如果连通，需要给出具体的路径 建模思路： 最简单而直观的假设是，对于连通的所有节点，我们可以认为它们属于一个组，因此不连通的节点必然就属于不同的组。随着Pair的输入，我们需要首先判断输入的两个节点是否连通。如何判断呢？按照上面的假设，我们可以通过判断它们属于的组，然后看看这两个组是否相同，如果相同，那么这两个节点连通，反之不连通。为简单起见，我们将所有的节点以整数表示，即对N个节点使用0到N-1的整数表示。而在处理输入的Pair之前，每个节点必然都是孤立的，即他们分属于不同的组，可以使用数组来表示这一层关系，数组的index是节点的整数表示，而相应的值就是该节点的组号了。

puffsun.iteye./blog/1294547 说明：计数排序（counting sort） 计数排序假设n个输入元素中的每一个都是介于0-k的整数，此处k为某个整数。计数排序顾名思义离不开计数，我们要计的是输入元素中相同元素出现的次数。对每一个输入元素x，确定小于x的元素的个数，那样排序之后，x在最终输出数组中的位置就可以确定了。例如：如果有17个元素小于x，则x就位于第18个输出的位置上。当然有几个元素相同时，这个方法就略微改进一下，因为不能将它们放在同一个位置上。

为了检查两个顶点是否属于同一个区域，我们对每个顶点使用set-find，为了合并两个区域，我们使用set-union。因此每条边最多有3个disjoint-set操作。如果我们知道每个区域的大小和Int。那么MInt可以在特定时间计算出来。在一个区域的MST中，最大权值的边引起合并。 5.网格图结果 首先单色（强度）图像的情况。彩色图是三个单独的单目图。对于n个像素的图像，我们对一个边连接着的两个像素，使用基于绝对强度不同边权重函数： 求权重 |)()(|)),((wjijipIpIvv 这里I(pi)是像素pi的强度值。 在计算边的权重前，一般，我们使用高斯滤波器对图像进行平滑。高斯滤波器的8.0。 对于彩色图像，我们运行程序3次，每次分别在红、绿、蓝这三个颜色通道，然后组合这三组。 算法有一个运行参数，用来计算阈值函数的||/)(CkC的k，这里的k是一个观察值。全文用两个k，主要是根据图象分辨率和分割的粗细程度来确定。比如，一个128*128的COIL数据库的图像我们使用k=50,320*240或者更大的图像，比如街道场景和棒球选手，k=300 图2是一个街道上的场景，注意到有一个可观变量从草坪到栅栏（Note that there is considerable variation in the grassy slope leading up to the fence. ）。我们的算法会处理这些变量。第二幅图显示了分割效果，每个区域随机分配一种颜色。