基于图论的图像分割方法关键技术研究

叶　青　胡昌标

(1.怀化学院计算机科学与工程学院　怀化　418008)(2.武陵山片区生态农业智能控制技术湖南省重点实验室　怀化　418008)



基于图论的图像分割方法关键技术研究

叶青1,2胡昌标1,2

(1.怀化学院计算机科学与工程学院怀化418008)(2.武陵山片区生态农业智能控制技术湖南省重点实验室怀化418008)

对基于图论的图像分割方法进行了相应的研究,针对传统分割方法不能通过算法自动实现对图像的分割,以及图像分割的质量与数据模型的建立有较大的联系,提出一种改进的基于图切割的自动分割算法,自动提取目标点和背景点,建立能量函数和网络图,实现图像的自动分割。实验表明,改进算法能够更有效地从背景中把目标物体分割出来。

图像分割; 图切割; SLIC算法; 能量函数; 图论

Class NumberTP391.41

1　引言

一幅图像通常是由很多不同类型的区域组成的,比如物体的目标和背景等。在图像分析中,往往关注的是图像中的某些目标,它们对应图像中的具有某种特定性质的区域。图像分割就是按照一定的规则将图像分成有意义的若干连通区域,并且提取感兴趣目标区域的技术和过程。图像分割是计算机视觉领域中的核心问题,是由图像处理过渡到图像分析的关键步骤,为使图像理解成为可能,必须通过图像分割、目标提取和特征抽取,将原始图像转换为更抽象的形式。

图像分割方法[1]主要分为以下几类:基于阈值的分割方法[2]、基于边缘检测的分割方法[3]、基于区域的分割方法[4～5]、基于能量泛函的分割方法以及基于特定理论的分割方法[6～7]等。近年来,研究人员不断改进原有的图像分割方法,把其它学科领域的一些新理论和新方法用于图像分割,提出了不少新的分割方法[8]。其中基于图论理论的图像分割方法[9]受到人们的关注。将图像分割算法与图论理论相结合,图论理论能够充分考虑图像像素之间的空间位置关系,可以兼顾边界和区域两方面的信息,能达到更好的图像分割效果。研究者提出了最小生成树分割算法[10],以及将图的图割理论[11]和频谱理论[12]运用到图像分割领域的算法等。

2　图像分割相关技术

2.1基于图论的图像分割相关技术理论

基于图论的图像分割技术的基本框架,就是将图像分割问题转换为基于图论中的网络图,将图像映射为网络图,将图像分割问题转化为对网络图的分割操作,实现对图像的分割。

Boykov等[13]提出了一种基于图切割的交互式图像分割方法。Graph cut是一种能量优化算法,把图像分割问题与图的最小割(min cut)问题相关联。将一幅图像视为一个带权的无向图G=(V,E),V为顶点的集合,每个像素对应图中的一个相应顶点,另外还有两个特殊顶点s(source:源点)和t(sink:汇点),称为终端顶点;E为连接顶点的边的集合,E中有两种边,图像中每两个邻域像素连接构成一条边,这种边叫n-links,每个普通顶点都必须与源点S及汇点T相连接,构成第二种边,这种边叫t-links。

图1　一个图像对应的s-t图

图1中,每个像素对应图中的一个相应顶点,另外还有S和T两个顶点。图中边n-links是每两个邻域普通顶点连接的实线边,边t-links是每个普通顶点与s和t连接的虚线边。

图像分割可以看成像素标记问题,假设图像的分割为L,整幅图像的标签标记为L=(l1,l2,…,lp),其中li为0(背景)或者1(目标),图像的能量可以表示为

E(L)=R(L)+λB(L)

(1)

其中,E(L)表示权值,即能量函数,R(L)为数据项,B(L)为光滑项,而k是决定数据项及光滑项对能量函数影响大小的因子。

数据项:

R(L)=∑p∈PRp(lp)

(2)

其中Rp(lp)表示为像素p分配标签lp的代价,为像素p分配其概率最大的标签lp时,能量最小,取概率的负对数值,边t-link的权值设定如下:

Rp(1)=-lnPr(Ip|’目标’);

