模糊C均值聚类与多相水平集图割优化相结合的图像分割

宋 琳， 高满屯， 王三民， 王淑侠

(西北工业大学机电学院，陕西 西安 710072)

模糊C均值聚类与多相水平集图割优化相结合的图像分割

宋 琳， 高满屯， 王三民， 王淑侠

(西北工业大学机电学院，陕西 西安 710072)

针对在分割多个目标时多相水平集模型对初始轮廓曲线敏感且计算量大的问题，提出采用模糊C均值聚类算法将图像进行粗分割，初始化多相水平集函数，使用图割算法分割出多相结果的方法。该方法能有效减小多相水平集算法对初始轮廓曲线的敏感性，使图割算法在分割图像时更容易分割出理想的目标轮廓；同时，采用图割算法可使水平集函数很快收敛到能量最小值，有效减少计算量，提高计算效率。实验表明该方法具有较好地分割效果和较高地分割效率。

模糊C均值聚类；图像分割；图割；多相水平集

图像分割的目的是获取输入图像中有意义的划分，并且将其变成有限数量的不相交的同质对象[1]。图像分割的方法很多，其中最有效的方法就是以能量最小化问题来处理图像分割问题，求解其最小极值。

求解最小极值一般采用两种方法：一种方法是

列出相关联的偏微分方程，计算偏微分方程的数值解；另一种方法是使用组合优化工具求解相类似的离散问题的解。

近年来，偏微分方程的单相水平集方法[2]，在界面演化、图像处理以及计算机视觉等领域得到了广泛应用。但单相水平集模型假设图像的目标区域和背景区域的灰度值近似为常量，所以，单相水平集模型适合分割灰度均匀、噪声小、仅含有一个目标的图像。使用单相水平集模型最终将图像分割为目标与背景。

一个真实图像往往存在两个以上或更多的目标，为了实现多相分割，Vese和Chan[3]将水平集模型扩展成多相模型，即同时采用多个水平集函数分割图像。通过多个水平集来表示多个区域(n个水平集函数最多可以表示“2n”个区域[4]，其中，n＞1)的多相分割算法。由于 C-V模型本身复杂的迭代算法，它的分割过程需要耗费大量的时间[5]。当采用多个水平集分割时，初始轮廓曲线的选择直接决定算法的收敛与否，选择不合适的初始轮廓曲线将导致算法最终不能收敛，从而大大降低了算法的稳定性；即使算法最后能够收敛，由于其各水平集之间缺乏从属约束关系，在实际计算中会出现多个水平集收敛于同一目标的情况，大大降低了水平集的实际分割效率。

另外一个成功的图像分割方法就是图割[6]。图割方法是一种快速计算的算法[7]。基于图割方法可将图像分割问题转换为能量函数的优化问题，通过合适的能量函数建立相应的网络图，利用最大流/最小割算法求解网络图最小割，从而获取图像分割的结果。图割-最大流/最小割方法是一种全局优化方法，通过解一系列二值分割问题来获得多相目标[8-9]。因其高效性，近年来被广泛应用于图像分割领域中。

在图像分割领域模糊 C均值聚类[10]方法是最普遍的数据聚类方法之一，其思想是使得被划分到同一簇的对象之间相似度最高，而不同簇之间的相似度最低。模糊 C均值聚类方法允许输入数据的噪声和变化范围相对大一些[11]。针对多相水平集和图割方法的特点，本文提出了采用模糊 C均值聚类的多相水平集与多层图割结合的图像分割方法。该方法，不需要初始化，既能减少水平集计算量，又能提高分割计算效率，快速准确分割出多个目标。

1 相关背景

多相水平集的核心是建立一种定义在多个曲线上的能量函数，当能量函数收敛至极小值时，多个曲线刚好收敛至目标边界。两个水平集函数同时收敛可将图像分割为4个目标区域如图1所示，也就是说，两个水平集函数可以找出4个目标边界；同时，初始化曲线所包含的目标信息，决定着水平集函数的收敛结果。本文的两个水平集是按两层来排列的结构。

图1 两个水平集函数(φ1和φ2)代表两个轮廓曲线

令 Ω为 R2的有界开子集，φ1、φ2：Ω→R 的Lipschitz连续的水平集函数。p=(x,y)表示图像中的任一像素点，两个水平集函数φ1和φ2将定义域划分成4个目标区域ω1, ω2, ω3和ω4，并且其中：

将零水平集曲线C定义为：

