基于快速FCM与随机游走算法的图像自动分割方法

许健才，张良均，余燕团

（1.广州城市职业学院，广东 广州 510405；2.广州泰迪智能科技有限公司，广东 广州 510300；3.湖南师范大学，湖南 长沙 410012）

基于快速FCM与随机游走算法的图像自动分割方法

许健才1，张良均2，余燕团3

（1.广州城市职业学院，广东 广州 510405；2.广州泰迪智能科技有限公司，广东 广州 510300；3.湖南师范大学，湖南 长沙 410012）

在图像分割中，针对FCM算法存在聚类数目需要预先给定、收敛速度慢等缺点，本文把快速模糊C均值聚类算法和随机游走算法相结合，具体方法为先采用快速模糊C均值聚类算法对图像进行预分割，以便获得聚类中心的位置，然后将该中心作为随机游走的种子点，再进行图像分割，实验结果得到了较为满意的预期效果，证明该方法是可行的.本文的研究为快速FCM实现自适应性和开发图形图像预处理系统提供了技术支持与理论依据.

快速FCM；随机游走；图像分割；自适应性；二层减法聚类算法

0 引言

随着信息科学和人工智能的发展和广泛应用，数字图像处理、模式识别和计算机视觉等逐步成为研究热点.在数字图像的分析处理与应用中，人们分析处理的目标，往往是图像的其中一部分（目标），而其他无关部分则为图像背景.所谓图像分割（Image Segmentation），是把需要识别的目标从图像中分离出来.从广义上来说，是根据图像的特征或者特征集合按照一定的规则将图像划分成若干有意义的区域，这些特征可以是灰度、颜色、纹理、形状等，特征在同一区域内呈现相似性，在不同区域呈现较为明显的差异性，各区域的并集是整个图像，交集为空集.图像分割是图像处理中的一项关键技术，其目的是简化图像的表示形式，使得图像更容易理解和分析［1］.图像分割通常应用于定位图像中的物体和边界，文献［2］从集合的角度出发，对图像分割进行了定义.图像分割在上世纪70年代起一直受到人们的重视和关注，并对图像分割进行了深入研究，当即使到今天，图像分割仍然没有一个通用的分割理论.自20世纪70年代以来，业已提出上千种类型的分割算法.如超像素法［3-4］、蛇线模型法、阈值法、区域生长法［5］、分裂—合并法［6］、水线法［7］、马尔科夫随机场模型法［8-9］、多尺度法［10］、小波分析法［11［12］等.不同的图像分割算法分别在各自的领域、不同程度上都取得了一定的成果，但这些算法通常都只是适用于某一类图像，或者是针对某一具体应用背景而设计的，不具有通用性.通常这些分割算法需要运用相关领域知识和结合应用背景结合起来才能解决该类图像分割问题，因此，当前设计一种通用和统一图像分割算法可以说是一道经典难题.本文在文献［13］，［14］，［15］，［16］研究思想的基础上，提出基于快速FCM与随机游走算法相结合的混合图像自动分割算法，并进行了实验论证与模型计算，结果表明，该方法所提供的种子点所进行的分割效果比较理想，实现了随机游走的自动分割，减少了操作时间，提高了工作效率.

1 图像分割算法

1.1 模糊C均值聚类算法

模糊C均值（Fuzzy C-means,FCM）聚类算法有着几十年的发展历史，其概念最早起源于Ruspini的文章中，Ruspini在Zadeh等人提出利用模糊集理论处理聚类问题的基础上，提出了基于目标函数的聚类方法.将FCM算法应用到图像分割中，其基本原理是使用像素灰度级的Euclidean距离作为相似性度量，重复计算目标函数，直至相邻两个函数值之差小于某个事先给定的大于0的阈值.设给定图像I={f（i，j），0≤i＜M，0≤j＜N}，将I分成C类来实现图像的分割，其中f（i，j）为像素的灰度级数.基于FCM算法的图像分割步骤如下.

Step1设n=M×N为图像像素的个数，确定聚类数c、隶属度指数m（1.5≤m＜2.5）和适当小的迭代停机准则ε=0.0005>0；

Step2用区间[0，1]的随机数初始化隶属度矩阵U=[uk（i，j）]和聚类中心V=[v1，v2，…，vc]；

1.2 快速模糊C均值聚类算法

1.2.1 二层减法聚类算法

