图割方法综述

林 强，董 平，林嘉宇

（国防科技大学电子科学与工程学院，长沙410073）

·微机软件·

图割方法综述

林 强，董 平，林嘉宇

（国防科技大学电子科学与工程学院，长沙410073）

介绍了近年来图像分割方法及图割的研究进展。首先将现有的多种类型图像分割方法归结为五类典型方法，并分析各自的特性；接着详细介绍图割的概念和图割的三种分割方法，每种方法的应用现状和特性；最后指出了图割的一些研究方向。

图割；交互式；能量函数；分水岭

1 引 言

图像分割是将图像分割成不同的有类似颜色、强度或纹理的区域［1］。图像分割作为预处理步骤在计算机视觉、目标识别、跟踪和图像分析等领域起着显著作用。通常，图像分割分成五类：第一类是基于阈值的分割方法。它是利用图像的灰度直方图信息得到分割阈值，将图像分成目标和背景，从而实现对图像的分割。阈值法包括单阈值分割［2］、多阈值分割［3］和可变阈值分割。基于阈值的方法实现简单，算法也比较简单，特别针对目标和背景差异比较大的图像。缺点是不容易找到合适的阈值，容易受到噪声的影响，难以处理多个目标的情况。最常用的阈值算法有最小误差法［4］、最大类间方差法［5］、模糊集法［6］、最大熵分割算法［7］等。

第二类是基于边缘的分割方法。该方法假定不同区域的像素值是不同的，通过特征的不连续来检测区域边缘，由此实现区域分割。这些不连续通常用第一阶或第二阶导数法来检测，如Laplace算法［8］。而基于梯度的Sobel［1］、Roberts和Prewitt算法比较容易实现，并且可以粗略检测轮廓外形，但它们和Laplace算法一样，对图像的噪声很敏感。由此，引入LOG算法，通过高斯滤波器平滑图像，然后利用Laplace算子降低噪声影响。这些算法都有一个缺点，不能够得到连续完整的边缘，因此需要进一步对边缘进行修正。常用的边缘修正的方法有相位编组法、启发式连接和层次记号编组法等。

第三类是基于区域的分割方法。区域分割方法利用局部空间信息进行分割，将具有相似特征的像素集合起来构成区域，区域分割法分为区域生长和区域分裂合并［1］。区域生长算法是在每个区域中找一个或多个种子像素点作为生长的起点，然后相邻像素根据预定义准则来分组，直至没有可以归并的点为止。区域分裂合并算法先将图像划分成一系列小区域，然后按照某种准则进行分裂或合并区域。因此区域分裂合并算法的研究重点是对分裂和合并的准则设计。基于区域的分割方法可以有效消除噪声干扰，算法上具有较强的鲁棒性，但分割速度较慢。

第四类是基于分水岭的分割方法［9］。该方法把图像看作拓扑面，把像素值看作高度。图像区域的最低值定义为集水区，两个相邻的集水区之间的最大值称为脊线，即分水岭，基于分水岭的分割算法就是在图像中找分水岭。该算法适用于目标对应为集水区，边界对应为分水岭的梯度图像。缺点是容易受到噪声和不规则梯度的影响，有时还会存在过度分割的问题。通常通过标记控制方法来减少过度分割。

第五类是基于能量的分割。该方法需要建立一个客观的能量函数，当图像按预期结果分割时函数达到极小值，由此将图像分割问题转化为能量最小化问题。常见算法有Live wire［10］、活动轮廓［11］、水平集［12］和图割［13］等。对于Live wire，种子必须位于目标的边界，最小化能量函数得到曲线最优解。基于活动轮廓的图像分割模型是一个动态的二维或高维闭合曲线模型。它在模型内力和外力的共同作用下向目标边界运动，最终到达平衡位置时即收敛到目标边缘，得到目标的分割结果。基于水平集的方法也是先给出初始曲线，让曲线按照某种规则演变，使能量函数得到极小值。这两种方法只利用边界信息且对初始曲线非常敏感，运算时间比较大，且不易得到全局最优结果。对于图割分割，能量函数的构造是基于区域和边界信息，将图像分割问题转换为能量函数的优化问题，通过合适的能量函数建立相应的网络图，通过最大流/最小割算法求解网络图最小割，实现能量的全局最优化，从而获取图像分割的结果。文中，首先介绍图割分割的概念，然后介绍图割分割的一些方法。

