94-46 Computing the Medial Axis Transform in Parallel with $O(1)$ scan operations

DIMACS TR: 94-46

Computing the Medial Axis Transform in Parallel with $O(1)$ scan operations

Authors: Afonso Ferreira, Stephane Ubeda

ABSTRACT
The main result of this paper shows that the block-based digital medial axis transform can be computed in parallel by a constant number of calls to scan (parallel prefix) operations. This gives time and/or work-optimal parallel algorithms for the distance based and the block based medial axis transform in a wide variety of parallel architectures. The most important contribution, however, is the practical aspects of our algorithms. In order to design such an algorithm, we first demonstrate that computing a block-based medial axis transform of a binary image reduces to computing the distance based medial axis transform of an oversampling of the image, because their labelings are equivalent.

Relation to Dimacs: Part of this work was done when the first author was visiting Dimacs in May, partially supported by Dimacs NSF grant STC--91--199999 and the NJ Commission.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-46.ps

DIMACS Home Page