### Computing Geodesics and Minimal Surfaces via Graph Cuts

In *International Conference on Computer Vision (ICCV)*, vol. I, pp. 26-33, Nice, France, 2003

### 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.

##### WHOLE PAPER: pdf file (183Kb)

##### CONFERENCE TALK: ppt file (477Kb)