Related Experiment Videos
What energy functions can be minimized via graph cuts?
Vladimir Kolmogorov1, Ramin Zabih
1Computer Science Department, Cornell University, Ithaca, NY 14853, USA. vnk@cs.cornell.edu
IEEE Transactions on Pattern Analysis and Machine Intelligence
|September 21, 2004
Summary
Graph cuts offer powerful energy minimization for computer vision tasks. This study characterizes applicable energy functions and provides a general construction, simplifying graph cut use for problems like stereo and image restoration.
Area of Science:
- Computer Vision
- Optimization Algorithms
Background:
- Graph cut algorithms are increasingly used for energy minimization in computer vision.
- Current graph constructions are complex and specific to energy functions, limiting broader application.
Purpose of the Study:
- To characterize energy functions minimizable by graph cuts for binary variables.
- To provide a general construction for minimizing these energy functions.
- To establish a necessary condition for graph cut minimizability.
Main Methods:
- Characterization of energy functions composed of terms with three or fewer binary variables.
- Development of a general-purpose graph construction for minimization.
- Derivation of a necessary condition for energy function minimizability.
Main Results:
- A precise characterization of energy functions minimizable by graph cuts for binary variables.
- A generalizable construction applicable to vision problems with multiple labels.
- A necessary condition for graph cut optimization.
Conclusions:
- The study simplifies the application of graph cuts by providing clear criteria and a universal construction.
- Researchers can now determine the feasibility of using graph cuts for specific energy functions.
- Freely available software facilitates implementation for tasks like stereo, motion, and image restoration.