基于图论的分割算法研究综述*

陈　杏　李　军

(1.西安工业大学电子信息工程学院　西安　710021)(2.西安工业大学计算机科学与工程学院　西安　710021)



基于图论的分割算法研究综述*

陈杏1李军2

(1.西安工业大学电子信息工程学院西安710021)(2.西安工业大学计算机科学与工程学院西安710021)

图像分割是计算机视觉领域中的经典问题之一,基于图论的分割算法因其良好的时间性能与分割效果成为众研究者新的关注点。论文在对图像分割算法综述的基础上,重点介绍了基于图论的分割算法并且通过实际仿真分别从时间性能与分割效果上对Grab Cut与One Cut算法进行了比较。最后对当前该领域存在的问题与发展方向进行了总结。

图像分割; 能量优化; 迭代最小化; 最优二元分割

Class NumberTP391.41

1　引言

所谓图像分割指的是根据灰度、颜色、纹理和形状等特征把图像划分成若干互不交迭的区域,并使这些特征在同一区域内呈现出相似性,而在不同区域间呈现出明显的差异性[1]。图像分割不仅是由图像处理到图像分析的关键步骤,而且是计算机视觉的一种基本技术。若想实现目标特征提取与参数测量,图像分割是其必须经历的步骤,也使得更深层次的图像分析和理解成为可能。针对图像分割领域的研究已经出现了很多算法,但是近些年来,基于图论的图像分割已经成为该领域研究的热点与方向。基于图论的图像分割算法将图像分割映射为加权图的形式,其像素及其颜色、灰度等特征信息分别代表图中的顶点及其属性,像素之间的邻接关系对应于图的边集,边的权重显示出对应像素的差异度。

图像处理技术不仅在诸多领域扮演着举足轻重地角色,而且图像分割是图像进行处理的键环节之一及基于图论的图像分割理论的前沿性,使针对该类图像分割技术的研究具有较大的价值与应用前景。

2　图像分割方法概述

针对图像分割技术的研究已经经历了很长时间,伴随着计算机技术与机器视觉的不断发展,图像处理技术越来越受到国内外研究者及各行各业的重视。其中,针对图像分割领域中的算法研究也是层出不穷,但至今仍然找不到一个适用于所有类型图像的分割方法,而对于图像分割算法的依据也是不唯一。本节将对当前主流的图像分割算法的进行归纳与总结,如图1所示为图像分割算法分类示意图。

图1　图像分割算法分类示意图

2.1基于阈值的分割算法

基于阈值的分割[2～4]是通过单个或多个阈值将图像的灰度直方图分成几类,认为图像中灰度值在同一灰度级别的像素属于同一物体。阈值分割法先确定适当的分割阈值,然后将图像中所有像素的灰度级与该阈值进行比较,从而可对区域进行划分,达到图像分割的目的。基于阈值的分割算法主要分为三种：基于点、区域的全局及局部与多阈值方法。

2.2基于边缘的分割算法

基于边缘的图像分割[5～7]是基于目标对象的边缘灰度变化较大的特点,利用边缘检测的方法将目标对象所属区域进行提取的分割方法。由于该方法是利用图像区域间的不同性质对区域进行划分处理,通常不仅会产生目标对象边缘的断点现象,而且可能产生错误的边缘。按照处理顺序可以将边缘分割技术分为串行与并行边缘检测。

2.3基于区域的分割算法[8]

基于区域的分割算法是按照相似性准则对图像进行划分,其方法可归纳为区域生长法、分裂合并法等几种类型。

1) 区域生长法

区域生长法是根据同一物体区域内像素的相似性对像素进行聚集的方法,从初始区域开始,将相同属性的相邻像素或区域归并于当前区域从而达到区域逐步扩散的目的,直至该图像中不存在可以进行归并的像素点或区域。

2) 分裂合并法

分裂合并法首先将图像分成若干互不相交的区域,然后按照相关规则对区域进行分裂或合并从而实现分割目的,该方法适用于灰度图像与纹理图像分割。

2.4基于图论的分割算法

