Computing geodesics and minimal surfaces via graph cuts

Y. Boykov, V. Kolmogorov, in:, IEEE, 2003, pp. 26–33.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
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.
Publishing Year
Date Published
2003-09-30
Volume
1
Page
26 - 33
Conference
ICCV: International Conference on Computer Vision
IST-REx-ID

Cite this

Boykov Y, Kolmogorov V. Computing geodesics and minimal surfaces via graph cuts. In: Vol 1. IEEE; 2003:26-33. doi:10.1109/ICCV.2003.1238310
Boykov, Y., & Kolmogorov, V. (2003). Computing geodesics and minimal surfaces via graph cuts (Vol. 1, pp. 26–33). Presented at the ICCV: International Conference on Computer Vision, IEEE. https://doi.org/10.1109/ICCV.2003.1238310
Boykov, Yuri, and Vladimir Kolmogorov. “Computing Geodesics and Minimal Surfaces via Graph Cuts,” 1:26–33. IEEE, 2003. https://doi.org/10.1109/ICCV.2003.1238310.
Y. Boykov and V. Kolmogorov, “Computing geodesics and minimal surfaces via graph cuts,” presented at the ICCV: International Conference on Computer Vision, 2003, vol. 1, pp. 26–33.
Boykov Y, Kolmogorov V. 2003. Computing geodesics and minimal surfaces via graph cuts. ICCV: International Conference on Computer Vision vol. 1. 26–33.
Boykov, Yuri, and Vladimir Kolmogorov. Computing Geodesics and Minimal Surfaces via Graph Cuts. Vol. 1, IEEE, 2003, pp. 26–33, doi:10.1109/ICCV.2003.1238310.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar