The DOI matches its Crossref record; 51 of the 51 references it cites were found in a registry or an index.
MRF Energy Minimization and Beyond via Dual Decomposition
Abstract
This paper introduces a new rigorous theoretical framework to address discrete MRF-based optimization in computer vision. Such a framework exploits the powerful technique of Dual Decomposition. It is based on a projected subgradient scheme that attempts to solve an MRF optimization problem by first decomposing it into a set of appropriately chosen subproblems, and then combining their solutions in a principled way. In order to determine the limits of this method, we analyze the conditions that these subproblems have to satisfy and demonstrate the extreme generality and flexibility of such an approach. We thus show that by appropriately choosing what subproblems to use, one can design novel and very powerful MRF optimization algorithms. For instance, in this manner we are able to derive algorithms that: 1) generalize and extend state-of-the-art message-passing methods, 2) optimize very tight LP-relaxations to MRF optimization, and 3) take full advantage of the special structure that may exist in particular MRFs, allowing the use of efficient inference techniques such as, e.g., graph-cut-based methods. Theoretical analysis on the bounds related with the different algorithms derived from our framework and experimental results/comparisons using synthetic and real data for a variety of tasks in computer vision demonstrate the extreme potentials of our approach.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Advances in neural information processing systems 7
Cios, K., & Shields, M. (1997) · Neurocomputing · doi:10.1016/s0925-2312(97)90018-7 · Cited by 22,059
(1988) · Cited by 16,582
Advances in Neural Information Processing Systems 19
(2007) · The MIT Press eBooks · doi:10.52202/085713 · Cited by 15,539
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
Advances in Neural Information Processing Systems 14: Proceedings of the 2001 Conference
(2002) · The MIT Press eBooks · doi:10.7551/mitpress/1120.001.0001 · Cited by 8,890
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
(1998) · Springer eBooks · doi:10.1007/978-94-011-5014-9 · Cited by 2,418
Pictorial Structures for Object Recognition
Felzenszwalb, P. F., & Huttenlocher, D. P. (2005) · International Journal of Computer Vision · doi:10.1023/b:visi.0000042934.15159.49 · Cited by 2,180
Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.850085 · Cited by 1,617
Minimization Methods for Non-Differentiable Functions
Shor, N. Z. (1985) · Springer Series in Computational Mathematics · doi:10.1007/978-3-642-82118-9 · Cited by 1,551
Freeman, W. T., Pasztor, E. C., & Carmichael, O. T. (2000) · International Journal of Computer Vision · doi:10.1023/a:1026501619075 · Cited by 1,459
Graphcut textures: image and video synthesis using graph cuts
Kwatra, V., Schödl, A., Essa, I., Turk, G., & Bobick, A. (2003) · ACM SIGGRAPH 2003 Papers · doi:10.1145/1201775.882264 · Cited by 1,216
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,095
Fields of Experts: A Framework for Learning Image Priors
Roth, S., & Black, M. J. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.160 · Cited by 1,039
Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., & Rother, C. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.70844 · Cited by 966
(2000) · Electric Power System Applications of Optimization · doi:10.1201/9781420056266-13 · Cited by 908
Graphcut textures: image and video synthesis using graph cuts
Kwatra, V., Schödl, A., Essa, I., Turk, G., & Bobick, A. (2003) · ACM Transactions on Graphics · doi:10.1145/882262.882264 · Cited by 787
MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
Wainwright, M. J., Jaakkola, T. S., & Willsky, A. S. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.856938 · Cited by 654
Incremental Subgradient Methods for Nondifferentiable Optimization
Nedic, A., & Bertsekas, D. P. (2001) · SIAM Journal on Optimization · doi:10.1137/s1052623499362111 · Cited by 589
On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs
Weiss, Y., & Freeman, W. T. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910585 · Cited by 581
Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology
Weiss, Y., & Freeman, W. T. (2001) · Neural Computation · doi:10.1162/089976601750541769 · Cited by 560
Graphical models for machine learning and digital communication
(1999) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(99)90253-5 · Cited by 454
Comparison of graph cuts with belief propagation for stereo, using identical MRF parameters
Tappen, & Freeman (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238444 · Cited by 451
Survey propagation: An algorithm for satisfiability
Braunstein, A., Mézard, M., & Zecchina, R. (2005) · Random Structures & Algorithms · doi:10.1002/rsa.20057 · Cited by 433
Optimizing Binary MRFs via Extended Roof Duality
Rother, C., Kolmogorov, V., Lempitsky, V., & Szummer, M. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383203 · Cited by 427
Nonparametric belief propagation
Sudderth, E. B., Ihler, A. T., Freeman, W. T., & Willsky, A. S. (2003) · 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings. · doi:10.1109/cvpr.2003.1211409 · Cited by 413
Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods
Nedić, A., & Ozdaglar, A. (2009) · SIAM Journal on Optimization · doi:10.1137/070708111 · Cited by 399
Feature Correspondence Via Graph Matching: Models and Global Optimization
Torresani, L., Kolmogorov, V., & Rother, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88688-4_44 · Cited by 388
Graphical Models for Machine Learning and Digital Communication
Frey, B. J. (1998) · The MIT Press eBooks · doi:10.7551/mitpress/3348.001.0001 · Cited by 352
A Linear Programming Approach to Max-Sum Problem: A Review
Werner, T. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1036 · Cited by 342
Kumar, M. P., Torr, P. H. S., & Zisserman, A. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.249 · Cited by 326
A Revolution: Belief Propagation in Graphs with Cycles
Frey, B. J., & Mackay, D. (1997) · Cited by 291
Image Completion Using Global Optimization
Komodakis, N. (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.141 · Cited by 273
Self-citationMRF Optimization via Dual Decomposition: Message-Passing Revisited
Komodakis, N., Paragios, N., & Tziritas, G. (2007) · 2007 IEEE 11th International Conference on Computer Vision · doi:10.1109/iccv.2007.4408890 · Cited by 256
Self-citationTightening LP Relaxations for MAP using Message PassingPreprint
Sontag, D. A., Meltzer, T., Globerson, A., Jaakkola, T., & Weiss, Y. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1206.3288 · Cited by 235
Visual correspondence using energy minimization and mutual information
Kim, J., Kolmogorov, & Zabih (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238463 · Cited by 234
Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing
Elidan, G., McGraw, I., & Koller, D. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1206.6837 · Cited by 225
Dynamic Graph Cuts for Efficient Inference in Markov Random Fields
Kohli, P., & Torr, P. H. S. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.1128 · Cited by 191
Fast, Approximately Optimal Solutions for Single and Dynamic MRFs
Komodakis, N., Tziritas, G., & Paragios, N. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383095 · Cited by 185
Self-citationEuler Spiral for Shape Completion
Kimia, B. B., Frankel, I., & Popescu, A.-M. (2003) · International Journal of Computer Vision · doi:10.1023/a:1023713602895 · Cited by 158
Linear Programming Relaxations and Belief Propagation -- An Empirical Study
Yanover, C., Meltzer, T., & Weiss, Y. (2006) · Journal of Machine Learning Research · doi:10.5555/1248547.1248615 · Cited by 153
Stable Fixed Points of Loopy Belief Propagation Are Local Minima of the Bethe Free Energy
Heskes, T. (2002) · neural information processing systems · Cited by 132
MAP Estimation, Linear Programming and Belief Propagation with Convex Free EnergiesPreprint
Weiss, Y., Yanover, C., & Meltzer, T. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1206.5286 · Cited by 122
Meltzer, T., Yanover, C., & Weiss, Y. (2005) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2005.110 · Cited by 109
On the optimality of tree-reweighted max-product message-passingPreprint
Kolmogorov, V., & Wainwright, M. J. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1207.1395 · Cited by 98
Beyond Loose LP-Relaxations: Optimizing MRFs by Repairing Cycles
Nikos Komodakis, A., & Nikos Paragios, A. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88690-7_60 · Cited by 86
Convexity Arguments for Efficient Minimization of the Bethe and Kikuchi Free Energies
Heskes, T. (2006) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1933 · Cited by 76
Lagrangian Relaxation for MAP Estimation in Graphical ModelsPreprint
Johnson, J. K., Malioutov, D., & Willsky, A. S. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0710.0013 · Cited by 72
Wiegerinck, W., & Heskes, T. (2002) · Cited by 69
An Analysis of Convex Relaxations for MAP Estimation
Kumar, M., Kolmogorov, V., & Torr, P. H. S. (2007) · UCL Discovery (University College London) · Cited by 28
MRFs forMRIs: Bayesian Reconstruction of MR Images via Graph Cuts
Raj, A., Singh, G., & Ramin Zabih, A. (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.192 · Cited by 27
Cited by
Deformable medical image registration: a survey
Sotiras, A., Davatzikos, C., & Paragios, N. (2013) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2013.2265603 · Cited by 1,587
“The inference was performed by a dual decomposition based method [333].”
MethodOrlando, J. I., Prokofyeva, E., & Blaschko, M. B. (2017) · IEEE Transactions on Biomedical Engineering · doi:10.1109/tbme.2016.2535311 · Cited by 503
Komodakis, N., & Pesquet, J.-C. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2377273 · Cited by 419
Self-citationDeep generative modeling for mechanistic-based learning and design of metamaterial systems
Wang, L., Chan, Y.-C., Ahmed, F., Liu, Z., Zhu, P., & Chen, W. (2020) · Computer Methods in Applied Mechanics and Engineering · doi:10.1016/j.cma.2020.113377 · Cited by 363
Message Passing Algorithms for Scalable Multitarget Tracking
Meyer, F., Kropfreiter, T., Williams, J. L., Lau, R., Hlawatsch, F., Braca, P., & Win, M. Z. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2789427 · Cited by 355
Metadata
- Authors
- Komodakis, N., Paragios, N., & Tziritas, G.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2011-03
- Volume
- 33
- Issue
- 3
- Pages
- 531-552
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2131538180
- Cited by
- 277
- References
- 51
- FWCI
- 33.54
- Type
- journal article
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.