Iterated graph cuts for image segmentation

Graph cuts based interactive segmentation has become very popular over the last decade. In standard graph cuts, the extraction of foreground object in a complex background often leads to many segmentation errors and the parameter λ in the energy function is hard to select. In this paper, we propose an iterated graph cuts algorithm, which starts from the sub-graph that comprises the user labeled foreground/ background regions and works iteratively to label the surrounding un-segmented regions. In each iteration, only the local neighboring regions to the labeled regions are involved in the optimization so that much interference from the far unknown regions can be significantly reduced. To improve the segmentation efficiency and robustness, we use the mean shift method to partition the image into homogenous regions, and then implement the proposed iterated graph cuts algorithm by taking each region, instead of each pixel, as the graph node for segmentation. Extensive experiments on benchmark datasets demonstrated that our method gives much better segmentation results than the standard graph cuts and the GrabCut methods in both qualitative and quantitative evaluation. Another important advantage is that it is insensitive to the parameter λ in optimization.