## 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