Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Boykov, Y., Funka-Lea, G.: Graph cuts and efficient n-d image segmentation (review). International Journal of Computer Vision 70(2), 109–131 (2006)
Boykov, Y., Kolmogorov, V.: Computing geodesics and minimal surfaces via graph cuts. In: ICCV 2003: Proceedings of the 9th IEEE International Conference on Computer Vision, p. 26 (2003)
Boykov, Y., Kolmogorov, V.: An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence 26(9), 1124–1137 (2004)
Boykov, Y., Veksler, O.: Graph cuts in vision and graphics: Theories and applications. In: Handbook of Mathematical Models in Computer Vision, pp. 79–96. Springer, Heidelberg (2006)
Brown, K.Q.: Geometric transforms for fast geometric algorithms. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA, USA (1979)
Chan, T.F., Vese, L.A.: Active contours without edges. IEEE Transactions on Image Processing 10(2), 266–277 (2001)
Kolmogorov, V., Boykov, Y.: What metrics can be approximated by geo-cuts, or global optimization of length/area and flux. In: ICCV 2005: Proceedings of the 10th IEEE International Conference on Computer Vision, pp. 564–571 (2005)
Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence 26(2), 147–159 (2004)
Mumford, D., Shah, J.: Optimal approximations by piecewise smooth functions and associated variational problems. Communications on Pure and Applied Mathematics 42, 577–684 (1989)
Zeng, Y., Chen, W., Peng, Q.: Efficiently solving the piecewise constant mumford-shah model using graph cuts. Tech. rep., Dept. of Computer Science, Zhejiang University, P.R. China (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Daněk, O., Matula, P. (2011). On Euclidean Metric Approximation via Graph Cuts. In: Richard, P., Braz, J. (eds) Computer Vision, Imaging and Computer Graphics. Theory and Applications. VISIGRAPP 2010. Communications in Computer and Information Science, vol 229. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25382-9_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-25382-9_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25381-2
Online ISBN: 978-3-642-25382-9
eBook Packages: Computer ScienceComputer Science (R0)