基于分裂式K均值聚类的图像分割方法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于分裂式K均值聚类的图像分割方法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：
模糊C均值聚类(FCM)算法是一种有效的无监督图像分割方法，适用于任意分类数，不需要预知图像特征，但其聚类效果直接受待分类样本噪声和分类初始条件的影响。因此，提出了一种适用于彩色图像分割的分裂式KЬ值聚类(FKM)算法，该算法首先使用中值滤波对分类样本去噪，然后使用一种分裂聚类法对图像样本进行预分类，得到一组样本集初始划分，最后以这组划分为起点，使用基于概率距离的KЬ值聚类对图像分割进行迭代优化。实验结果表明，该算法可以避免FCM的误分类，诸如陷于中心死区、中心重叠和局部极小值，而且提高了分割速度。
ス丶词：
ブ型挤掷嗪牛 TP391.41
文献标志码：A
英文标题
Image segmentation by fissive KИmean clustering method
び⑽淖髡呙
ZHANG Jian, SONG Gang
び⑽牡刂(
School of Information Science and Engineering,Shandong University, Jinan Shandong 250100,China
英文摘要
)
Abstract:
Fuzzy CMeans (FCM) clustering algorithm is an efficient unsupervised segmentation method, which is suitable for any classification number without the need to predict the image characteristics, but its clustering result has direct impact from sample noise component and the set of initial conditions. Therefore, a Fissive KИMeans(FKM) clustering algorithm for color image segmentation was proposed, which firstly denoised the sample data using median filtering, then preclassified the image samples according to a fissive clustering method to get an initial partition of sample set, finally iteratively optimized segmentation using KИmeans clustering based on the rule of probability distance from the initial partition. The experimental results show that the algorithm can avoid the misclassification of FCM such as dead center, center overlapping and local minima, and accelerate the segmentation speed.
英文关键词
Key words:
image segmentation; Fissive KИMeans (FKM)；Fuzzy CMeans (FCM); clustering; unsupervised
0 引言
图像分割是指依据灰度、彩色、空间纹理、几何形状等特征把图像划分成若干个互不相交的区域,使得这些特征在同一区域内,表现出一致性或相似性,而在不同区域间表现出明显的不同［1］。分割图像是图像分析的关键步骤,分割结果的好坏直接影响最终图像分析质量和对象识别结果。尽管已经提出了很多用于图像分割和特征提取的方法，但由于图像种类多样和复杂程度不同，设计一种通用和有效的分割算法仍然具有重要的研究意义。目前图像分割方法主要有阈值法、区域提取法、聚类法和边沿检测法［2］4类，本文所提出的图像分割方法是一种聚类法。
聚类法是图像分割中较为实用的方法,它首先根据一定的规则将像素灰度等特征映射到几个区域的特征空间里,然后根据像素在特征空间的位置判定其所属的区域,并进行归类分割。通过聚类分割，在同一区域类的像素要比区域间的像素更相似。聚类法有硬聚类和模糊聚类两个分支。经典的KЬ值聚类是一种硬聚类方法，而模糊C均值（Fuzzy CMeans, FCM）［3］是一种模糊聚类的方法。在KЬ值聚类中，每个样本只属于一类，每次更新每个类别的中心只与该类别的样本有关；而在FCM中，每个样本同时属于多类，每次更新每个类别的中心要计算所有类的所有样本，从而对同一幅图像的分割，FCM的计算量一般要比KЬ值聚类大［4］。但是FCM实现了一种软分割，可以抵抗由于图像亮度不均匀造成的分割错误。由于这两种经典聚类方法都存在对图像噪声敏感，没有考虑图像的空间特性，而且分割的结果有效性直接与初始类均值的选择有关［5］的缺点，本文为克服上述缺点，引出一种分裂式KЬ值聚类(Fissive KИMeans, FKM)算法，以减小样本噪声和分类初始条件的影响。
1 图像分割框架
为了减少因图像噪声造成的分割错误，可以使用平滑滤波来消减噪声，但是，平滑处理也会损失图像细节信息，诸如图像边缘或边沿［6］。本文考虑使用中值滤波的方法来去除噪声和图像亮度的不均匀性，中值滤波法可以很好地保留图像的边沿信息同时去除噪声。KЬ值聚类算法是在样本各类具有同分布方差的前提下进行的迭代优化，而且优化也是建立在具有一组正确的初始类均值上的。如果以上前提不满足，KЬ值聚类的最终分割结果会陷于局部最优和误分割。本文提出一种类初始均值筛选方法，该方法是一种分裂聚类法，可以在预期时间内完成筛选，而且产生的筛选值分布尽量分散，以利于建立KЬ值聚类的分割条件。同时，以概率距离作为重新划分的基础，这样，聚类分割就可以适用于样本分布方差不同的情况。以下是FKM图像分割的步骤：
1）对图像进行中值滤波去噪和加强各区域低频分量；
2）对图像进行分裂聚类预分割；
3）将预分割图像的划分作为KЬ值聚类的初始划分；
4）对预分割图像进行KЬ值聚类分割；
5）返回最后的聚类分割图像作为图像的分割结果。
2 图像空间特征度量
彩色图像分割后形成一组区域，区域间的色度差异较大而区域内色度相近，因此找到各区域的代表色，就可以依色度分布将图像划分为区域，所以可以选取像素颜色作为分类的样本。图像像素的颜色由R、G、B3个分量组成，取样本特征向量f=［R,G,B］T,R、G、B分别为彩色图像各像素在RGB空间的颜色分量，以下给出对颜色空间聚类的一组参量定义。
样本间距离度量定义为：
d(f1,f2)=f1－f2=(R1－R2)2+(G1－G2)2+(B1－B2)2(1)
其中：两个样本f1=［R1,G1,B1］T, f2=［R2,G2,B2］T。
类内均值ui和方差σ2i 定义为:
ui=1ni∑fj∈Cifj (2)
σ2i= 1ni ∑fj ∈Ci d(fj ,ui )(3)
其中ni为Ci类的样本总数。И
а本点fk与第i类Ci的欧氏距离度量定义为：
Dist(fk,Ci)=d(fk,ui)(4)
其中ui为Ci类的类内均值。
样本点fk与第i类Ci的概率距离度量定义为：
DistPr(fk ,Ci ) = d(fk ,ui )/σ2i (5)
其中ui为Ci类的类内均值；
两次划分的距离定义为:
ε=∑Ki=1(d(u1i,u2i)+|σ2i1－σ2i2|)(6)
其中：uji为第j种划分的第i类Cji的类内均值；σ2ji为第i种划分的第j类Cj的类内方差。
┑2期
张健等：基于分裂式K均值聚类的图像分割方法
┆扑慊应用 ┑31卷
3 图像去噪和类初始均值估计
3.1 中值滤波
由于KЬ值聚类法没有利用图像的区域特征且易受噪声样本的影响，所以对于图像中的颗粒噪声只会以其色度来分类而不会滤除。通过中值滤波一方面可以既消减噪声又保留图像边沿信息；另一方面使得滤波后每个样本成为一个邻域的代表样本。中值滤波定义为：
f(x,y)=middle(σ)
σ={im(i,j)|i∈［x－w,x+w］;j∈［y－w,y+w］}(7)
其中：middle()为取集合中元素的中间值；Е椅图像以（x,y）坐标为中心，边长为2w+1的方块的像素集合; f(x,y)为滤波后坐标(x,y)处的像素值；im（i,j）为原图像坐标(i,j)处的像素值。
3.2 分裂聚类
待划分样本的类均值分布反应了各类的分布，若两个类均值相近，则表明这两类分布有重叠部分。通过使用尽量分散的类均值，可以期望得到一组类间分散的分割区域。分裂聚类可以有效地分离类均值，每次重新划分，将最低样本归属度的样本分离为一个新类的样本，这样可以使由于新划分造成的误分类最小。在样本集各类同为方差相同的高斯分布时， fi∈Ck的概率密度正比于exp(－Dist(fk,Ci))，从而Dist(fk,Ci)为最大的fk是需要分裂的样本。
其算法按以下步骤进行。
1）置样本集S={fi|i∈［1,N］}的初始类别数k=1，随机抽取1个样本fi作为C1类均值u1的初始估计；
2）遍历k类集合Ci(i∈［1,k］)，找到k类中离各类中心ui最远点fm=┆argmaxfj∈Ci(i∈［1,k］)(d(fj,ui)),增加一个均值向量uk+1=fm, 样本集类数k=k+1;
3) 对样本集的N个样本fj逐一依照各自最近的均值Ci,i=┆argmink(Dist(fj,Ck))进行k类划分Sk={Ci|i∈［1,k］}；
4) 依据样本集划分Sk，重新计算k类均值ui；
5)若k
6) 返回最后一次的样本集划分SK作为对样本集S的K类划分。И
4 KЬ值聚类
若图像分割的各类服从高斯分布N(ui,σ2i)， 则fi∈Ck的概率密度正比于exp(－DistPr(fk,Ci))，同时若样本属于各类的先验概率相同，则由贝叶斯决策理论可知，样本fi∈Ck的后验概率也正比于exp(－DistPr(fk,Ci))，从而以样本最大后验概率归属来划分，可以使分割方法适用于高斯型样本集的不同分布方差集。本文改进的K均值聚类使用基于概率距离的度量方法，不断更新各类分布参数直到不再改变。И
其具体算法步骤如下：
1）给定样本集S={fi|i∈［1,N］}的K类初始划分Ci和变动系数δ；
2）对样本集的N个样本fj逐一依照各自最近的类Ci(i=┆argmink(DistPr(fj,Ck)))进行K类划分SK={Ci|i∈［1,K］}；
3）依据样本集划分SK，重新计算K类样本均值和方差ui、σi；
4）若样本集划分SK有变动，即ε>δ，使用式6），就转2），否则继续；
5）返回最后一次的样本集划分SK作为对样本集S的K类划分。И
5 实验结果与分析
下面，通过5组图像的分割实验来验证本文提出算法的有效性。实验环境为Matlab 7.0编程环境。测试图像如┩1~4所示。由于FCM对每个样本使用模糊归属度，这样得到的分类中心要比KЬ值聚类的更准确，从而最终的分割区域也要比KЬ值聚类的平滑，所以对比使用FKM和FCM聚类两种情况下的分割效果。图像分割的性能主要由两方面决定：错误分割的比例和分割所用时间。由于FCM和FKM的时间复杂度都可以表示为O(ndcT),其中n为样本数，d为样本特征维数，c为分类数，T为聚类所需迭代次数，n等于图像的像素个数，d等于3，所以造成FCM和FKM方法计算时间差异的主要参数就是聚类迭代次数T，因此表1统计了两种聚类方法迭代次数的比较。И
图片
表格(有表名)
表1 FCM方法与FKM方法的迭代次数和分割时间比较
图像名分类数
迭代次数
FCMFKM
总分割时间/s
FCMFKM
moonlight314926.3211．83
geometry5171030.2112.45
coin27421.537.78
grain4271535.6716.75
就各组图像的分割结果做出如下分析：
1）在图1和图2中，FCM方法对原图像都存在严重的误分割：moonlight图中的月亮被判为背景，geometry图中的三角形与环形被判为一体，说明分割结果陷于中心重叠；而FKM方法则准确地分辨了图1和图2中的各个对象。
2）在图3和图4中，要求对有噪图像进行分割。从coin图的分割结果，可以明显看出FCM方法无法抵抗噪声，也没有利用区域特征来分割，从而误分割比例明显大于FKM方法的分割效果。FCM使用收敛后的聚类中心对样本归属去模糊，从而实现图像分割，但是由于样本没有包含图像的局部区域信息，以致coin图中的噪声依靠颜色相近被误分类。FKM在分割前使用中值滤波，一方面去除噪声；另一方面，增强了区域低频分量，这有利于降低误分割。在grain图中，由于叠加的噪声，FCM方法没有将稻谷田判为一类，并且上方的蓝天和白云也混为一类，而FKM方法则给出了grain图的理想四块区域的分割。在这两幅图中，FKM的误分割率是明显低于FCM方法的。
3）由于分裂聚类预分割的迭代次数等于分类数，从表1可见，预分割所占分割总时间近似为3/9，5/9，2/4，4/15，每幅图的预分割时间比例都大于1/4，FKM的平均迭代次数和平均分割时间都要小于FCM方法，尤其在多类分割时，FKM比FCM方法收敛地更快，从以上4幅图的分割结果来看，FKM的平均误分割率是远小于FCM方法的，这说明预分割所提取的有效类初始分布参数为进一步分割建立了正确的方向。同时由于在KЬ值聚类中使用概率距离度量样本归属度，使得新分割方法适用于以上4幅不同图像结构的图。
6 结语
本文FKM算法通过使用中值滤波对图像去噪和融合样本邻域信息，再用分裂聚类对图像预分类，最后通过基于概率距的KЬ值聚类进行图像优化分类。实验结果表明，该算法可以减小噪声样本对分割结果的影响，避免陷入中心死区和中心重叠以及局部极小值问题。同时，通过使用适应度分裂聚类的预分割提高了分割准确性和分割速度；基于概率距的KЬ值聚类也使分割方法可以适应更多不同类型的图像，但是如何进一步利用图像的区域特征，使该方法可以适用于各种纹理图像是下一步要继续研究的课题。
げ慰嘉南:
［1］CHENG H D, JIANG X H. SUN H, et al. Color image segmentation:advances and prospects［J］. Pattern Recognition, 2001,34 (12) : 2259-2281.ぃ2］
何俊,葛红,王玉峰.图像分割算法研究综述［J］.计算机工程与科学,2009,31(12):58-61.
ぃ3］
ISA N A M,SALAMAH SA,NGAH UK,Adaptive fuzzy moving Kmean clustering algorithm for image segmentation［J］. IEEE Transactions on Consumer Electronics,2009,55(4):2145-2146.
ぃ4］
丁震山，胡钟山，杨静宇，等. FCM 算法用于灰度图象分割的研究［J］. 电子学报，1997，25(5)：39-43.
ぃ5］
KIM T, BEZDEK JC, HATHAWAY R J. Optimality tests for the fixed points of the fuzzy cmeans algorithms［J］. Pattern Recognition，1988，21(6)：651-663.
ぃ6］
KRINIDIS S, CHATZIS V. A robust fuzzy local information cmeans clustering algorithm［J］ . IEEE Transactions on Image Processing,2010,19(5):1328-1329.