Abstract: There are two limitations with the graph cut models used in image segmentation. The parameters are predefined manually and a cut may end up with a local minimum. To overcome these limitations, an interactive kernel graph cut based upon EM algorithm is proposed. Image data is mapped into a kernel space and a new objective function is defined. Various parameters which are needed in the previous step are calculated according to the subimages; these two steps iterate until object function converges. Real and synthesis image segmentation experiments confirm it that the proposed algorithm is more precise and accurate compared with interactive graph cut based on normalized cut, especially when segmenting optical images; this algorithm can also keep detailed image information that cannot be captured by the normalized cut. Interactive kernel graph cut can offer a global optimum segmentation, and EM algorithm calculates various parameters needed in the graph cut. That’s why the word “adaptive” is used.

Key words: image segmentation, spectral cluster, kernel methods, interactive graph cut, Expectation-Maximization（EM） algorithm

摘要： 为了克服图割模型算法在实现图像分割时需要人为选定参数，以及图割模型可能会陷入局部最小值的不足，考虑到交互图割是一种灵活的全局最优算法，提出了基于EM方法的交互核图割算法。数据映射到核空间，构造了新的目标函数，这样可以更有效地解决分类分割问题；为了估计交互图割所需要的参数以及图割算法所需要的各种阈值，采用EM算法来估计这些参数，避免人为随机选取可能造成的不利影响，因而该方法是一种自适应的分割算法。实验结果表明，相对于交互图割算法，该算法分割合成图像时具有更低的误分率，处理光学等图像时，分割结果更准确，保留图像细节信息的能力更强。

关键词: 图像分割, 图谱聚类, 核方法, 交互图割, 最大期望（EM）算法