在线编码谱聚类及图像分割方法

Image Segmentation via Online Encoding Based Spectral Clustering

目前,谱聚类已经成为图像分割领域的研究热点,但是,常见谱聚类算法具有O(n3)的复杂度,在图像分割的应用受到限制.基于在线的多尺度竞争学习,文中提出了一种基于在线编码的多尺度谱聚类算法,并应用于图像分割.首先,算法通过在线竞争学习算法构造m(m<n)个原型来编码原始数据.然后,利用多尺度谱聚类对原型进行分组,标注样本并得到最终的聚类结果.算法的复杂度近似为O(mn+m2),因而,较好地提高了谱聚类在图像分割上的效率.在三组数据上开展了实验:在非凸数据集上的结果表明,文中算法具有良好的多尺度性质.在合成的高斯数据集上进行了效率对比分析,说明文中算法能有效压缩样本量,提高效率.在标准的图像上的分割效率优于通常的NJW谱聚类算法和在分割质量上优于k-means算法.和基于抽样的Nystrm算法相比,具有一定优势.

Currently, spectral clustering is a state-of-art technique in image segmentation. However, the O（n^3） complexity of spectral clustering its application in image segmentation. Based on the online multiscale compeittive learning, this paper proposes a new rapid spectral clustering algorithm for segmenting of images. This algorithm uses m （m≤n） constructed prototypes by online competitive learning to approximate the distribution of data and then groups prototypes by multiscale spectral clustering. With the approximate complexity O（mn＋m^2）, our algorithm shows high performance and segmentation quality for large scale images. Our algorithm is tested on three data sets. On first data set, our algorithm shows correct grouping of data while NJW algorithm does not. Second, we compute the time consumption of our algorithm and NJW, and present the compression ratios in our algorithm. Results have shown our algorithm behavior better than NJW. At last the segmentation results on standard images of our algorithm take advantage of NJW and Kmeans algorithms and sampling based Nystrrm grouping method.