Computing geodesics and minimal surfaces via graph cuts
Top Cited Papers
- 1 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 194, 26-33 vol.1
- https://doi.org/10.1109/iccv.2003.1238310
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.Keywords
This publication has 18 references indexed in Scilit:
- Exact optimization for markov random fields with convex priorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Graphcut texturesPublished by Association for Computing Machinery (ACM) ,2003
- Image segmentation by nested cutsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Fast approximate energy minimization via graph cutsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2001
- An Experimental Comparison of Min-cut/Max-flow Algorithms for Energy Minimization in VisionPublished by Springer Nature ,2001
- Images as Embedded Maps and Minimal Surfaces: Movies, Color, Texture, and Volumetric Medical ImagesInternational Journal of Computer Vision, 2000
- Geometry of Cuts and MetricsPublished by Springer Nature ,1997
- Dynamic programming for detecting, tracking, and matching deformable contoursPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1995
- An optimal graph theoretic approach to data clustering: theory and its application to image segmentationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1993
- Snakes: Active contour modelsInternational Journal of Computer Vision, 1988