Statistical priors for efficient combinatorial optimization via graph cuts

Daniel Cremers, Leo Grady

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

16 Scopus citations


Bayesian inference provides a powerful framework to optimally integrate statistically learned prior knowledge into numerous computer vision algorithms. While the Bayesian approach has been successfully applied in the Markov random field literature, the resulting combinatorial optimization problems have been commonly treated with rather inefficient and inexact general purpose optimization methods such as Simulated Annealing. An efficient method to compute the global optima of certain classes of cost functions defined on binary-valued variables is given by graph min-cuts. In this paper, we propose to reconsider the problem of statistical learning for Bayesian inference in the context of efficient optimization schemes. Specifically, we address the question: Which prior information may be learned while retaining the ability to apply Graph Cut optimization? We provide a framework to learn and impose prior knowledge on the distribution of pairs and triplets of labels. As an illustration, we demonstrate that one can optimally restore binary textures from very noisy images with runtimes on the order of a second while imposing hundreds of statistically learned constraints per pixel.

Original languageEnglish
Title of host publicationComputer Vision - ECCV 2006, 9th European Conference on Computer Vision, Proceedings
Number of pages12
StatePublished - 2006
Externally publishedYes
Event9th European Conference on Computer Vision, ECCV 2006 - Graz, Austria
Duration: 7 May 200613 May 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3953 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference9th European Conference on Computer Vision, ECCV 2006


Dive into the research topics of 'Statistical priors for efficient combinatorial optimization via graph cuts'. Together they form a unique fingerprint.

Cite this