Interactive Organ Segmentation Using Graph Cuts

Yuri Boykov, Marie-Pierre Jolly

In Medical Image Computing and Computer-Assisted Intervention (MICCAI), LNCS 1935, pp. 276-286, Pittsburgh, PA, October 2000.


An N-dimensional image is divided into "object'' and "background'' segments using a graph cut approach. A graph is formed by connecting all pairs of neighboring image pixels (voxels) by weighted edges. Certain pixels (voxels) have to be a priori identified as object or background seeds providing necessary clues about the image content. Our objective is to find the cheapest way to cut the edges in the graph so that the object seeds are completely separated from the background seeds. If the edge cost is a decreasing function of the local intensity gradient then the minimum cost cut should produce an object/background segmentation with compact boundaries along the high intensity gradient values in the image. An efficient, globally optimal solution is possible via standard min-cut/max-flow algorithms for graphs with two terminals. We applied this technique to interactively segment organs in various 2D and 3D medical images.

WHOLE PAPER: pdf file (294 Kb)