Image segmentation technology is an important research direction in the field of computer vision and an important part of image semantic understanding. Image segmentation refers to the process of dividing an image into several areas with similar properties. From a mathematical point of view, image segmentation is the process of dividing an image into disjoint areas.The area can be the foreground and background of the image or a single object. These areas can be constructed using features such as color, edges, or similarity of neighbors.

图像分割技术是计算机视觉领域的重要研究方向，也是图像语义理解的重要组成部分。 图像分割是指将图像划分为多个具有相似属性的区域的过程。 从数学的角度来看，图像分割是将图像划分为不相交的区域的过程，该区域可以是图像的前景和背景，也可以是单个对象。 可以使用诸如邻居的颜色，边缘或相似性之类的特征来构造这些区域。

Graph cutting algorithm is one of the classic algorithms of combinatorial graph theory. In recent years, many scholars have applied it to image and video segmentation and achieved good results. This article briefly introduces the graph cut algorithm and interactive image segmentation technology, as well as the application of graph cut algorithm in interactive image segmentation.

图切割算法是组合图理论的经典算法之一。 近年来，许多学者将其应用于图像和视频分割，并取得了良好的效果。 本文简要介绍了图割算法和交互式图像分割技术，以及图割算法在交互式图像分割中的应用。

基本概念 (Basic concept)

We use the theories and methods in the field of graph theory to map the image into a weighted undirected graph, treat the pixels as nodes, and regard the image segmentation problem as the vertex division problem of the graph, using the smallest cutting criterion to obtains the best segmentation of the image.

我们使用图论领域中的理论和方法，将图像映射成加权无向图，将像素作为节点，并将图像分割问题视为图的顶点划分问题，并使用最小的切割准则获得图像的最佳分割。

This type of method associates the problem of image segmentation with the problem of MIN-CUT . The usual approach is to map the image to be segmented into a weighted undirected graph G=(V, E), where , V is the set of vertices, and E is the set of edges.

这种类型的方法将图像分割问题与MIN-CUT问题联系起来。 通常的方法是将要分割的图像映射到加权无向图G =(V，E)，其中，V是顶点集，E是边缘集。

The edge formed by the connection of every two neighboring vertices are called n-links and the connection between each ordinary vertex and the two terminal vertices are called t-links.

每两个相邻顶点之间的连接所形成的边称为n-link ，每个普通顶点与两个终端顶点之间的连接称为t-link。

Each node corresponds to each pixel in the image, and each edge ∈ E connects a pair of adjacent pixels, and the weight of the edge is w(i,j) represents the non-negative similarity in gray, color or texture between adjacent pixels.

每个节点对应于图像中的每个像素，每个边缘∈E连接一对相邻的像素，并且边缘的权重为w(i，j)表示相邻像素之间在灰度，颜色或纹理上的非负相似度。

Boykov and Jolly originally proposed to compute the histograms of the labeled pixels to approximate probability density functions , and to let

Boykov和Jolly最初提出计算标记像素的直方图，以近似概率密度函数，并让

For example, if fB is very low, then wi,F will be very high, making it much more likely that the edge between i and B is cut. The inter-node weights are computed using a simple similarity measure

例如，如果fB非常低，则wi，F将非常高，从而更有可能切割i和B之间的边缘。 使用简单的相似性度量来计算节点间权重

Blake et al. showed how the parameter σ could be estimated based on the local contrast of an image sample.

布莱克等。 展示了如何根据图像样本的局部对比度估计参数σ。

We take a two-category division as an example, divide G = (V,E) into two subsets A, B .These two subsets correspond to the foreground pixel set and the background pixel set of the image, which is equivalent to completing the image segmentation, where:

我们以两类划分为例，将G =(V，E)划分为两个子集A，B，这两个子集分别对应于图像的前景像素集和背景像素集，相当于完成了图像分割，其中：

A segmentation S of an image is a cut of the image, and each region C ∈ S that is segmented corresponds to a sub-image in the image. It is normal in combinatorial optimization to define the cost of a cut as the sum of the costs of the edges that it severs.

图像的分割S是图像的切割，并且被分割的每个区域C∈S对应于图像中的子图像。 在组合优化中，将切割的成本定义为切割的边的成本之和是正常的。

The cost of the cut is the sum of the weights of all edges in the edge set C.If a cut has the smallest sum of weights of all edges, then this cut is called a minimum cut.

切割的成本是边集C中所有边的权重的总和。如果切割的所有边的权重总和最小，则此切割称为最小切割。

Maxflow–Mincut定理 (Maxflow–Mincut Theorem)

图流 (Flow in a graph)

We consider a directed graph (S, A), with afinite set of vertices S and a set of arcs which connect some of these vertices .

我们考虑一个有向图(S，A)，它具有一组有限的顶点S和一组连接这些顶点中的一些的弧。

Among the vertices are distinguished the source S, and the well P.With each arc is associated a strictly positive real number, called capacitance .

