---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Vladimir
foaf_name: Vladimir Kolmogorov
foaf_surname: Kolmogorov
foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Ramin
foaf_name: Zabih, Ramin
foaf_surname: Zabih
bibo_doi: 10.1109/TPAMI.2004.1262177
bibo_issue: '2'
bibo_volume: 26
dct_date: 2004^xs_gYear
dct_publisher: IEEE@
dct_title: What energy functions can be minimized via graph cuts? @
...