Exhaustive Family of Energies Minimizable Exactly by a Graph Cut - Archive ouverte HAL Access content directly
Conference Papers Year : 2011

Exhaustive Family of Energies Minimizable Exactly by a Graph Cut



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.
Fichier principal
Vignette du fichier
exhaustive_final_web.pdf (233.89 Ko) Télécharger le fichier
Vignette du fichier
poster.pdf (124.92 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Other

Dates and versions

inria-00616370 , version 1 (22-08-2011)


  • 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⟩
122 View
154 Download


Gmail Facebook Twitter LinkedIn More