Rp(0)=-lnPr(Ip|’背景’)

(3)

光滑项主要反映分割L的边界属性,设p和q为邻域像素,如果两邻域像素的差别很大,那么这两个像素很有可能处于目标和背景的边缘部分,如果两邻域像素差别很小,那么它们属于同一个目标或背景区域的可能性就较大。

光滑项:

B(L)=∑{p,q}B(p,q)*δ(lp,lq)

(4)

(5)

每两个邻域普通顶点连接的边,即边n-links上的权值设置为边界光滑项B(L)。每个普通顶点与s连接的边的权值由Rp(1)来决定,与t连接的边的权值由Rp(0)来决定,所有边的权值就确定了,这样就构建了一个基于能量函数的网络图。

一个图割cut就是图中边的集合E的一个子集C,那这个割的权值就是边子集C的所有边的权值的总和。权值之和最小的割,就称为最小割min cut。Ford和Fulkerson[14]证明了著名的最大流最小切割定理,即在任何网络中,网路的最大流max flow与最小割min cut相等,最大流的值等于最小切割的容量,并给出了求解的具体算法。解决最大流问题常用到Ford-Fulkerson方法[14]、Edmonds-Karp算法、Push-Relabel算法[15]等。使用这些求解最大流/最小切割的方法就可以获得s-t图的最小割min cut。这个min cut就是权值和最小的边的集合,这些边的断开恰好可以使目标和背景被分割开,即完成了图像分割,也就是min cut对应于能量的最小化。2004年在Boykov工作的基础上,Rother[16]提出了Grab cut算法,该算法通过建立高斯混合模型,进行GMM模型参数学习和分割估计的交互迭代来实现能量函数最小化。

2.2SLIC(simple linear iterative cluster)算法[17～18]

SLIC算法将图像颜色空间设置为CIELab颜色空间,对应每个像素的颜色分量[L,a,b]和坐标分量[x,y]组成一个五维向量[L,a,b,x,y],通过计算像素点在色彩上的相似度和空间位置的接近程度来完成图像像素的局部聚类。算法接受一个参数K,用于指定生成的超像素数目。设原图有N个像素,则分割后每块超像素有N/K个像素,每块超像素的边长大致为S=[N/K]^0.5,开始时每隔S个像素生成一个种子点,在以这个种子点为中心的2S*2S的周围范围进行搜索距离该种子点最近的若干像素,标记为与种子点一类,直到所有像素点都标记完毕。然后计算这K个超像素里所有像素点的平均向量值,重新得到K个种子点,重复上述计算过程,直到算法收敛。

设超像素中心为:Ck=[lk,ak,bk,xk,yk]，k∈[1,K],像素的相似度计算方法为:计算每个像素点与最近的种子点之间的相似度,赋给该像素最相似种子点的标记。

向量距离的相似度计算如下:

(6)

(7)

ds=dlab+(m/s)*dxy

(8)

其中dlab和dxy分别是色彩距离和空间距离,ds是dlab和dxy归一化后的和,m用来调整dxy的权值,一般设为1～20,在算法中设置为12。为了避免所选的种子点处于图像的边缘位置,或者可能是噪声点,算法将聚类中心移至3*3领域的梯度最小处。采用SLIC算法对图像进行预处理,能够产生高质量的超像素小区域,运算速度快,算法简便。

3　一种改进的基于图切割的自动分割算法

Grabcut是目前基于图切割进行交互式图像分割中最好的一种方法,但存在的不足是不能通过算法自动实现对图像的分割,并且图像分割的质量与数据模型的建立、种子点的选取有较大的关系。基于图切割对图像进行自动分割,关键问题是如何根据图像分割的要求自动提取目标点和背景点,建立能量函数中的数据项和光滑项。在能量函数的计算中,不仅要考虑图像的区域信息,同时还要考虑图像的边缘信息,这样才能提高图像分割的质量。

3.1算法的基本思想

1) 预处理待分割图像。针对传统基于图论的分割算法在初始化时以每个像素作为一类,图中的一个点与其他所有的点都需要建立边的连接,造成图的结构过于复杂而且增加了计算复杂度的缺点,本算法采用SLIC算法对待分割图像进行预分割,使用分割后产生的超像素小区域来代替像素,计算超像素小区域中的灰度均值来代替原先的像素的灰度值。这样构建的图的节点数将大大降低,提高分割的运行效率。

