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. p. 45-52. ISBN 978-80-87342-10-7. 2010.

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

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Czech Republic
• Confidentiality degree: is not subject to a state or trade secret
• 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

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.

Abstract (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