辛月兰

0 引言

近年来，图割技术作为一种鲁棒的能量最小化方法，得到越来越多的重视，通过对图像分割的推广，图割技术已经应用在整个计算机视觉领域。

1 图割基本理论

1.1 图割基本理论的概述

设一个无向图为G = 〈V，E〉，V 为图中节点的集合，E 为连接节点的边集。通常，节点代表了像素、体元或其它特征，而图中也包含一些附加的特殊节点，称为终端节点。在立体视觉应用的能量最小化方法中，图的结构有很多种形式，但大多数都是基于规则的二维或三维网格图。

一个具有两个终端节点的二维图，定义V = { s，t} ∪P为无向图 G 中的节点，包含了两个表示“目标”和“背景”标签的特定终端节点，分别为源点s 和汇点t，以及一系列非终端节点的集合P。图中每一边被赋与一个非负的容量( 或称权值) ，边缘代价通过边缘厚度（线的粗细）表现出来。图中的边可以被分为两类: n-links 和t-links。连接非终端节点的边称为n-links; 连接像素到终端节点的边称为t-links。

Boykov[1,2]的交互式分割的具体过程，如图1所示：

图1 二维图网络（基于图割理论进行图像分割）

1.2 分割能量

其中公式（2）

这里负对数是通过MAP-MRF构想产生的公式（3）

B(A)项包含分割A的边界性能，系数Bp,q≥0应该看作p和q之间不连续的一个处罚，

如图 1（a）所示，“O”为交互设置的目标种子点，“B”为交互设置的背景种子点；图1（b）是根据（1）式建立的能量函数所构造的网络图，网络图的权值，如表1所示：

表1 边权值定义

图1（c）是使用最大流/最小割算法对图1（b）建立的网络图进行的切割；图 1（d）是根据图割获得的图像分割结果，相当于二元分区将图像划分为“目标”和“背景”部分。

1.3 图割的能量最小化

根据能量优化的观点求解最小图割，是目前图割中的主要求解方法。该方法需要根据图像的特征信息，建立合适的能量函数，然后根据能量函数，建立图论中的网络图，通过对网络图采用最大流/最小割算法，获得分割的结果。

从理论上讲，基于图割的能量函数最小化方法，可以提供能量函数的全局最小化；也就是说，即使产生的结果是局部最小值，也是具有很强性质的局部最小值。因此对特定领域里一些有争议的问题，可利用基于图割的能量最小化方法，得到最准确的解决方式，因此，将其应用到图像分割上，以期得到更好的分割结果。

计算机视觉中的很多相关问题，都可以归结为能量最小化的问题[3]。能量最小化存在很多优点：首先，它可以与解决它的算法分开，清楚地描述需要解决的问题；其次，它可以用空间光滑的结果来求解多义性的问题；最后，能量最小化避免了陷入早期硬约束的窘境。

能量最小化在计算机视觉中，已经存在很长的一段历史，并广泛应用于很多问题中，如光流、图像恢复、表面重构、纹理合成以及边缘检测等。梯度下降和模拟退火算法，是两种典型的能量最小化方法，前者适用于所有连续变量的函数，而后者几乎可以用于所有的离散变量函数。但这些方法可能会产生比较差的结果，因为它们经常陷于局部最小化中，或者是花费很长时间才能收敛。在实践中，即使在非常简单的二值图像修复中，模拟退火得到的解，离全局最小也很远。

1989年，Greig等人[3]将图割理论引入计算机视觉领域，出现了基于图割的能量最小化方法，它克服了以上两者的不足，实现了能量的全局最优化。它将图像分割问题转换为图论中网络图的切割问题，依据最小割准则，使切割后划分的区域间具有最小的相似性。基于图割的图像分割，将图像分割问题转换为能量函数的优化问题，通过合适的能量函数建立相应的网络图，通过最大流/最小割算法求解网络图最小割，从而获取图像分割的结果。

