Skip to Main content Skip to Navigation
Conference papers

Exhaustive Family of Energies Minimizable Exactly by a Graph Cut

Abstract : Graph cuts are widely used in many fields of computer vision in order to minimize in small polynomial time complexity certain classes of energies. These specific classes depend on the way chosen to build the graphs representing the problems to solve. We study here all possible ways of building graphs and the associated energies minimized, leading to the exhaustive family of energies minimizable exactly by a graph cut. To do this, we consider the issue of coding pixel labels as states of the graph, i.e. the choice of state interpretations. The family obtained comprises many new classes, in particular energies that do not satisfy the submodularity condition, including energies that are even not permuted-submodular. A generating subfamily is studied in details, in particular we propose a canonical form to represent Markov random fields, which proves useful to recognize energies in this subfamily in linear complexity almost surely, and then to build the associated graph in quasilinear time. A few experiments are performed, to illustrate the new possibilities offered.
Document type :
Conference papers
Complete list of metadata
Contributor : Guillaume Charpiat Connect in order to contact the contributor
Submitted on : Monday, August 22, 2011 - 12:17:37 PM
Last modification on : Thursday, February 11, 2021 - 2:56:34 PM
Long-term archiving on: : Monday, November 12, 2012 - 3:41:58 PM


  • HAL Id : inria-00616370, version 1



Guillaume Charpiat. Exhaustive Family of Energies Minimizable Exactly by a Graph Cut. Computer Vision and Pattern Recognition, Jun 2011, Colorado Springs, United States. ⟨inria-00616370⟩



Les métriques sont temporairement indisponibles