图片分割之最大流最小割

在图像分割领域，最近几年基于深度学习的方法占据了绝对领先的地位。但是相对于黑匣子的深度学习，传统的方法更有几分味道。这次要介绍的是图割算法，这是一种基于能量优化的方法，在前景背景分割上很有效果。

1. 最大流与最小割

在了解图割之前，首先需要了解最大流与最小割的概念。

1.1 最小割min-cut

举例说明，如下一个有向加权图所示，从顶点S(source)到顶点T(sink)有三条路径，每条路径的代价c(cost)是该路径上所有边的权重之和。最小割的意思就是说通过割断边将图中所有节点划分为两个不相交的集合，S与T分别在其中一个集合中。并且最小割保证所割断的边的权重之和最小：

gc

可以很明显的发现割断的边是s->a与b->t时是最小割。

1.2 最大流max-flow

我们将边想象成管道，权重表示流量，那么从S能流入T的最大流量就是2+3=5，而在计算最大流量的过程中，我们可以发现起到约束作用的边是s->a与b->t。这也就是最大流。

可以发现，最大流与最小割结果是一致的，其实有人已经证明过（福特-福克森定理）这两者等价。因此可以将最小割问题转化成最大流问题来进行求解。

1.3 最大流问题的求解

传统求解最大流问题的方法是增广路径算法，原理是利用广度优先搜索在图中搜索所有从S到T的路径，最终找到最大流路径。这种方法几乎是需要遍历图中所有的节点，因此效率很低。因此目前大多是使用基于优化的方法。

2. 图割graph-cut

图割算法其实就是将最大流最小割的理论应用到了图像分割的领域。

比如说前景背景分割问题，可以将图像表示为一张无向图G=(V,E)，其中V是顶点集合，E是边集合。在这个图上多添加两个顶点，一个代表前景的S(Source,源)节点，一个代表背景的T(Sink,汇)节点。在初始构造的图中，每个像素顶点都和S与T连接，并且它们之间的边被叫做t-links。如下图：

gc

• t-links：每个像素节点与类别节点（S/T，t是terminal的缩写）相连的边；

• n-links：像素节点之间边（上面图中每个像素节点只与自身周围的四个像素节点相连，n是neighbour的缩写）；

• Cuts：一组边的集合，Cuts的断开会使得节点S与T之间没有通路，即每个像素只会与S或T中的一个相连接。其中t-links的断裂实现了像素的分类，而n-links的断裂实现了分割；另外！Cuts是最大流或者最小割的结果，其权重之和最小；

2.1 权重costs

由上可知图割算法中如何确定costs至关重要。

在前景背景的分割领域中，前景与背景是有一些外观差异的，这个体现在像素值上。因此t-links对应的权重可以是像素值与目标像素的相似度（因此此类算法可能需要手工给定前景背景的像素初始值），相似度越大，对应的割断代价也越大。

而对于n-links，上面每个像素节点都只与相邻的四个像素节点相连（n-links），表示临近像素之间属于同一类的概率，同时临近像素之间会有邻域相似性，而相似性较差的区域往往是前景和背景的交界处。即如果相邻的两个像素像素值相似，那么断开该边的代价就会高。

2.1.1 t-links的权重

对于一个像素点，其有两条t-links边，分别是连接前景节点S与背景节点T的边。边的权重可以是终端节点的颜色差异。

2.1.2 n-links的权重

对于一个像素点，其有周围相邻的像素点之间存在n-links边，在图像分割任务时边的权重一般也是用颜色差异来确定的。

其实上面讲述的还是图的建立，关于图割进行时的能量最小化算法其实也非常重要，但是这个我现在没想到如何简短的说明白，之后再补充。

2.2 示例

如下，对于一个3x3的图，

1. 首先取两个种子点（即人为指定分别属于前景背景的两个像素点）；
2. 建立一个图，图中边的粗细表示对应权重的大小；
3. 找到最大流或最小割的边的组合，完成图像分割；

gc

参考文献

• [1] Boykov Y , Kolmogorov V . An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(9):1124-1137.

• [2] https://pengyizhang.github.io/2020/04/07/graphcut/