2 图割分割

在本节中，将介绍图割的概念以及如何建立图割分割的图像对应的无向图。

2.1 图割概念

设一个无向图G＝＜V，E＞，V是图中两种不同类型节点的集合，定义V＝｛s，t｝∪P，P表示对应图像像素的点集，s和t表示两个特殊的顶点或称为终端，通常一个称为源点s，代表目标，一个称为汇点t，代表背景。这种图形也被称为S－T图。

在图中，也有两种类型的边，n－links和tlinks，n－links连接图像内相邻的像素p、q，t－links连接像素和终端，每个像素有两条t－links，｛p，s｝和｛p，t｝。每条边都被赋予一个非负权重We，也被称为代价。图G的一个割C是边集E的一个子集，将图G的两个终端分离（即两个终端之间没有边连接），而对于C的任一子集，均不能将两个终端分离。割C的代价（记作｜C｜）定义为组成割C的所有边的权重总和，表示如下：

最小割就是图G中所有割代价最小的割，它根据L.Ford and D.Fulkerson［16］提出的网络流理论，通过寻求网络图的最大流而得到。文献［17］证实，该最小割相当于最大流，而这个最小割正是要求解的能量函数的全局最优值。因此，该图节点被分为两个互不相交的子集S和T，s∈S、t∈T且S∪T＝V。两个子集对应图像的目标和背景。

2.2 图割分割

图像分割可以视为像素标记问题。目标（s节点）的标签设置为1，背景（t节点）的标签设置为0，这个过程可以通过最小化能量函数实现。为了使分割合理，分割应该在目标和背景之间的边界内。考虑一个数据集合（像素）P和用一个集合L表示的邻域系统L＝｛l1，l2，...，li，...，lp｝，p是图像像素的数量，li∈｛0，1｝。向量L定义一个分割，该分割的能量函数为以下方程，它可以在S－T图中用最小割来最小化［13］：

其中，R（L）表示包括区域分割信息的区域项，B（L）表示约束边界分割的边界项，μ是区域项和边界项之间的相对因子。区域项R（L）定义如下：

Rp（lp）是像素p到目标和背景的处罚，可以通过比较像素p与目标和背景强度的直方图获得。t－links的权重定义如下：

从上式看到，当Pr（Ip｜′obj′）大于Pr（Ip｜′bkg′）时，Rp（1）小于Rp（0），因此，当所有的像素正确分成两个子集时，区域项减小到最低程度。边界项B（L）定义如下：

其中，p、q是相邻像素，δ（lp，lq）定义如下：

当相邻像素具有相同的标签时，处罚为0。B＜p，q＞定义如下：

σ看作是图像的噪声，Ip和Iq表示像素p、q的强度值，‖p－q‖是像素p与q的欧式距离。Yuri Boykov和Vladimir Kolmogorov［17］发现能量函数的极小值可以通过最大流最小割计算，把能量最小问题转化为图割问题。

根据能量优化的观点求解最小图割，是目前图割的主要求解方法。该方法需要根据图像的特征信息，建立合适的能量函数，然后根据能量函数，建立图论中的网络图，通过对网络图采用最大流/最小割算法，获得分割结果。从理论上讲，基于图割的能量函数最小化方法，可以提供能量函数的全局最小化。因此对特定领域里一些有争议的问题，可利用基于图割的能量最小化方法，得到准确的解决方式，以期得到更好的分割结果。

3 图割算法分类

在本节中，我们将图割基础技术分为三类：第一类是基于加速的图割，旨在改善以图割为基础的方法的速度；第二类是基于交互式的图割，将用户的交互融入到分割中，从而改善分割结果；第三类是基于形状先验的图割，将目标之前的形状纳入考虑范围，使分割更为合理。

