一种改进的图割目标分割算法

汤依婷，韩彦芳

(上海理工大学 光电信息与计算机工程学院，上海 200093)



一种改进的图割目标分割算法

汤依婷，韩彦芳

(上海理工大学 光电信息与计算机工程学院，上海 200093)

为了减少图像目标在分割过程中受到噪声、复杂背景等因素的影响，将图像的多特征信息引入到图割算法中，提出了一种结合图像的多特征信息图割目标分割方法。该方法先选取像素点的多种图像特征组成特征向量，并对已做好标记的目标和背景种子点的特征向量分别进行FCM聚类，然后分别计算各像素点与这两类种子点的各聚类中心的最短欧式距离，并据此信息完成对能量函数的构造，最终运用最大流/最小割的方法得到图像分割的结果。其与传统图割算法相比，分割结果有了明显改善。实验结果表明，该算法具有有效性。

图割；图像分割；特征向量；FCM聚类；最大流最小割

TANG Yiting, HAN Yanfang

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology,Shanghai 200093, China)

图像分割是由图像处理到图像分析的关键步骤。只有在图像分割的基础上才能对目标进行特征提取和参数测量，使得更高层的图像分析和理解成为可能。因此，对图像分割方法的研究具有重要意义。经典算法有阈值法[1]、区域合并[2]、基于边缘检测[3]、分水岭算法[4]和聚类分析[5]等，这些算法在不同领域得到了广泛应用。而图割(Graph Cuts)算法可在全局最优的框架下进行分割，能确保能量的全局最优解，因而得到广泛关注。

传统Graph Cuts算法仅依赖图像的灰度信息构造能量函数。对于简单图像分割效果良好，但当背景较为复杂，且与目标灰度较为接近时，图像目标的准确分割变得困难。故本文在传统Graph cuts算法的基础上，提出一种依赖图像多特征信息构造能量函数的图割方法。待分割的目标与背景总会在某一种或多种图像性质上存在差异，综合考虑多种因素，增加多特征的信息，可实现目标的正确分割，提高算法精确度。

1 Graph Cuts图像分割理论

1.1 图割理论

图割法是利用图论中的最小割算法求能量函数全局最优解的算法。利用图割来解决图像分割问题的步骤如下。

1.1.1 构造图结构

将图像转变成图结构，构造的图为G=(V,E)，V和E分别代表图的节点和边的集合，每一条边均有一个非负的权值。V中包括两类节点：(1)由图像像素集合P组成的领域节点；(2)两个特殊的端点称为终端：源点s与汇点t，分别对应图像中的目标种子点和背景种子点。E中也包括两类：1)相邻像素节点p和q之间带有权值Wpq的边epq,其中q∈Np，通常q为p点的4领域或8领域；2)像素p与s和t之间带有权值Wsp和Wpt的边esp和边ept(p∈P)。一幅二维图像及其构造图，如图1(a)和图1(b)所示。

1.1.2 构造能量函数

用一组像素集合I表示一幅图像，领域系统N用以表示I中两个像素{p,q}的相互关系，向量A=(A1,A2,…,A|I|)描述了I中各像素的属性状态，Ai={′obj′,′bkg′},Ai是一个二元值，代表像素i属于目标或背景。在通过向量A来构造能量函数时，需考虑各个像素自身的情况以及像素间的相互联系。因此，Boykov给出了能量函数的定义为[6]

E(A)=λ·R(A)+B(A)

(1)

其中

(2)

(3)

式中，B(A)表示平滑项能量，为相邻像素之间的能量；R(A)表示数据项能量，为各个像素自身情况在能量函数中的体现。

1.1.3 最大流/最小割

利用该算法求解能量函数全局最小值得到的就是对图像的分割结果，如图1(c)和图1(d)所示。

图1 图和图割

1.2 最大流/最小割

最大流/最小割分割法通过计算图的最大流求得图最小割的值，从而使能量函数最优化，得到最优解。本文采用的是利用两棵动态搜索树的方法计算最大流/最小割的算法[7]。

根据网络流的理论[8]和由L.Ford and D.Fulkerson提出的定理[9]可知，在s-t网络中，可行流的最大值等于割的容量最小值。因此，网络图的最小割与最大流可相互转化来得到，故图的最小割可通过计算图的最大流得到。

