Global Optimization for First Order Markov Random Fields with Submodular Priors

From LRDE

Abstract

This paper copes with the optimization of Markov Random Fields with pairwise interactions defined on arbitrary graphs. The set of labels is assumed to be linearly ordered and the priors are supposed to be submodular. Under these assumptions we propose an algorithm which computes an exact minimizer of the Markovian energy. Our approach relies on mapping the original into a combinatorial one which involves only binary variables. The latter is shown to be exactly solvable via computing a maximum flow. The restatement into a binary combinatorial problem is done by considering the level-sets of the labels instead of the label values themselves. The submodularity of the priors is shown to be a necessary and sufficient condition for the applicability of the proposed approach.

Documents

Bibtex (lrde.bib)

@InProceedings{	  darbon.08.iwcia,
  author	= {J\'er\^ome Darbon},
  title		= {Global Optimization for First Order {Markov} Random Fields
		  with Submodular Priors},
  booktitle	= {Proceedings of the twelfth International Workshop on
		  Combinatorial Image Analysis (IWCIA'08) },
  year		= 2008,
  address	= {Buffalo, New York, USA},
  month		= apr,
  abstract	= {This paper copes with the optimization of Markov Random
		  Fields with pairwise interactions defined on arbitrary
		  graphs. The set of labels is assumed to be linearly ordered
		  and the priors are supposed to be submodular. Under these
		  assumptions we propose an algorithm which computes an exact
		  minimizer of the Markovian energy. Our approach relies on
		  mapping the original into a combinatorial one which
		  involves only binary variables. The latter is shown to be
		  exactly solvable via computing a maximum flow. The
		  restatement into a binary combinatorial problem is done by
		  considering the level-sets of the labels instead of the
		  label values themselves. The submodularity of the priors is
		  shown to be a necessary and sufficient condition for the
		  applicability of the proposed approach.}
}