3.1 EGBIS

在本章内容中，我们将介绍基于图的高效图像分割（Efficient Graph-Based Image Segmentation, EGBIS）算法，该算法是基于图的贪婪聚合算法，原理简单，速度较快，也是后期诸如选择搜索、语义分割等算法的基础。EGBIS 算法的目标是作为一种通用的图像分割计算方法，因此在设计之初就被要求满足：

能够捕获视觉上重要的区域，且具有全局观
需要具备较高的计算性能，运行时间应该是图像像素大小的线性函数

然而，这样的设计目标存在很多难点，例如，如何将一个图片划分为多个区域，如何定义一个指标去检测划分的优劣，以及如何解决局部高变区域的划分以及如何保证这个过程的计算高效性。实际上，在此之前已有许多解决方案，但是这些方式通常速度很慢，且对局部高变区域处理的不够理想，不能捕获非局部特性。

下图解释了什么是高变区域及非局部图像特征，
【图 1】

左上角是我们的原始图像，直觉上它分为三个主要区域，左侧的渐变矩形区域，右侧带孔的常值矩形区域以及右侧中间像素高度变化的小矩形区域。如果我们仅仅使用相邻像素之间的差值作为划分依据，由于高变区域内像素之间的差值远大于渐变区域内以及渐变区域边界与常值区域之间的差值，若阈值设定较大，则高变区域内图像则会被划分为多个极小的区域而其他区域化为一体（如右下角图像），这就是典型的单纯局部特性捕获，反之处理，则高变区域会归为常值区域中（如右上角图像），而通过 EGBIS 自适应的非局部特征捕获则可以较好的将图像划分为视觉上的三个区域（如左下角图像）。

3.1.1 算法基础概念

图在计算机算法中是一种基本的数据结构，可以表达为 $G = (V, E)$ ，其中 $V$ 是图中的所有顶点集合，在该算法中，对应的是图像中的所有像素点集合， $E$ 代表图中顶点之间的边。每条边具有不同的权重 $w(v_i, v_j)$ ，以衡量两个顶点 $v_i, v_j$ 之间的差值。我们可以将图 $G$ 划分为多个不重叠的区域集合 $S$ ， $S$ 中每个小区域我们称之为 $C$ 。
【图 2】

为了判断两个区域之间是否存在一个边界，我们定义如下的判定准则，

$D(C_1, C_2)= \begin{cases} \text{true}, & \text {if $Dif(C_1, C_2) > MInt(C_1,C_2)$} \\ \text{false}, & \text{otherwise} \end{cases}$

其中 $Dif（C_1,C_2）$ 评估的是两个不同区域中元素之间的距离值，而 $MInt(C_1, C_2)$ 评估的是一个区域内部两个元素之间的距离值，如图 2 所示。

$Dif(C_1, C_2)$ 具体指的是两个不同区域中所有元素组合中距离最小的值，形象化可以理解为两个区域中最近点之间的距离，反过来 $M I n t$ 应该评估的是一个区域内部某种最大的距离。即，如果一个区域内部相当紧密，不同区域间最小间距大于单个区域内部的最大距离，我们则认为两个区域间确实存在边界，否则，两个区域应该被合并为一个大区域。具体地：

$Dif(C_1, C_2)=\min_{v_i \in C_1, v_j \in C_2, (v_i, v_j)\in E} w(v_i, v_j)$

在给出 $M I n t$ 具体形式之前，我们先介绍一下最小生成树（MST）的概念。最小生成树是一棵连通加权无向图中所有节点且整体权值最小的一棵树。

【图 3，图片来源自维基百科】

如图 3 所示，浅灰色线及黑色线组成一个带有权值的无向图，黑色线组成的树连接了图中所有顶点且保证了所有权重加权最小。 $I n t$ 被定义为 MST 中权值最大的边（以上图为例为 8）。即：

$Int(C)=\max_{e \in MST(C,E)}w(e)$

这里并没有直接在内部采用任意两个元素之间的距离，因为这存在大量的冗余连接，而最小生成树可以摒弃这种冗余连接。在实际使用过程中，我们在 $I n t$ 指标上做了一点处理，即 $M I n t$

$MInt(C_1,C_2)=\min(Int(C_1)+\tau(C_1), Int(C_2)+\tau(C_2))$

根据公式，我们可知， $M I n t$ 取两个区域中 $I n t$ 较小者，即两个区域中，只要有一个内部区域的最大值小于 $D i f$ ，则认为两个区域间存在边界，这也是很直观的。另外 $\tau(C)=k/|C|$ 是一个阈值项。 $∣ C ∣$ 表示区域内顶点数。如果不加这一项，对于较小的区域评估误差较大，例如极端情况下，如果区域中只存在一个顶点，则 $I n t = 0$ . $k$ 是一个常量，对于较大的 $k$ 会导致趋向于划分较大区域块，极端情况，如果 $k=+\infty$ ，则 $MInt=+\infty$ ，则任意区域间不存在边界，即整理聚为一块。 $k$ 的取值需要结合聚类结果决定，对于边界差异较强的图像可以采用较小的 $k$ 值。

3.1.2 EGBIS 算法

将图 $G$ 中所有边按权重值大小非递减排序， $\text{Sort}_E = \pi=(o_1, \dots, o_m)$ ，共有 $m$ 个边
$S^0$ 作为初始阶段，所有的顶点 $v_i$ 分别作为一个独立的区域 $C$
设置一个变量 $\dots, m$ 循环第 3 步：
给定 $S^{q-1}$ 我们构造 $S^q$ ，具体的：
1. 取出第 0 步中经过排序的，边序列中的第 $q$ 个权重， $v_i,v_j$ 分别为该边所连接的两个顶点，例如 $o_q=w(v_i, v_j)$
2. 如果在 $S^{q-1}$ 阶段， $v_i, v_j$ 处于两个不同的区域中，且 $w(o_q)$ 比它们的内部区域距离都小，则应该合并它们，否则什么也不做。
  
  上步中形式化描述为：设 $S^{q-1}$ 阶段包含 $v_i$ 顶点的区域为 $C_i^{q-1}$ ，包含 $v_j$ 顶点的区域为 $C_j^{q-1}$
  
  if $C_i^{q-1} \neq C_j^{q-1}$ and $w(o_q) \leq MInt(C_i^{q-1},C_j^{q-1})$ :
  
  from $S^{q-1}$ to $S^q$ by $\text{merge}(C_i^{q-1}, C_j^{q-1})$
  
  else:
  
  $S^q = S^{q-1}$
最终的 $S = S^m$ 作为返回结果。