基于改进的K均值聚类彩色图像分割方法

摘要:提出了一种改进的K均值聚类图像分割方法。针对彩色图像的像素特征,利用Ohta等人的研究成果,选取能有效表示彩色像素特征的彩色特征集中的第一个分量作为图像像素的一维特征向量,用来替代经典K均值聚类图像分割中的灰度,大大降低了运算量。基于粗糙集理论的算法,求出初始聚类个数与均值。选用对特征空间结构没有特殊要求的特征距离代替欧氏距离,应用改进的K均值聚类算法对样本数据进行聚类,从而实现对彩色图像的快速自动分割。实验表明,该图像分割算法可有效提高图像分类的精度和准确度,并且运算代价小,收敛速度快。

关键词:图像分割;粗糙集;K均值聚类;特征向量

中图分类号:TP182文献标识码:A文章编号:1009-3044(2010)04-0962-03

Color Image Segmentation Method Based on an Improved K-means Clustering Algorithm

WANG Hui1, SHEN Shi-lei1,2

(1.School of Computer & Information Engineering, Henan University, Kaifeng 475004, China; puting Center, Henan University, Kaifeng 475004,China)

Abstract: A new image segmentation method based on an improved K-means clustering algorithm is proposed in this paper. To reduce the computational cost, the first component of color feature set discovered by Ohta et al. is chosen as the one-dimensional eigenvector. It is used as the image gray in the image segmentation method employing the classic K-means clustering method. Applying the algorithm based on the rough set theory, the number and the centroids of the clusters are obtained, which initialize the kernel K-means clustering. Feature distance, which is suitable for any structure of eigenvector space, is used instead of Euclidian distance to overcome the influence caused by the structure of eigenvector space. Then an improved K-means clustering algorithm is introduced to cluster the sample data. Experimental results show that the presented image segmentation method can effectively improve the precision and accuracy of image segmentation, and has small computational cost and fast convergence speed.

Key words: image segmentation; rough sets; K-means clustering; eigenvector

在计算机视觉和图像分析中,如何把目标物体从图像中有效分割出来一直是个经典难题之一,它决定图像的最终分析质量和模式识别的判别结果。图像分割是指将图像中具有特殊意义的不同区域分开来,并使这些区域相互不相交,且每个区域应满足特定区域的一致性条件。图像一旦被分割,就可作进一步的处理,如基于内容的图像检索、分类及识别等。因此,图像分割是图像处理和模式识别中的一个重要研究领域。

目前图像分割的算法主要有阈值分割法、边缘提取法、区域分割法、分水岭分割法等[1],这些分割算法各有优缺点。近年来,许多研究人员提出用聚类算法来分割图像[2],并取得了较好的实验结果。但如何初始划分(分类)样本以及选择代表点将直接影响分割的效果。在以往的研究中,基于K均值聚类及其改进算法的图像分割技术受到了广泛关注。K均值聚类是聚类方法中一种无监督动态算法,具有一定的自适应性,但聚类结果易受初始聚类中心的影响。基于传统K均值聚类的图像分割算法存在如下缺陷:①直接针对像素样本集进行聚类,运算代价太大,耗时长;②使用欧氏距离来度量各个特征向量之间的差异,这种度量方法要求样本数据在特征空间呈球形或椭球形分布,然而样本数据在特征空间的结构多样,不一定能满足这种特殊要求,从而会对聚类结果产生影响。

在以上研究的基础上,本文提出了一种改进的K均值聚类图像分割方法。首先根据Ohta等人提出的彩色图像分析方法,选取彩色图像的彩色特征集中的第一个分量作为图像像素的一维特征向量,用来替代传统K均值聚类图像分割中的灰度。再基于粗糙集理论,求出初始聚类的个数与均值。选用对特征空间结构没有特殊要求的特征距离代替欧氏距离,从而减少特征空间结构对聚类结果的影响。最后利用改进的K均值聚类算法对样本数据进行聚类,实现对彩色图像的快速自动分割。实验结果表明,该图像分割方法可有效提高彩色图像分类的精度和准确度,并且运算代价小,收敛速度快。

1 初始聚类中心与个数的确定

1967年,MacQuen首次提出K均值聚类算法[3],该算法是解决聚类问题的一种经典算法。K均值算法的基本思想是:对于给定的聚类数目k,首先随机选择k个对象,每个对象初始地代表一个聚类的平均值或中心。对剩余的每个对象,根据其与各个聚类中心的距离,将它赋给最近的聚类。然后重新计算每个聚类的平均值,对数据库中的每个对象与每个聚类的平均值相比较,把对象赋给最相似的某个聚类。重复执行该过程,直到准则函数收敛使平方误差函数值最小。