基于图论的分割算法将图的最小割问题应用于图像分割领域。该算法首先将图像映射为带权无向图G=〈V,E〉,图中每个节点N∈V对应于图像中的每个像素,每条边∈E连接着一对相邻的像素,边的权值表示了相邻像素之间非负相似度(灰度、颜色或纹理)。对图像一个分割S相当于一次剪切处理,每个被分割的区域C∈S与图中一个子图相对应。基于图论的分割方法的实质是移除特定的边,将图划分为若干子图从而达到分割的目的。目前所了解基于图论的方法有Graph Cut、Grab Cut和One Cut等。

2.5基于能量泛函的分割算法

基于能量泛函的分割算法是指活动轮廓模型(Active Contour Model)及在其基础上衍生出的相关算法,其基本思想是将目标对象的边缘用连续曲线进行表达,并定义一个能量泛函使得其自变量包括边缘曲线,因此分割过程就转变为求解能量泛函的最小值过程。按照模型中曲线表达形式的不同,活动轮廓模型可以分为两大类：参数活动轮廓模型(Parametric Active Contour model)和几何活动轮廓模型(Geometric Active Contour Model)。

3　基于图论的分割算法

在上文针对图像分割算法分类介绍的基础,本节就基于图论的分割算法展开详细的介绍。依据其算法发展的历程,分别就Graph Cut、Grab Cut与One Cut算法原理进行深层次地理解与探讨。

3.1Graph Cut算法[9]

在图像处理与机器视觉中,很多问题最后都是汇聚于解决一个最小化能量函数的问题。由于该问题需要在一个相当高维数空间求解一个非凸函数的最小化,以致在此问题的最优化上显的较为困难。Graph Cuts方法可对一类具有某种特定形式的能量函数得到快速而有效地最优解,导致该方法受到越来越多的关注。20世纪90年代末Boykov等将该技术应用于图像分割领域,并提出了该算法。

3.1.1S-T图像映射结构

首先用一个无向图G=〈V,E〉表示要分割的图像,V和E分别是顶点(vertex)和边(edge)的集合。如图2所示为图像转换成图结构后对应的S-T图,图中每个顶点对应于图像中每个像素,在此基础上还另外增加了顶点S与T。S-T图中存在两种类型的边,实线表示两个邻域顶点相连形成的边(n-links),虚线表示每个顶点与S和T相连形成的边(t-links)。在前后景分割中,S一般表示前景目标,T一般表示背景。若边集合中的所有边断开将会导致“S”与“T”图的分开,故将其称为“割”。若一个割的过程中其对应边的所有权值之和最小,就将其称为最小割。

图2　S-T图

3.1.2最小割S-T图

由Boykov和Kolmogorov发明的最大流(Max-Flow)/最小割(Min-Cut)算法可以达到S-T图的最小割目的。最小割可以将图的顶点划分为两个没有交集的集合S与T,其中s∈S,t∈T和S∪T=V。此时S与T分别代表了前景和背景的像素集,同时意味着图像分割过程的结束。

假设整幅图像的标签label为L= {l1,l2,…,lp},其中li为0(背景)或者1(目标)。那假设图像的分割为L时,图像的能量可以表示为

E(L)=aR(L)+B(L)

R(L)为区域项,B(L)为边界项。a为区域项与边界项之间的影响因子,决定了二者对能量的影响程度。E(L)为能量函数,图割的目标就是优化该能量函数并使其值最小化。区域项(t-links)中边的权值计算公式为

Rp(lp)能量项的权重可以通过将像素p的灰度与给定目标和背景的灰度直方图进行比较而获得,即像素p属于标签lp的概率,所以t-links的权值如下：

Rp(1)=-lnPr(lp|′obj′)

Rp(0)=-lnPr(lp|′bkg′)

边界项：n-links中每条边权值如下：

其中

p和q为相邻像素,边界项体现分割L的边界属性,B〈p,q〉表示像素p与q之间不连续的程度。

在确定了每条边的权重后,可以通过mincut算法对图像进行最小割处理,这些边的断开既实现了对目标与背景的分离,又实现了能量的最小化。

3.2GrabCut算法[10]

GrabCut算法是在GraphCut算法的基础上进行改进而产生的一种新的图像分割算法。该算法利用图像中的纹理与边界信息,只需用户少量的交互操作就可以得到较为满意的分割结果。若目标与背景之间的色差较大将会影响分割的效果。

GrabCut在GraphCut算法的基础上做出的改进工作可以归纳为以下几点：

1)GraphCut中目标与背景的模型采用灰度直方图,而GrabCut将其改为RGB三通道的混合高斯模型(GMM);