减法聚类是以样本数据点作为聚类中心候选点，把分布密度最大的点作为聚类中心，当n值大时可应用二层减法聚类算法以降低计算量.二层减法聚类［17］是将待分割图像分成Np个样本子集，先对各个子集进行第一层聚类，把这些聚类的中心重新组成一个新的数据集，再对该数据集聚类求得第二层聚类中心.在第一层中，将数据集Cx分为大小相等的t个数为b的子集（n=bt），记为，l=1，2，…，t.数据点xi邻域内的数据点个数为该数据点的密度函数，xi的邻域则定义为以xi为中心的圆，圆的半径r必须取一个合适的数值.根据Heaviside（赫维赛德）函数

第k个样本xk与第i个聚类中心vi的隶属关系，使用隶属度函数uik表示为：

模糊矩阵U的大小由原来的n×c变为Np× c，则c个聚类中心vi以及目标函数Jm（U，V）分别为

模糊聚类的划分矩阵属于以下划分空间：

其中，m∈[1，∞）为模糊加权指数，又称为平滑系数.

1.2.2 快速模糊C均值聚类算法步骤

快速模糊C均值聚类算法是迭代优化算法，根据上文，给出算法具体步骤如下：

（1）利用二层减法聚类对图像数据进行聚类，获得个Np子集.

（4）计算聚类有效性分析指标：

（5）令c=c+1，若c>cmax转下一步；否则，转（3）.

（7）利用V重新计算U并根据uik=max{u1k，u2k，…，uck}则xi∈第i类进行图像分割.

2 快速FCM与随机游走混合算法

随机游走（RandomWalks）是一种基于图论的半自动图像分割算法，其优点是运算速度快，分割结果好.首先由用户指定一组种子点，分别代表每一特定区域的K个像素，然后为每个未标记像素赋予一个K元组的向量［13，18］，由该向量表示一个随机游走从每个非种子点第一次到达K个种子点的概率，根据K概率最大者判别其所属类别，从而实现图像分割.

随机游走算法在处理弱边界或边界缺失和含噪声图像时显示了较强的优势，但由于该算法是一种半自动的图像分割算法，需要人工手动选取种子点，所以该算法有一定适用范围有一定的限制，例如一些实时性要求较高的场合就不适应该算法.要扩大随机游走算法的应用范围，需要解决种子点的自动选取问题.利用快速FCM聚类算法进行分割时，能直接得到聚类数和聚类中心点坐标，为快速选获取种子点提供了支持，所以，将快速FCM与随机游走分割算法结合，使得随机游走能够实现对图像自动分割，是本文研究的出发点，其处理过程如图1所示.

图1 随机游走算法图像处理过程

3 结果分析

为了评估基于快速FCM的自动标识随机游走算法的性能和验证其有效性，选取了一些图像来，在MatlabR2013a平台进行实验.

基于快速FCM的自动标识随机游走算法的实验结果图如图2所示.（a）为待分割的原图像；（b）在原图像进行快速模糊C-均值聚类分割得到的聚类中心点，使用空心圆圈标识出来，聚类数C由预先给定；（c）快速模糊C-均值聚类分割得到的结果；（d）快速FCM的自动标识随机游走算法分割的结果.

图2的第一行为船只在水中的分割实验图，同样提取了两个种子点，分别在（b）中标识出来，（d）将快速FCM预分割得到的聚类中心作为种子点，然后再进行随机游走图像分割，虽然所得的分割效果也不是很好，在船侧面的阴影部分出现了部分误分割，但是对比（c）其效果是有改进的.

图2 基于快速FCM的自动标识随机游走算法的实验结果

上图第二行为某一道路横向裂缝的实验结果，对比快速FCM和基于快速FCM的自动标识的随机游走算法，可以看出，（d）应用本文算法所得的分割结果用黑色线标出，分割结果较好，表明由快速FCM所提供的种子点是有效的，（c）将道路裂缝和其背景已经分割开了.

表1 算法计算时间对比

表1给出了两种分割算法在运算时间上的比较，可以看出，在图像大小接近、迭代次数一样的情况下，本文的图像分割方法在分割速度上具有明显的优势.

4 结论

对当前主流的图像分割算法原理进行了简单分析、比较和归纳，对传统和经典的图像分割技术进行了讨论研究.利用FCM对图像进行分割具有直观、易于实现等优点，在彩色图像分割中，能够综合考虑三个彩色分量，分割效果良好.但同时也存在聚类数需要预先给定（甚至陷入无法确定的困境）、计算速度慢等缺点，从而限制它在计算中的应用.基于此，把快速模糊C均值聚类算法和随机游走算法相结合，即先采用快速FCM对图像进行预分割处理，以便获得聚类中心的位置，然后将该中心作为随机游走的种子点，再进行图像分割.从文中实验可以发现，这一方法得到了较为满意的结果.因而，混合算法能有效地进行图像的自动分割处理，为后续选择的快速FCM实现自适应性和开发图形图像预处理系统提供了技术支持与理论依据.

［1］Linda G.Shapiro and George C.Stockman.Computer Vision［M］.New Jersey,Prentice-Hall,2001,279-325.

［2］刘松涛,殷福亮.基于图割的图像分割方法及其新进展［J］.自动化学报，2012,38(6):911-920.

［3］Ning J F,Zhang L,Zhang D,Wu C K.Interactive image segmentation by maximal similarity based region merging.Pattern Recognition,2011,43(2):445-456.

［4］Alper A,Stefano S.Motion segmentation with occlusions on the superpixel graph.In:Proceedings of the 12th IEEE In-ternational Conference on Computer Vision.Kyoto,Japan:IEEE,2010.727-734.

［5］Pong T C,Shapiro L G,Watson L T.Experiments in segmentation using facemodel region grower［J］.Computer Vision,Graphics and Image Processing,1984,25(1):1-23.

［6］Monga O.An optimal region growing algorithm for image segmentation.Pattern Recog Artif Intell.2011,1(4): 351-375.

［7］Ishikawa H.Transformation of general binary MRF min-imization to the first-order case.IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33 (6):1234-1249.

［8］黄宇,付琨,吴一戎.基于Markov随机场K-Means图像分割算法［J］.电子学报,2009,37(12):2700-2704.

［9］詹劲峰,戚飞虎,王海龙.基于时空马尔科夫随机场的运动目标分割技术［J］.通信学报,2000,21(11): 63-68.

［10］Tabb M,Huj A.Multi-scale image segmentation integrated edge and region detection［J］.IEEE Trans on IP,1997,6(5):642-654.

［11］汪祖媛,庄镇泉,汪炳权.红外热图像分割中的二维灰度直方图小波变换方法.红外技术,2000,2(4):1-3.

［12］龚炜,石青云,程民德.数字空间中的数学形态学［M］.北京:科学出版社,1997,54-60.

［13］Grandy L.Random walks for image segmentation［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(11):1768-1783

［14］龚劬,廖忠武,卢力等.基于图论的快速FCM图像分割算法［J］.计算机工程,2008,38(8):192-194.

［15］依玉峰,高立群,郭丽.基于Mean Shift随机游走图像分割算法［J］.计算机辅助设计与图形学学报, 2011,23(11):1875-1881.

［16］陈圣国,孙正兴,周杰.基于FCM和随机游走的地层图像分割方法［J］.电子学报,2013,42(3):526-531

［17］杜海顺,汪凤泉.一种快速的模糊C均值聚类彩色图像分割方法［J］.计算机工程与应用,2009,45(33): 138-140.

［18］侯叶,郭宝龙.基于图论的运动对象分割［J］.吉林大学学报(工学版),2008,38(4):902-906.

［责任编辑：郭正涛］

The Automatic Image Segmentation M ethod Based on Fast FCM and Random W alk Algorithm

XU Jian-cai1,ZHANG Liang-jun2,YU Yan-tuan3
（1.Guangzhou City Polytechnic,Guangzhou 510405,China；2.Guangzhou TipDM Information Technology co.,ltd, Guangzhou 510300,China；3.Hunan Normal University,Guangzhou 410012,China）

As far as image segmentation,the defeat of the number of clusters for FCM algorithm is reeded to be improued.In this paper,the fast fuzzy C-means clustering and random walk algorithm are combined to solve the problem of image segmentation.Firstly,the fast FCM for image pre-segmentation to obtain the number of clusters and cluster central location as the seed points of random walk firstly.Then,for image segmentation, experimental results show that thismethod is feasible,and get a more satisfactory desired purpose.Results of this study achieve self-adaptive and fast FCM develop graphical image preprocessing system provides technical support and theoreticalbasis.

fast FCM;random walk;image segmentation;self-adaptive;two-layer subtraction cluster

TP 391.41

B

1672-402X（2016）02-0048-05

10.13408/j.cnki.gjsxb.2016.02.011

2015-11-20

广州市科技和信息化局2013年应用基础研究专项（2013J4100073）

许健才(1978-)，男，广东清远人，广州城市职业学院讲师，广东省“千百十人才培养工程”培养对象；研究方向:移动互联网、AR、图像识别等研究.

张良均（1969-），男，湖南长沙人，广州泰边智能科技有限公司高级工程师，研究方向：大数据挖掘应用.

余燕团（1989-），男，广东英德人，湖南师范大学工程师，研究方向：智能计算与数据挖掘.