On Euclidean Metric Approximation via Graph Cuts

DANĚK, Ondřej and Pavel MATULA. On Euclidean Metric Approximation via Graph Cuts. In Computer Vision, Imaging and Computer Graphics. Theory and Applications. Berlin, Heidelberg: Springer-Verlag, 2011, p. 125-134, 11 pp. ISBN 978-3-642-25381-2. Available from: https://dx.doi.org/10.1007/978-3-642-25382-9_9.

Basic information

Original name

On Euclidean Metric Approximation via Graph Cuts

Name in Czech

Aproximace Euklidovské metriky pomocí grafových řezů

Authors

DANĚK, Ondřej (203 Czech Republic, guarantor, belonging to the institution) and Pavel MATULA (203 Czech Republic, belonging to the institution)

Edition

Berlin, Heidelberg, Computer Vision, Imaging and Computer Graphics. Theory and Applications. p. 125-134, 11 pp. 2011

Publisher

Springer-Verlag

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

References:

URL

RIV identification code

RIV/00216224:14330/11:00067229

Organization unit

Faculty of Informatics

ISBN

978-3-642-25381-2

ISSN

DOI

http://dx.doi.org/10.1007/978-3-642-25382-9_9

UT WoS

000309949200009

Keywords in English

graph cuts; euclidean metric; anisotropic grids; image segmentation

Tags

International impact, Reviewed

---

Abstract

V originále

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.

In Czech

Článek se zabývá aproximací Euklidovské metriky pomocí grafových řezů.

---

Links

LC535, research and development project	Name: Dynamika a organizace chromosomů během buněčného cyklu v normě a patologii Investor: Ministry of Education, Youth and Sports of the CR, Dynamika a organizace chromosomů během buněčného cyklu v normě a patologii
MSM0021622419, plan (intention)	Name: Vysoce paralelní a distribuované výpočetní systémy Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
MUNI/A/0914/2009, interní kód MU	Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Acronym: SV-FI MAV) Investor: Masaryk University, Category A
2B06052, research and development project	Name: Vytipování markerů, screening a časná diagnostika nádorových onemocnění pomocí vysoce automatizovaného zpracování multidimenzionálních biomedicínských obrazů (Acronym: Biomarker) Investor: Ministry of Education, Youth and Sports of the CR, Determination of markers, screening and early diagnostics of cancer diseases using highly automated processing of multidimensional biomedical images