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

摘要： 针对近邻传播（Affinity Propagation，AP）聚类算法存在运算复杂度高且未考虑数据点密度对聚类效果的影响的问题，提出一种改进的近邻传播聚类算法并应用于图像分割。首先，在度量数据点之间的相似性时，考虑到密度差异对数据点成为类代表点可能性的影响，利用密度聚类的思想设置偏向参数，同时引入数据点的空间邻近位置信息，充分利用图像信息，提高相似度矩阵构造的合理性，增强聚类的内聚性，并提高分割精度；其次，为降低计算相似度矩阵的复杂度，减小计算机内存开销，引入Nystr?m逼近策略求解相似度矩阵，提升了算法的效率。实验表明，改进后的算法与传统的近邻传播聚类算法相比获得了更好的图像分割效果。

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