Publication IEICE TRANSACTIONS on Information and SystemsVol.E79-DNo.8pp.1038-1045 Publication Date: 1996/08/25 Online ISSN: DOI: Print ISSN: 0916-8532 Type of Manuscript: Special Section PAPER (Special Issue on Architectures, Algorithms and Networks for Massively Parallel Computing) Category: Algorithms Keyword: parallel algorithm, image processing, medial axis transform, PRAM, mesh, hypercube,
Full Text: PDF>>
Summary: 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 nn 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 pp mesh and in O(n2/p2 + (n log p)/p) time on a p2 processor hypercube (for 1 pn). The algorithm is cost optimal on the PRAMs, on the mesh (for 1 pn) and on the hypercube (for 1 pn/log n).