3.7　基于聚类分析的图像分割方法

利用特征空间聚类法来分割图像，就是将图像空间中的像素用对应的特征空间点表示，利用它们在特征空间的聚集对特征空间进行分割，然后将它们映射回原图像空间，得到分割结果。其中，K均值算法、模糊C均值聚类算法（FCM）是最常用的聚类算法。

对于K均值算法而言，要先选K个初始类均值，然后将每个像素归入均值离它最近的类并计算新的类均值。迭代执行前面的步骤直到新旧类均值之差小于某一阈值。模糊C均值聚类算法是在模糊数学基础上对K均值算法的推广，是通过最优化一个模糊目标函数方式来实现聚类，它不像K均值聚类那样认为每个点只能属于某一类，而是赋予每个点对各类的隶属度，用隶属度能更好地描述边缘像素亦此亦彼的特点，适合处理事物内在的不确定性。

3.7.1　K均值聚类分割算法

3.7.1.1　聚类

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

K均值聚类算法是常见的划分聚类分割方法，其基本思想是：给定一个有N个元组或者记录的数据集，利用分裂法将其构造成K个分组，每一个分组就代表一个聚类，K<N。而且这K个分组满足下列条件：（1）每一个分组至少包含一个数据记录；（2）每一个数据记录属于且仅属于一个分组。对于给定的K，算法首先给出一个初始的分组方法，然后通过反复迭代的方式来改变分组，使得每一次改进之后的分组方案都较前一次好。而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的记录越远越好。

3.7.1.2　K均值聚类算法的工作原理

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

3.7.1.3　K-means聚类算法的一般步骤

该算法主要包括以下几个步骤：

（1）从n个数据对象中任意选择k个对象作为初始聚类中心；

（2）循环（3）到（4）直到每个聚类不再发生变化为止；

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

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

3.7.1.4　K均值聚类法的问题

在应用过程中，K均值聚类法也存在一些问题，主要包括：

（1）K是事先给定的，这个K值的选定是很难估计的。

（2）需要根据初始聚类中心来确定一个初始划分，然后对初始划分再进行优化。

（3）需要不断对样本进行分类调整，不断计算调整后新的聚类中心，当数据量非常大时，算法耗时非常长。

（4）在样本数据相同的情况下，初始值的距离不同，得到的结果可能不同。

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

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

粗糙集的研究对象是由一个多值属性集合描述的对象集合，主要思想是在保持分类能力不变的情况下，通过知识约简，导出问题的决策和分类规则。从图像的直方图可以看出，图形一般呈谷峰状分布，同一区域内像素的灰度值比较接近，而不同区域内像素的灰度值大小不等。若灰度值相差不大的像素可归为一类，则可将图像分为几类。

为此，定义像素的灰度值差为条件属性，等价关系R可定义为：如果两个像素灰度值差小于给定间距D，则两个像素是相关的，它们属于等价类，即有R-{z‖z。-z，I<D}（i，J-0，1，…，255）。在计算过程中，先确定间距D，通过原图可求出灰度值的分布范围，再根据灰度值范围可求出灰度级数L。将灰度级范围内对应像素个数最多的灰度值定义为中心点P。计算L个中心点之两两间距，若最小距离小于间距D，则将相应的中心点合并，并将两点的算术平均值作为该中心点的值。重复进行上述步骤直到所有中心点的两两间距均大于间距D。中心点的个数和均值就是K均值聚类所需要的初始类的个数和均值。

像素的灰度值为x_p（p=0，1，…，255），其中为第i次迭代后赋给类j的像素集合，μ_j为第j类的均值。具体步骤如下：

（1）将粗糙集理论提供的L个中心点P作为初始类均值，，…，。

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

则x_p。

（3）对于j=1，2，…，l，计算新的聚类中心，更新类均值：，式中，N_j是中的像素个数。

（4）将所有像素逐个考察，如果j=1，2，…，K，有μ^（i+1）_j=μ^（i）_j，则算法收敛，结束；否则返回（2）继续下一次迭代。

（5）以上聚类过程结束后，为了增强显示效果，各像素以聚类中心灰度值作为该类的最终灰度值。

实验表明，基于粗糙集理论和K均值聚类算法的图像分割方法，减小了运算量，提高了分类精度和准确性，而且对于低对比度、多层次变化背景的图像的形状特征提取，具有轮廓清晰、算法运行速度快等特点，是一种有效的灰度图像分割算法。