图像分割的结果可通过求解式(1)能量函数最小值来获得。

式中，ε为非负参数，当ε趋近于0时，式(2)接近于 H(φ)：

2 本文模型

多相水平集对于灰度均匀的图像可以实现多目标分割，但对于灰度不均匀，噪声较大的自然图像，因多相水平集受初始轮廓曲线影响较大，分割结果不准确。多相水平集本身计算量大，计算效率低。因此，本文提出了采用模糊C均值聚类的多相水平集与多层图割结合的图像分割方法。

2.1 模糊C均值聚类初始化

模糊 C均值聚类方法通过计算每个数据样本与聚类原型之间的隶属度对图像进行分割。假设样本集合为T={ t1,t2,···,tn}，将其分成a个模糊组，并求每组的聚类中心mj(j=1,2,···,a)，使得非相似性指标的价值函数达到最小。该方法采用模糊划分，将每个给定数据点用值在0,1间的隶属度来确定其属于各组的程度。

模糊C均值聚类方法的固有缺陷是：需要预先给定聚类个数；容易陷入局部极小值而得不到全局最优解。因此，本文利用模糊C均值聚类方法将图像粗略的划分为a个部分，并聚类为预先设定的a个模糊组，初始化多相水平集函数，使用图割算法，确定多相目标轮廓。

在本文中，以两相水平集为例，预先给定的聚类个数为4，模糊C均值聚类将图像粗分割成4个区域R1、R2、R3、R4，初始水平集函数可定义为：

2.2 离散化能量泛函

本文采用图割方法构造能量函数，即以能量最小化模型构造能量函数，从而将视觉问题转化为能量函数最小化问题。利用图割方法构造两相水平集能量函数，首先将两相水平集泛函离散化表示。

将图割方法引入两相水平集模型，需要根据图像构造网络，对于每一个像素点p∈Ω，(离散像素点集合)都有一个二进制变量组成的矢量与之对应，每一个像素点p对应着图割网络的一个节点，Xp所对应的节点是图像像素点的两倍，即构造一个两层网络xp、yp，xp、yp的定义如下：

在离散优化领域中，多相问题被称为多标记问题，是将图像区域中的每个像素点赋予的标记值的分配问题[12]。因此，Xp∈ {[1 1],[0 1],[1 0],[0 0]}。在两相水平集模型中的 4个目标区域 ω1, ω2, ω3, ω4，分别对应4个标记值11，01，10和00。

能量函数的离散公式可表示为：

式中，p=(x,y)表示任一层中的图像像素点，u （p）是p点的图像灰度值， N(p)是p点的邻域集合， wpq是边 vpvq的权值。

平均灰度值可表示为：

通过探索能量函数的最小能量值，来获得分割结果图像，其结果图像是具有光滑轮廓的分段常数区域[13]。分段常数模型可近似为：

2.3 能量泛函最优解

图割方法根据图像所构造的网络，使得能量与网络割相对应，从而将能量最小化问题转化为网络最小割问题。根据最大流/最小割定理，将网络最小割问题转化为最大流问题。通过求解最大流问题，求得图的最小割，从而获得视觉问题的解。

利用图割方法找到图像对应的能量模型的最小割，计算出最小能量结果，最终生成多个目标区域的轮廓曲线。图割方法的网络节点(像素点)是按两层来排列的，层内节点之间的关系、层间节点之间的关系以及各节点与源、汇点的关系见图 2～4。因此，为求得式(11)的最优解，构建的 3个图分别代表 FL1、FL2、FData。G 代表离散能量函数FD。

利用图割方法解能量泛函的最优解，层内像素点间的关系(边)的权值，层间像素点间的关系(边)和各像素点与源、汇点的关系(边)的权值按如下方法确定。

图2 G1、G2示意图

图3 G3示意图

图4 分割结果，G示意图

每一个像素点p对应图G2中的一个节点zp,p点的8邻域集合为N(p)。当q∈N(p)，则有边ezpzq的权值为wzpzq。

S点(源点)到节点vp的边Svp的权值为wSvp：

节点zp到T点(汇点)的边zpT的权值wzpT：

本文的计算方法如下：

(1) 用模糊C均值聚类算法将图像聚类，并进行初始化，构造xp和yp。

(2) 计算c11, c10, c01, c00。

(3) 计算权值wvpvq, wzpzq, wvpzp, wSvp和wzpT。

(4) 计算能量函数值FD。

(5) 利用图割算法解出图G(图4)的最小割，同时更新xp和yp。

