A reduction method for graph cut optimization

In a few years, graph cuts appeared as a leading method in computer vision and graphics due to their efficiency in computing globally optimal solutions to popular minimization problems. Such an approach remains, however, impractical for very large-scale problems due to the memory requirements for storing the graphs. Among the strategies to overcome this situation, an existing one consists in reducing the size of these graphs by only adding the nodes which satisfy a local condition. In the image segmentation context, this means, for instance, that we do not need to consider a node when the unary terms are large in its neighborhood. The remaining nodes are typically located in a thin band around the boundary of the segmented object. In this paper, we detail existing strategies to reduce the memory footprint of graph cuts, describe the proposed reduction criterion, and empirically prove on a large number of experiments that the distance between the minimizer found and the global minimizer remains null or very small. We also provide extra parameters for further reducing the graphs and for removing isolated nodes due to noise.