Connectivity Constrained Graph-Cut for Fast Interactive Image Segmentation

Graph-Cut segmentation algorithm is known to be a classical and effective method for extracting foreground objects from images or videos.However,the algorithm does not usually lend itself to real time applications due to its high computational complexity.Moreover,it tends to produce so called shrinking bias phenomena when foreground and background have similar color distributions.In this paper,an improved algorithm is proposed to deal with these problems.There are two points behind our algorithm.First,a Mean-Shift technology based pre-segmentation is used so that the Graph-Cut algorithm is performed on the pre-segmented regions rather than on image pixels,thus dramatically reducing the computational overhead of the algorithm.In addition,the pre-segmentation result can also be used in the subsequent estimation of the foreground and background color distributions.Second,and more importantly,a connectivity constraint with adaptive weight adjustment functionality is added as a new term to the energy function to be minimized.In this way,the shrinking bias phenomenon is remarkably mitigated and the segmentation accuracy is enhanced.Experimental results on a set of images have shown that our algorithm has good real time interactivity with stable and accurate segmentation.