基于图的分割 Efficient Graph-Based Image Segmentation 论文详解

输入图片

不同参数下的分割结果

原图片

产生superpixel的方法

1. How to segment an image into regions?    怎样把一张图片分割成不同的区域？

2. How to define a predicate that determines a good segmentation?    如何判定一个好的分割？

3. How to create an efficient algorithm based on the predicate?    怎样根据这个判定创造一个好的算法？

4. How do you address semantic areas with high variability in intensity?怎样处理亮度变化较大的分割区域？

5. How do you capture non-local properties in an image?如何获取图像的非局部特征？

第一个问题:怎样把一张图片分割为不同区域？

一个无向图，由边，节点，权重组成

在这篇论文中，两点之间边的权重指的是两个顶点的不相似性，使用两个顶点RGB之间的平方差来得到。

树：特殊的图，图中任意两个顶点，都有路径相连接，但是没有回路。如上图中加粗的边所连接而成的图。如果，i和h这条边也保留下来，那么h,I,c,f,g就构成了一个回路，就不是树了。

最小生成树（MST,minimum spanning tree）：特殊的树，给定需要连接的顶点，选择边权之和最小的树。上图即是一棵MST。

第一个问题解答：本文中，初始化时每一个像素点都是一个顶点，然后逐渐合并得到一个区域，确切地说是连接这个区域中的像素点的一个MST。如图，棕色圆圈为顶点，线段为边，合并棕色顶点所生成的MST，对应的就是一个分割区域。分割后的结果其实就是一棵一棵的书。

最小生成树示意图

第二个问题：如何判定一个好的分割？

最左边原始图中，左部分是斜坡区，右侧平缓区，嵌在平缓区里的是高频区

一个好的分割就是能够区分好这三种区域的分割。

先看一下，我们原始的分割造成上图中间效果的原因。

如何确定两个区域是否可以合并

判定红色区域和绿色区域是否合并，通过紫色边<不相似性>来判断，设置一个唯一阈值，如果小于这个阈值，就合并。对于高频区，我们可以称为二维码区，想要把这个区域分割成一个区域，这个阈值就得设置成很大的数，那么对于斜坡和平缓区，所有的值都会小于这个阈值，导致，这三个区域并到一起，失去分割效果。相反，如果，我们的阈值设置的很小，就会导致二维码区域保留，一小块一小块的。

造成贴图的中间的那个不正确分割效果图的原因是，我们设置的阈值适中，把二维码图并到了平缓区中。

第三、四个问题：怎样根据这个判定创造一个好的算法？怎样处理亮度变化较大的分割区域？

我们应该对于不同的区域设置不同的阈值。根据这个想法，作者提出了自适应的阈值调整方法。这样，对于高频区，我们的阈值自动变大，平缓区阈值自动小，这样就可以实现上面三个高频，斜坡，平缓区的分割了。

C1和C2表示两颗MST

Mint表示同一颗树下权重最大的边（最不相似的两个点）

Dif 表示链接两个树的最小权重边

如果Dif>=Min（Mint(c1),mint(c2)），两个树之间的距离>min(这两个树中最大的那两个权重边);  表示他们不是同一个类，合到一起。Min（Mint(c1),mint(c2)表示c1和c2能够共同容忍的最大差异。

对于初始点，图片的每一个像素都是一个独立的MST,所以必须是两个像素值完全一样才能满足上面条件，所以我们，要设置一个初始阈值，这个阈值要有一个性质，随着我们树的变大（C变大），这个初始阈值tao(C)逐渐趋向于0,使得我们的自适应阈值起作用。k控制合并后的区域的大小。k=0,表示，所有像素值完全相同才可以合并。k非常大，不同像素值之间可以有差异。

左边是k小，右边k大

初始阈值,c表示树节点的个数

算法步骤：首先，下图中的每一个圆点都是代表一个像素，

1. 我们先对每一个像素计算与他相邻的八个位置的不相似性，也就是他们之间权重。

2.按照从小到大的顺序排列，选出最小的边，把他们合并到一个分割里面

3.此时，就要参照，两颗树如何合并了，如果类间的差异<类内共同容忍的最大差异，那么合并，更新新区域，一直重复这个操作

4.更新该类的不相似度阈值，C变大了。

5.结束条件，找不到一条边能够满足条件，结束。

算法步骤

如何获取图像的非局部特征？

使用了位置，颜色作为每个像素的描述

计算两个pixel的欧式距离，选取10个最近邻，保证时间复杂度。这个是用来解决分割区中间稍微有断开的情况，如果只考虑颜色方面的信息，会导致分割区域被断开，如果考虑他们的位置信息，可以稍微避免这个问题。

对于彩色图片，上文是将R,G,B作为距离，整张图片只进行一次分割，原文说对每一个通道都进行一次分割，最后对结果取交集，也就是说图片中的两个点要划分到同一个区域，则在R,G,B三个通道的划分结果中，始终在同一个区域作为最终分割结果。