The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Convergent Tree-Reweighted Message Passing for Energy Minimization
Abstract
Algorithms for discrete energy minimization are of fundamental importance in computer vision. In this paper, we focus on the recent technique proposed by Wainwright et al. [33]--tree-reweighted max-product message passing (TRW). It was inspired by the problem of maximizing a lower bound on the energy. However, the algorithm is not guaranteed to increase this bound--it may actually go down. In addition, TRW does not always converge. We develop a modification of this algorithm which we call sequential tree-reweighted message passing. Its main property is that the bound is guaranteed not to decrease. We also give a weak tree agreement condition which characterizes local maxima of the bound with respect to TRW algorithms. We prove that our algorithm has a limit point that achieves weak tree agreement. Finally, we show that, our algorithm requires half as much memory as traditional message passing approaches. Experimental results demonstrate that on certain synthetic and real problems, our algorithm outperforms both the ordinary belief propagation and tree-reweighted algorithm in [33]. In addition, on stereo problems with Potts interactions, we obtain a lower energy than graph cuts.
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
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
A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms
Scharstein, D., & Szeliski, R. (2002) · International Journal of Computer Vision · doi:10.1023/a:1014573219977 · Cited by 6,740
Cited by
Graphical Models, Exponential Families, and Variational Inference
Wainwright, M. J., & Jordan, M. I. (2007) · now publishers, Inc. eBooks · doi:10.1561/9781601981851 · Cited by 2,959
Object scene flow for autonomous vehicles
Menze, M., & Geiger, A. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7298925 · Cited by 2,270
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
“Kwon et al. [442] used TRW-S to perform inference in a factor graph that models higher-order spatial smoothness constraints for image registration.”
MethodInfluentialRobust Higher Order Potentials for Enforcing Label Consistency
Kohli, P., Ladický, L., & Torr, P. H. S. (2009) · International Journal of Computer Vision · doi:10.1007/s11263-008-0202-0 · Cited by 853
Learning Conditional Random Fields for Stereo
Scharstein, D., & Pal, C. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383191 · Cited by 851
Scene Text Recognition using Higher Order Language Priors
Mishra, A., Alahari, K., & Jawahar, C. (2012) · Procedings of the British Machine Vision Conference 2012 · doi:10.5244/c.26.127 · Cited by 831
MSM: a new flexible framework for Multimodal Surface Matching
Robinson, E. C., Jbabdi, S., Glasser, M. F., Andersson, J., Burgess, G. C., Harms, M. P., Smith, S. M., Van Essen, D. C., & Jenkinson, M. (2014) · NeuroImage · doi:10.1016/j.neuroimage.2014.05.069 · Cited by 640
Li, J., Bioucas-Dias, J. M., & Plaza, A. (2012) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2011.2162649 · Cited by 731
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
Furukawa, Y., & Hernández, C. (2015) · Foundations and Trends in Computer Graphics and Vision · doi:10.1561/0600000052 · Cited by 598
RAFT-Stereo: Multilevel Recurrent Field Transforms for Stereo Matching
Lipson, L., Teed, Z., & Deng, J. (2021) · 2021 International Conference on 3D Vision (3DV) · doi:10.1109/3dv53792.2021.00032 · Cited by 536
Baby talk: Understanding and generating simple image descriptions
Kulkarni, G., Premraj, V., Dhar, S., Li, S., Choi, Y., Berg, A. C., & Berg, T. L. (2011) · CVPR 2011 · doi:10.1109/cvpr.2011.5995466 · Cited by 521
Learning object class detectors from weakly annotated video
Prest, A., Leistner, C., Civera, J., Schmid, C., & Ferrari, V. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6248065 · Cited by 443
Optical flow modeling and computation: A survey
Fortun, D., Bouthemy, P., & Kervrann, C. (2015) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2015.02.008 · Cited by 431
Komodakis, N., & Pesquet, J.-C. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2377273 · Cited by 419
Hyperspectral Image Segmentation Using a New Bayesian Approach With Active Learning
Li, J., Bioucas-Dias, J. M., & Plaza, A. (2011) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2011.2128330 · Cited by 417
Fast approximate energy minimization with label costs
Delong, A., Osokin, A., Isack, H. N., & Boykov, Y. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5539897 · Cited by 404
3-D Video Representation Using Depth Maps
Muller, K., Merkle, P., & Wiegand, T. (2011) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2091090 · Cited by 397
Using Multiple Hypotheses to Improve Depth-Maps for Multi-View Stereo
Campbell, N. D. F., Vogiatzis, G., Hernández, C., & Cipolla, R. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88682-2_58 · Cited by 390
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
Self-citationA Comparative Study of Energy Minimization Methods for Markov Random Fields
Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., & Rother, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11744047_2 · Cited by 386
Self-citationGraph cut based image segmentation with connectivity priors
Vicente, S., Kolmogorov, V., & Rother, C. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587440 · Cited by 385
Self-citationFast Approximate Energy Minimization with Label Costs
Delong, A., Osokin, A., Isack, H. N., & Boykov, Y. (2012) · International Journal of Computer Vision · doi:10.1007/s11263-011-0437-z · Cited by 381
Hyperspectral Image Classification With Convolutional Neural Network and Active Learning
Cao, X., Yao, J., Xu, Z., & Meng, D. (2020) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2020.2964627 · Cited by 365
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
Top-down and bottom-up cues for scene text recognition
Mishra, A., Alahari, K., & Jawahar, C. V. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6247990 · Cited by 335
Ghamisi, P., Maggiori, E., Li, S., Souza, R., Tarablaka, Y., Moser, G., De Giorgi, A., Fang, L., Chen, Y., Chi, M., et al. (2018) · IEEE Geoscience and Remote Sensing Magazine · doi:10.1109/mgrs.2018.2854840 · Cited by 325
MRF-Based Deformable Registration and Ventilation Estimation of Lung CT
Heinrich, H. P., Jenkinson, M., Brady, M., & Schnabel, J. A. (2013) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2013.2246577 · Cited by 311
Hyperspectral Image Classification With Markov Random Fields and a Convolutional Neural Network
Cao, X., Zhou, F., Xu, L., Meng, D., Xu, Z., & Paisley, J. (2018) · IEEE Transactions on Image Processing · doi:10.1109/tip.2018.2799324 · Cited by 305
Stereo Correspondence by Dynamic Programming on a Tree
Veksler, O. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.334 · Cited by 295
On the convergence of approximate message passing with arbitrary matrices
Rangan, S., Schniter, P., & Fletcher, A. (2014) · 2014 IEEE International Symposium on Information Theory · doi:10.1109/isit.2014.6874830 · Cited by 279
MRF Energy Minimization and Beyond via Dual Decomposition
Komodakis, N., Paragios, N., & Tziritas, G. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.108 · Cited by 277
Weakly Supervised Localization and Learning with Generic Knowledge
Deselaers, T., Alexe, B., & Ferrari, V. (2012) · International Journal of Computer Vision · doi:10.1007/s11263-012-0538-3 · Cited by 272
Programmable aperture photography: multiplexed light field acquisition
Liang, C.-K., Lin, T.-H., Wong, B.-Y., Liu, C., & Chen, H. H. (2008) · ACM Transactions on Graphics · doi:10.1145/1360612.1360654 · Cited by 261
Inverse statistical problems: from the inverse Ising problem to data science
Nguyen, H. C., Zecchina, R., & Berg, J. (2017) · Advances in Physics · doi:10.1080/00018732.2017.1341604 · Cited by 258
MRF 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
A study on continuous max-flow and min-cut approaches
Yuan, J., Bae, E., & Tai, X.-C. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5539903 · Cited by 237
Discriminative Models for Multi-Class Object Layout
Desai, C., Ramanan, D., & Fowlkes, C. C. (2011) · International Journal of Computer Vision · doi:10.1007/s11263-011-0439-x · Cited by 208
Transformation of General Binary MRF Minimization to the First-Order Case
Ishikawa, H. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.91 · Cited by 144
Optical flow estimation with uncertainties through dynamic MRFs
Glocker, B., Paragios, N., Komodakis, N., Tziritas, G., & Navab, N. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587562 · Cited by 69
GeoF: Geodesic Forests for Learning Coupled Predictors
Kontschieder, P., Kohli, P., Shotton, J., & Criminisi, A. (2013) · 2013 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2013.16 · Cited by 63
Intrinsic dense 3D surface tracking
Zeng, Y., Wang, C., Wang, Y., Gu, X., Samaras, D., & Paragios, N. (2011) · CVPR 2011 · doi:10.1109/cvpr.2011.5995513 · Cited by 19
Metadata
- Authors
- Kolmogorov, V.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2006-10
- Volume
- 28
- Issue
- 10
- Pages
- 1568-1583
- ISSN
- 0162-8828 (ISSN-L)
- 2160-9292
- OpenAlex
- W2164918853
- Cited by
- 1,095
- References
- 2
- FWCI
- 60.85
- 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.