5.2 常用的图像聚类分割算法

在图像分割中，根据图像中要处理的数据、分割的目的以及用途，可选取不同的聚类算法以实现图像分割的目的，目前常用于图像分割的聚类算法大体上可分为划分聚类算法、层次聚类算法、基于密度的聚类算法、基于模型的聚类算法以及基于网格的聚类算法。

5.2.1 划分聚类算法

划分聚类算法采用目标函数最小化策略把一个确定的N个数据对象的数据集分成k个组，并且该算法使得每一组中的对象相似度相当高，而不同组的对象相似度比较低，由此可知相似度的定义是划分聚类算法的关键环节。该算法的目标函数一般定义为式（5-5），其中x_i表示对象空间中一个数据对象，且x_i是第i类的均值，J为集合A中全部对象与对应的聚类中心的均方差之和。最常用的划分聚类算法包含k-means算法和k-medoids算法。

1.k-means算法

k-means算法的原理是将恒定的N个数据目标的数据集分成事先给定的数目为k的簇，首先随机选择k个对象作为初始的k个聚类中心C=（C₁，C₂，…，C_k），接着通过算出其余的所有样本到各自聚类中心的距离，把该样本划分到距离它很近的类中，之后再使用平均值的方法计算调整后的新类的聚类中心，重复上述步骤直到计算出的两次类中心保持不变时，标志着数据集中的样本分类结束且聚类平均误差准则函数F处于收敛状态，聚类平均误差准则函数F的表达式见式（5-6），其中q为数据集的数据对象，m_i是第i类聚类中心C_i的平均值，F代表数据集中全部数据对象的平方误差的总和。

k-means算法虽然容易实现，但是该算法也具有一些缺陷：k-means算法当选用不一样的初始值时，能够得到不相同的聚类结果，因此该算法对初始聚类中心的依赖性较大；k-means算法对独立点及噪声点反应较为敏锐，严重时会导致聚类中心的偏离；k-means算法需要预先掌握的知识来求出待生成的簇的数目。

2.k-medoids算法

k-medoids算法的处理过程如下：先随意选出k个对象作为初始的k个聚类的代表点，接着算出其余的样本到其最靠近聚类中心的对象的距离，把该样本归类到离它最近的聚类中，并依据某代价函数估算目标与代表点间的相异度平均值，若对象与代表点相似则替换代表点，反复进行上述过程直到不再有对象替换代表点为止。k-medoids算法包括PAM算法、CLARANS算法以及CLARA算法。当数据集和簇的数目较大时，PAM算法的性能就会变得很差；CLARANS算法不能辨认套嵌或其余繁杂形状的聚类形状，而且该算法具有运算效率低、没有处理高维数据的能力以及不能准确找到局部极小点产生错误的聚类结果的缺陷；CLARA算法的聚类结果与抽样的样本大小有关，当抽样的样本发生偏差时，CLARA算法的性能就会变差而不能得到良好的聚类结果。

5.2.2 层次聚类算法

层次聚类算法分为凝聚层次聚类算法和分裂层次聚类算法。凝聚层次聚类认为每一个对象是一个簇，遵循自下而上的原则逐步归并簇，继而构成很大的簇，反复这一过程直到图像中所有的对象都在同一个簇中或满足某一约束条件时，该算法结束。分裂层次聚类的过程与凝聚层次聚类的过程相反，分裂层次聚类认为图像中所有的对象已经在一个簇中，遵循自上而下的原则逐渐将图像中的对象从一个簇中划分为越来越小的簇，反复这一过程直到图像中每一个对象被分为单独的一簇或满足某一约束条件时，该算法结束。经常使用的层次聚类算法有BIRCH算法、ROCK算法、CURE算法、Chameleon算法等。BIRCH算法通过扫描数据来建立一个有关聚类结构的CF树，并对此CF树的叶节点进行聚类；ROCK算法根据相似度阈值与共同邻域的基本概念计算出图像的相似度矩阵，接着从图像的相似度矩阵中构建一个稀疏图，并对该稀疏图进行聚类；CURE算法依据收缩因子的值调整每个簇的大小和形状，从而形成不同类型的簇而完成聚类；Chameleon算法依据若图像中存在两个簇之间相似性以及互联性高度相关的对象，则动态地合并这两个簇，重复上述过程直到不能合并为止，该算法结束。