2 图割的研究现状

2.1 图割的发展状况

近年来，基于图割的能量最小化方法在图像处理和计算机视觉中的应用越来越广泛。图割理论自1989年首次被发现，可以最小化计算机视觉中的某个能量函数，且只限于二值图像。1998年Roy和Cox首次用来解决非二值图像问题，其方法是图的最大流/最小割算法。Yuri Boykov和Maric-Pierre Jolly[4]2001年首次将图割（graph cuts）理论引入计算机视觉领域，他们提出并实践了一种新的基于能量最小化进行目标分割的方法，并提出了利用最大流/最小割算法，进行全局组合优化的目标提取方法。自此以后，利用图割来解决计算机视觉的问题越来越受到欢迎。许多研究者提出了多种分割算法，如 Rother[5]等人，在 2004年提出的GrabCut算法，是目前目标提取效果较好的方法；Ning Xu[6]等人提出的基于图割理论的活动轮廓（GCBAC）算法，克服了传统的活动轮廓算法容易陷入局部最优的缺陷，能够快速、准确地收敛到目标的边界。

国内自2006年有论文发表以来，用图割研究的领域也越来越广。电子科技大学、安徽大学和吉林大学在图像复原、图像匹配、三维重构和目标提取、图像去噪、运动目标检测、合成、分割等多个领域都有研究。

为得到更加鲁棒的分割性能，许多学者试图将形状先验引入到图割分割过程中。这种将高层先验引入到底层分割的做法是近年来的新趋势。文献［7］用一个初始轮廓在终端边缘和执行图割迭代开始加强了形状先验模型，给出一组训练的形状，他们的方法是利用核主成分分析（kPCA），建立一个统计形状空间，在每一步迭代，这个形状空间标记的上一个图用来作为先验概率图，负记录被分配到终端权重。虽然这方法取得了可喜成果，但他们的外形产生的能量不是基于形状的度量标准，此外，该方法不能同时处理形状的仿射变换和同时分割多目标物体。文献［8］提出了一个新的广义形状先验，称为星型先验。它可以表示比紧凑先验更为一般的形状，而且同样只需提供一个内部点就满足分割需要。特别是对于凸形状，这个点可以选在内部任意位置而不会对最终分割结果产生影响。但文献中星型先验的计算方法略显复杂，需要计算图像中内部点的所有离散直线。Lang 等人［9］对其提出了改进，在简化计算步骤的同时，保证了与原算法分割效果的一致性，而且，可以处理目标具有复杂纹理的情况。

图割理论在国外的计算机视觉领域中，得到了成功且广泛应用，但在国内的研究还处于初级阶段，尤其是图割理论用于图像分割这一领域的研究报道并不多，将图像的形状等先验知识引入图割技术的研究更是寥寥无几，因此，基于图割理论的图像分割在现阶段仍然是一个研究热点。

2.2 图割的应用

图割技术因其能量全局最优化而格外引人注目，是计算机视觉中正在兴起的一个有用的工具。

目前，通过各种方法将形状先验融入到图割技术中是图割研究的热点之一。 例如文献[23]的作者提出一种全新的方法分割一个特殊类的形状，调整光滑项防止过大，如果违反这个规则用一个紧凑形状来维护，然而，在实际应用中涉及到变化的形状时该方法是受限的。文献[24]的作者提出了一种分割时执行迭代的类似方法，每步迭代拟合一个椭圆到当前分割，定义为形状先验联合分割内部，然而，如紧凑的方法。该方法也不能推广到高度可变的形状，同时，这种方法合并形状先验作为一个附加的固定权重，不是概率意义上的贝叶斯先验。为获取更多的任意形状，文献[25]作者在光滑项中使用一个距离函数帮助边界定位，执行图割前决定形状分割和固定对准，该方法似乎对初始估计相当敏感，还有，因为形状先验在边界项的作用，在某种意义上有一个局部效应和对错位的敏感。