(6) 将xp和yp组合出的4个区域标记为l1, l2, l3, l4。

(7) 重新计算c11, c10, c01, c00；回到第(3)步；直

到循环结束。

3 实验结果分析比较

图割算法的计算效率高；但基于梯度下降法的多相水平集，很容易得到局部极小，要获得满意的分割结果，算法的初始化很重要[14]，合适的初始位置才能分割出理想的多相结果。本文采用的自然图像来自Berkeley数据库。

图 5(a)是采用手动方法初始化多相水平集函数，图5(b)是经过200次迭代计算后得到的分割结果。有的初始化曲线，使得算法不收敛，降低了算法的稳定性，这里不再赘述。总之使用多相水平集算法，计算量大，且效率低，要得到满意的分割结果需要耗费大量的时间去寻找最佳初始化曲线。

图5 多相水平集方法分割图像

图6 不同初始化位置对分割结果的影响

图 6(a1)～(a3)是采用手动初始化多相水平集函数的方法，图 6(b1)～(b3)是经过使用图割算法对图像进行多相分割得到的结果。

图 6(a1)～(a3)中的圆圈线是多相水平集的初始化曲线；图 6(b1)～(b3)是分割出的多相结果用不同灰度填充后的效果；图 6(c1)～(c3)是三次分割的能量值曲线。从分割结果可以看出，分割结果对初始化非常敏感，图6(a1)和(a2)的初始化都只分割出两相结果，只有图6(a3)的初始化得到了三相结果。在实际计算中，满意地分割结果，往往伴随着很多次初始化之后才能得到。由于图割算法的使用，三次分割的能量值很快收敛到最小，计算效率很高。

模糊C均值聚类能快速将图像进行粗分割，本文的算法就是采用模糊 C均值聚类初始化水平集函数，使用图割算法对图像进行多相分割。

以下采用本文的算法将图像分割为多相结果，

并予以说明分析。

图7是要被分割的自然图像。图8是采用模糊C均值聚类将图像聚类后，来构造的像素点Xp，红色和青色区域是构造的初始化像素点xp、yp中的目标相。初始化是图像分割的第一步，由于模糊C均值聚类已经将图像进行聚类，因此两相水平集函数的初始化轮廓曲线就是对图像进行了粗分割的结果。图像中待分割的目标与背景信息已经粗略形成，再者，两层水平集之间又有着联系和约束关系，目标就会更容易被分割出来。因此，模糊C均值聚类初始化水平集轮廓曲线有利于多相分割结果的形成，使得多相分割结果对初始化的敏感性大大降低，从而提高了算法的稳定性。

图7 原始图像

图8 用模糊C粗分割图像

图 9是采用图割算法迭代后的分割结果矢量Xp，红色和黄色区域是结果变量xp、yp中的目标相。图 10是采用本算法的图像分割结果，使用不同灰度来填充分割出的多个区域面积。

图9 使用本文算法的xp和yp结果

从图7～10可以看出，采用模糊C均值聚类粗分割的图像，噪声比较大，初始化的轮廓曲线还有噪声的干扰。使用多相水平集图割算法迭代后，噪声被去掉，图像中目标的边界被快速准确的分割出来。

模糊 C均值聚类只能将图像聚类为预设定的几个部分，边缘比较模糊，这是由于模糊C均值聚类对噪声比较敏感，当灰度值相近时，图像内的目标不能被完全分割。图割方法有着全局最优性和分割结果的强鲁棒性，快速确定目标个数，使图像中的目标相很快被分割，水平集函数的能量值迅速收敛，达到最小。

图10 分割结果

从图11的能量值得出曲线看，水平集图割算法在3～4次迭代就可以使得能量值收敛到最小，得到满意的分割结果，计算效率很高，计算量大幅度降低。

图11 能量值曲线

图 12是采用本文算法对自然图像分割的又一个实例，图12(a)是原始图像；图12(b)是采用模糊C均值聚类对离散水平集函数进行了初始化，这样的初始化使得图像的两个层的目标信息相对明确；

图12 分割图像实例

图13 实例的能量值曲线

4 结 论

本文提出了采用模糊 C均值聚类初始化两相水平集函数的图割算法。该模型可以有效减小多相水平集函数对初始轮廓曲线的敏感性，增强了水平集算法的稳定性，初始化使得图像分割的目标相与噪声相对明晰，更容易分割出目标相；采用图割算法进行优化，能量值很快收敛至最小，有效减少计算量，提高计算效率。

