Computing geodesics and minimal surfaces via graph cuts Export

@inproceedings{citeulike:961126, 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.}, author = {Boykov, Y. and Kolmogorov, V.}, citeulike-article-id = {961126}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/ICCV.2003.1238310}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1238310}, doi = {10.1109/ICCV.2003.1238310}, journal = {Computer Vision, 2003. Proceedings. Ninth IEEE International Conference on}, keywords = {computation, geometry, graphs, imaging}, pages = {26--33 vol.1}, posted-at = {2009-06-30 08:55:12}, priority = {1}, title = {Computing geodesics and minimal surfaces via graph cuts}, url = {http://dx.doi.org/10.1109/ICCV.2003.1238310}, year = {2003} }

TY - CONF ID - citeulike:961126 L3 - citeulike-article-id:961126 N2 - 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. JF - Computer Vision, 2003. Proceedings. Ninth IEEE International Conference on EP - 33 vol.1 TI - Computing geodesics and minimal surfaces via graph cuts SP - 26 KW - computation KW - geometry KW - graphs KW - imaging AU - Boykov, Y AU - Kolmogorov, V PY - 2003/// UR - http://dx.doi.org/10.1109/ICCV.2003.1238310 ER -