关键词: 图像分割, 近邻传播聚类, 偏向参数, 空间邻近位置信息, 相似度矩阵, Nystr?m逼近策略

Abstract: Since the computational complexity of Affinity Propagation（AP） algorithm is excessively high, and the impact of density difference of data points made on clustering effect is inevitably, an improved affinity propagation clustering algorithm is proposed in this paper and applied to image segmentation. Firstly, when measuring the similarity between data points, the influence that density difference makes on the possibility that the data point is suited to be the exemplar is considered, and the preference is set according to density clustering thought. At the same time, spatial adjacency information is taken into consideration and image information is made full use of to enhance the rationality of constructing the similarity matrix. Consequently, the cohesiveness of clustering and segmentation accuracy are improved. Secondly, Nystr?m approximation strategy is introduced to reduce the computational complexity to solve similarity matrix and the memory consumption, which improves the efficiency of the algorithm. The experiments prove that the proposed algorithm can obtain better segmentation results than the affinity propagation clustering algorithm.

Key words: image segmentation, affinity propagation clustering, preference, spatial adjacency information, similarity matrix, Nystr?m approximation