UWEE Tech Report Series

Cooperative Cuts for Image Segmentation


Stefanie Jegelka, Jeff Bilmes

Image segmentation, submodularity, edge-submodular graph cut, cooperative cut, global potential functions


We propose a novel framework for graph-based cooperative regularization that uses submodular costs on graph edges. We introduce an efficient iterative algorithm to solve the resulting hard discrete optimization problem, and show that it has a guaranteed approximation factor. The edge-submodular formulation is amenable to the same extensions as standard graph cut approaches, and applicable to a range of problems. We apply this method to the image segmentation problem. Specifically, Here, we apply it to introduce a discount for homogeneous boundaries in binary image segmentation on very difficult images, precisely, long thin objects and color and grayscale images with a shading gradient. The experiments show that significant portions of previously truncated objects are now preserved.

Download the PDF version

Download the Gzipped Postscript version