K均值聚类算法中重要的一步是初始聚类中心的选取,一般是随机选取待聚类样本集的k个样本,聚类的性能与初始聚类中心的选取有关,聚类的结果与样本的位置有极大的相关性。若这k个样本选取不合理,将会增加运算的复杂程度,误导聚类过程,得到不合理的聚类结果。为提高聚类的效率和分类的精度,我们根据粗糙集理论来确定K均值聚类所需要的初始类的个数和均值[4]。

令知识系统K=(U,R)表示图像信息,R表示图像中的等价关系。利用不可分辨关系计算图像像素的灰度值,计算规则是定义的等价关系R,从而求出初始聚类中心和个数。对于有M×N个像素组成的图像U,其直方图一般呈谷峰状分布,同一区域内像素的灰度值比较接近,且不同区域内像素数不相等。灰度值相近的像素可归为一类,这样可将图像分为几类。假设灰度值xi为集合U的一个对象,φ(xi)(i=1,2,…,255)表示灰度值为xi的像素的个数。定义像素的灰度值差为条件属性,等价关系R定义为:如果两个像素灰度值差小于定间距d,则两个像素是相关的,属于等价类,可用下式表示:

(1)

具体方法为:首先确定间距阈值d,通过直方图可求出灰度值分布范围,根据灰度值范围可以求出灰度级数L;对于每一个灰度级而言,将该灰度级范围内象素个数最多的灰度值定义为中心点。计算L个中心点之间的两两间距,若最小距离小于阈值d,则将相应中心点合并,并将两点的算术均值作为该中心点的值;重复以上过程,直到所有中心点的两两间距均大于d。最终所求得的中心点的个数和数值就是K均值聚类所需要的初始聚类中心和个数。

2 基于改进的K均值聚类彩色图像分割

以往的一些K均值聚类和模糊K均值聚类图像分割算法直接针对图像的像素集合进行聚类,聚类规模很大,随之而来的是巨大的计算量以及大量的时间消耗。为了解决这一问题,人们提出将灰度图像像素空间映射到其灰度直方图特征空间中,从而把针对像素集合进行的聚类映射成针对灰度级集合进行的聚类,大大提高了对灰度图像的分割速度。在实际应用中,许多图像处理的对象都是彩色图像,表征彩色像素需要RGB三个分量,不能直接应用K均值或模糊K均值聚类图像分割算法来处理彩色图像。日本学者Ohta等人[5]通过对大量的彩色图像区域分割实验,得到一个适合进行彩色图像分割的彩色特征集

(2)

实验证明,仅使用I1分量就可有效进行彩色图像分割。

2.1 特征距离

传统K均值聚类算法常使用欧氏距离来度量待分类对象与各类具有代表性的典型对象间的差异,但这种距离测度要求样本数据在特征空间呈球形或椭球形分布,然而样本数据在特征空间的结构是多样的,且真实数据中很少有紧致、界限清晰、比例均匀的类群。这就需要一种对向量空间结构没有严格限制的向量距离度量方法,而特征距离[6]能满足这一要求,并具有较强的普适能力,其定义如下:

定义1 设样本向量f=(f1,f2,…,fn),g=(g1,g2,…,gn)∈Rn(Rn为向量空间),则特征距离向量S=(d1,d2,…,dn)T中的各个分量定义为:

(3)

定义特征距离为特征距离向量的内积范数,即

2.2 改进的K均值聚类算法

根据Ohta等人的研究成果,本文使用I1分量作为彩色图像像素的一维特征量,用I1分量代替K均值聚类图像分割中的灰度。用T表示像素点的数目,I1p∈{0,1,…,Lmax-1}(p=1,2,…,T),I1p为集合Ai(j)中像素的灰度值。Lmax为I1的亮度级数,λi(j)为第j次迭代后第i类的均值,Ai(j)表示第j次迭代后第i类的像素集合。本文提出的改进的K均值聚类算法步骤如下:

1)根据I1分量,应用粗糙集理论选取K均值聚类所需要的初始聚类个数k和均值λi(0)(i=1,2,…,k)。

2)对于每个像素,保存它与第j-1次迭代时的聚类均值的距离Di(j-1)(i=1,2,…,k);在第j次迭代时,考察每个像素, 首先计算它与上次聚类更新后(即第j-1次)均值的距离,得到新的距离Di(j),其中, ■。如果Di(j)≤Di(j-1),则像素点i仍然保留在原来的聚类中,无须计算它与其它聚类均值的距离[7]。这里的距离指的是2.1节定义的特征距离。

3)对于i=1,2,…,k,计算新的聚类中心,按照下式更新类均值:

