A Reduction Method For Graph Cut Optimization

Nicolas Lermé (1) , François Malgouyres (2)

1 SATIE - Systèmes et Applications des Technologies de l'Information et de l'Energie
2 IMT - Institut de Mathématiques de Toulouse UMR5219

In a couple of years, graph cuts methods appeared as a leading method in computer vision and graphics due to their efficiency in computing globally optimal solutions. Such an approach remains however impractical for large-scale problems due to the memory requirements for storing the graphs. Among strategies to overcome this situation, an existing strategy 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 when unary terms are locally strong, the remaining nodes are typically located in a thin band around the object of interest to segment. In this paper, we empirically prove on a large number of experiments that the distance between the global minimizer and the minimizer obtained with an heuristic test, remains very low. In addition to this preliminary work, we detail existing strategies to reduce the memory footprint of graph cuts and provide extra parameters for further reducing the graphs and removing isolated speckles and islands due to noise in the segmentation.

Mots clés: reduction; graph cuts; segmentation; filtering

Domaines: Optimisation et contrôle [math.OC]; Traitement des images [eess.IV]

Nicolas Lermé, François Malgouyres. A Reduction Method For Graph Cut Optimization. Pattern Analysis and Applications, 2014, 17 (2), pp.361-378. ⟨10.1007/s10044-013-0337-7⟩. ⟨hal-01486804v5⟩