2004年，Boykov和Kolmogorov在增广路算法基础上，提出了一种新算法[11]求解最大流，并将其应用于图像分割及计算机视觉中，大幅度地提高了求解速度。在 push-relabel算法基础上，Hochbaum[12,13]提出采用pseudoflow解决最大流问题，在Olivier Juan和Yuri Boykov提出的Active Graph cuts[14]图割方法中，应用此最大流算法对网络能量函数进行了求解；文献[15]提出了一种基于简化网格图的立体匹配算法.算法通过区域匹配，得到每个像素的初始视差值，然后只保留完整网格图的部分可能的视差值，去除其余大部分的节点和边缘，建立简化的网格图.该方法大为缩减了网格图的容量，缩短匹配所用时间，并且能够选用更大的视差范围.

Boykov[1]等人在2000年发表了一篇在N维空间交互式的图像分割方法，以其简洁的交互方式、较快的处理速度以及能将各种信息融合，而引起人们的关注；Rother[16]等在Boykov等人的基础上提出Grab cut算法，通过高斯混合建模与数据的估计代替 Boykov的直方图模型，可对彩色图像进行分割，而且使得交互更为方便，目前是交互式图像分割中最好的一种方法；文献[17]提出一种新的基于图割(graph cuts)的交互式图像分割方法。该方法将图像的纹理、色彩、边缘等多种特征，通过一个概率模型结合在一起，其中纹理和色彩用以Texton 为基的直方图来建模，并用Fisher 判别准则来对特征空间进行降维。利用图割方法，可以快速求解该模型下的最优分割；文献[18]针对腹部CT 图像中组织分割的问题，提出了一种基于图割与改进的快速水平集的交互式分割方法；文献[19]提出一种基于图割的全变差( TV) 图像去噪算法， 该算法将全变差去噪模型的能量函数最小化问题转化为图的最小割问题, 然后采用图割技术( 最大流/最小割算法) 求得能量函数的全局最优解。

文献[20]基于多尺度思想对图像分割，它先对原始图像下采样，用图割对低分辨率图像分割，然后将分割的结果映射到较高分辨率图像的带状区域，并逐级在较高分辨率图像的窄带状区域分割，直至得到原分辨率图像的分割结果；文献[21]将图割技术与分水岭算法相结合进行分割，先用分水岭将图像分成若干小的区域，再对这些小区域采用图割技术，提高了分割速度。

文献[22]将图割与主动轮廓相结合，通过设置初始化轮廓建立轮廓区域，利用图割全局能量最优在一定的轮廓区域寻找目标边界的最优解；文献[23]提出图割计算测地线和最小表面的方法，通过建立网格图及设置边缘权使得割的代价任意接近相应轮廓的长度或表面面积。

图割可用于3D目标或序列的分割，在文献[1]中，通过交互式选取若干帧的种子点，采用3D图对运动目标进行了分割。

图割技术还在图像修复、图像合成、区域融合、多摄像机场景重建、聚类、目标识别、形状重建等诸多方面都有广泛的应用，充分表明图割的应用前景是非常广泛的。

3 能量函数的构造及求解

一个图像分割的问题可以看做给图像中所有的像素分配一系列对应标号的问题。如对于一个二值标号的问题，如果像素点i属于前景，设其标号值为1，反之，如果像素点i属于背景，设其标号值为 0，这样通过对像素标号实现对图像前景和背景的分割。在不确定的情况下，找到最好的标号成为一个优化问题。优化的方法通常由两步构成：构造能量函数及求解能量函数的最优解。

3.1 能量函数的构造

图割是解决优化能量函数问题的，因此需要将要解决的问题构造成能量函数，这是前提。

在图像分割问题中，能量函数的构造包含两个通常的约束：数据项约束和平滑项约束公式（4）其中数据项Edata(f)对应t-links，它评价分配一个标签到给定区域的惩罚；光滑项 Esmooth(f)对应n-links，评价两个相邻像素不同区域的惩罚，即边界不连续性。