2) 自动提取目标点和背景点。采用SLIC算法,在K值设置为2的情况下,可以将待分割的图像划分成两个超像素区域,分别称为目标区域和背景区域。目标区域即图切割中的源点s,背景区域即图切割中的汇点t。

3) 数据项的自动计算。分割目的就是将图像中所有的像素划分成目标区域和背景区域;数据项设置为超像素归属这两个区域的代价,根据每个超像素与目标区域和背景区域内每个像素的相似性之和计算像素的数据代价。

4) 光滑项的自动计算。根据图像的边缘信息和空间位置关系建立光滑项,将光滑项定义为拉普拉斯零阶算子,通过拉普拉斯零阶算子进行边缘检测得到代价的大小。

3.2算法描述

Step1:初始化。对待分割图像进行滤波处理,滤波后的图像记为Im;将滤波后的图像进行颜色空间转换,转换为CIELab颜色空间,转换后的图像记为Ic;将颜色转换后的图像进行预分割,采用SLIC算法对图像Ic进行预分割,使用分割后产生的超像素小区域来代替像素,计算超像素小区域中的灰度均值来替代像素的灰度值。预分割后的图像记为Ib;同时,用K值为2的SLIC算法对图像Ib进行块划分,得到的图像记为Ia,图像Ia被划分成两个较大的区域,分别当作目标区域和背景区域。分别计算目标区域和背景区域的中心点,作为源点S和汇点T。

Step2:将预分割后得到的基于超像素的图像Ib转换为一个带权的无向图G=(V,E),V为顶点超像素的集合,每个超像素对应图中的一个相应顶点。另外还有Step1计算得到的两个特殊顶点源点S和汇点T;E为连接顶点的边的集合,图像中每两个相邻顶点连接构成n-links连接,每个普通顶点都必须与源点S及汇点T相连接,构成t-links连接。

Step3:分别计算预分割后得到的图像Ib中每个超像素与块划分后得到的图像Ia中目标区域和背景区域中每个超像素的相似性之和,并将它们作为数据项中的R(L)。

Step4:根据图像的边缘信息和空间位置关系,本算法通过拉普拉斯零阶算子进行边缘检测建立光滑项B(L)。

Step5:根据公式E(L)=R(L)+λB(L)建立能量函数和网络图,数据项和光滑项分别对应网络图中的t-links与n-links的权值,其中的λ值为目标区域或者背景区域的面积与图像大小的比值。

Step6:根据最大流/最小割准则对建立的网络图求最小割并获得分割的结果。

4　实验结果与分析

为了验证本文算法的有效性,将本文改进算法与传统图论算法进行比较实验分析,利用Matlab7.8进行仿真处理。选用的测试图像为不同类别的实际图像,图像包含有明确的目标和背景。实验结果如图2所示。可以看出本文算法能够有效地从背景中把目标物体分割出来。

图2　本文算法与其他算法的对比实验

为进一步验证改进算法的有效性,本文采用客观标准绝对误差率指标来评价算法的优劣。令N为图像总的像素个数,n0为目标像素的个数,n1为采取本文改进分割算法所得到的目标像素的个数,则本文改进分割算法所得到的绝对误差率error定义为

(9)

从式(9)中可以看出绝对误差率error越小,分割的效果就越好。比较上面实验中分割算法的error值如表1所示。

表1　采用不同算法得到的绝对误差率的比较

从表1中可以看出,本文算法的绝对误差率较小,实验结果表明,本文改进算法能够有效地从背景中把目标物体分割出来,分割结果更贴近于人的视觉感觉。

5　结语

随着各项应用技术的发展,在图像处理领域又提出了许多新的要求,基于图论的图像分割方法是值得进行深入研究的图像分割方法。本文简要地介绍了基于图论的图像分割方法的基本理论,并提出了一种改进的基于图论的图像分割算法,实验表明该改进算法能较好的把目标物体从背景中分割出来,分割效果较好。在图像分割算法中如何取得更好的分割结果,需要在今后的研究工作中继续探索和创新。本文获得“怀化学院重点学科建设项目资助”。

