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.
Type de document :
Communication dans un congrès
Computer Vision and Pattern Recognition, Jun 2011, Colorado Springs, United States. 2011
Liste complète des métadonnées

https://hal.inria.fr/inria-00616370
Contributeur : Guillaume Charpiat <>
Soumis le : lundi 22 août 2011 - 12:17:37
Dernière modification le : samedi 27 janvier 2018 - 01:30:48
Document(s) archivé(s) le : lundi 12 novembre 2012 - 15:41:58

Identifiants

  • HAL Id : inria-00616370, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

215

Téléchargements de fichiers

188