Abstract
In the last few years, several new algorithms based on graph cuts
have been developed to solve energy minimization problems in computer
vision. Each of these techniques constructs a graph such that the
minimum cut on the graph also minimizes the energy. Yet, because
these graph constructions are complex and highly specific to a particular
energy function, graph cuts have seen limited application to date.
In this paper, we give a characterization of the energy functions
that can be minimized by graph cuts. Our results are restricted to
functions of binary variables. However, our work generalizes many
previous constructions and is easily applicable to vision problems
that involve large numbers of labels, such as stereo, motion, image
restoration, and scene reconstruction. We give a precise characterization
of what energy functions can be minimized using graph cuts, among
the energy functions that can be written as a sum of terms containing
three or fewer binary variables. We also provide a general-purpose
construction to minimize such an energy function. Finally, we give
a necessary condition for any energy function of binary variables
to be minimized by graph cuts. Researchers who are considering the
use of graph cuts to optimize a particular energy function can use
our results to determine if this is possible and then follow our
construction to create the appropriate graph. A software implementation
is freely available.
- algorithms,artificial
- analysis,pattern
- and
- enhancement,image
- enhancement:
- graphics,computer-assisted,computer-assisted:
- intelligence,automated,computer
- interface
- interpretation,imaging,information
- methods,image
- methods,numerical
- methods,user-computer
- of
- processing,subtraction
- recognition,reproducibility
- results,sensitivity
- retrieval,information
- retrieval:
- specificity,signal
- storage
- technique,three-dimensional,three-dimensional:
Users
Please
log in to take part in the discussion (add own reviews or comments).