然而对于具体问题来说，可以在这两项的基础上加上符合自己问题的约束条件。例如：基于Potts模型的能量形式公式（5）

式中，E（.）是能量，p和q是像素， N是像素的连通邻域点集合； Dp(·)是一个数据补偿函数，表示数据约束，用于保证每个像素尽可能地找到其对应标号；V{p,q}是平滑项，是对相邻像素标号不一致的惩罚，V{p,q}通过衡量像素之间的不连续性来决定空间一致性。

在二元标号问题中，即将图像分为目标和背景两部分的情形，能量函数得公式（6）

其中f是一个从像素集p到标号集L{0,1}的映射值，对每个像素点给定一个标号值f，f值为0的像素集设定为目标，f值为1的像素集设定为背景。

在加入形状先验知识的分割问题中，基于potts模型的能量函数得公式（7）

在图像修复中，基于Potts模型的能量函数得公式（8）

3.2 能量函数的求解

对公式（5）这种组合优化问题，找到全局最优值是一个难以解决的问题。

1956年，ford[24]等证明了著名的最大流/最小割定理，即在任何网络图中，最大流的值等于最小割的容量，并给出了求解的具体算法，该算法可以依据多项式时间完成计算；1989年，Greig[23]等人首先发现最大流/最小割算法，能被用来最优化某些重要的能量函数，并根据公式（5）的结构，建立了具有两个终点的一个图，使图的最小割给出了全局最优的二元标号。目前，解决最大流常用Ford-fulkerson算法、push-relabel算法及Boykov等人的新算法。

总之，采用图割求解能量函数的基本思路，就是对一个给定的能量函数构造对应的网络图，然后通过对网络图的最小割求解，使得能量函数最优。

4.基于图割提取图像信息的解题步骤

综上所述，基于图割提取图像信息的解题步骤，一般为：根据问题建立能量函数、构造有两个终端节点的网络图、用最大流（最小割）算法求解、提取图像信息，如图2所示：

图2 图割解题步骤

其中最关键的步骤，就是根据图像分割问题，建立合适的能量函数及对能量函数求解。

4.1 建立能量函数

能量函数的建立，主要体现在数据项和光滑项的建立上。典型应用图割对图像分割的不同只在数据项和光滑项的定义上。

4.1.1 数据项的建立

图割在不同领域的应用，主要体现在数据项的建立上。在不同的应用与问题中，数据项的定义不一样。

4.1.2 光滑项的建立

如式（3），V{p,q}是光滑项，它是所有相邻像素的相邻交互函数的和。光滑项的建立可以提高图像分割的质量，V{p,q}的形式决定光滑先验信息的类型，其主要类型有：处处光滑、分段常数及分段光滑。

处处光滑约束的常用形式得公式（10）

分段常数约束的常用形式得公式（11）

分段光滑约束的常用形式得公式（12）

对上式中的系数u{p,q}可根据具体问题做相应的设置。在公式（12）式中，当u{p,q}为常数时，式中的光滑能量为potts能量，光滑项给出了两个相邻像素为不同标号时的惩罚，这个惩罚不依赖于设置的标号。在图像分割中常采用这样的约束作为光滑项。

建立了数据项和光滑项后，就可建立能量函数。综上所述，在图像分割中，常用的能量函数为如下的potts模型，如公式（13）

其中T(·)是指示函数，括号中的值为真，它为1，否则为0。k(p,q)表示对相邻像素标号不一致的惩罚。

4.2 构造网络图

如图3所示：

图3 网络图

构建一个图表示这个能量，每个像素看作除表示目标和背景节点外的图节点，数据项实现每个像素都连接到目标和背景节点，非负边缘权重 Rp(O)和Rp(B)表示目标和背景区域存在相似像素P。最后，光滑项实现每对相邻像素(p ,q)的连接，非负边缘权重 B(p,q)决定边缘不连续的处罚。由此可见，基于能量函数可以建立网络图。