在顶点之间可以区分出源S和阱P。每个圆弧都有一个严格的正实数，称为电容。

We seek to pass a maximum flow of a liquid , from the source to the well — the flow in each arc not exceeding its capacity. In other words, we are looking for a function f of the set of arcs in R such that:

我们力求使液体的最大流量从源头流向井-每个电弧中的流量均不超过其容量。 换句话说，我们正在寻找R中的一组弧的函数f，使得：

• for any arc a, 0≤f (a) ≤c (a), where c (a) is the capacity of the arc.
  对于任何弧a，0≤f(a)≤c(a)，其中c(a)是弧的容量。
• for any vertex other than the source or the well, the sum of the flow rates of the incoming arcs is equal to the sum of the flows of the outgoing arcs.
  对于除源或井以外的任何顶点，输入弧的流率之和等于输出弧的流之和。

We speak of a flow for such an application. We seek to determine a maximum flow , in the sense that

我们谈到了此类应用程序的流程 。 我们试图确定最大流量 ，

• The sum of the flow rates of the arcs leaving the source is maximum.
  离开源头的电弧的流量之和最大。

Here is an example of a flow .

这是流程的示例。

However, it is not maximum,it can for example be improved by adding a bit rate of 1 on the S-a-b-d-e-P path .

但是，它不是最大的，例如可以通过在SabdeP路径上添加1的比特率来改善 。

There are several algorithms to achieve maximum flow, such as Dinic or ISAP algorithm.

有几种算法可以实现最大流量，例如Dinic或ISAP算法。

最小割 (Minimum cut)

The value of a maximum flow is equal to the value of a minimum cut.

最大流量的值等于最小切割的值。

Moreover, if (A, B) is a minimal cut, and that a is an arc having its start in A and its end in B, is saturated by any maximum flow.

此外，如果(A，B)是最小切口，并且a是在A处开始而B处结束的弧，则任何最大流量都将其饱和。

结论 (Conclusion)

This lesson cover the basic, low-level operations and tools of image processing, which are necessary for understanding most of the commonly used methods and tools of computer vision.

本课程涵盖图像处理的基本，低级操作和工具，这对于理解计算机视觉的大多数常用方法和工具都是必需的。

提价 (Refrences)

1. Yuri Y. Boykov Marie-Pierre Jolly.Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images
   Yuri Y.Boykov Marie-Pierre Jolly。交互式图割用于ND图像中对象的最佳边界和区域分割
2. A. Blake, C. Rother, M. Brown, P. Pérez, and P. Torr. Interactive image segmentation usingan adaptive GMMRF model. InEuropean Conference on Computer Vision (ECCV), 2004.
   A. Blake，C。Rother，M。Brown，P。Pérez和P. Torr。 使用自适应GMMRF模型进行交互式图像分割。 在欧洲计算机视觉会议(ECCV)上，2004年。
3. Yuri Boykov, Vladimir Kolmogorov: An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. IEEE Trans. Pattern Anal. Mach. Intell. 26(9): 1124–1137 (2004)
   尤里·博伊科夫(Yuri Boykov)，弗拉基米尔·科莫莫洛夫(Vladimir Kolmogorov)：最小切割/最大流量算法在视觉上实现能量最小化的实验比较。 IEEE Trans。 模式肛门。 马赫 智力 26(9)：1124-1137(2004)

4. Adelson, Edward H., and James R. Bergen (1991), “The plenoptic function and the elements of early vision”, Computational models of visual processing 1.2 (1991).

   Adelson，Edward H.和James R. Bergen(1991年)，“ 全光功能和早期视觉的要素 ”，视觉处理1.2的计算模型(1991年)。

5. Boykov, Y., Veksler, O., and Zabih, R. (2001), “approximate energy minimization via graph cuts,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11): 1222–1239.

   Boykov，Y.，Veksler，O.和Zabih，R.(2001)，“ 通过图割实现近似能量最小化 ”，《 IEEE模式分析和机器智能交易 》 ， 23(11)：1222-1239。

6. D.M. Greig, B.T. Porteous and A.H. Seheult (1989), Exact maximum a posteriori estimation for binary images, Journal of the Royal Statistical Society, Series B, 51, 271–279.

   DM基利，BT波蒂厄斯和AH Seheult(1989)， 精确最大为二进制图像后验估计 ，杂志皇家统计学会，B系列，51，271-279的。

7. D. Geman and S. Geman (1984), Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images, IEEE Trans. Pattern Anal. Mach. Intell., 6, 721–741.

   D. Geman和S. Geman(1984)， 随机松弛，Gibbs分布和图像的贝叶斯复原 ，IEEE Trans。 模式肛门。 马赫 INTELL，6，721-741。

8. J.E. Besag (1986), On the statistical analysis of dirty pictures (with discussion), Journal of the Royal Statistical Society Series B, 48, 259–302.

   JE Besag(1986年)， 在肮脏的照片(与讨论)的统计分析 ， 皇家统计学会的 B系列，48，259-302。