# Serial and Parallel Algorithms for the Medial Axis Transform

John Jenq, Sartaj Sahni

Research output: Contribution to journalArticleResearchpeer-review

29 Citations (Scopus)

### Abstract

We develop an Q(n2) time serial algorithm to obtain the medial axis transform (MAT) of an n x n image. An 0(log n) time CREW PRAM algorithm and an 0(log2 n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use 0(n2) processors. Two problems associated with the MAT are also studied. These are the area and perimeter reporting problem. We develop an 0(log n) time hypercube algorithm for both of these problems. Here, n is the number of squares in the MAT, and the algorithms use 0(n2) processors.

Original language English 1218-1224 7 IEEE Transactions on Pattern Analysis and Machine Intelligence 14 12 https://doi.org/10.1109/34.177389 Published - 1 Jan 1992

### Fingerprint

Medial Axis Transform
Parallel algorithms
Parallel Algorithms
Mathematical transformations
Hypercube
Perimeter

### Keywords

• Hypercube algorithms
• image processing
• medial axis
• serial and parallel algorithms
• transform

### Cite this

@article{2002932953ba4d55a85698bdb9269489,
title = "Serial and Parallel Algorithms for the Medial Axis Transform",
abstract = "We develop an Q(n2) time serial algorithm to obtain the medial axis transform (MAT) of an n x n image. An 0(log n) time CREW PRAM algorithm and an 0(log2 n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use 0(n2) processors. Two problems associated with the MAT are also studied. These are the area and perimeter reporting problem. We develop an 0(log n) time hypercube algorithm for both of these problems. Here, n is the number of squares in the MAT, and the algorithms use 0(n2) processors.",
keywords = "Hypercube algorithms, image processing, medial axis, serial and parallel algorithms, transform",
author = "John Jenq and Sartaj Sahni",
year = "1992",
month = "1",
day = "1",
doi = "10.1109/34.177389",
language = "English",
volume = "14",
pages = "1218--1224",
journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",
issn = "0162-8828",
publisher = "IEEE Computer Society",
number = "12",

}

In: IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 14, No. 12, 01.01.1992, p. 1218-1224.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Serial and Parallel Algorithms for the Medial Axis Transform

AU - Jenq, John

AU - Sahni, Sartaj

PY - 1992/1/1

Y1 - 1992/1/1

N2 - We develop an Q(n2) time serial algorithm to obtain the medial axis transform (MAT) of an n x n image. An 0(log n) time CREW PRAM algorithm and an 0(log2 n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use 0(n2) processors. Two problems associated with the MAT are also studied. These are the area and perimeter reporting problem. We develop an 0(log n) time hypercube algorithm for both of these problems. Here, n is the number of squares in the MAT, and the algorithms use 0(n2) processors.

AB - We develop an Q(n2) time serial algorithm to obtain the medial axis transform (MAT) of an n x n image. An 0(log n) time CREW PRAM algorithm and an 0(log2 n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use 0(n2) processors. Two problems associated with the MAT are also studied. These are the area and perimeter reporting problem. We develop an 0(log n) time hypercube algorithm for both of these problems. Here, n is the number of squares in the MAT, and the algorithms use 0(n2) processors.

KW - Hypercube algorithms

KW - image processing

KW - medial axis

KW - serial and parallel algorithms

KW - transform

UR - http://www.scopus.com/inward/record.url?scp=0026978922&partnerID=8YFLogxK

U2 - 10.1109/34.177389

DO - 10.1109/34.177389

M3 - Article

VL - 14

SP - 1218

EP - 1224

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

SN - 0162-8828

IS - 12

ER -