Graph Cuts in Vision and Graphics: Theories and Applications

Yuri Boykov, Olga Veksler

In Handbook of Mathematical Models in Computer Vision, Springer, 2006.


Combinatorial min-cut algorithms on graphs emerged as an increasingly useful tool for problems in vision. Typically, the use of graph- cuts is motivated by one of the following two reasons. Firstly, graph-cuts allow geometric interpretation; under certain conditions a cut on a graph can be seen as a hypersurface in N-D space embedding the corresponding graph. Thus, many applications in vision and graphics use min-cut algo- rithms as a tool for computing optimal hypersurfaces. Secondly, graph- cuts also work as a powerful energy minimization tool for a fairly wide class of binary and non-binary energies that frequently occur in early vi- sion. In some cases graph cuts produce globally optimal solutions. More generally, there are iterative graph-cut based techniques that produce provably good approximations which (were empirically shown to) corre- spond to high-quality solutions in practice. Thus, another large group of applications use graph-cuts as an optimization technique for low-level vision problems based on global energy formulations. This chapter is intended as a tutorial illustrating these two aspects of graph-cuts in the context of problems in computer vision and graphics. We explain general theoretical properties that motivate the use of graph cuts, as well as, show their limitations.

WHOLE TEXT: pdf file (466 Kb)