K均值算法图像分割

3.2K均值聚类分割算法 3.2.1 聚类

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法。聚类分析计算方法主要有如下几种：划分方法，层次方法，基于密度的方法，基于网格的方法，基于模型的方法。

K-均值聚类算法是著名的划分聚类分割方法。划分方法的基本思想是：给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K

3.2.2 K-均值聚类算法的工作原理：

K-means算法的工作原理：算法首先随机从数据集中选取 K个点作为初始聚类中心，然后计算各个样本到聚类中的距离，把样本归到离它最近的那个聚类中心所在的类。计算新形成的每一个聚类的数据对象的平均值来得到新的聚类中心，如果相邻两次的聚类中心没有任何变化，说明样本调整结束，聚类准则函数 已经收敛。本算法的一个特点是在每次迭代中都要考察每个样本的分类是否正确。若不正确，就要调整，在全部样本调整完后，再修改聚类中心，进入下一次迭代。这个过程将不断重复直到满足某个终止条件，终止条件可以是以下任何一个：

（1）没有对象被重新分配给不同的聚类。

（2）聚类中心再发生变化。 （3）误差平方和局部最小。 3.2.3 K-means聚类算法的一般步骤：

处理流程：

（1） 从 n个数据对象任意选择 k 个对象作为初始聚类中心； （2） 循环（3）到（4）直到每个聚类不再发生变化为止；

（3） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；

（4） 重新计算每个（有变化）聚类的均值（中心对象），直到聚类中心不再变化。这种划分使得下式最小

13

E??k2j?1xi???xi?mj

j3.2.4 K-均值聚类法的缺点：

缺点:

（1）在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。 （2）在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。

（3） K-means算法需要不断地进行样本分类调整不断地计算调整后的新的聚类中心因此当数据量非常大时算法的时间开销是非常大的。

（4）K-means算法对一些离散点和初始k值敏感，不同的距离初始值对同样的数据样本可能得到不同的结果。

3.3．基于灰度空间的彩色图像像素聚类

1．读取彩色图像，将RGB值转化为灰度值

2. 利用k均值聚类对像素的灰度值进行划分，提取特征点（本方法采用误差平方和准则函数判断聚类是否合理）。 3.利用matlab编程实现结果如下： 随即地取c1(1)=25; c2(1)=125;

c3(1)=200;%选择三个初始聚类中心

图1

得到最终聚类中心的灰度值如下：

14

R =109.5763 G =158.0943 B =212.8034 随机选取聚类中心的K-均值聚类结果：

图2

3.4改进的k-均值聚类图像分割算法

4.1 K-均值聚类算法中重要的一步是初始聚类中心的选取，一般是随机选取待聚类样本

集的K个样本，聚类的性能与初始聚类中心的选取有关，聚类的结果与样本的位置有极大的相关性。一旦这 K个样本选取不合理，将会增加运算的复杂程度，误导聚类过程，得到不合理的聚类结果。通过粗糙集理论提供 K-均值聚类所需要的初始类的个数和均值，提高了聚类的效率和分类的精度。

于粗糙集理论的灰度空间划分

1.粗糙集的研究对象是由一个多值属性集合描述的对象集合。主要思想是在保持分类能力不变的情况下，通过知识约简，导出问题的决策和分类规则[4]。粗糙集理论能很好地近似分类。从图像的直方图可以看出图形一般呈谷峰状分布，同一区域内像素的灰度值比较接近，而且不同区域内像素数大小不等。若灰度值相差不大的像素可归为一类，则可将图像分为几类。为此，定义像素的灰度值差为条件属性，等价关系R定义为：如果两个像素灰度值差小于定间距D，则两个像素是相关的，属于等价类。

首先确定间距D，通过原图可求出灰度值分布范围，根据灰度值范围可求出灰度级数L。将灰度级范围内对应像素个数最多的灰度值定义为中心点P。计算L个中心点之两两间距，若最小距离小于间距D，则将相应中心点合并，并将两点的算术平均值作为该中心点的值。

15

重复进行直到所有中心点的两两间距均大于间距D。中心点的个数和数值就是K_均值聚类所需要的初始类的个数和均值。

2.像素的灰度值为xp(p?0,1,其中Q(ji)为第 i次迭代后赋给类j的像素集合, ,255)，

?j为第 j类的均值。

具体步骤如下：

① 将粗糙集理论提供的L个中心点P作为初始类均值

?1(1),?2(2),,?l(l)。

② 在第i次迭代时，考察每个像素，计算它与每个灰度级的均值之间的间距，即它与聚类中心的距离 D，将每个像素赋均值距其最近的类，即

Dxp??l(i)?minDxp??j(i),(j?1,2,则xp?Q(ji)。 ③对于j?1,2,?l) (3.6)

?(i?1)?1/Njl,计算新的聚类中心，更新类均值:?jx?Q(ji)?xp，式中，Nj是Q(ji)中的像素个数。

④将所有像素逐个考察，如果j?1,2,否则返回②继续下一次迭代。

⑤ 以上聚类过程结束后，为了增强显示效果，分割结果各像素以聚类中心灰度值作为该类最终灰度

由原图像的灰度直方图，本文将定间距D设为32，灰度级L的个数为8。原灰度图的灰度值范围为[0，255]，被分成8个灰度级，七个灰度级对应中心点P为{32，64，96，128，160，192，224，256}。计算这12个中心点之两两间距，若最小距离小于间距20，则将相应中心点合并，并将两点的算术平均值作为该中心点的值，处理后结果P{32,160，192}

下面将c1(1)=32;c2(1)=160;c3(1)=192;作为初始聚类中心，编程进行聚类分析。得到结果如下：

K，有 ?j(i?1)??j(i)，则算法收敛，结束；

16