A Simple Parallel Algorithm for the Medial Axis Transform

Akihiro FUJIWARA  Michiko INOUE  Toshimitsu MASUZAWA  Hideo FUJIWARA  

IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.8   pp.1038-1045
Publication Date: 1996/08/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Architectures, Algorithms and Networks for Massively Parallel Computing)
Category: Algorithms
parallel algorithm,  image processing,  medial axis transform,  PRAM,  mesh,  hypercube,  

Full Text: PDF>>
Buy this Article

The medial axis transform (MAT) is an image representation scheme. For a binary image, the MAT is defined as a set of upright maximal squares which consist of pixels of value l entirely. The MAT plays an important role in image understanding. This paper presents a parallel algorithm for computing the MAT of an n n binary image. We show that the algorithm can be performed in O(log n) time using n2/log n processors on the EREW PRAM and in O(log log n) time using n2/log log n processors on the common CRCW PRAM. We also show that the algorithm can be performed in O(n2/p2 + n) time on a p p mesh and in O(n2/p2 + (n log p)/p) time on a p2 processor hypercube (for 1 p n). The algorithm is cost optimal on the PRAMs, on the mesh (for 1 p n) and on the hypercube (for 1 p n/log n).