第5卷第1期 智能系统学报 Vol.5 No.1 2010年2月 CAAI Transactions on Intelligent Systems Feh.2010 doi:10.3969/i.i8gn.1673-4785.2010.01.011 基于空间位置约束的K均值图像分割 刘咏梅，代丽洁 (哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001) 摘要：K均值聚类分割是一种有效的基于聚类的图像分割算法.传统的K均值聚类分割算法采用特征空间中的相 似性测度来度量像素的归属类别.由于自然景物图像的复杂性，位置邻近且本应属于同一分割区域的像素点，由于 它们视觉特征的差异性，导致其在特征空间中相距甚远而被分割为不同的区域.以投票的方法将像素的局部空间位 置信息引入到【均值聚类分割算法中，达到了改善分割效果的目的.实验结果证实了该方法的有效性， 关键词：K均值聚类：图像分割：空间位置信息 中图分类号：1TP391文献标识码：A文章编号：16734785(2010)01006703 An improved method of K-means image segmentation based on spatial position information LIU Yong-mei,DAI Li-jie (School of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China) Abstract:K-means clustering is an effective algorithm for image segmentation,which attempts to separate objects of interest from their background.Traditional K-means clustering algorithms use the visual similarity measures of pix- els in the feature space to determine which segmentation region the pixels belong to.Because of the complexity of natural images,neighboring pixels with different visual features,which should be treated as part of the same ob- ject,may end up in separate regions.As a result,it is hard to get satisfactory results when depending only on visu- al features.A spatially constrained image segmentation algorithm was therefore developed.It improved on the K- means clustering algorithm by adding a corrective step,the application of positional information from neighboring pixels.Experiments showed that the algorithm is effective. Keywords:K-means clustering;image segmentation;spatial position information 图像分割是一种基本的计算机视觉技术，是大因素的影响，对图像物体进行有效分割却一直是基 多数图像识别和理解任务所需要的基础步骤.有效础性的难点问题.一般的边缘检测方法，如Cany边 合理的图像分割能够为基于内容的图像检索、对象 缘检测算子，虽然能比较好地解决噪音过滤与边缘 分析等抽象出十分有用的信息，从而使得更高层的 定位、响应问题，但对自然景物图像往往出现过分割 图像理解成为可能1. 或欠分割23]的现象，难以取得满意的效果.同时， 所谓图像分割就是把图像分成若干个互不相交 受光照条件的影响，物体与背景的边缘模糊造成边 的小区域，并提取出感兴趣的目标的过程，即将图像 缘不连续，也使得一些基于边界特征的图像分割方 细分为构成它的子区域或对象.分割的程度取决于 法，如基于区域同质性的区域生长46]，很难做到很 要解决的问题.在实际应用中，当感兴趣的对象已经 好的分割效果.另外，物体具有多灰度的特性使得根 被分割出来时，就停止分割.常用的图像分割方法主 据图像灰度直方图的分割方法，如最大类间熵，在实 要有：阈值化分割、基于边缘检测的分割、基于区域 际中也缺乏必要的稳健性刃 的分割、基于形态学分水岭的分割、聚类分割等.但 K均值分割是聚类分割中比较常见的一种分割 是由于物体自身的复杂性，以及受图像获取条件等 方法，它对于噪声较小的图像分割可取得良好的效 收稿日期：20080901 果.由于该方法是对像素的视觉特征在特征空间聚 通信作者：刘咏梅.E-mail:liuyongmei@hrbeu.edu.cm 类，并没有考虑像素的空间位置信息，这就造成了在 空间位置上很接近的像素点在特征空间中却相距很
·68 智能系统学报 第5卷 远.为了有效地消除这种情况，本文对传统的K均 做为初始聚类中心；当T=1时，按随机方式选取. 值聚类分割方法进行了改进，提出了一种基于空间 2)计算每个像素点的类别，即按距离最小原则 位置约束的K均值图像分割方法.即对于图像像 式(1)将特征空间中所有特征点x分配到个聚类 素，不仅要考虑它们视觉特征的相似性，还要考虑在 中心的某一个聚类Z,(K)中，K为迭代次数，其初值 图像空间内其邻域内像素的类别情况，并据此对该 为1. 像素的类别做出修正，以此在K均值算法中引入像 D(K)=min{lx-Z(K)‖，i=1,2,…,k}. 素位置的先验信息 (1)》 1K均值聚类分割算法 则x∈S,(K).式中：S,(K)=arg max(N(K)). 3)对每个像素点，选取n×n大小的邻域，利用 聚类就是将待分类样本分成若干类，每个类内 邻域内多数像素点的类别来修正该像素所属的类别. 的样本具有很高的相似性，而各个类的样本之间的 即统计邻域内每个像素点所属的类别，采用投票法用 相似性很低.K均值聚类算法是常用的图像分割算 包含像素点最多的类别来修正当前像素点的类别， 法，其优点在于可以很方便地进行多阙值分割，而且 4)重新计算k个聚类中心Z(K+1),即求聚类 用于分割的特征也可以有多个[8 中包含特征点的均值向量， K均值聚类算法的主要思想是：选取一批样本 (2) 点做为初始聚类中心，并将所有样本进行初始聚类， 2+)=壳 然后进行迭代，修改聚类直到所选取的聚类准则函 式中：W为第j个聚类域S中的特征点数. 数的值满足要求后停止，该算法主要分以下步 5)如果新的聚类中心与原来重合，即若Z(K+ 骤： 1)=Z(K)则停止；否则，转到2). 1)随机选取k个初始聚类中心； 3实验结果分析 2)计算每个像素到个聚类中心的距离，找出 最小距离，并且把该像素归为该聚类中心的类别； 为了验证本文提出算法的有效性，采用了Corel图 3)重新调整k个聚类中心，即将每个类别的所 片库中的图像进行实验，实验的图像均为自然景物图 有像素点的均值向量作为新的聚类中心； 像.实验的硬件环境为Genuine Intel(R)CPUT24OO 4)判断新的聚类中心是否与上一次的聚类中 1.83GHz,1.00GB内存，操作系统为Microsoft Windows 心点重合，如果是则结束，不是则返回2) XP Home Edition,实验平台采用了Matlab7.0. 部分实验结果见图1.图1共5组图像，每一组 2 基于空间位置约束的K均值聚类 图像由3幅图片组成，其中第1列是原图像，第2列 分割算法 为K均值聚类分割算法的分割结果，第3列是本文 提出算法的分割结果.由图1可以看出，所提出的基 对于数字图像来讲，每个像素点对应特征空间 于空间位置约束的K均值分割算法的分割效果好 中的一个点.基于位置约束的K均值分割算法的基 于传统的K均值聚类分割算法， 本思想是在原来K均值聚类算法的基础上，在计算 聚类中心和重新计算每个像素的类别这2个步骤中 加入一个新的步骤，即在像素的局部邻域内采用投 票方法，利用邻域内多数像素点的类别来修正该像 素所属的类别.这样原本属于同一个对象，但是颜色 特征与其他像素不同的那些噪声像素就不会被错误 的分割到其他类别中.从而实现了对噪声的恰当分 割.该算法的具体描述见算法1. (a)图像编号1 算法1： 1)在特征空间中，选取k个初始聚类中心 Z(1)、Z2(1)、·、Z.(1).括号内为迭代次数.聚类 中心可以随机选取或按顺序选取前k个点.可采用 (b)图像编号2 变量T来控制，当T=0时表示按顺序选取前k个点
第1期 刘咏梅，等：基于空间位置约束的K均值图像分割 69… 参考文献： [1]章毓晋.图像工程[M].北京：清华大学出版社，2000： 73-75. (c)图像编号3 [2]ZHOU Junni,CAO Jianzhong,LIU Bo,et al.New image seg- mentation methods based on regionally minimal cost water- shed transform[J].Acta Photonica Sinica,2005,34(1): 142-145. (d)图像编号4 [3]DORIN C,VISVANATHAN R,PETER M.Kemel-based ob- ject tracking[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2003,25(5):564-577. [4]CHEN Qiuxiao,CHEN Shupeng,ZHOU Chenghu.Segmenta- tion approach for remote sensing images based on local hom- (e图像编号5 ogeneity gradient and its evaluation[J].Journal of Remote Sensing,2006,10(3):357-365. 图1本文算法与K均值聚类分割算法分割的结果比较 [5]LI Huihui,GUO Lei,LIU Hang.A region based remote sens- Fig.1 Comparing segment results between K-means clus- ing image fusion method[J].Acta Photonica Sinica,2005, tering and our method 34(12):1901-1905. 表1列出了进行实验的参数设置及运行时间情 [6]刘金梅，赵春晖.组合均值平移和区域合并的图像分割 况.对同一幅图像，2种算法采用了相同的参数设置 算法[J].哈尔滨工程大学学报，2008,29(10)：1126- 1130. 进行实验，以便进行比较.表1的参数设置中，k为 LIU Jinmei,ZHAO Chunhui.Image segmentation with 分割区域数，n×n为邻域窗口的大小. mean shift and region merging methods[J].Journal of Har 表1参数设置及运行时间 bin Engineering University,2008,9(10):1126-1130. Table 1 Parameters and run time [7]张海军，王春光，翟改膜.用小波分析进行基于遗传算法 图像 K均值聚类分割算法1运行 的2DMBV图像分割[J].自动化技术与应用，2008,27 编号 参数设置 算法运行时间/s 时间/s (4):15-18,23. 1 k=3,n=21 3.053756 4.367060 ZHANG Haijun,WANG Chunguang,ZHAI Gaixia.ZDMBV 2 k=4,n=21 0.747108 2.587962 image segmentation based on gentic algorithm with wavelet k=3,n=17 1.572898 5.094940 analysis[J].Techniques of Automation and Applications, 4 k=3,n=17 0.988414 45.343819 2008,27(4):15-18,23. 5 k=3,n=21 0.864361 9.700752 [8]刘健庄，涂予青.使用高效C均值聚类算法的图像阙值 化方法[J].电子科学学刊，1992,14(4)：424427. 4 结束语 LIU Jianzhuang,TU Yuqing.Thresholding of images using an efficient C-mean clustering algorithm[J].Joumal of E 通过考虑图像的空间位置信息，结合传统的K lectronics,1992,14(4):424-427. 均值聚类分割算法，提出了一种改进算法—基于 [9]杨淑莹.图像模式识别一VC++技术实现[M].北 空间位置约束的K均值聚类分割算法，并通过实验 京：清华大学出版社，2005：202-205. 结果证明了提出的算法对有些图像可以取得较K 作者简介： 均值聚类分割算法更好的效果.这说明在图像分割 刘咏梅，女，1973年生，副教授、硕 士生导师、博士.主要研究方向为模式 中加入空间位置信息是可以改善分割效果的，是对 识别、图像处理、生物信息学。 图像自身先验知识的一种合理利用. 由于本文算法以K均值算法为基础，因此与K 均值算法一样，对于初始聚类中的模型选择仍然很 敏感.而且，算法的改进是以运行时间换取精度的， 不可避免地存在时间复杂度高的问题，而且对有些 代丽洁，女，1983年生，硕士研究 图像的分割效果与原K均值聚类分割算法没有比 生，主要研究方向为图像处理与模式识 较明显的改善.因此，在将来的工作中，可以考虑如 别、图像标注。 何提高算法的运行效率、进一步改善分割结果，以及 对初始聚类中心的模型选择问题进行研究