The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Computing geodesics and minimal surfaces via graph cuts
Abstract
Geodesic active contours and graph cuts are two standard image segmentation techniques. We introduce a new segmentation method combining some of their benefits. Our main intuition is that any cut on a graph embedded in some continuous space can be interpreted as a contour (in 2D) or a surface (in 3D). We show how to build a grid graph and set its edge weights so that the cost of cuts is arbitrarily close to the length (area) of the corresponding contours (surfaces) for any anisotropic Riemannian metric. There are two interesting consequences of this technical result. First, graph cut algorithms can be used to find globally minimum geodesic contours (minimal surfaces in 3D) under arbitrary Riemannian metric for a given set of boundary conditions. Second, we show how to minimize metrication artifacts in existing graph-cut based methods in vision. Theoretically speaking, our work provides an interesting link between several branches of mathematics -differential geometry, integral geometry, and combinatorial optimization. The main technical problem is solved using Cauchy-Crofton formula from integral geometry.
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
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
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
Caselles, V., Kimmel, R., & Sapiro, G. (1997) · International Journal of Computer Vision · doi:10.1023/a:1007979827043 · Cited by 5,244
Level Set Methods and Dynamic Implicit Surfaces
Osher, S., & Fedkiw, R. (2003) · Applied Mathematical Sciences · doi:10.1007/b98879 · Cited by 4,951
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
Differential geometry of curves and surfaces
(2011) · Choice Reviews Online · doi:10.5860/choice.48-3330 · Cited by 3,706
Interactive 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
Level Set Methods and Fast Marching Methods
Sethian, J. A. (1999) · Medical Entomology and Zoology · Cited by 3,616
(2003) · Selected Papers of Alan J Hoffman · doi:10.1142/9789812796936_others05 · Cited by 2,465
Integral Geometry and Geometric Probability
Santaló, L. A., & Kac, M. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511617331 · Cited by 1,794
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
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
Deza, M. M., & Laurent, M. (1997) · Algorithms and combinatorics · doi:10.1007/978-3-642-04295-9 · Cited by 1,014
Multi-camera Scene Reconstruction via Graph Cuts
Kolmogorov, V., & Zabih, R. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-47977-5_6 · Cited by 739
Global Minimum for Active Contour Models: A Minimal Path Approach
Cohen, L. D., & Kimmel, R. (1997) · International Journal of Computer Vision · doi:10.1023/a:1007922224810 · Cited by 625
A geometric snake model for segmentation of medical imagery
Yezzi, A., Kichenassamy, S., Kumar, A., Olver, P., & Tannenbaum, A. (1997) · IEEE Transactions on Medical Imaging · doi:10.1109/42.563665 · Cited by 581
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
Dynamic programming for detecting, tracking, and matching deformable contours
Geiger, D., Gupta, A., Costa, L. A., & Vlontzos, J. (1995) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.368194 · Cited by 429
Geodesic Active Regions: A New Framework to Deal with Frame Partition Problems in Computer Vision
Paragios, N., & Deriche, R. (2002) · Journal of Visual Communication and Image Representation · doi:10.1006/jvci.2001.0475 · Cited by 358
(1998) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(98)90683-6 · Cited by 342
An Experimental Comparison of Min-cut/Max-flow Algorithms for Energy Minimization in Vision
Boykov, Y., & Kolmogorov, V. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44745-8_24 · Cited by 320
Images as Embedded Maps and Minimal Surfaces: Movies, Color, Texture, and Volumetric Medical Images
Kimmel, R., Malladi, R., & Sochen, N. (2000) · International Journal of Computer Vision · doi:10.1023/a:1008171026419 · Cited by 297
Stereo Without Epipolar Lines: A Maximum-Flow Formulation
Roy, S. (1999) · International Journal of Computer Vision · doi:10.1023/a:1008192004934 · Cited by 124
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
Cited by
GrabCut: Interactive foreground extraction using iterated graph cuts
Rother, C., Kolmogorov, V., & Blake, A. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015720 · Cited by 5,703
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
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
Graph Cuts and Efficient N-D Image Segmentation
Boykov, Y., & Funka-Lea, G. (2006) · International Journal of Computer Vision · doi:10.1007/s11263-006-7934-5 · Cited by 1,910
Large-Scale Data for Multiple-View Stereopsis
Aanæs, H., Jensen, R. R., Vogiatzis, G., Tola, E., & Dahl, A. B. (2016) · International Journal of Computer Vision · doi:10.1007/s11263-016-0902-9 · Cited by 672
Metadata
- Authors
- Boykov, & Kolmogorov
- Venue
- Proceedings Ninth IEEE International Conference on Computer Vision
- Publisher
- IEEE
- Published
- 2003
- Pages
- 26-33 vol.1
- OpenAlex
- W2105365768
- Cited by
- 555
- References
- 26
- FWCI
- 15.55
- 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.