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

Efficient graph-based image segmentation
2.相关工作
G=(V,E)，每个节点对应图像中一个像素点，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。因此我们的阈值函数为

这里的|C|是C的大小，K是某个特定常量参数。对于小的区域我们需要明显的边界。实际上k设置为一系列值.
说明：
当二者都是孤立的像素值时，，所有像素都是"零容忍"只有像素值完全一样才能合并，自然会导致过分割。所以刚开始的时候，应该给每个像素点设定一个可以容忍的范围，当生长到一定程度时，就应该去掉该初始容忍值的作用。原文条件如下

增加项:

其中为区域所包含的像素点的个数，如此，随着区域逐渐扩大，这一项的作用就越来越小，最后几乎可以忽略不计。那么就是一个可以控制所形成的的区域的大小，如果，那么，几乎每个像素都成为了一个独立的区域，如果，显然整张图片都会聚成一块。所以，越大，分割后的图片也就越大

4算法和它的特性
定义1 分得太细。
定义2 分得太粗

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

0. 首先将边E按照权重大小由小到大排列为；
1. 开始一个分割，每一个顶点是它自己的区域；
2. 重复步骤3，q=1,....,m
3. 按照如下方法，通过构建：按顺序，和表示第q次相连的两个顶点，比如，。如果和在的不相交的两个区域中，并且是较小的相对于这些区域的内在差异性，那么合并这两个区域除非什么也不做。包含成为的一部分，让包含成为一部分（let Ci q−1 be the component of Sq−1 containing vi and Cj q−1 the component containing vj）。如果，将和合并到中成为。否则=
4. 返回

算法分析：具有全局特性，既不会分得太细也不会分得太粗。该算法是贪心决策

引理1 上述算法中的步骤3，如果和没有合并，那么和中至少有一个最后会在分类的区域中。证明见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）可在线性时间内完成。

http://dongxicheng.org/structure/union-find-set/

说明：并查集+排序+路径压缩

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

说明：计数排序（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个像素的图像，我们对一个边连接着的两个像素，使用基于绝对强度不同边权重函数：
求权重

这里I(pi)是像素pi的强度值。
在计算边的权重前，一般，我们使用高斯滤波器对图像进行平滑。高斯滤波器的。
对于彩色图像，我们运行程序3次，每次分别在红、绿、蓝这三个颜色通道，然后组合这三组。
算法有一个运行参数，用来计算阈值函数的的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. ）。我们的算法会处理这些变量。第二幅图显示了分割效果，每个区域随机分配一种颜色。
最大的6个区域是通过下面的算法得到的：
栅栏后面的三块草坪区域，草坪斜坡，面包车，公路。左下角缺失的公路部分是一个可见的直观区域（a spot due to an imaging artifact）。注意到面包车也不是统一的颜色，因为镜面反射，但是由于有足够的漫反射，它们被当做内部变量，并且合并为一个单一的区域。

图3是两个棒球选手，在之前的例子中，草地部分是可观的变量。统一制服的棒球选手也有很多变量，由于衣服的褶皱。算法找到了6个区域墙、大都会队徽、大草坪（包括球员身下的一部分墙体）、每个球员的衣服、第二个球员身下的一小块草坪。大草坪包括了小部分墙体是因为在这个部分相对高的变量，并且在墙体和草地边缘有长而缓慢的变化。

6.最近邻图割的结果
对图像进行分割的常用方法是基于每个像素映射到特征空间的一个点，然后对相似点进行聚类【3,4,9】。这部分我们将用第4部分描述的基于图割的算法来考察来找到相似点的类。这里，图上的每个顶点会有一个对应的特征点，连接特征点vi个vj的边(vi,vj)在特征空间是邻近的而不是图像中的相邻像素点。我们将每个点与特定数目的最邻近点相连，或者在特定的区域d内将所有点相连
权重由特征空间对应点的距离决定，实验显示，我们映射每个点到特征空间中的点(x,y,r,g,b),我们用点与点之间的欧几里得距离作为边的权值。
类内差，Int(C)，需要指定一个最小半径将C中在特征空间中的所有特征点联系在一起。通过一个半径为r的球将每一个特征点进行替换。从最小生成树的定义可以看出，当且仅当时，这些球体将会连接形成一个单一的空间。不同的区域，，has a simple underlying intuition .它指定一个最小的半径连接C1和C2间最少一对点。我们的分割技术很大程度上是[4]，
不是构造一个所有点都是与另一个点相邻的完全图，我们要找到每个点都有最小的固定数量的邻近点。那么有n个像素点的图将会有n个边。我们使用ANN近似最邻近算法[1]来查找每个点的最近邻点。给出一个5维的有成百上千个点。作为实例，我们对每个像素使用10个最近邻点来生成图的边。
对于先前方法的一个关键不同点是，图像网格用来定义图，特征空间中的最近邻点获得更多空间非局部特性。在图割中，图中所有的邻域点都是相邻的。这里，点在图像中的位置可以使很远的，但依然会有大量的最邻近点（如果颜色高度相似并且影响图像像素的是不相似颜色）。比如，这将导致区域分割图像不相连，在网格图中将不会发生。
图6显示了一个从[12]和[18]的合成图及其分割效果图。这里k=150,并且没有进行平滑()。

说明：前文是只用了空间位置来构件图的连接关系，缺点是明显的，空间不相邻，色彩完全一样也白搭，于是中间稍微有断开都会分成多个部分。于是另一种更为平等的策略是二者一块考虑，先映射到特征空间，再构建图。此时有连接关系的就不一定是4/8邻域了，由于有对边，因此如果考虑所有边的连接关系的话，太恐怖了！原文是对每个像素点找10个欧氏距离最近的点即10最近邻，构建图，当然，另外一种方法不是固定邻居数目，而是限定距离范围。

那么类内距离的解释就和直观了，类内最短的距离，那么会以这条边为半径，在特征空间构成一个超球体，不过会和别人有相交。
同样还是两个类之间的最短距离。
找10-NN，原文采用近似算法ANN 《Approximate nearest neighbor searching》来找10近邻。剩下的和上面一样，但是有一点我没明白，就是的更新，比如上图，肯定是用绿色这条线更新，那么的意义就不再是包含集合所有点的最短半径了，求解？

总结
Do-efficient graph-based image segmentation.docx
（1） 贪心决策-greedy decision
（2） 全局特性
（3） 分割得当-不会太粗太细，阈值函数
（4） 最小生成树-MST