The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
Fast approximate energy minimization via graph cuts
Abstract
In this paper we address the problem of minimizing a large class of energy functions that occur in early vision. The major restriction is that the energy function's smoothness term must only involve pairs of pixels. We propose two algorithms that use graph cuts to compute a local minimum even when very large moves are allowed. The first move we consider is an /spl alpha/-/spl beta/-swap: for a pair of labels /spl alpha/,/spl beta/, this move exchanges the labels between an arbitrary set of pixels labeled a and another arbitrary set labeled /spl beta/. Our first algorithm generates a labeling such that there is no swap move that decreases the energy. The second move we consider is an /spl alpha/-expansion: for a label a, this move assigns an arbitrary set of pixels the label /spl alpha/. Our second algorithm, which requires the smoothness term to be a metric, generates a labeling such that there is no expansion move that decreases the energy. Moreover, this solution is within a known factor of the global minimum. We experimentally demonstrate the effectiveness of our approach on image restoration, stereo and motion.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
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
Kass, M., Witkin, A., & Terzopoulos, D. (1988) · International Journal of Computer Vision · doi:10.1007/bf00133570 · Cited by 17,070
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,502
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
Horn, B. K., & Schunck, B. G. (1981) · SPIE Proceedings · doi:10.1117/12.965761 · Cited by 7,394
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
On 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
Ford, D. R., & Fulkerson, D. R. (1962) · Cited by 4,072
Nonuniversal critical dynamics in Monte Carlo simulations
Swendsen, R. H., & Wang, J.-S. (1987) · Physical Review Letters · doi:10.1103/physrevlett.58.86 · Cited by 2,844
Some generalized order-disorder transformations
Potts, R. B. (1952) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100027419 · Cited by 2,122
Blake, A., & Zisserman, A. (1987) · The MIT Press eBooks · doi:10.7551/mitpress/7132.001.0001 · Cited by 2,105
Computational vision and regularization theory
Poggio, T., Torre, V., & Koch, C. (1985) · Nature · doi:10.1038/317314a0 · Cited by 1,412
Scene Labeling by Relaxation Operations
Rosenfeld, A., Hummel, R. A., & Zucker, S. W. (1976) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1976.4309519 · Cited by 1,399
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
Wu, Z., & Leahy, R. (1993) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.244673 · Cited by 1,137
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
Using dynamic programming for solving variational problems in vision
Amini, A. A., Weymouth, T. E., & Jain, R. C. (1990) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.57681 · Cited by 1,008
Wojnar, L. (1998) · Cited by 917
On the Foundations of Relaxation Labeling Processes
Hummel, R. A., & Zucker, S. W. (1983) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1983.4767390 · Cited by 885
(2018) · Physics Subject Headings (PhySH) · doi:10.29172/0660b3fe-654b-49c9-a7fa-79f18efe2aa0 · Cited by 882
Regularization of Inverse Visual Problems Involving Discontinuities
Terzopoulos, D. (1986) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1986.4767807 · Cited by 767
A pixel dissimilarity measure that is insensitive to image sampling
Birchfield, S., & Tomasi, C. (1998) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.677269 · Cited by 585
Image Analysis, Random Fields and Dynamic Monte Carlo Methods
Winkler, G. (1995) · Springer eBooks · doi:10.1007/978-3-642-97522-6 · Cited by 515
A maximum-flow formulation of the N-camera stereo correspondence problem
Roy, S., & Cox, I. J. (2002) · Sixth International Conference on Computer Vision (IEEE Cat. No.98CH36271) · doi:10.1109/iccv.1998.710763 · Cited by 485
Boundary detection by constrained optimization
Geman, D., Geman, S., Graffigne, C., & Dong, P. (1990) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.56204 · Cited by 476
Markov random fields with efficient approximations
Boykov, Y., Veksler, O., & Zabih, R. (2002) · Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.98CB36231) · doi:10.1109/cvpr.1998.698673 · Cited by 422
Self-citationDepth Discontinuities by Pixel-to-Pixel Stereo
Birchfield, S., & Tomasi, C. (1999) · International Journal of Computer Vision · doi:10.1023/a:1008160311296 · Cited by 417
Bayesian modeling of uncertainty in low-level vision
Szeliski, R. (1990) · International Journal of Computer Vision · doi:10.1007/bf00126502 · Cited by 303
The theory and practice of Bayesian image labeling
Chou, P. B., & Brown, C. M. (1990) · International Journal of Computer Vision · doi:10.1007/bf00054995 · Cited by 272
Weiss, Y., & Adelson, E. H. (1996) · Proceedings CVPR IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.1996.517092 · Cited by 230
Efficient graph-based energy minimization methods in computer vision
Zabih, R., & Veksler, O. (1999) · Cited by 223
Self-citationThe complexity of multiway cuts (extended abstract)
Dahlhaus, E., Johnson, D. S., Papadimitriou, C. H., Seymour, P. D., & Yannakakis, M. (1992) · Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 · doi:10.1145/129712.129736 · Cited by 221
Occlusions, discontinuities, and epipolar lines in stereo
Ishikawa, H., & Geiger, D. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0055670 · Cited by 190
Comparison of the efficiency of deterministic and stochastic algorithms for visual reconstruction
Blake, A. (1989) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.23109 · Cited by 178
A common framework for image segmentation
Geiger, D., & Yuille, A. (1991) · International Journal of Computer Vision · doi:10.1007/bf00115697 · Cited by 177
Segmentation by grouping junctions
Ishikawa, H., & Geiger, D. (2002) · Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.98CB36231) · doi:10.1109/cvpr.1998.698598 · Cited by 163
Parallel Integration of Vision Modules
Poggio, T., Gamble, E. B., & Little, J. J. (1988) · Science · doi:10.1126/science.3175666 · Cited by 143
An Experimental Comparison of Stereo Algorithms
Szeliski, R., & Zabih, R. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44480-7_1 · Cited by 138
Self-citationThe Dynamics of Nonlinear Relaxation Labeling Processes
Pelillo, M. (1997) · Journal of Mathematical Imaging and Vision · doi:10.1023/a:1008255111261 · Cited by 110
Image segmentation by nested cuts
Veksler, O. (2002) · 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.2000.855838 · Cited by 82
Self-citationDiscontinuity detection for visual surface reconstruction
Eric, W., Grimson, L., & Pavlidis, T. (1985) · Computer Vision Graphics and Image Processing · doi:10.1016/0734-189x(85)90163-x · Cited by 79
One-dimensional regularization with discontinuities
Lee, D., & Pavlidis, T. E. (1988) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.9105 · Cited by 71
Global optimization using embedded graphs
Geiger, D., & Ishikawa, H. (2000) · Cited by 34
Depth and motion discontinuities
Tomasi, C., & Birchfield, S. T. (1999) · Cited by 33
Fast Approximate Maximum A Posteriori Restoration of Multicolour Images
Ferrari, P. A., Frigessi, A., & de Sá, P. G. (1995) · Journal of the Royal Statistical Society Series B (Statistical Methodology) · doi:10.1111/j.2517-6161.1995.tb02043.x · Cited by 30
Unsupervised image segmentation
Barker, S. A., & Rayner, P. J. (2002) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.1998.678094 · Cited by 12
Cited by
A Database and Evaluation Methodology for Optical Flow
Baker, S., Scharstein, D., Lewis, J. P., Roth, S., Black, M. J., & Szeliski, R. (2011) · International Journal of Computer Vision · doi:10.1007/s11263-010-0390-2 · Cited by 2,205
Stereo matching using belief propagation
Sun, J., Zheng, N.-N., & Shum, H.-Y. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1206509 · Cited by 1,271
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
ScribbleSup: Scribble-Supervised Convolutional Networks for Semantic Segmentation
Lin, D., Dai, J., Jia, J., He, K., & Sun, J. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.344 · Cited by 1,129
“(5) can be solved by the graph cuts solution [3, 2].”
BackgroundComputing visual correspondence with occlusions using graph cuts
Kolmogorov, V., & Zabih, R. (2002) · Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001 · doi:10.1109/iccv.2001.937668 · Cited by 1,119
Self-citation
Metadata
- Authors
- Boykov, Y., Veksler, O., & Zabih, R.
- Venue
- Proceedings of the Seventh IEEE International Conference on Computer Vision
- Publisher
- IEEE
- Published
- 1999
- Pages
- 377-384 vol.1
- OpenAlex
- W2148852318
- Cited by
- 470
- References
- 46
- FWCI
- 14.45
- 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.