李昌兴， 黄艳虎， 支晓斌， 谢笑娟

(1.西安邮电大学 理学院，陕西 西安 710121；2.西安邮电大学 通信与信息工程学院，陕西 西安 710121)



基于加速k均值的谱聚类图像分割算法改进*

李昌兴1， 黄艳虎2， 支晓斌1， 谢笑娟1

(1.西安邮电大学 理学院，陕西 西安 710121；2.西安邮电大学 通信与信息工程学院，陕西 西安 710121)

对谱聚类图像分割算法进行改进，即引入加速 均值算法替换原算法中的k均值算法，得出加速谱聚类的图像分割算法。将改进算法应用于微软剑桥研究院Grab cut数据集中的5幅实验图像，结果显示：在平均区域一致性评价不降低的前提下，改进算法完成分割所花费的平均时间比改进前可缩短58 %。

图像分割； 谱聚类； 加速k均值； 加速谱聚类

0　引　言

图像分割是计算机视觉领域的重要组成部分[1]。谱聚类算法[2]在图像分割和特征提取方面应用广泛[3]。

谱聚类算法能在任意形状的样本空间上聚类，且收敛于全局最优解[4]，将谱聚类算法应用于图像分割，通常能取得很好的分割效果[5]，但同时它也有着自身的缺陷—计算相似性矩阵高度复杂，问题的求解会变得异常费时[6]。文献[7]中提出基于路径的相似性度量，但对边界点过于敏感，分割耗时不理想；文献[8]提出基于密度敏感的相似性度量，但当位于高密度区的两个样本数据点穿过的路径较长时，效果尚不明显，并且最终采用k均值聚类简化后的向量空间，造成聚类耗时过长。本文对谱聚类图像分割算法进行了改进，即引入加速 均值替换原有算法中的k均值算法，得出加速谱聚类的图像分割算法。……