[1] Y. J. Zhang, J. J. Gerbrands. Objective and Quantitative Segmentation Evaluation and Comparison[J]. Signal Processing,1994,39:43-54.

[2] P. K. Sahoo, S. Soltani, A. K. C. Wong, et al. A Survey of Thresh-olding Techniques[J]. Comput. Vision, Graphics, Image Proc,1988,4:233-260.

[3] R. Kirsch. Computer Determination of the Constituent Structure of Biological Images[J]. Comput. Biomed. Res.,1971,4:315-328.

[4] J. F. Haddon, J. F. Boyce. Image Segmentation by Unifying Region and Boundary Information[J]. IEEE Trans. Pattern Anal. Machine Intell,1990,12(10):929-948.

[5] T. Pavlidis, Y. T. Liow. Integrating Region Growing and Edge Detection[J]. IEEE Trans. Pattern Anal. Mach. Intell.,1990,12(3):255-233.

[6] M. Kass, A. Witkin, D. Terzopoulos. Snakes: Active Contour Models[J]. International Journal on Computer Vision,1988,1(4):321-331.

[7] P. Felzenszwalb, D. Huttenlocher. Efficient Graph-Based Image Segmen-tation[J]. International Journal of Computer Vision,2004,59(2):167-181.

[8] D. Forsyth, J. Ponce. Computer Vision: A Modern Approach[M].New Jersey:Prentice-Hall, Englewood Cliffs,2002.

[9] Wang S, Siskind J M. Image segmentation with ratio cut[J]. IEEE Trans on PAKI,2003,25(6):675-690.

[10] C. Zahn. Graph Theoretical Methods for Detecting and Describing Gestalt Clusters[J]. IEEE Transactions on Computation,1971,20:68-86.

[11] S. Wang, J. M. Siskund. Image Segmentation with Ratio Cut[J]. IEEE Trans. on Pattern Analysis and Machine Intelligence,2003,25(6):675-690.

[12] P. Perona, W. Freeman. A Factorization Approach to Grouping[C]//ComputerVision-ECCV’98. 5th European Conference on Computer Vision,1998,1:655-670.

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

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

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

[16] ROTHER C, KOLMOGOROV V, BlAKE A. GrabCut: interactive foreground extraction using iterated graph cuts[J]. ACM Transactions on Graphics,2004,23(3):309-314.

[17] ACHANTA R, SHAJI A, SMITH K, et al. Slicsuperpixels, EPFL149300[R].[S. l.]: ÉcolePolytechnique Fédéral de Lausssanne(EPFL),2010.

[18] ACHANTA R, SHAJI A, SMITH K, et al. SLIC superpixels com-pared to state-of-the-art superpixel methods[J]. IEEE Trans onPattern Analysis and Machine Intelligence,2012,34(11):2274-2282.

Key Techniques of Image Segmentation Based on Graph Theory
YE Qing1,2HU Changbiao1,2
(1. College of Computer Science and Engineering, Huaihua University, Huaihua418008)

(2. Key Laboratory of Intelligent Control Technology for

Wuling-Mountain Ecological Agriculture in Hunan Province, Huaihua418008)

In this paper, image segmentation methods based on graph theory was researched. In view that traditional method cannot automatically realize image segmentation and the quality of image segmentation was related to the established data model, an improved automatic segmentation algorithm based on graph cut was proposed, which could automatically extract target and background points and establish energy function and network graph, and realize automatic segmentation of image.It was shown by experiment that the improved algorithm could be more effective in segmenting target object from the background.

image segmentation, graph cut, SLIC algorithm, energy function, graph theory

2016年2月4日,

2016年3月26日

湖南省教育厅科学研究基金项目(编号:13C714);怀化学院重点学科建设项目资助。

叶青,女,硕士研究生,副教授,研究方向:数字图像处理、模式识别。胡昌标,男,高级实验师,研究方向:计算机软件与理论、算法设计与分析。

TP391.41

10.3969/j.issn.1672-9722.2016.08.035