Exact optimization for Markov Random Fields with convex priors

Hiroshi Ishikawa*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

412 Citations (Scopus)


We introduce a method to solve exactly a first order Markov Random Field optimization problem in more generality than was previously possible. The MRF shall have a prior term that is convex in terms of a linearly ordered label set. The method maps the problem into a minimum-cut problem for a directed graph, for which a globally optimal solution can be found in polynomial time. The convexity of the prior function in the energy is shown to be necessary and sufficient for the applicability of the method.

Original languageEnglish
Pages (from-to)1333-1336
Number of pages4
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number10
Publication statusPublished - 2003 Oct
Externally publishedYes


  • Global optimization
  • Markov random field
  • Maximum flow
  • Minimum cut

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Exact optimization for Markov Random Fields with convex priors'. Together they form a unique fingerprint.

Cite this