2)GraphCut中能量最小化是一次性达到,而GrabCut采用交互迭代的方式对其进行分割估计与模型参数的学习;

3)GraphCut需要用户指定目标与背景的一些种子像素点,而GrabCut只需提供背景区域的像素集。若需要分割的结果更加精确,可以在初次分割的基础上提供一些确定的种子像素点,在运行该算法即可。

3.2.1颜色空间模型

GrabCut对图像采用RGB颜色空间,分别用一个k割高斯分量的全协方差混合高斯模型(GMM)对目标及背景进行模型的建立。在该过程中衍生出向量K= {k1,…,kn,…,kN},其中kn是第n个像素对应的高斯分量,kn∈{1,…,K},则可以将整个图像的Gibbs能量定义为

结合高斯模型,其中U的定义为

参数β由图像对比度决定,如果图像对比度较低,像素m和n的差‖zm-zn‖比较小,此时需乘一个较大的β放大这种差别;如果图像对比度较高,像素m和n的差‖zm-zn‖比较大,那么此时需乘以一个较小的β缩小这种差别。这样就使得V项在对比度高或低的情况下均可正常工作,此时可以对该图进行分割操作了。

3.2.2初始化

迭代能量最小化分割算法的初始化过程如下:

1) 通过用户框选目标来得到初始的trimapT,可将框外像素视为背景像素TB,而框内像素TU可视为目标的可能像素;

2) 初始化TB内的每一像素n的标签αn=0;初始化TU内的每个像素n的标签αn=1;

3) 经过上述过程,可以得到目标与背景的一些像素。通过这些像素可进行目标和背景GMM的估计。首先通过k-mean算法将目标和背景的像素聚类为K类,其次通过RGB值估计参数均值和协方差,最后通过该高斯分量中的像素数目与像素总数的比值确定高斯分量的权值。

3.2.3迭代最小化

迭代最小化的算法过程如下:

4) 重复1)和3),直至收敛;

5) 采用bordermatting对分割的边界进行平滑等等后期处理。

3.3OneCut算法[11]

Tang等在GrabCut算法的基础上提出了OneCut图像分割算法,GrabCut算法通过迭代的图切割来达到预期的图像分割目的,而OneCut算法是通过一次图切割便可以得到预期的结果,并在时间和分割效果上均优于GrabCut算法。

OneCut算法使用快速全局最优二元分割技术,明确了最小化目标、背景颜色分布之间的表观重叠,其一次图切割最小化能量函数表达式如下：

其中,R⊆Ω表示包围盒对应的二元码,S⊆Ω是一个分割段,ls={sp|p∈Ω}是S⊆Ω的特征函数。第一项与第二项分别表示包围盒R的一个标准膨胀与表观重叠惩罚项;最后一项是对比敏感平滑项,其展开式为

|∂S|=∑wpq|sp-sq|

Nn指n(I)元素个数,n(I)的值表示图像I中相邻像素对集合

β′是一个全局参数,经实验得出β′=0.9,λ=9。

用户根据特定图像提供一个其感兴趣的目标矩形包围盒,矩形包围盒外面的像素使用硬性约束分配为背景,又可以将分割能量函数简化为以下形式：

由于One Cut算法对矩形框比较敏感,则需要用户绘制的矩形框要完全覆盖目标,并且尽可能小。该方法使用了少量的辅助节点实现了高效率的图像分割,与Grab Cut算法相比,对于复杂图像来说该算法依然具备很好的分割效果与时间性能。

4　实验结果与分析

通过前面针对图论的图像分割算法的详细介绍,本节就Grab Cut与One Cut图像分割算法进行分割效果与算法性能的分析。

4.1Grab Cut与One Cut实验结果

在充分理解Grab Cut与One Cut的算法原理基础上,分别对这两个分割算法做了分割效果的实验,其图像分割结果分别如图3、4所示。

图3　Grab Cut图像分割结果

图4　One Cut图像分割结果

由图3,4比较可知,虽然从分割结果上来说,它们均达到了较好的效果,但是从交互方式上来看,One Cut算法更具优势。

4.2Grab Cut与One Cut时间性能分析

本文针对Grab Cut与One Cut时间性能做了具体而实际地分析工作,它们的时间性能情况如图5中所示。

