On Euclidean Metric Approximation via Graph Cuts

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

DANĚK Ondřej MATULA Pavel

Year of publication 2011
Type Article in Proceedings
Conference Computer Vision, Imaging and Computer Graphics. Theory and Applications.
MU Faculty or unit

Faculty of Informatics

Citation
Web http://www.springerlink.com/content/q82839476621k687/
Doi http://dx.doi.org/10.1007/978-3-642-25382-9_9
Field Informatics
Keywords graph cuts; euclidean metric; anisotropic grids; image segmentation
Description The graph cut framework presents a popular energy minimization tool. In order to be able to minimize contour length dependent energy terms an appropriate metric approximation has to be embedded into the graph such that the cost of every cut approximates the length of a corresponding contour under a given metric. Formulas giving a good approximation have been introduced by Boykov and Kolmogorov for both Euclidean and Riemannian metrics. In this paper, we improve their method and obtain a better approximation in case of the Euclidean metric. In our approach, we combine the well-known Cauchy-Crofton formulas with Voronoi diagrams theory to devise a general method with straightforward extension from 2D to 3D space. Our edge weight formulas are invariant to mirroring and directly applicable to grids with anisotropic node spacing. Finally, we show that our approach yields smaller metrication errors in both the isotropic and anisotropic case and demonstrate an application of the derived formulas to biomedical image segmentation.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.