3.1 基于加速的图割

按照惯例，图像中每个像素都被看作是图的一个节点，随着图像分辨率的增加，图像越来越大，导致图形的计算加大，速度变慢。为了加快图割算法的计算，人们研究相应的方法。V.Vineet和P.J.Narayanan［18］建议应用基于CUDA分割的GPU硬件加速，相对于串行计算，该方法采用具有良好性能的并行计算达到加速目的，但效果不是很好。另外一种常用的方法是在图的重建过程中减少图的节点。在大多数情况下，目标比较集中，只占据图像的一个小区域，由此可以只考虑分割覆盖目标的相对较小的一部分，使图像像素减少，节点也相应减少，该部分可以由用户输入或通过一些匹配算法进行［15］。此外，当两个相邻像素强度非常相似时，在图中的权重也非常大，这意味着这两个像素不会分开，换句话说，可以把这两个像素看作是一个像素，以此类推。这种由许多相似的像素点组合在一起，将它们作为一个整体来替代原有像素点，这个整体称之为超像素，这是集群的一种应用方法。生成超像素的算法主要分为两类：基于图论的方法和基于梯度上升的方法。基于图论的分割方法的本质就是移除特定的边，将图划分为若干子图从而实现分割；基于梯度上升的分割方法是指先获得一个不精确的粗略聚类，在后面每一次的迭代过程中，利用梯度上升的方法去改进在上一次迭代的聚类结果，直到最后收敛为止。在图割中生成超像素最常用的算法是分水岭方法［17］。在分水岭算法的基础上，把相似强度的小区域归为一个集群，把这些集群作为图割新图的点，分水岭的计算过程是一个迭代标注过程。该水域重新分割后，每个集群的平均强度作为新的像素点值（超点）。因此，t－links的权重可以通过比较超点与目标背景直方图的强度值来设置，与（4）（5）类似，而n－links的权重可以通过下面的等式计算［17］：

其中，gradij（i）是集群i平均梯度值，j是其相邻集群。此外，还可以将两种方法结合，也即分水岭不需要在整个图像，只需要在图像的某些部分应用就可以了。在文献［15］中，只有边界附近区域是基于分水岭的图割；马秀丽等［17］基于分水岭算法都使图的顶点数大大减少，取得了较好的实时性。分水岭算法的优点是可获得微弱边缘的良好响应，精度较好速度快，可以保证封闭连续边缘。但是由于图像噪声及细节信息等影响，该算法常常会产生过分割的现象。基于加速的图割特别是基于分水岭的图割广泛应用于医疗影像、工业图像、自然图像等不同种类［18－20］。

3.2 基于交互式的图割

对大多数图像而言，完全自动分割是很困难的，特别是对目标精度要求比较高的图像，进行交互式分割是不可避免的。基于交互式的图割首先选择简单的区域或者单一的种子节点，其次是迭代的种子节点。在［15］里，使用边界框选定目标区域，边界外部区域看作背景，边界框的中心当作目标。在［13］中，迭代的交互式图割得到了应用。当结果不完美时，更多的种子节点被添加，直到分割到满意的目标。迭代交互式分割在目标的周边有较好的鲁棒性。通常，交互式分割的图形权重可以从表1得到，图表示为G＝＜V，E＞，其中V＝P∪｛S，T｝［13］。

当一点分为目标，这点与S节点的权重就比较高，而与T节点的权重则为0，若该点为背景，则相反。在迭代的交互式分割中，边的权重会动态改变，一轮图割过后，一些新的点选定为目标或背景，权重会按上表的方式更新，而后图割再次运行。新选定的节点权重如表2所示。

表1 交互式分割图形权重表

表2 迭代后图形权重表

当新的点选为目标或背景，新的权重不会改变先前的最优分割，这意味着可以用基于先前的最大流获得最优分割，这种方法用在大部分的交互式迭代算法中，但是分割效率不是很好。

3.3 基于形状先验的图割

