区域生长和C-均值聚类结合的图像分割方法✴

李 媛,王浩全,张 培

(中北大学信息与通信工程学院,山西太原 030051)

图像分割是指在一幅图像中分离出具有相同或相似的较为感兴趣的目标区域,即把目标区和背景区区分开来,实现图像描述方式的转换,给图像的后续处理提供重要的依据[1-4].图像分割方法主要有:基于边缘的图像分割、基于阈值的图像分割、基于聚类的图像分割、基于神经网络的图像分割[5]和基于区域的图像分割等.

区域生长分割[4]是由若干种子点按一定的生长准则,对相邻像素点进行判别连接,直到所有像素点连接完成为止.但由于有具有主观性的颜色相似度和空间相近度的影响,对有阴影区域的图像产生欠分割或过生长的现象.模糊C均值聚类分割[6]是一种无监督的聚类算法,运用了迭代优化目标函数,对色彩或灰度相似度较高的图像进行分割会得到很好的效果.但因为反复迭代,运行时间比较长.

本文根据区域生长的分割算法与聚类分析具有较为相近的思想,提出了一种基于区域生长和C均值聚类相结合的图像分割方法.运用聚类中的集合思想,确定生长区域的种子点并给出生长半径;把所有合并到区域中的点必须与区域中至少一个像素点具有8邻接性,作为聚类中模糊集合的一个限制条件,最后得到分割结果.

1 算法描述

1.1 模糊C均值聚类分割算法[7]

模糊C-均值聚类算法是根据最小二乘法对目标函数进行迭代优化并获得最终的数据划分.在图像分割应用中,是根据分割图像中的像素及C个聚类中心的每一中心的加权隶属度,对目标函数进行迭代优化的.

设图像中所有像素的集合为X,c为聚类的类别数,取像素的灰度值作为聚类特征.C-均值聚类的目标函数为

聚类中心

隶属矩阵

更新聚类中心

式中:m＞l为加权指数;vi为第i个聚类中心;c满足2≤c≤n,表示模糊聚类的类别数;μij代表第j个样本xj隶属于第i类的程度.

传统的模糊C-均值聚类算法中,分割结果仅仅和聚类中心与特征空间中的像素点之间的距离有关.

模糊C-均值聚类方法运用于图像分割的步骤为:①模糊加权指数m、聚类类别数c、迭代停止条件 ε、最大迭代次数U(0)及初始化划分矩阵V(0)的确定;②根据公式(4)计算更新聚类中心;③根据公式(3)计算新的隶属矩阵;④对隶属函数矩阵进行判定,是否满足迭代终止条件 ‖U(γ+1)-U(γ)‖ ≤ε,或达到给定的迭代次数停止迭代;否则返回步骤(2),重复步骤,直到聚类中心收敛.

1.2 区域生长算法

区域生长的基本思想是通过一个初始种子,将具有相似性质的像素集合在种子像素所在的区域.在图像分割中最重要的就是种子点的确定和区域生长准则的建立.

图像分割应用区域生长法,需解决三个问题[8]:①选择或确定可以正确代表目标区的种子像素;②确定生长过程中能将相邻像素包括进来的生长准则;③制定让生长停止的条件或规则.

区域生长分割的具体算法描述为:首先在目标区中选取初始种子点像素,其次根据某一生长准则,从种子点像素邻域(8邻域)中寻找与种子点相同或相似的像素,并入种子点像素所在区域,然后将新的像素作为闲的种子点子像素重复以上过程,直到找不到符合规则的像素为止.

1.3 基于区域生长与聚类分析相结合的分割方法

区域生长中首先确定种子点并给出生长半径,这也正符合了聚类中的集合思想;与此同时,所有合并到区域中的点必须与区域内至少一个像素点具有8邻接性,作为聚类中模糊集合的一个限制条件.这正表明了区域生长的分割算法与聚类分析有着较为相近的思想.

目标函数

Nikhil[10,11]等人研究指出,加权指数m=2是较为理想的取值;c代表类别数,一般取2≤c≤n,本文中取2,即目标区和背景区;n表示图像中的像素数.

式(5)中:A是对称的正定矩阵,本文中的A为单位矩阵,当A为单位矩阵时,di,k恰好是欧式距离.xk在式(5)中代表论域中的数据点,vi表示第i类模糊集Xi的聚类中心.

U[μi,k]是一个c×n的矩阵;J(U,V)代表各类中聚类中心到样本数据点的加权距离平方和,J(U,V)的值反映的是:在某种差异定义下的类内统一程度.它的值越小,表示所得到的分割效果越好.