文献[29]研究了能量函数进行图割优化应该具备的条件，并给出了具体构造图的方法。

4.3 求解网络图

对于建立的网络图G，可通过最大流/最小割算法求解，即求取该网络的最小割，由于最小割是沿着边界的总数，最小割的加权图分割表示从背景分离最好的目标。这样对能量函数的最优解是通过图的最小割实现的。

4.4 获取图像的处理结果

最小割准则将图像分割成两个区域。对于二元标号，通常可直接将一个区域作为目标，另一个区域作为背景。显然对图像的二元分割可直接采用图割方法来获取全局最优解。

5 存在的问题和研究前景

图割是基于图论的图像分割方法，且具有二元全局能量最优化的特性，尽管它广泛地应用于图像分割，但它在分割对象具有弱边缘、杂波及部分被遮挡时容易失败，合并形状先验信息可防止这样的失败，然而将这样的信息融入图割是一个长期的研究领域。

目前，基于图割的交互式分割得到了良好的分割结果与广泛应用，但是基于图割对图像进行自动分割以及对运动目标自动分割，还没有太多研究与应用，因此，解决该问题是研究的方向之一。

图割是基于能量优化的方法，而现有的许多基于能量函数优化的图像分割方法，都具有其各自的特性和不足。因此，为克服现有方法的不足，如何将现有的方法与其它基于能量的优化方法相结合，或者重建一个新的模型，在一定程度上取长补短是需要研究的问题之一。

随着图割在计算机视觉中的广泛应用，图割方法本身也存在许多有待改进的不足之处，其中最重要的就是能量函数的更新和最小化问题。利用图割解决问题要利用网络图，而构图时的计算量过大是一个难题，目前，许多算法已针对图割方法构图时计算量过大问题进行了改进，把图割理论和其他方法结合，用于图像分割可达到很好的效果，如何找到更好的方法解决该问题，是我们努力的一个方向。

正则性是函数可以用图表示的必要条件。只给出了F3集合中函数的构造[23]。至于在 F4，F5，…，Fk集合中，如果函数也满足正则性，图割法是否仍然适用，是应该思考的问题。

图割对应的是二元标号优化问题，而Multiway cut对应多元标号的问题，对它的能量最优求解是一个 NP-Hard问题，目前对Multiway cut的能量最优化采用近似求解，如α-βswap算法和α-expansion算法。这种近似算法，目前多用于计算机视觉的其他方面，在图像分割中很少应用。如何更好地应用此类算法，解决图像分割是需要研究的问题。

6 结束语

基于图割的图像分割，作为目前国际上图像分割领域的一个新的研究热点，因其具有独特的结构，得到了很多研究者的青睐，并得到了广泛的应用。然而正因为它是一种新的图像分割方式，对它的研究和应用还处于初级阶段，仍有大量的问题有待研究和解决。基于图割的图像分割技术涉及到的理论知识和学科比较广泛，对其研究不仅可丰富图像分割的应用，而且在图像处理领域具有重要的理论价值和巨大的应用潜力，在学科交叉的研究与应用上也具有重要的意义。

[1]Boykov Y,Jolly M P.Interactive organ segmentation using graph [C]cuts.In:Proc.Third International Conference on Medical Image Computing and Computer-Assisted Intervention,2000,276-286.

[2]Yuri Boykov,Olga Veksler.Graph cuts in vision and graphics theories and applications.In [K]Handbook of Mathematical Models in Computer Vision,Springer,2006.

[3]Greig,D.Porteous, B.A.Seheult.Exact maximum a Posteriori estimation for binary images[J], JOumal of the Royal Statistieal Society: SeriesB, 1989, 51(2): 271一279.

