Une méthode de réduction exacte pour la segmentation par graph cuts

National audienceFrom now on, graph cuts are a standard in the computer vision community. However, their huge memory consumption remains a challenging problem since underlying graphs contains billions of nodes and even more edges. Except some exact methods [14, 10, 5], the heuristics in the literature can only obtain an approached solution [12, 8]. First, we present a new strategy for reducing exactly these graphs : the graph is built by adding nodes which satisfy locally a given condition and corresponds in a narrow band around the segmented object edges. The experiments presented for segmenting gray-levels and color images highlight low memory usage and show a low distance between segmentations. We also present an application of this method for segmenting lung tumors in CT images.Les graph cuts sont désormais un standard au sein de la communauté de la vision par ordinateur. Néanmoins, leur grande consommation mémoire reste un problème majeur : les graphes sous-jacents contiennent des milliards de noeuds et davantage d'arcs. Excepté quelques méthodes [14, 10, 5] exactes, les heuristiques présentes dans la littérature ne permettent d'obtenir qu'une solution approchée [12, 8]. Dans un premier temps, nous présentons une nouvelle stratégie pour réduire exactement ces graphes : le graphe est construit en ajoutant les noeuds qui satisfont localement une condition donnée et correspond à une bande étroite autour des contours de l'objet à segmenter. Les expériences présentées pour segmenter des images en niveaux de gris et en couleur mettent en évidence une faible consommation mémoire tout en garantissant une faible distance sur les segmentations. Nous présentons aussi une application de cette méthode pour segmenter des tumeurs dans des images scanner