Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

An efficient parallel algorithm for graph-based image segmentation

: Wassenberg, Jan; Middelmann, Wolfgang; Sanders, Peter


Jiang, X.:
Computer analysis of images and patterns. 13th international conference, CAIP 2009 : Münster, Germany, September 2-4, 2009; Proceedings
Berlin: Springer, 2009 (Lecture Notes in Computer Science 5702)
ISBN: 3-642-03766-6
ISBN: 978-3-642-03766-5
ISSN: 0302-9743
International Conference on Computer Analysis of Images and Patterns (CAIP) <13, 2009, Münster>
Fraunhofer IOSB ()

Automatically partitioning images into regions (‘segmentation’) is challenging in terms of quality and performance. We propose a Minimum Spanning Tree-based algorithm with a novel graph-cutting heuristic, the usefulness of which is demonstrated by promising results obtained on standard images. In contrast to data-parallel schemes that divide images into independently processed tiles, the algorithm is designed to allow parallelisation without truncating objects at tile boundaries. A fast parallel implementation for shared-memory machines is shown to significantly outperform existing algorithms. It utilises a new microarchitecture-aware single-pass sort algorithm that is likely to be of independent interest.