The DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
Minimizing Nonsubmodular Functions with Graph Cuts-A Review
Abstract
Optimization techniques based on graph cuts have become a standard tool for many vision applications. These techniques allow to minimize efficiently certain energy functions corresponding to pairwise Markov Random Fields (MRFs). Currently, there is an accepted view within the computer vision community that graph cuts can only be used for optimizing a limited class of MRF energies (e.g., submodular functions). In this survey, we review some results that show that graph cuts can be applied to a much larger class of energy functions (in particular, nonsubmodular functions). While these results are well-known in the optimization community, to our knowledge they were not used in the context of computer vision and MRF optimization. We demonstrate the relevance of these results to vision on the problem of binary texture restoration.
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
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.
Geman, S., & Geman, D. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767596 · Cited by 17,949
(1988) · Cited by 16,582
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
Spatial Interaction and the Statistical Analysis of Lattice Systems
Besag, J. (1974) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1974.tb00999.x · Cited by 6,067
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-citationOn the Statistical Analysis of Dirty Pictures
Besag, J. (1986) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1986.tb01412.x · Cited by 4,191
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
Self-citationNetwork flows: Theory, algorithms and applications
(1994) · Discrete Applied Mathematics · doi:10.1016/0166-218x(94)90171-6 · Cited by 2,585
Probabilistic Networks and Expert Systems
(1999) · Information Science and Statistics · doi:10.1007/b97670 · Cited by 1,727
Markov Random Field Modeling in Computer Vision
Li, S. Z. (1995) · Computer Science Workbench · doi:10.1007/978-4-431-66933-3 · Cited by 1,276
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
Exact Maximum A Posteriori Estimation for Binary Images
Greig, D. M., Porteous, B. T., & Seheult, A. H. (1989) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1989.tb01764.x · Cited by 1,055
A 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
Interactive digital photomontage
Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., Salesin, D., & Cohen, M. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015718 · Cited by 829
Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827
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
Filters, Random Fields and Maximum Entropy (FRAME): Towards a Unified Theory for Texture Modeling
Zhu, S. C., Wu, Y., & Mumford, D. (1998) · International Journal of Computer Vision · doi:10.1023/a:1007925832420 · Cited by 652
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 486
Discriminative Learning of Markov Random Fields for Segmentation of 3D Scan Data
Anguelov, D., Taskar, B., Chatalbashev, V., Koller, D., Gupta, D., Heitz, G., & Ng, A. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.133 · Cited by 356
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
Prior learning and Gibbs reaction-diffusion
Zhu, S. C., & Mumford, D. (1997) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.632983 · Cited by 319
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 316
Efficient graph-based energy minimization methods in computer vision
Zabih, R., & Veksler, O. (1999) · Cited by 223
Interactive digital photomontage
Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., Salesin, D., & Cohen, M. (2004) · ACM SIGGRAPH 2004 Papers · doi:10.1145/1186562.1015718 · Cited by 212
Discriminative Fields for Modeling Spatial Dependencies in Natural Images
Kumar, S., & Hebert, M. (2018) · Figshare · doi:10.1184/r1/6554576 · Cited by 196
Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities
Barbu, A., & Zhu, S.-C. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.161 · Cited by 181
Some Network Flow Problems Solved with Pseudo-Boolean Programming
Ivănescu, P. L. (1965) · Operations Research · doi:10.1287/opre.13.3.388 · Cited by 170
Tree consistency and bounds on the performance of the max-product algorithm and its generalizations
Wainwright, M. J., Jaakkola, T., & Willsky, A. S. (2004) · Statistics and Computing · doi:10.1023/b:stco.0000021412.33763.d5 · Cited by 125
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-citationTexture modeling by multiple pairwise pixel interactions
Gimel’farb, G. (1996) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.544081 · Cited by 96
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
A decomposition method for minimizing quadratic pseudo-Boolean functions
Billionnet, A., & Jaumard, B. (1989) · Operations Research Letters · doi:10.1016/0167-6377(89)90043-6 · Cited by 22
Cited by
ClassCut for Unsupervised Class Segmentation
Alexe, B., Deselaers, T., & Ferrari, V. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-15555-0_28 · Cited by 993
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
Self-citationOptical 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
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
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-citation
Metadata
- Authors
- Kolmogorov, V., & Rother, C.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2007-07
- Volume
- 29
- Issue
- 7
- Pages
- 1274-1279
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2153396823
- Cited by
- 362
- References
- 35
- FWCI
- 29.67
- 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.