由于噪声或目标被遮挡、污染，边缘扩散等影响，传统的图割仅仅考虑区域和边缘的信息，不容易得到理想的分割结果，基于交互式的图割可以适当减少这类程度的问题，但影响分割效率。此时要想得到更好的分割结果，一个比较好的办法是在分割过程中融入形状先验知识。如何将形状先验信息转化为能量函数，从而提高分割效果，许多研究者做了大量工作。Slabaugh［21］等提出了一种基于椭圆形状与图割的分割技术，该方法用椭圆表示形状先验，并将其添加到能量函数的区域项中，对含有噪声、遮挡物的图像有较好的分割结果，但对高度不同的图像具有很大限制。Nhat Vu［22］等定义了离散形状的形状先验，并将其通过边缘权值合并到图中，该方法的形状模板比较单一，对和形状模板有差异的目标无法得到较好的分割效果。Veksler［23］采用星形先验信息，没有局限于具体形状，可部分解决多目标问题，但不能区分目标。Wang［24］等提出了自适应形状先验方法，主要思想是目标的边缘信息越少，越需要更强的形状先验信息，但该方法只适用于灰度图像等。在大多数情况下，将形状先验项添加到能量函数中，通常定义如下方程：

Eshape是形状先验项，目的是使目标边界的像素变小而远离目标边界的像素变大。有两种能量形式表示形状先验，第一是选择逼近目标的中心点像素为参考点，设置该点像素值较高而其他点的值根据该像素点与中心像素点的距离逐步变小，在目标内部点的像素值较高在背景区域值较低。由于目标中心值比模板其他位置相对较大，可将该模板的值与区域项结合。因此（10）式可改变如下：

另一种先验信息能量形式也是采用距离比较，但设置目标边界区域的值为零，靠近目标边界区域的值比较小，而其他值比较大，这种形状信息的能量被纳入到边界项中，表示如下：

因此，形状模板的建立是很重要的，许多预分割目标采用训练集来建立形状先验模板。此外，训练集的排列也将影响模板与图像的匹配，进而得到改进的能量模型。

4 总结与展望

在文中，简要介绍了图像分割方法与图割的优势，还详细介绍了图割的概念，而后将基于图割的众多分割方法分为三类：基于加速的图割、基于交互式的图割和基于形状先验的图割。这种分类有助于研究者理清研究方向，而且这些图割方法往往相互组合应用以提高分割效果。

图像分割是计算机视觉研究中的一个难以解决的问题。国内外学者进行了广泛而深入的研究，提出了各种分割方法，但至今尚无比较完整的理论体系，没有普遍的适用性。基于图割的图像分割，是目前图像分割领域一个新的研究热点，因其具有独特的优势，得到了很多研究者的青睐。然而这一种新的图像分割方式，还有大量问题有待研究和解决，例如如何克服现有图割方法的不足、如何扩展图割方法的应用范围以及如何将其他一些经典方法融入图割当中等。与此同时，将多种图割方法综合运用，得到具有较强适应性和快速高效的分割方法也是今后的一个研究重点。总而言之，图像分割方法正朝着更快速、更精确的方向发展，将不断完善图像分割的理论体系，取得新的突破和创新。

［1］ Gonzalez R C，Woods R E.Digital Imaging Processing［M］.Prentice Hall：New York，NY，USA，2002.

［2］ Bernsen J.Dynamic thresholding of gray—level images［J］.InProc 81CPR，1986：1251－1255.

［3］ SBoukaharouba，JM Rebordao，R L Wendel.An amplitude segmentation method based on the distribution of an image.Computer Vision［J］.Graphics and Image Processing，1985，29：47－59.

［4］ Chow C K，Kaneko.Automatic boundary detection of left ventricle from cineangiograms［J］.Compat Biomed Res，1972（5）：388－410.

［5］ Nobuyuki Otsu.A threshold selection method from gray level histogram［J］.IEEE Trans on System，Man and Cybemetics，1979，9（1）：62－66.

［6］ Pal S K，King R A，Hashim A.A Automatic grey level thresholding through index of fuzziness and entropy［J］.Patt ern Recognit ion Letters，1983，1（3）：141－146.

