### Graph Cuts in Vision and Graphics: Theories and Applications

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

### Abstract

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)