Many computer vision and image processing problems can be formulated as a discrete optimization problem. Among several available optimization schemes, combinatorial min-cut algorithms on graphs emerged as an increasingly useful tool for performing these optimizations. This success is mainly twofold. First, in some cases graph cuts produce globally optimal solutions. More generally, there are iterative graph-cut based techniques that produce provably good local optimizer that are also high-quality solutions in practice. Second, graph-cuts allow for a geometric interpretation. Provided some assumptions, a cut on a graph can be seen as a hypersurface in N-D space embedding the corresponding graph. This point of view has been very fruitful in computer vision for computing hypersurfaces. Besides, graph-cut approaches have been shown to be very fast in practice. Finally some links between graph-cuts, message passing and belief propagation have been recently shown.
(University of Western Ontario)
Daniel Cremers (University of Bonn)
Jerome Darbon (University of California, Los Angeles (UCLA))
Hiroshi Ishikawa (Nagoya City University)
Vladimir Kolmogorov (University College London)
Stanley Osher (University of California, Los Angeles (UCLA))