浅谈聚类算法在图像分割中的应用

王平禄 董昱威

摘 要：聚类算法在图像分割领域有广泛的应用，本文通过对四种聚类算法的介绍与分析，深入了解其算法原理，以及其在图像分割领域中的应用效果，通过四种的算法的比较，总结出了各个算法的优缺点。

关键词：聚类算法；K均值；模糊聚类；均值漂移；近邻传播算法

随着信息技术的高速发展，人们每天都处理大量的图像信息，然而，不是图像中的所有信息都是我们需要的，所以，这就需要我们进一步对图像进行处理，得到能够满足人们需要的信息。这就需要我们通过技术手段把图像中特定的信息从整体中分割出来，这便是图像分割，即将输入的图像分割成若干有意义的目标区域[1]。近年来，聚类算法在图像分割中有着广泛的应用。目前比较经典的聚类算法有：K均值聚类，模糊聚类，均值漂移算法，近邻聚类算法。

1 聚类算法

⑴K均值聚类。K均值算法是最经典的聚类算法。由于其简单高效，是应用最广泛的聚类算法。它的基本思想是：预先设定K类，随机选中K个元素作为每一类的中心。计算其它元素与K个中心之间的聚类，根据距离的大小，归入距离最小的类中。然后重新计算每一个类的中心值，即所有类中元素的平均值，得到新的中心值后。再次重新分类，不断重复此过程，直到目标函数收敛。通常定义的目标函数为：

式中：p为对象空间中一个数据对象；mi为类ci的均值。

⑵模糊聚类。模糊聚类算法是由K均值聚类算法发展而来的。它的基本思想是：把所有元素分为C个模糊聚簇，求出每个簇的中心，使得非相似性指标的函数达到最小值。它在确定每一个元素时，不是K均值非0即1，而是使用0～1之间的数字来赋予元素隶属于某一簇的程度。它的目标函数为：FCM聚类算法目标函数为：

式中：Xj表示样本；N表示样本数目，通常表示图像像素数；C表示聚类数目； 是矢量Xj隶属于第i类的隶属度函数，满足uij∈[0，1]且 ；Z表示聚类中心。

⑶均值漂移算法。均值漂移是一种不需要参数的无监督聚类方法。它的主要思想是，在概率空间中求解概率密度极值的最优算法。它让每一个点漂移到密度函数局部最大值出，即均值漂移向量的方向是数据的密度梯度估计方向一致。[2]文献[3]中对均值漂移算法原理的描述如下：假设核函数H如果满足一定的统计矩约束概率密度函数，可以用于非参数概率密度估计，若样本集{xi}n是依密度函数f（x）经过n次独立抽样得到的，则给出的密度函数估计为[4]：

其中，核函数满足：

⑷近邻聚类算法。近邻传播聚类算法是一种基于近邻信息传播的聚类算法，其目的是找到最优的类代表点集合，一个类代表点对应为实际数据集中的一个数据点，使得所有数据点到最近的类代表点的相似度之和最大。如果设数据点的相似度为数据点的欧式距离的负数，则妙算法的目标函数与经典的K中心聚类算法的目标函数一致。近邻传播聚类算法还有两个重要的信息量参数，分别是responsibility和availability，r（i，k）表示从点i发送到候选聚类中心k的数值消息，反映k点是否适合作为i点的聚类中心。a（i，k）则从候选聚类中心k发送到i的数值消息，反映i点是否选择k作为其聚类中心。r（i，k）与a（i，k）越强，则k点作为聚类中心的可能性就越大，并且i点隶属于以k点为聚类中心的聚类的可能性也越大。对于任意数据点xi，计算所有数据点的r（i，k）和a（i，k）。

3 小结

K均值聚类由于其简单高效，是应用最广泛的聚类算法。但是它也有很多局限性，其中聚类类别的数目需要先验知识，而初试聚类中心的选择不同也对聚类最终结果有很大的影响，所以聚类的稳定性欠缺。

模糊聚类算法，也是比较普遍使用的聚类算法。一般情况下不需要人为干预和设定阈值，就可使圖像分割区域自动化。但是模糊聚类数目的确定也是个难题，需要先验知识，而算法本身迭代过程计算量非常大，而算法对噪音比较敏感，所以，时常会出现过分割现象。

均值漂移算法是一种无需任何参数的聚类算法，对噪音有很好的鲁棒性，可以处理任意形状和特征空间的图像，非常适用于真实世界中的图像。但是该算法受核函数的影响比较大，由于核函数参数的设置问题，图像会产生过分割或欠分割现象。

近邻传播聚类算法，相比较其它算法能更快的处理大规模数据，得到较好的聚类结果。它对数据形成的相似矩阵的对称性没有任何要求，所以其应用的范围很大。但是对于一些本书具有复杂结构的数据集，近邻传播算法通常得不到合理的聚类结果。

[参考文献]

[1]Gonzalez Rafael C，Woods Richard E，Eddins Steven L.Digital Image Processing.阮秋琦，等，译.电子工业出版社，2005.

[2]王爽，夏玉，焦李成.基于均值漂移的自适应纹理图像分割方法[J]. Journal of Software，2010，21（6）：1451-1461.

[3]沈占锋，骆剑承，胡晓东，孙卫刚.高分辨率遥感影像多尺度均值漂移分割算法研究[J].武汉大学学报（信息科学版），2010，03：313-316.

[4]Comaniciu D， Meer P.Mean Shift： a Robust Approach Toward Feature Space Analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（5）：603-619.