[1] Moreno J C, Surya P V B, Proença H, et al. Fast and globally convex multiphase active contours for brain MRI segmentation [J]. Computer Vision and Image Understanding, 2014, 125(2)： 237-250.

[2] Osher S, Sethian J A. Fronts propagating with curvature dependent speed： algorithms based on Hamilton-Jacobi formulation [J]. Journal of Computational Physics, 1988, 79(1)： 12-49.

[3] Vese L A, Chan T F. A multiphase level set framework for image segmentation using the Mumford and Shah model [J]. International Journal of Computer Vision, 2002, 50(3)： 271-293.

[4] Bogovic J A, Prince J L, Bazin P L. A multiple object geometric deformable model for image segmentation [J]. Computer Vision and Image Understanding, 2013, 117(2)：145-157.

[5] Zhao Minrong, Zhang Xiwen, Jiang Juanna. Topography image segmentation based on improved Chan-Vese model [J]. Computer Aided Drafting, Design and Manufacturing, 2013, 23(2)：13-16.

[6] Boykov Y, Veksler O, Zabih R. Fast approximate energy minimization via graph cuts [J]. IEEE Transactios on Pattern Analysis and Machine Intelligence, 2001, 23：1222-1239.

[7] Kolmogorov V, Zabih R. What energy functions can be minimized via graph cuts? [J]. IEEE Transactios on Pattern Analysis and Machine Intelligence, 2004, 26(2)：147-159.

[8] Boykov Y, Funka-Lea G. Graph cuts and efficient N-D image segmentation [J]. International Journal of Computer Vision, 2006, 70(2)： 109-131.

[9] Zeng Yun, Samaras D, Chen Wei, et al. Topology cuts： a novel min-cut/maxflow algorithm for topology preserving segmentation in ND images [J]. Computer Vision and Image Understanding, 2008, 112(1)： 81-90.

[10] Pal N R, Pal K, Keller J M, et al. A possibilistic fuzzy c-means clustering algorithm [J]. IEEE Transactions on Fuzzy Systems, 2005, 13(4)： 517-530.

[11] Wang Zhimin, Song Qing, Soh Y C, et al. An adaptive spatial information-theoretic fuzzy clustering algorithm for image segmentation [J]. Computer Vision and Image Understanding, 2013, 117(10)： 1412-1420.

[12] Bae E, Jing Yuan, Tai Xuecheng. Global minimization for continuous multiphase partitioning problems using a dual approach [J]. International Journal of Computer Vision, 2011, 92(1)： 112-129.

[13] Sashida S, Okabe Y, Lee H K. Comparison of multi-label graph cuts method and Monte Carlo simulation with block-spin transformation for the piecewise constant Mumford-Shah segmentation model [J]. Computer Vision and Image Understanding, 2014, 119(1)： 15-26.

[14] Brown E S, Chan T F, Bresson X. Completely convex formulation of the Chan-Vese image segmentation model [J]. International Journal of Computer Vision, 2012, 98(1)： 103-121.

An Image Segmentation Method by Combining Fuzzy C-Means Clustering with Graph Cuts Optimization for Multiphase Level Set Algorithms

Song Lin, Gao Mantun, Wang Sanmin, Wang Shuxia
(School of Mechanical Engineering, Northwestern Polytechnical University, Xiʹan Shaanxi 710072, China)

Multiphase level set model is sensitive to initial contour curve and has huge computation in the process of the multiple objectsʹ segmentation. A novel Image segmentation method is presented for multiphase scenario, which initializes the multiphase level set function by coarse image segmentation using fuzzy C-means clustering algorithm and applies graph cuts algorithm to acquire multiphase output image. The method can effectively reduce the sensitivity of the multiphase level set algorithm to initial contour and is easier to gain the multiphase output image by graph cuts algorithm. At the same time, the multiphase level set function quickly converge to the minimum energy value with small amount of calculation and high computational efficiency using the graph cuts algorithm. The experiments show that this method has better segmentation effect and higher efficiency of image segmentation.

fuzzy C-means clustering; image segmentation; graph cuts; multiphase level set

TP 391

A

2095-302X(2015)04-0563-07

2014-12-11；定稿日期：2015-02-11

国家自然科学基金资助项目(51105310)

宋 琳(1975–)，女，河北任县人，讲师，博士研究生。主要研究方向为计算机视觉和模式识别。E-mail：songlim03@sina.com