搜索树算法的基本思想是：分别以源点s和汇点t来构造搜索树S和T，通过生长树S和T来寻找增广路径。可分成以下4个步骤：

步骤1 寻找增广路径(Growth Stage)；

步骤2 处理增广路径(Augmentation Stage)；

步骤3 组合深林成树(Adoption Stage)；

步骤4 若步骤1中寻找不到增广路径，则找到最小割，算法退出；否则，继续执行步骤1～步骤3。

由上述算法思想可找到一条从源点s到汇点t的增广路径，如图2所示。与源点和汇点均不相连的点被归为背景区域。

图2 从源点s到汇点t的一条路径

2 基于多特征的图割分割算法

2.1 算法原理

2.1.1 限制条件

为使图像分割结果能达到预期的目的，适当的限制性条件必不可少。基于图割的分割方法可看做是一类交互式图像分割方式，故人机交互的标示就是一种简单而有效的限制性条件。在文中的限制条件即为人在图像上对目标和背景所做的标示。

2.1.2 特征信息选取与融合

对于图像特征信息的选取，本文主要从像素灰度和梯度两方面考虑。对于一幅灰度图像I，本文选取6个特征组成其特征向量，即Vp=(a1,a2,a3,a4,a5,a6)。其中，a1代表像素p的灰度；a2代表像素p为中心的8领域内的灰度类方差；a3代表像素p灰度值的横向梯度；a4代表像素p灰度值的纵向梯度；a5代表了像素p所在的行信息；a6代表像素p所在的列信息

图3 8领域像素块

(4)

(5)

a3=(|Ip-I4|+|Ip-I5|)/2

(6)

a4=(|Ip-I2|+|Ip-I7|)/2

(7)

a5=m,m为像素点所在的行

(8)

a6=n,n为像素点所在的列

(9)

以单个像素作为基本处理单元，在选定若干个有效的图像特征后，每一个像素均对应一个特征向量。首先对特征向量进行FCM聚类[10]，每个聚类中心对应的向量代表了一组典型的图像特征。在聚类后，每一个像素均对应一个聚类类型，以k代表其属于第k类。

在本文算法中，针对上文标示的目标和背景种子像素分别用FCM聚类分为k类，则可知目标像素和背景像素所可能具有的k类典型特征向量，为下文构造能量函数做准备。为减小计算量，此处k取10。

2.1.3 构造能量函数

构造能量函数是图割算法最为重要的部分，能量函数构造的优劣将直接影响到分割结果。能量函数表达式如下所示

E(A)=λ·R(A)+B(A)=

(10)

其中，第一项为数据项能量，Rp(Ap=′obj′)反映了像素p属于目标的可能性，若像素p属于目标的可能性越大，则Rp(Ap=′obj′)的取值就越小，反之亦然。同理，有Rp(Ap=′bkg′)。而这一可能性如何度量，则是构造能量函数的关键。

定义Dist(p,′obj′)和Dist(p,′bkg′)分别代表像素点p与目标和背景的距离。由上文已计算出分别代表目标和背景的k类典型特征向量，分别计算像素点p的特征向量与代表目标的k类特征向量和代表背景的k类特征向量的欧式距离，并取其中的最小值作为Dist(p,′obj′)和Dist(p,′bkg′)的值，设p的特征向量可表示为 (n个特征)，目标的特征向量可表示为αoi={Bi1,βi2,…,βin} (n个特征，第i类特征向量，1≤i≤k)；同理得背景的特征向量可表示为： (n个特征，第i类特征向量， )。计算公式如式(11)和式(12)所示。

(11)

(12)

Dist(p′obj′)和Dist(p,′bkg′)也可理解为此像素属于目标或背景的可能性。此时数据项可表示为

(13)

其中

(14)

由Dist(p,Ap)定义可知，Dist(p,Ap)是一个非负数，ε1和ε2均为正常数，是保证Pr(p|Ap)∈(0,1)，且应尽可能减小其对Pr(p|Ap)取值的影响。

第二项B(A)是平滑项，其大小反映的是两个相邻像素之间的相似性，两个像素越相似，其值越大。定义Bp,q为

(15)

其中

Rq(′obj′))2+(Rp(′bkg′)-Rq(′bkg′))2)

(16)

2.2 算法总结

算法分为4步：

步骤1 人机交互，选取目标和背景的种子像素;

