A Reduction Method For Graph Cut Optimization

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

1 LAGA - Laboratoire Analyse, Géométrie et Applications
2 LIPN - Laboratoire d'Informatique de Paris-Nord
3 IMT - Institut de Mathématiques de Toulouse UMR5219

Since last decades, graph cuts have become a leading algorithm of computer vision due to the introduction of a fast maximum-flow algorithm and efficient heuristics in the multi-labels case. Nevertheless, graph cuts result in an excessive computational burden for high-resolution data since underlying graphs contain billion of nodes and even more edges. Except some rare exact methods, the heuristics generally fail to fully capture shape complexities. In this paper, we present a new strategy for reducing the size of these graphs in the image segmentation context while preserving the same solution. The graph is progressively built by only adding nodes which satisfy a given local condition. In the manner of, the resulting nodes belong to a narrow band around the object contours to segment. However, unlike, the proposed method preserve accurately details without requiring any other low-level segmentation tool. Experiments for segmenting images exhibit a low memory usage while maintaining a solution identical to the solution obtained with the whole graph. Extra parameters are also provided to further reduce the size of these graphs and remove small segments in the segmentation.

Mots clés: graph cuts; discrete optimization; denoising; segmentation

Domaines: Traitement des images [eess.IV]

Nicolas Lermé, François Malgouyres. A Reduction Method For Graph Cut Optimization. 2011. ⟨hal-01486804v1⟩