Journal of Systems Engineering and Electronics ›› 2014, Vol. 25 ›› Issue (3): 514-522.doi: 10.1109/JSEE.2014.00059

• SOFTWARE ALGORITHM AND SIMULATION • Previous Articles     Next Articles

Simulated annealing spectral clustering algorithm for image segmentation

Yifang Yang1,3,∗ and Yuping Wang2   

  1. 1. School of Mathematics and Statistics, Xidian University, Xi’an 710071, China;
    2. School of Computer Science and Technology, Xidian University, Xi’an 710071, China;
    3. College of Science, Xi’an Shiyou University, Xi’an 710065, China
  • Online:2014-07-01 Published:2010-01-03


The similarity measure is crucial to the performance of spectral clustering. The Gaussian kernel function based on the Euclidean distance is usually adopted as the similarity measure. However, the Euclidean distance measure cannot fully reveal the complex distribution data, and the result of spectral clustering is very sensitive to the scaling parameter. To solve these problems, a new manifold distance measure and a novel simulated annealing spectral clustering (SASC) algorithm based on the manifold distance measure are proposed. The simulated annealing based on genetic algorithm (SAGA), characterized by its rapid convergence to the global optimum, is used to cluster the sample points in the spectral mapping space. The proposed algorithm can not only reflect local and global consistency better, but also reduce the sensitivity of spectral clustering to the kernel parameter, which improves the algorithm’s clustering performance. To efficiently apply the algorithm to image segmentation, the Nystr¨om method is used to reduce the computation complexity. Experimental results show that compared with traditional clustering algorithms and those popular spectral clustering algorithms, the proposed algorithm can achieve better clustering performances on several synthetic datasets, texture images and real images.