A Simple Topology Preserving Max-Flow Algorithm for Graph Cut Based Image Segmentation

DANĚK, Ondřej and Martin MAŠKA. A Simple Topology Preserving Max-Flow Algorithm for Graph Cut Based Image Segmentation. In 6th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: NOVPRESS, 2010, p. 45-52. ISBN 978-80-87342-10-7.

Basic information

Original name

A Simple Topology Preserving Max-Flow Algorithm for Graph Cut Based Image Segmentation

Name in Czech

Jednoduchý topologii zachovávající algoritmus pro segmentaci obrazu pomocí grafových řezů

Authors

DANĚK, Ondřej (203 Czech Republic, guarantor, belonging to the institution) and Martin MAŠKA (203 Czech Republic, belonging to the institution)

Edition

Brno, 6th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, p. 45-52, 8 pp. 2010

Publisher

NOVPRESS

---

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Czech Republic

Confidentiality degree

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

Publication form

printed version "print"

RIV identification code

RIV/00216224:14330/10:00044732

Organization unit

Faculty of Informatics

ISBN

978-80-87342-10-7

Keywords in English

maximum flow algorithm; topology preserving; image segmentation; graph cuts

Tags

cbia-web

Tags

International impact, Reviewed

---

Abstract

V originále

In this paper, we propose a modification to the Boykov-Kolmogorov maximum flow algorithm in order to make the algorithm preserve the topology of an initial interface. This algorithm is being widely used in computer vision and image processing fields for its efficiency and speed when dealing with problems such as graph cut based image segmentation. Using our modification we are able to incorporate a topology prior into the algorithm allowing us to apply it in situations in which the inherent topological flexibility of graph cuts is inconvenient (e.g., biomedical image segmentation). Our approach exploits the simple point concept from digital geometry and is simpler and more straightforward to implement than previously introduced methods. Due to the NP-completeness of the topology preserving problem our algorithm is only an approximation and is initialization dependent. However, promising results are demonstrated on graph cut based segmentation of both synthetic and real image data.

In Czech

Článek se zabývá návrhem algoritmu pro výpočet maximálního toku se zachováváním topologie iniciálního rozhraní a využití tohoto přístupu v oblasti segmentace obrazu.

---

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