摘要： 最小最大割算法(Mcut)能满足聚类算法的一般准则，但在实际求解过程中，通常把Mcut算法的目标函数松弛转换为标准分割算法(Ncut)的目标函数进行求解，而未充分使用Mcut的聚类性能。为此，利用子空间技术，提出一种改进的Mcut算法(SMcut)，设计基于图像分块的SMcut算法(BSMcut)，以提高SMcut算法的分割速度。实验结果表明，SMcut和BSMcut算法均具有较好的分割性能，且BSMcut算法的计算复杂度较低。

关键词: 图像分割, 谱聚类, 子空间, 标准分割算法, 最小最大割算法

Abstract: Min-max cut(Mcut) algorithm completely satisfies the general criterion of the cluster algorithms, so Mcut has good grouping performance. However, in the actual solution, the objective function of Mcut usually is relaxed into the objective function of Normalized cut(Ncut). It does not make full use of the clustering performance of Mcut. In order to overcome this problem, this paper presents an improved Mcut algorithm(SMcut) that uses subspace technology. In order to improve SMcut’s speed in image segmentation, a SMcut based on block(BSMcut) is proposed. Experimental result shows that SMcut and BSMcut has better segmentation performance, at the same time, BSMcut can reduce the computational complexity.

Key words: image segmentation, spectral clustering, subspace, Normalized cut(Ncut) algorithm, Min-max cut(Mcut) algorithm

中图分类号: 

• TP391