The DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
Optimizing Binary MRFs via Extended Roof Duality
Abstract
Many computer vision applications rely on the efficient optimization of challenging, so-called non-submodular, binary pairwise MRFs. A promising graph cut based approach for optimizing such MRFs known as "roof duality" was recently introduced into computer vision. We study two methods which extend this approach. First, we discuss an efficient implementation of the "probing" technique introduced recently by Bows et al. (2006). It simplifies the MRF while preserving the global optimum. Our code is 400-700 faster on some graphs than the implementation of the work of Bows et al. (2006). Second, we present a new technique which takes an arbitrary input labeling and tries to improve its energy. We give theoretical characterizations of local minima of this procedure. We applied both techniques to many applications, including image segmentation, new view synthesis, super-resolution, diagram recognition, parameter learning, texture restoration, and image deconvolution. For several applications we see that we are able to find the global minimum very efficiently, and considerably outperform the original roof duality approach. In comparison to existing techniques, such as graph cut, TRW, BP, ICM, and simulated annealing, we nearly always find a lower energy.
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
Network Flows: Theory, Algorithms, and Applications.
Smith, D. K., Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1994) · The Journal of the Operational Research Society · doi:10.2307/2583863 · Cited by 8,034
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
An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision
Boykov, Y., & Kolmogorov, V. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.60 · Cited by 4,577
Self-citationInteractive graph cuts for optimal boundary & region segmentation of objects in N-D images
Boykov, Y. Y., & Jolly, M.-P. (2002) · Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001 · doi:10.1109/iccv.2001.937505 · Cited by 3,674
Freeman, W. T., Pasztor, E. C., & Carmichael, O. T. (2000) · International Journal of Computer Vision · doi:10.1023/a:1026501619075 · Cited by 1,459
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
Self-citationA linear-time algorithm for testing the truth of certain quantified boolean formulas
Aspvall, B., Plass, M. F., & Tarjan, R. E. (1979) · Information Processing Letters · doi:10.1016/0020-0190(79)90002-4 · Cited by 892
Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827
Intelligent scissors for image composition
Mortensen, E. N., & Barrett, W. A. (1995) · Proceedings of the 22nd annual conference on Computer graphics and interactive techniques - SIGGRAPH '95 · doi:10.1145/218380.218442 · Cited by 778
A 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-citationMinimizing 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
Self-citationRoof 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 316
Efficiently solving dynamic Markov random fields using graph cuts
Kohli, P., & Torr, P. H. S. (2005) · Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1 · doi:10.1109/iccv.2005.81 · Cited by 173
Image-based rendering using image-based priors
Fitzgibbon, Wexler, & Zisserman (2003) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2003.1238625 · Cited by 161
Heuristic algorithms for the unconstrained binary quadratic programming problem
Beasley, J. E. (1998) · Cited by 157
Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)
Boros, E., Hammer, P. L., & Tavares, G. (2007) · Journal of Heuristics · doi:10.1007/s10732-007-9009-3 · Cited by 142
Rother, C., Kumar, S., Kolmogorov, V., & Blake, A. (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.130 · Cited by 103
Self-citationOn 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
Self-citationPreprocessing of unconstrained quadratic binary optimization
Boros, E., Hammer, P. L., & Tavares, G. (2006) · Cited by 66
A graph cut algorithm for generalized image deconvolution
Raj, A., & Zabih, R. (2005) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2005.8 · Cited by 59
Statistical 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 35
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
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
Learning human activities and object affordances from RGB-D videos
Koppula, H. S., Gupta, R., & Saxena, A. (2013) · The International Journal of Robotics Research · doi:10.1177/0278364913478446 · Cited by 683
Anticipating Human Activities Using Object Affordances for Reactive Robotic Response
Koppula, H. S., & Saxena, A. (2016) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2430335 · Cited by 596
Motion Detail Preserving Optical Flow Estimation
Xu, L., Jia, J., & Matsushita, Y. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.236 · Cited by 493
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
Metadata
- Authors
- Rother, C., Kolmogorov, V., Lempitsky, V., & Szummer, M.
- Venue
- 2007 IEEE Conference on Computer Vision and Pattern Recognition
- Publisher
- IEEE
- Published
- 2007-06
- Pages
- 1-8
- ISSN
- 1063-6919 (ISSN-L)
- OpenAlex
- W2137117160
- Cited by
- 427
- References
- 22
- FWCI
- 22.17
- Type
- conference paper
- 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.