Abstract

Optimization of surface functionals using discrete graph cut algorithms

Yuri Boykov
University of Western Ontario

Regular grid graphs and complexes can be used to approximate geometric
surface functionals. Standard combinatorial algorithms for max-flow/min-cut problems
such as augmenting paths, push-relabel, pseudo-flow, and parametric max-flow techniques
can efficiently compute (in low-order polynomial time) global optima solutions for
the corresponding approximations of geometric problems widely used in computer vision,
graphics, and medical imaging. We review a range of applications
and discuss some computational issues (what geometric functionals can be approximated on graphs,
metrication errors, global optimization vs. local optimization, running-time and memory
efficiency).