Transformation of General Binary MRF Minimization to the First-Order Case
Abstract
We introduce a transformation of general higher-order Markov random field with binary labels into a first-order one that has the same minima as the original. Moreover, we formalize a framework for approximately minimizing higher-order multi-label MRF energies that combines the new reduction with the fusion-move and QPBO algorithms. While many computer vision problems today are formulated as energy minimization problems, they have mostly been limited to using first-order energies, which consist of unary and pairwise clique potentials, with a few exceptions that consider triples. This is because of the lack of efficient algorithms to optimize energies with higher-order interactions. Our algorithm challenges this restriction that limits the representational power of the models so that higher-order energies can be used to capture the rich statistics of natural scenes. We also show that some minimization methods can be considered special cases of the present framework, as well as comparing the new method experimentally with other such techniques.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The potentially large overhead in the number of variables lead to the development of several methods for degree reduction.
“The potentially large overhead in the number of variables lead to the development of several methods for degree reduction (e.g., References [160, 167, 168, 180, 188])”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [188]
Cites
Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
Lafferty, J., McCallum, A., & Pereira, F. C. N. (2001) · ScholarlyCommons (University of Pennsylvania) · Cited by 12,953 · see citing works
Martin, D., Fowlkes, C., Tal, D., & Malik, J. (2002) · Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001 · doi:10.1109/iccv.2001.937655 · Cited by 8,216 · see citing works
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.969114 · Cited by 6,988 · see citing works
An analysis of approximations for maximizing submodular set functions—I
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978) · Mathematical Programming · doi:10.1007/bf01588971 · Cited by 4,412 · see citing works
What energy functions can be minimized via graph cuts?
Kolmogorov, V., & Zabih, R. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1262177 · Cited by 3,127 · see citing works
Efficient Belief Propagation for Early Vision
Felzenszwalb, P. F., & Huttenlocher, D. P. (2006) · International Journal of Computer Vision · doi:10.1007/s11263-006-7899-4 · Cited by 1,338 · see citing works
Convergent Tree-Reweighted Message Passing for Energy Minimization
Kolmogorov, V. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.200 · Cited by 1,100 · see citing works
Fields of Experts: A Framework for Learning Image Priors
Roth, S., & Black, M. J. (2005) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2005.160 · Cited by 1,087 · see citing works
Robust Higher Order Potentials for Enforcing Label Consistency
Kohli, P., Ladický, Ľ., & Torr, P. H. S. (2009) · International Journal of Computer Vision · doi:10.1007/s11263-008-0202-0 · Cited by 858 · see citing works
An analysis of approximations for maximizing submodular set functions - 1Preprint
Fisher, M. L., Nemhauser, G. L., & Wolsey, L. A. (1978) · RePEc: Research Papers in Economics · Cited by 837 · see citing works
Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827 · see citing works
Cosegmentation of Image Pairs by Histogram Matching - Incorporating a Global Constraint into MRFs
Rother, C., Minka, T. P., Blake, A., & Kolmogorov, V. (2006) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2006.91 · Cited by 540 · see citing works
Boolean Methods in Operations Research and Related Areas
Hammer, P. L., & Rudeanu, S. (1968) · Ökonometrie und Unternehmensforschung · doi:10.1007/978-3-642-85823-9 · Cited by 529 · see citing works
Exact optimization for markov random fields with convex priors
Ishikawa, H. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1233908 · Cited by 487 · see citing works
Self-citationOptimizing Binary MRFs via Extended Roof Duality
Rother, C., Kolmogorov, V., Lempitsky, V., & Szummer, M. (2007) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2007.383203 · Cited by 424 · see citing works
Graph cut based image segmentation with connectivity priors
Vicente, S., Kolmogorov, V., & Rother, C. (2008) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2008.4587440 · Cited by 391 · see citing works
Minimizing Nonsubmodular Functions with Graph Cuts-A Review
Kolmogorov, V., & Rother, C. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1031 · Cited by 362 · see citing works
Roof duality, complementation and persistency in quadratic 0–1 optimization
Hammer, P. L., Hansen, P., & Simeone, B. (1984) · Mathematical Programming · doi:10.1007/bf02612354 · Cited by 318 · see citing works
Efficient Belief Propagation with Learned Higher-Order Markov Random Fields
Lan, X., Roth, S., Huttenlocher, D. P., & Black, M. J. (2006) · Lecture notes in computer science · doi:10.1007/11744047_21 · Cited by 200 · see citing works
Texture synthesis via a noncausal nonparametric multiscale Markov random field
Paget, R. D., & Longstaff, I. D. (1998) · IEEE Transactions on Image Processing · doi:10.1109/83.679446 · Cited by 181 · see citing works
Beyond pairwise energies: Efficient optimization for higher-order MRFs
Komodakis, N., & Nikos Paragios, A. (2009) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2009.5206846 · Cited by 180 · see citing works
Energy Minimization via Graph Cuts: Settling What is Possible
Freedman, D., & Drineas, P. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.143 · Cited by 173 · see citing works
Minimizing sparse higher order energy functions of discrete variables
Rother, C., Kohli, P., Feng, W., & Jia, J. (2009) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2009.5206739 · Cited by 161 · see citing works
FusionFlow: Discrete-continuous optimization for optical flow estimation
Lempitsky, V., Roth, S., & Rother, C. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587751 · Cited by 145 · cited 1× · see citing works
“Ç”
Higher-order clique reduction in binary graph cut
Ishikawa, H. (2009) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2009.5206689 · Cited by 128 · see citing works
Self-citationGlobal stereo reconstruction under second order smoothness priors
Woodford, O. J., Torr, P. H. S., Reid, I. D., & Fitzgibbon, A. W. (2008) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2008.4587672 · Cited by 120 · see citing works
Meltzer, T., Yanover, C., & Weiss, Y. (2005) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2005.110 · Cited by 105 · see citing works
P³ & Beyond: Move Making Algorithms for Solving Higher Order Functions
Kohli, P., Kumar, M., & Torr, P. H. S. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.217 · Cited by 99 · see citing works
LogCut - Efficient Graph Cut Optimization for Markov Random Fields
Lempitsky, V., Rother, C., & Blake, A. (2007) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2007.4408907 · Cited by 96 · see citing works
Exact inference in multi-label CRFs with higher order cliques
Ramalingam, S., Kohli, P., Alahari, K., & Torr, P. H. S. (2008) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2008.4587401 · Cited by 88 · see citing works
Efficient Belief Propagation for Vision Using Linear Constraint Nodes
Potetz, B. R. (2007) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2007.383094 · Cited by 73 · see citing works
Preprocessing of unconstrained quadratic binary optimization
Boros, E., Hammer, P. L., & Tavares, G. (2006) · Cited by 66 · see citing works
A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
Boros, E., Hammer, P. L., Sun, R. L., & Tavares, G. (2007) · Discrete Optimization · doi:10.1016/j.disopt.2007.02.001 · Cited by 50 · see citing works
Higher-order gradient descent by fusion-move graph cut
Ishikawa, H. (2009) · IEEE International Conference on Computer Vision · doi:10.1109/iccv.2009.5459187 · Cited by 35 · see citing works
Self-citationStatistical Priors for Efficient Combinatorial Optimization Via Graph Cuts
Cremers, D., & Grady, L. J. (2006) · Lecture notes in computer science · doi:10.1007/11744078_21 · Cited by 32 · see citing works
Rethinking the Prior Model for Stereo
Ishikawa, H., & Geiger, D. (2006) · Lecture notes in computer science · doi:10.1007/11744078_41 · Cited by 16 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Quantum annealing for industry applications: introduction and review
Yarkoni, S., Raponi, E., Bäck, T., & Schmitt, S. (2022) · Reports on Progress in Physics · doi:10.1088/1361-6633/ac8c54 · Cited by 341 · see citing works
A cross-disciplinary introduction to quantum annealing-based algorithms
Venegas-Andraca, S. E., Cruz-Santos, W., McGeoch, C., & Lanzagorta, M. (2018) · Contemporary Physics · doi:10.1080/00107514.2018.1450720 · Cited by 83 · see citing works
Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
Pelofske, E., Bärtschi, A., & Eidenbenz, S. (2023) · Lecture Notes in Computer Science · doi:10.1007/978-3-031-32041-5_13 · Cited by 47 · see citing works
Quadratization of symmetric pseudo-Boolean functions
Anthony, M., Boros, E., Crama, Y., & Gruber, A. (2016) · Discrete Applied Mathematics · doi:10.1016/j.dam.2016.01.001 · Cited by 26 · see citing works
Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study
Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F. (2024) · ACM Computing Surveys · doi:10.1145/3620668 · Cited by 22 · see citing works
“The potentially large overhead in the number of variables lead to the development of several methods for degree reduction (e.g., References [160, 167, 168, 180, 188]), which are explained and compared in References [53, 62, 135, 218].”
MethodBias-field digitized counterdiabatic quantum algorithm for higher-order binary optimization
Romero, S. V., Visuri, A.-M., Cadavid, A. G., Simen, A., Solano, E., & Hegade, N. N. (2025) · Communications Physics · doi:10.1038/s42005-025-02270-3 · Cited by 18 · see citing works
“We discuss the reduction of entanglement in more detail in Entanglement in the iterative optimization.”
- Authors
- Ishikawa, H.
- Affiliations
- Waseda University (JP)
- Corresponding author
- Ishikawa, H
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2011-06
- Volume
- 33
- Issue
- 6
- Pages
- 1234-1249
- ISSN
- 0162-8828 (ISSN-L)
- 2160-9292
- OpenAlex
- W2124558257
- Cited by
- 144
- References
- 36
- Citations by year
- 2026: 5 · 2025: 8 · 2024: 9 · 2023: 10 · 2022: 9 · 2021: 5 · 2020: 5 · 2019: 8 · 2018: 10 · 2017: 10 · 2016: 11 · 2015: 8 · 2014: 16 · 2013: 9 · 2012: 14
- FWCI
- 11.13
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Pattern Analysis and Machine Intelligence (publishedVersion)
- PubMed (publishedVersion)
- Funders
- Japan Society for the Promotion of Science
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Medical Image Segmentation Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Bayesian Modeling and Causal Inference
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Neural Network Applications
- Keywords
- Markov random fields, higher-order interactions, approximate optimization
- MeSH terms
- Algorithms, Artificial Intelligence, Image Enhancement, Markov Chains, Pattern Recognition, Automated
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
