L’équipe OCAD accueille Nicolas Lermé (doctorant, LIPN).

In few years, graph cuts have become a leading method for solving a wide range of problems in computer vision and graphics. However, graph cuts involve the construction of huge graphs which sometimes do not fit in memory.

Currently, most of the max-flow algorithms are totally impracticable to solve such large scale problems. In the image segmentation context, some authors have proposed banded of hierarchical approximation methods to get round this problem.

We propose a new strategy for reducing graphs during the creation of the graph where the nodes of the reduced graph are typically located in a narrow band surrounding the object edges.

Empirically, solutions obtained on the reduced graphs are identical to the solutions on the complete graphs. Moreover, the time required by the reduction if often compensated by the time that would be needed to create the remove nodes and the additional time required by the max-flow on the larger graph. Finally, we show experiments for segmenting large volume data in 2D and 3D.