针对One Cut每一次分割过程中,取其时间消耗值,样本数为10。通过对Grab Cut递增其迭代次数得到其时间消耗值,迭代次数由1逐渐增至10。由图中可知,Grab Cut随着迭代次数的增加,其时间消耗越大;One Cut各个样本的时间变化不大,时间消耗始终在100ms上下浮动。

图5　Grab Cut与One Cut算法时间性能对比图

通过实验与分析可知,在相同分割效果的前提下,One Cut在交互及时间性能上均是优于Grab Cut图像分割算法。

5　结语

本文在描述图像分割算法的基础上,重点针对基于图论的分割算法进行算法原理进行详细阐述,并对Grab Cut与One Cut算法进行分割效果及时间性能上的实验分析。虽然在分割效果上满足要求,但是由于分割过程中对交互的依赖性过大,达不到图像分割的自动化与实时性的目标,而且在该类方法是基于图像像素为对象展开方法的研究工作,若图像中像素过多将会导致计算量过大。所以在保证分割效果的前提下,算法效率的提高将是图像分割算法在未来的发展过程中很长时间内亟待解决的课题。

[1] Abadi D J, Carney D, Cetintemel U, et al. Aurora:A New Model and Architecture for Data Stream Management[J]. VLDB Journal,2003,12(2):120-139.

[2] Noma A, Graciano A B V, Consularo L, et al. A new algorithm for interactive structural image segmentation[J]. The Computing Research Repository,2008(1):4-6.

[3] 武红玉.阈值分割算法在图像处理中的应用[J].科技信息,2012(27):201-202.

WU Yuhong. Application of threshold segmentation algorithm in image processing[J]. Science and Technology Information,2012(27):201-202.

[4] Han S Q, Wang L. The review of threshold methods in image segmentation[J]. System Engineering and Electronics,2002,4(6):91-102.

[5] Mortensen E. Interactive segmentation with intelligent scissors[J]. Graphical Models and Image Processing,1998,60(5):349-384.

[6] Falcao A X, Udupa J K, Miyazawa F K. An ultra-fast user-steered image segmentation paradigm: livewire on the fly[J]. IEEE Transaction on Medical Imaging,2000,19(1):55-62.

[7] De Miranda P A V, Falcāo A X, Udupa J K. Synergistic arc-weight estimation for interactive image segmentation using graphs[J]. Computer Vision and Image Understanding,2010,114(1):85-99.

[8] 舒添慧,胥布工,胡战虎.基于区域生长法的医学图像分割[J].微计算机信息,2008,24(6-3):284-285.

SHU Tianhui, XU Bugong, HU Zhanhu. Medical image segmentation based on region growing method[J]. Microcomputer information,2008,24(6-3):284-285.

[9] Yuri Boykov M. P. Jolly. Interactive graph cuts for optimal boundary region Segmentation of objects in N-D images[C]//Proceedings of ICCV,2001:106-110.

[10] Carsten Rother, Vladimir Kologorov, Andrew Blake. “GrabCut”—Interactive foreground extraction using iterated graph cuts[J]. In ACM Transactions on Graphics (SIGGRAPH),August 2004:3-10.

[11] TANG M, GORELICK L, VEKSLER O, et al. GrabCut in One Cut[C]//International Conference on Computer Vision, Sydney: IEEE,2013:1769-1776.

Summary of Segmentation Algorithm Based on Graph Theory

CHEN Xing1LI Jun2

(1.School of Electronic Information Engineering, Xi’an Technological University, Xi’an710021) (2.School of Computer Science and Engineering, Xi’an Technological University, Xi’an710021)

In the field of computer vision,image segmentation is one of the classical problems. Because of its good time performance and segmentation results,the segmentation algorithm based on graph theory has become a new focus for the researchers. On the basis of the summary of image segmentation algorithm,this paper focuses on the segmentation algorithm based on graph theory and compares the Grab Cut and One Cut algorithms from the time performance and the segmentation results. Finally,the existing problems and the development direction of this field are summarized.

image segmentation, energy optimization, iterative minimization, optimal two partition

2016年4月8日,

2016年5月28日

陈杏,女,硕士研究生,研究方向：计算机视觉。李军,男,硕士研究生,研究方向：智能计算与机器视觉。

TP391.41

10.3969/j.issn.1672-9722.2016.10.038