基于多尺度的改进Graph cut算法

An improved multi-scale Graph cut algorithm

针对Graph cut算法存在着计算复杂度高及可能出现过分割等不足,提出了一种基于多尺度的改进算法,以更好地解决图像分割问题。该算法将多尺度的Normalized cut作为Graph cut算法的目标函数,避免了过分割的现象,同时将精细尺度的精确性和粗糙尺度的易分割性统一结合起来,对像素点进行采样,不仅保留了原来像素点间的关系,还降低了计算复杂度。然后运用基于谱图理论的求解方式,将问题转化为对相似矩阵求解特征值和特征向量的问题,相似度较高。试验结果表明,本研究算法能够对用户选取的图片进行有效地分割,无需用户交互,分割快速且结果精确。

Aimed at Graph cut algorithm that has the short comings of high computational and possible aver-segmentation,a developed algorithm was presented. The algorithm used multi-scale normalized cut as an objective function of Graph cut algorithm which could avoid the over-segmentation phenomenon. Meanwhile,by combining accuracy of fine scale and easy divisibility of rough scale,sampling pixels not only retained the relationship between the original pixels,but also reduced computational complexity. By using the solving approach based on spectral graph theory,the problem was transformed into similarity matrix eigenvalue and eigenvectors problems,and the similarity was high. Experimental results showed that the proposed algorithm could effectively segment images without user interaction. The segmentation process was fast and segmentation results were accurate.