式中,x∈Ai(j)表示集合Ai(j)中任意像素x,Nj表示集合Ai(j)中的像素个数。求误差平方和准则E(j)为:

这里, ||Ilp-λi(j)||指的是特征距离。

4)若|E(j)-E(j-1)|< ε,则算法结束;否则,j=j+1,转(2),继续执行。

3 图像分割实验

为了验证本文所提出的彩色图像分割算法的有效性和可行性,从选用不同的距离测度、聚类算法运行时间及图像分割效果三个方面来进行实验。

1)选用欧氏距离与特征距离的实验结果比较:图1(a)为原彩色图像,根据文献[5]中的方法,我们选用I1分量作为彩色图像像素的一维特征量,用I1分量代替K均值聚类图像分割中的灰度。选取间距阈值d=30,亮度级个数Lmax=11,各亮度级对应的中心点为{36,50,84,112,121,135,146,188,217,240},通过粗糙集理论可求得K均值聚类初始聚类个数为5,各类初始均值为{43,84,136,203,240}。图1为实验结果。图1(b)为当选用欧氏距离,使用本文算法的分割结果;图1(c)为当选用特征距离,使用本文算法的图像分割结果。从图中可看出,图1(b)的图像分割细节明显好于图1(c)。可见,选用特征距离的图像分割效果明显好于选用欧氏距离的图像分割效果。

(a)原始图像 (b) 使用欧氏距离的分割结果 (c) 使用特征距离的分割结果

图1 分别使用欧氏距离与特征距离的图像分割结果比较

2)选用传统K均值聚类图像分割算法和本文算法图像分割效果比较:与 (1)中的方法类似,根据原始图像图2(a)和粗糙集理论,可求得初始聚类个数为5。图2(b)给出了选用传统K均值聚类图像分割方法的分割效果,图2(c)给出了选用本文算法时的图像分割效果。与图2(b)相比,图2(c)的图像边缘更清晰,分割结果既突出了目标,又保留了细节信息,达到了比较理想的分割效果。因此,本文分割算法要优于基于传统K均值聚类的分割算法。

(a) 原始图像 (b) 使用K均值聚类算法的分割结果(c) 使用本文算法的分割结果

图2 使用不同分割算法的图像处理结果

3)选用不同图像分割算法时的分割速度比较:分别选用传统K均值聚类算法、快速模糊K均值聚类算法和本文算法进行图像分割实验,图3为三幅不同像素的原始图像。表1所示为对各图像进行分割的相关数据,表中k表示聚类方法最终确定的聚类数目,t表示对图像分割所需要的时间。图4是三种图像分割算法所需要的运行时间曲线图,图中,“”表示使用传统K均值聚类算法所需要的时间,“”表示使用快速模糊K均值聚类算法所需要的时间,“”表示使用本文算法所需要的时间。从表1中各算法所需要的处理时间和图4的时间曲线可看出,本文提出图像分割算法聚类速度快,明显优于其它两种方法。

图3 待分割的原始图像

5 结论

K均值聚类方法是一种无监督动态算法。K均值聚类的结果易受聚类中心的个数及初始聚类中心的影响,同时也受样本的几何形状的影响。针对以上问题,本文提出了一种改进的K均值聚类算法,基于粗糙集理论确定K均值聚类的初始类个数与类中心;利用Ohta等人的研究成果,选取能有效表示彩色像素特征的彩色特征集中的第一个分量作为图像像素的一维特征向量,用来替代经典K均值聚类图像分割中的灰度,大大降低了运算量;K均值聚类的距离测度选用特征距离,提高了算法的适用性和准确性。实验表明,本文提出的图像分割算法可有效提高图像分类的精度和准确度,并且运算代价小,收敛速度快。

参考文献:

[1] Pal N R, Pal S K. A review on image segmentation techniques[J]. Pattern Recognition,1993,26(9):1277-1294.

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

[3] MacQueen J B. Some methods for classification and analysis of multivariate observations[C].The 5th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, USA: University of California Press, 1967: 281-297.

[4] 邵锐,巫兆聪,钟世明.基于粗糙集的K-均值聚类算法在遥感影像分割中的应用[J].现代测绘,2005,28(2):3-5.

[5] Ohta Y, Kanade T, Sakai T. Color information for region segmentation. Computer Graphics and Image Processing,1980,13(3):222-241.

[6] 张新明,沈兰荪,沈波.基于特征距离的阈值法及其在眼科图象分割中的应用[J].中国图象图形学报,2001,6(2):159-163.

[7] Fahim A M, Salem A M, Torkey F A, Ramadan M A. An efficient enhanced k-means clustering algorithm. Journal of Zhejiang University Science A, 2006, 7(10): 1626-1633.

注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文