Abstract :
Combinatorial graph cut algorithms have been successfully applied to a wide range of problems in
vision and graphics. This paper focusses on possibly the simplest application of graph-cuts: segmentation of objects
in image data. Despite its simplicity, this application epitomizes the best features of combinatorial graph cuts
methods in vision: global optima, practical efficiency, numerical robustness, ability to fuse a wide range of visual
cues and constraints, unrestricted topological properties of segments, and applicability to N-D problems. Graph
cuts based approaches to object extraction have also been shown to have interesting connections with earlier
segmentation methods such as snakes, geodesic active contours, and level-sets. The segmentation energies optimized
by graph cuts combine boundary regularization with region-based properties in the same fashion as Mumford-Shah
style functionals. We present motivation and detailed technical description of the basic combinatorial optimization
framework for image segmentation via s/t graph cuts. After the general concept of using binary graph cut algorithms
for object segmentation was first proposed and tested in Boykov and Jolly (2001), this idea was widely studied
in computer vision and graphics communities. We provide links to a large number of known extensions based
on iterative parameter re-estimation and learning, multi-scale or hierarchical approaches, narrow bands, and other
techniques for demanding photo, video, and medical applications.