[4]Boykov, Y.Jolly, M, P.Interactive Graph cuts for optimal boundary ®ion segmentation of objects in N-D images.[C]Proceedings of “intimation conference on computer vision”, Vancouver, 2001（7）: 105-112

[5]Rother, C.Kolmogorov, V.A.BLAKE.GrabCut:interactive foreground extraction using iterated graph cuts[C], proceeding of the 2004 SIGGRAPH conference，Aug 2004，I：309-314.

[6]Xu, N.Abuja, N.Bansal.R.Object segmentation using graph cuts based active contours[J].computer vision and image understanding，2007,107(3):210-224.

[7]Malcolm, J.Rathi, Y.and Tannenbaum.A.Graph cut segmentation with nonlinear shape priors.[j]In ICIP,2007.1

[8]徐秋萍，郭敏，王亚荣.基于图割的目标提取实时修正算法.[j]计算机应用.2008(12):28(12),3116-3122.

[9]Ford L R,Fulkerson D R.Maximal flow through a network.[M]Canadian Journal of Mathematics, 1956, 8(3):399-404.

[10]Cherkassky B V,Goldberg A V.On implementing the push-relabel method for the maximum flow problem.[M]Algorithmica.1997,19(4):390-410.

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

[12]Hochbaum D.S.The Pseudoflow algorithm:A new algorithm for the maximum flow problem.Operations Research to appear.Extended abstract in The pseudoflow algorithm and the pseudoflow-based simplex for the maximum flow problem.[G]Proc.Int'l Conf.Integer Programming and Combinatorial Optimization, 98:325-337.

[13]Hochbaum D.S.The Pseudoflow algorithm:A new algorithm for the maximum flow problem.[M]Operations Research,2008,58(4):992-1009.

[14]Juan O,Boykov Y.Active graph cuts.Proc.of IEEE Conference on Computer Vision and Pattern Recognition.[C]New York:IEEE Computer Society,2006: 1023-1029.

[15]Rother C, Kolmogorov V,Blake A.GrabCut:interactive foreground extraction using iterated graph cuts.[j]ACM Transactions on Graphics(TOG),2004,23(3): 309～314.

[16]刘嘉，王宏琦.一种基于图割的交互式图像分割方法.[j]电子与信息学

[17]杨昌俊，杨新..基于图割与快速水平集的腹部CT图像分割..[j]CT理论与应用研究.2011(3): 291-300

[18]吴亚东，孙世新，张红英等.一种基于图割的全变差图像去噪算法.[j]电子学报.2007(2):35(2),265-268.

[19]Herve Lombaert,Yiyong Sun,Leo Grady,et al.A multilevel banded graph cuts method for fast image segmentation.Proceedings of the Tenth IEEE International Conference on Computer Vision, [C]ICCV 2005,1:259-265.

[20]Li Y,Sun J,Tang C K,Shum H Y.Lazy snap-ping.[C]In Proceedings of ACM SIGGRAPH, ACM Press, 2004,23(4):303-308.

[21]Xu N,Bansal R,Ahuja N.Object segmentation using graph cuts based active contours.[C]In IEEE International Conference on Computer Vision and Pattern Recognition,2003,2:46-53.

[22]Greig D,Porteous B,Seheult A.Exact maximum a posteriori estimation for binary images.[C]Journal of the royal statistical society,series B.1989,51(2): 271-279.

[23]Slabaugh G.and Unal, G.“Graph cuts segmentation using an elliptical shape prior,” in Int.Conf.[G]on Image Processing, 2005, pp.1222-5.

[24]D.Freedman and T.Zhang, “Interactive graph cut based segmentation with shape priors,” [j]in Computer Vision and Pattern Recognition, 2005, pp.755-762.

[25]Das, P.Veksler, O.Zavadsky, V.and Boykov, Y.“Semiautomatic segmentation with compact shape prior,”in Canadian Conf.[j]on Computer and Robot Vision,2006, pp.28-36.