［7］ Kapur JN，Sahoo P K，Wong A K C.A new method for gray level picture thresholding using the entropy of the histogram［J］.Computer Vision，Graphics and Image Processing，1985，29（3）：273－285.

［8］ S Raut，M Raghuvanshi，R Dharaskar，A Raut.Image Segmentation－A State－of－Art Survey for Prediction［J］.ICACC，2009：420－424.

［9］ S Naz，H Majeed，H Irshad.Image segmentation using fuzzy clustering：A survey［J］.International conference on emerging technologies，2010：181－186.

［10］ A X Falcao，J K Udupa，F K Miyazawa.An ultra－fast user－steered image segmentation paradigm：live wire on the fly［J］.IEEE trans on Medical Imaging，2002，19（1）：55－62.

［11］ G Sundaramoorthi，A Yezzi，A C Mennucci.Coarseto－Fine Segmentation and Tracking Using Sobolev Active Contours［J］.IEEE trans on Pattern Analysis and Machine Intelligence，2008，30（5）：851－864.

［12］ R M Willett，R D Nowak.Minimax Optimal Level－Set Estimation［J］.IEEE trans on Image Processing，2007，16（12）：2965－2979.

［13］ Y B Yuri，G F Lea.Graph Cuts and Efficient N－D Image Segmentation［J］.Intenational Journal of Computer Vision，2006，70（2）：109－131.

［14］ Ford L，Fulkerson D.Flow s in Netw or ks［M］.New Jersey.Princeton Univer sity Press，1962.

［15］ Y Boykov，V Kolmogorov.An experimental comparison of mincut/max－flow algorrithms for energyminimization in vision［J］.IEEE trans on PAMI，2004，26（9）：1124－1137.

［16］ V Vineet，P J Narayanan.CUDA cuts：Fast graph cuts on the GPU［C］.IEEE conference on CVPRW，2008：1－8.

［17］ 马秀丽，焦李成.基于分水岭－谱聚类的SAR图像分割［J］.红外与毫米波学报，2008，27（6）：452－456.

［18］ Z Yu，M Xu，Z Gao.Biomedical image segmentation via constrained graph cuts and presegmentation［C］.International conference of the IEEE on EMBC，2011：5714－5717.

［19］ XWu，W Xu，L Li，G Shao，JZhang.An Interactive Segmentation Method Using Graph Cuts for Mamographic Masses［C］.International conference on iCBBE，2011：1－4.

［20］ X Wu，Y Wang.Interactive Forreground/Background Segmentation Based on Graph Cut［C］.Congress on Image and Signal processing，2008：692－696.

［21］ Slabaugh G，Unal G.inInt.Graph cuts segmentation using an elliptical shape prior［C］.inIntConf.on Image Processing，2005：1222－1225.

［22］ Nhat V，Manjunath B.Shape prior segmentation ofmuttiple objects with graph cuts［C］.In proc.IEEE conference on computer vision and pattern recognition，2008：1－8.

［23］ Veksler O.Star shape prior for graph－cut image segmentation［J］.Procedings of the 10th European Conference on Com puter Vision［C］.Mar seille，France：Springer，2008：454－467.

［24］ Wang H，Zhang H.Adaptive shape prior in graph cut image segmentation［J］.Pattern Recognition，2012（11）：1－6.

A Survey on Graph Cut Techniques

Lin Qiang，Dong Ping，Lin Jiayu
（School of Electronic Science and Engineer，National University Defense Technology，Changsha 410073，China）

The image segmentationmethods and the research progress of graph cut in recent years are introduced in this paper.At first，image segmentation methods are classified into five typical types，and their characteristics are analyzed.Secondly，the concept of graph cut and three categories of graph cut，and applications and characteristics of each category are described in details.Finally，some directions of graph cut is presented.

Graph cut；Interactive；Energy function；Watershed

10.3969/j.issn.1002－2279.2015.01.011

TP391

A

1002－2279（2015）01－0035－05

林强（1982－），男，福建福州人，工程硕士，主研方向：图形图像处理。

2014－08－11