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 languageEnglish
Pages (from-to)1218-1224
Number of pages7
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Volume14
Issue number12
DOIs
StatePublished - 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",

}

Serial and Parallel Algorithms for the Medial Axis Transform. / Jenq, John; Sahni, Sartaj.

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 -