2 实验结果及分析

依据上述几种图像分割方法,针对实验图像(图 1),分别用模糊C-均值分割算法、区域生长分割算法以及本文算法对其进行分割处理,得到的处理结果如图2所示.

图1 实验图像Fig.1 Experimental image

图2 分割结果Fig.2 Segmentation result

图1(a)为原始目标图像,图中矩形和椭圆形为目标区域,图1(b)为经过超声CT重建后的图像.

图2(a)为模糊C-均值分割结果,图2(b)为区域生长分割结果,图 2(c)为本文算法的分割结果.以上结果对比显示:目标区的面积、位置及轮廓等方面的信息比较准确.本文提出的新算法对目标区的分割是比较平滑的、完整的,显示了较好的分割效果.

2.1 运行时间的对比

本文就聚类分割算法、区域生长分割算法与本文提出的方法在运行时间上作了比较,本文方法在得到较好分割效果的同时消耗时间较其它两种算法要长一些.实验的硬件环境为Pentium(R)Dual-Core CPU E5300 2.60GHz,2.00GB内存.仿真软件为Matlab7.0.

2.2 目标区位置准确性的对比

目标区像素数相等不足以说明分割后目标区分割的准确性,在目标区分割后位置信息具有一定偏差的情况下,依旧可得到与原始目标区像素数相吻合的结果,故对本文提出的算法就目标区分割前后的位置信息做了详细对比,如图3所示.表2给出的是重建后图像中两个目标区上下左右边界点的位置信息,表3给出的是本文提出算法得到的分割图中两个目标区上下左右边界点的位置信息.对比可知,二者位置信息完全相同,很大程度上说明了分割的准确性,即此方法分割的完整性和准确性均达到了100%.

图3 目标区位置图Fig.3 Location plan of target area

表2 原始图像中目标区的位置信息Tab.2 Target zone’s position information of the original image

表3 分割后得到的目标区位置信息Tab.3 Target zone’s position information after segmentation

3 结 论

本文将区域生长和模糊C均值聚类分割方法存在的优缺点有机结合在一起,提出了一种基于区域生长与C均值聚类图像相结合的分割方法,并通过仿真软件实现了这种图像分割的方法.结果表明:通过本算法预先设置的参数,实现了无监督的图像分割.结合不同的图像分割算法,充分利用各自的优点,扬长避短,达到较为理想的分割效果.

[1]马英辉,韩焱.彩色图像分割方法综述[J].科技情报开发与经济,2006,16(4):158-159.

Ma Yinghui,Han Yan.Overview of the methods for color image segmentation[J].Sci-Tech Information Development&Economy,2006,16(4):158-159.(in Chinese)

[2]杜宇慧,桂志国,李晋华.基于类别方差的三维医学图像分割新方法[J].中北大学学报(自然科学版),2007,28(2):166-170.

Du Yuhui,Gui Zhiguo,LI Jinhua.A new method of 3D medical images segmentation based on class variance[J].Journalof North University of China(Natural Science Edition),2007,28(2):166-170.(in Chinese)

[3]Jar-Ferr Yang,Shu-Sheng Hao,Pau-Choo Chung.Color image segmentation using fuzzy C-means and eigenspace projections[J].Signal Processing,2002,82:461-472.

[4]Cheng H D,Jiang X H,Sun Y,et al.Color image segmentation:advances and prospects[J].Pattern Recognition,2001,34(12):2259-2281.

[5]Wangenheima A,Bertoldir,Abdala D,et al.Color image segmentation using an enhanced gradient network method[J].Pattern Recognition Letters,2009,30(15):1404-1412.

[6]Cinque L,Foresti G,Lombardi L.A clustering fuzzy approach for image segmentation[J].Pattern Recognition,2004,37:1797-1807.

[7]郭桂蓉.模糊模式识别[M].长沙:国防科技大学出版社,1992:178-186.

[8]章毓晋.图像工程(中册)图像分析(第二版)[M].北京:清华大学出版社,2005:102-104.

[9]Nikhil R.Pal,James C.Bezdek,Richard J.Hathaway.Sequential competitive learning and the fuzzy C-means clustering algorithms[J].Neural Networks,1996,9:787-796.

[10]李明,李云松.改进的快速模糊C均值聚类的图像分割方法[J].兰州理工大学学报 ,2007,(3):95-99.

Li Ming,Li Yunsong.A modified method for image segmentation with fast fuzzy C-mean clustering[J].Journal of Lanzhou University of Technology,2007,(3):95-99.(in Chinese)