2016年第35卷第9期
传感器与微系统（Transducer and MicrosystemTechnologies）
137
D0I:10.13873/J.1000-9787(2016)09-0137-04
基于加速k均值的谱聚类图像分割算法改进
李昌兴"，黄艳虎”，支晓斌"，谢笑娟”（1.西安邮电大学理学院，陕西西安710121；
2.西安邮电大学通信与信息工程学院，陕西西安710121)
摘要：对谱聚类图像分割算法进行改进，即引人加速均值算法替换原算法中的均值算法，得出加速谱聚类的图像分割算法。将改进算法应用于微软剑桥研究院Grabcut数据集中的5幅实验图像，结果显示：在平均区域一致性评价不降低的前提下，改进算法完成分割所花费的平均时间比改进前可缩短58%。关键词：图像分割；谱聚类；加速&均值；加速谱聚类
中图分类号：TP391
文献标识码：A
文章编号：1000-9787(2016)09-0137-04
Improvements of accelerationk-meansbased spectral clustering
algorithm for image segmentation
LI Chang-xing',HUANG Yan-hu",ZHI Xiao-bin',XIE Xiao-juan
(1. School of Science,Xi'an University of Posts and Telecommunications,Xi'an 710121,China; 2. School of Communication and Information Engineering,Xi'an University of Posts and
Telecommunication,Xi'an 710121,China)
Abstract: A spectral clustering algorithm for image segmentation is achieved by improving spectral clustering a o aaaeda a a eaaooeaons eoas ae o oe algorithm. The improved algorithm is applied in five experimental images from the Grab Cut dataset of Microsoft Research at Cambridge, results show that time consuming of image segmentation by the improved algorithm can be shortened by 58 % in the premise of average area of conformance assessment without reducing.
Key words : image segmentation; spectral clustering; acceleration k-means; acceleration spectral clustering
旱 0
图像分割是计算机视觉领域的重要组成部分"]。谱聚类算法"在图像分割和特征提取方面应用广泛(3)。
谱聚类算法能在任意形状的样本空间上聚类，且收敛于全局最优解4]，将谱聚类算法应用于图像分，通常能取得很好的分割效果")，但同时它也有着自身的缺陷一计算相似性矩阵高度复杂，间题的求解会变得异常费时(*]。文献[7]中提出基于路径的相似性度量，但对边界点过于敏感，分割耗时不理想；文献[8]提出基于密度敏感的相似性度量，但当位于高密度区的两个样本数据点穿过的路径较长时，效果尚不明显，并且最终采用&均值聚类简化后的向量空间，造成聚类耗时过长。本文对谱聚类图像分割算法进行了改进，即引入加速均值替换原有算法中的 k均值算法，得出加速谱聚类的图像分割算法。
1谱聚类算法与均值算法 1.1谱聚类算法
给定n个数据点，2，""，。，谱聚类算法构建了一个
相似性矩阵，它反映了，与之间的关系。然后，它使用相似性信息，将，，“"，。聚类成个簇“9)。诺聚类有很多种解释，最常用的就是基于图切的理论。它要求将谱聚类转化为求出数据集的Laplacian矩阵，然后再求该矩阵的特征向量，进而对特征向量进行聚类[1]。其算法流程如下：
1)计算数据间的相似性矩阵W=（w），其中，， exp(x;, l2"),(ij1,2,",n)。
2)计算度矩阵D=diag（du，da，，da），其中，
d.
wgo 台
3)计算Laplacian矩阵L，—般取L=D-I/WD=1/2
4)计算矩阵L的前&个特征值所对应的特征向量v， Ve,"*,
5)将vi，"，"",",按列组成矩阵VeR**
收稿日期：2015-10-27
*基金项目：陕西省自然科学基金资助项目(2014JM8307）；陕西省教育厅科学研究计划资助项目（14JK1661）