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
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
Optimal Surface Segmentation in Volumetric Images-A Graph-Theoretic Approach
Li, K., Wu, X., Chen, D. Z., & Sonka, M. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.19 · Cited by 664
Xing, F., & Yang, L. (2016) · IEEE Reviews in Biomedical Engineering · doi:10.1109/rbme.2016.2515127 · Cited by 519
Surface Capture for Performance-Based Animation
Starck, J., & Hilton, A. (2007) · IEEE Computer Graphics and Applications · doi:10.1109/mcg.2007.68 · Cited by 452
Superpixels and Supervoxels in an Energy Optimization Framework
Veksler, O., Boykov, Y., & Mehrani, P. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-15555-0_16 · Cited by 443
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
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
A survey of graph theoretical approaches to image segmentation
Peng, B., Zhang, L., & Zhang, D. (2013) · Pattern Recognition · doi:10.1016/j.patcog.2012.09.015 · Cited by 390
Normalized Cut Loss for Weakly-Supervised CNN Segmentation
Tang, M., Djelouah, A., Perazzi, F., Boykov, Y., & Schroers, C. (2018) · 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2018.00195 · Cited by 336
Power Watershed: A Unifying Graph-Based Optimization Framework
Couprie, C., Grady, L., Najman, L., & Talbot, H. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.200 · Cited by 305
Multiview Stereo via Volumetric Graph-Cuts and Occlusion Robust Photo-Consistency
Vogiatzis, G., Hernandez Esteban, C., Torr, P. H. S., & Cipolla, R. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.70712 · Cited by 284
Multi-View Stereo Reconstruction and Scene Flow Estimation with a Global Image-Based Matching Score
Pons, J.-P., Keriven, R., & Faugeras, O. (2007) · International Journal of Computer Vision · doi:10.1007/s11263-006-8671-5 · Cited by 279
Multi-View Stereo via Volumetric Graph-Cuts
Vogiatzis, G., Torr, P. H. S., & Cipolla, R. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.238 · Cited by 275
Soft Edge Smoothness Prior for Alpha Channel Super Resolution
Dai, S., Han, M., Xu, W., Wu, Y., & Gong, Y. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383028 · Cited by 266
Advanced Level-Set-Based Cell Tracking in Time-Lapse Fluorescence Microscopy
Dzyubachyk, O., van Cappellen, W. A., Essers, J., Niessen, W. J., & Meijering, E. (2010) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2009.2038693 · Cited by 255
A convex relaxation approach for computing minimal partitions
Pock, T., Chambolle, A., Cremers, D., & Bischof, H. (2009) · 2009 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2009.5206604 · Cited by 253
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
Energy Minimization via Graph Cuts: Settling What is Possible
Freedman, D., & Drineas, P. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.143 · Cited by 173
“As a result, they have seen use in a number of different computer vision applications, including stereo [22], motion [10], and segmentation [8].”
BackgroundGeneralized Gradients: Priors on Minimization Flows
Charpiat, G., Maurel, P., Pons, J.-P., Keriven, R., & Faugeras, O. (2007) · International Journal of Computer Vision · doi:10.1007/s11263-006-9966-2 · Cited by 91
Feulner, J., Kevin Zhou, S., Hammon, M., Hornegger, J., & Comaniciu, D. (2013) · Medical Image Analysis · doi:10.1016/j.media.2012.11.001 · Cited by 72
Incorporating prior knowledge in medical image segmentation: a survey
Nosrati, M. S., & Hamarneh, G. (2016) · arXiv · doi:10.48550/arxiv.1607.01092 · Cited by 55
GPU-friendly multi-view stereo reconstruction using surfel representation and graph cuts
Chang, J. Y., Park, H., Park, I. K., Lee, K. M., & Lee, S. U. (2011) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2010.11.017 · Cited by 24
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.