层次聚类算法虽然易处理不同粒度水平上的数据，但是该算法的结束条件模糊；其扩展性不良，因而要求预先算出图像中大部分的簇才可完成合并或分裂操作；并且该算法的归并或割裂簇的处理是不可修正的，因此该算法聚类质量较低。

5.2.3 基于密度的聚类算法

基于密度的聚类算法弥补了划分聚类算法和层次聚类算法的不足，不仅可以处理凸形簇的聚类，而且可以处理任意形状簇的聚类，该算法依据图像中数据集密度的相似度，把密度相近的数据集划分为一个簇，反之，把密度不接近的数据集划分为不同的簇，从而完成聚类的目的。常用的基于密度的聚类算法有DBSCAN算法、DENCLUE算法以及OPTICS算法等。DBSCAN算法通过图像中对象集合的每个对象的特定邻域来确定簇的区域，该算法的聚类结果不受数据输入顺序的影响，但此算法在执行的时候，需要事先知道图像中确定输入的聚类参数，但由于现实中的高维数据集不容易确定出聚类参数，因此该方法具有一定的局限性；DENCLUE算法依据图像中数据集的影响函数来计算数据空间的整体密度，接着确定出密度吸引点并寻找到确定的各个簇的区域而完成聚类的目的，但是该算法受聚类参数的影响较大，往往参数值的轻微变化会引发差别较大的聚类结果；OPTICS算法可以自动、交互地算出图像中簇的次序，并且此次序表示数据集的聚类结构，但是由于该算法所确定的聚类结构是从一个宽泛的参数所设置的范围中所获得，因此该算法不能产生一个数据集的合簇，因而聚类结果不太理想。

5.2.4 基于模型的聚类算法

基于模型的聚类算法依据图像中的数据集符合某一概率分布这一假设，把数据集表示为某一数学模型来实现聚类的目的，因而该方法划分的每一个簇的形式均是通过概率描述来表示的。常用的基于模型的聚类算法有统计方法和神经网络方法，此外还有一些新的模型聚类算法，例如，支持矢量方法的聚类算法、SPC算法以及SyMP算法等。

统计聚类方法有COBWEB算法、CLASSIT算法、AutoClass算法以及高斯混合模型算法等。COBWEB算法是最著名的基于统计聚类的方法，该算法用一个启发式估算度量将数据集中的对象加入到能够产生最高分类效果分类树的位置，于是会不断地创建出新的类，从而完成聚类的目的。COBWEB算法不需要事先提供数据集的聚类参数就可以自动地修正并划分出数据集的簇的数目，但是由于该方法进行的前提是假设每个簇的概率分布是相互独立的，因而该方法具有局限性；此外该方法在存储和更新数据集的每个簇的概率分布的时候，均会付出较高的代价而效率变低。CLASSIT算法可以处理连续性数据集的增量的聚类，并且该算法是COBWEB算法的一个衍生算法，因而该算法存在与COBWEB算法相同的缺陷，因此该算法也不适用于解决大型数据集的聚类问题。

神经网络方法将数据集的每一个簇看作是一个例证，并将该例证视为聚类的初始点，接着该算法依据某种相似度，将新的对象分配到与其最相似的簇中而完成聚类的目的。主要的神经网络方法包含竞争学习神经网络方法和自组织特征映射神经网络方法。基于神经网络的聚类算法处理数据需要的时间较长，并且不适合将其用于大型数据集的处理。

5.2.5 基于网格的聚类算法

基于网格的聚类算法是首先将图像空间数据量化成某些单元，然后该算法对这些量化单元进行聚类。经典的基于网格的聚类算法有STING算法、CLIQUE算法以及WaveCluster算法。STING算法是一种针对不同级别的分辨率将图像空间分为多个级别的长方形单元的多分辨率的聚类方法；CLIQUE算法是一种综合密度与网格的针对处理高维数据集的聚类算法；WaveCluster算法采用小波变换把图像的数据集的空间域转变为其频率域，并在这个频率域中找到密集的数据区域而实现数据聚类。基于网格的聚类算法虽然能快速聚类，但是该算法只能对垂直和水平边界执行聚类，不能对斜边界执行聚类，因此该算法具有一定的局限性；其时间复杂程度通常与数据集的规模无关而与网格数目相关，若网格单元数太大，则其时间复杂度就会变大，反之若网格单元数太小，该算法的聚类精确度就会受影响，因此该算法选取恰当的网格数是取得良好的聚类效果的关键环节。