A graph cut algorithm for higher-order Markov random fields

Alexander Fix, Aritanan Gruber, Endre Boros, Ramin Zabih

Research output: Chapter in Book/Report/Conference proceedingConference contribution

65 Scopus citations


Higher-order Markov Random Fields, which can capture important properties of natural images, have become increasingly important in computer vision. While graph cuts work well for first-order MRF's, until recently they have rarely been effective for higher-order MRF's. Ishikawa's graph cut technique [8, 9] shows great promise for many higher-order MRF's. His method transforms an arbitrary higher-order MRF with binary labels into a first-order one with the same minima. If all the terms are submodular the exact solution can be easily found; otherwise, pseudo-boolean optimization techniques can produce an optimal labeling for a subset of the variables. We present a new transformation with better performance than [8, 9], both theoretically and experimentally. While [8, 9] transforms each higher-order term independently, we transform a group of terms at once. For n binary variables, each of which appears in terms with k other variables, at worst we produce n non-submodular terms, while [8, 9] produces O(nk). We identify a local completeness property that makes our method perform even better, and show that under certain assumptions several important vision problems (including common variants of fusion moves) have this property. Running on the same field of experts dataset used in [8, 9] we optimally label significantly more variables (96% versus 80%) and converge more rapidly to a lower energy. Preliminary experiments suggest that some other higher-order MRF's used in stereo [20] and segmentation [1] are also locally complete and would thus benefit from our work.

Original languageEnglish (US)
Title of host publication2011 International Conference on Computer Vision, ICCV 2011
Number of pages8
StatePublished - 2011
Externally publishedYes
Event2011 IEEE International Conference on Computer Vision, ICCV 2011 - Barcelona, Spain
Duration: Nov 6 2011Nov 13 2011

Publication series

NameProceedings of the IEEE International Conference on Computer Vision


Other2011 IEEE International Conference on Computer Vision, ICCV 2011

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Vision and Pattern Recognition


Dive into the research topics of 'A graph cut algorithm for higher-order Markov random fields'. Together they form a unique fingerprint.

Cite this