步骤2 将彩色图像变为灰度图像，计算种子像素的特征向量，并分别对目标种子像素和背景种子像素进行FCM聚类，各分为10类;

步骤3 由文中介绍的构造能量函数的方法构造能量函数;

步骤4 采用最大流/最小割的搜索树算法实现图像的分割。

3 实验与分析

文中算法程序采用Matlab编写，其中核心部分由C++语言实现，编程环境为Matlab 2014，选择标准图像库Berkeley Segmentation Dataset中的图像进行实验。并分别用传统的图割算法和本文的图割算法对图像进行分割，分割结果如图4～图6所示，其中交互图像中十字点为目标种子点，圆圈为背景种子点。

图4 分割结果示意图

图5 分割结果示意图

图6 分割结果示意图

以上几幅图像均包括较为复杂的背景，通过本算法和传统算法的分割结果比较可看出，本算法优于传统算法，加入了多特征的向量构造能量函数，使分割结果有了明显改善，去除了背景中大部分杂乱部分，且边缘细节的捕捉能力也更好，验证了本算法的有效性。

4 结束语

本文介绍了一种基于多种特征构造能量函数的图割算法。本算法通过FCM聚类来融合多个图像特征，分别计算目标和背景的k类特征向量，计算各个像素点和种子像素点的最短欧式距离得到数据项函数，然后利用相邻像素点间的灰度信息构造平滑项函数，最终通过最大流/最小割中的搜索树算法得到图像分割结果。相比于传统图割方法，该方法在背景较为复杂的情况下，对于目标区域的分割依然效果良好。实验结果表明，加入多特征构造能量函数方法在分割过程中起到了一定的作用。

[1] Joe H. Bivariate threshold methods for extremes[J].Journal of the Royal Statistical Society, 1992,54(1):171-183.

[2] Richard N,Frank N.Statistical region merging[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2004, 26(11):1452-1458.

[3] Catté F,Coll T. Image selective smoothing and edge detection by nonlinear diffusion:II[J].Siam Journal on Numerical Analysis,1992,29(3):845-866.

[4] Vincent L, Soille P. Watersheds in digital spaces: an efficient algorithm based on immersion simulations[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1991,13(6):583-598.

[5] Arifin A Z, Asano A. Image Segmentation by histogram thresholding using hierarchical cluster analysis[J]. Pattern Recognition Letters,2006,27(13):1515-1521.

[6] Boykov Y Y,Jolly M P.Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images[C].UT,USA:ICCV Proceedings,Eighth IEEE International Conference on Computer Vision, IEEE,2001.

[7] Yuri B,Vladimir K.An Experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2004,26(9):1124-1137.

[8] 田丰,张运清.图与网络流理论[M].2版.北京:科学出版社,2015.

[9] Ford L R,Fulkerson D R.Flows in networks[J].Princeton University Press Princeton N J,2010,18(4):157-172.

[10] Bezdek J C,Ehrlich R,Full W.FCM: The fuzzy c-means clustering algorithm[J].Computers & Geosciences, 1984, 10(84):191-203.

[11] Xu N,Ahuja N, Bansal R. Object segmentation using graph cuts based active contours[C].Hongkong:IEEE Conference on Computer Vision & Pattern Recognition,2003.

An Improved Algorithm of Graph Cut Segmentation

A combination of multiple image feature information and graph cut algorithm is proposed for segmenting target by introducing multiple feature image information into the graph cut algorithm to reduce the negative influence on the target image of noise, complex background and other factors in the segmentation process. First, multiple image features are selected to compose the feature vectors, and the feature vectors of labeled target and background seed points are clustered by FCM. Second, the shortest distance of each pixel to the cluster center of each seed point of the two types is calculated, according to which the energy function is constructed. Finally, the maximum flow minimum cut method is used to get the results of image segmentation. Experimental results show that the proposed algorithm significantly improves the segmentation results over the traditional graph cut algorithm.

graph cut; image segmentation; feature vector; FCM clustering; max-flow min-cut

2016- 01- 04

汤依婷(1993-)，女，硕士研究生。研究方向：数字图像处理与计算机视觉。韩彦芳(1974-)，女，博士，讲师。研究方向：图像处理和模式识别。

10.16180/j.cnki.issn1007-7820.2016.10.013

TP391.41

A

1007-7820(2016)10-043-04