Serial and Parallel Algorithms for the Medial Axis Transform

John Jenq, Sartaj Sahni

Research output: Contribution to journalConference article

30 Citations (Scopus)

Abstract

We develop an O(n2) time serial algorithm to obtain the medial axis transform (MAT) of an n×n image. An O(log n) time CREW PRAM algorithm and an O(log2 n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use O(n2) processors. Two problems associated with the MAT are also studied. These are the area and perimeter reporting problem. We develop an O(log n) time hypercube algorithm for both of these problems. Here n is the number of squares in the MAT and the algorithms use O(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 Dec 1992
EventProceedings of the 6th International Parallel Processing Symposium - Beverly Hills, CA, USA
Duration: 23 Mar 199226 Mar 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{7b796e3d91d842cdb62313b9e8c715a6,
title = "Serial and Parallel Algorithms for the Medial Axis Transform",
abstract = "We develop an O(n2) time serial algorithm to obtain the medial axis transform (MAT) of an n×n image. An O(log n) time CREW PRAM algorithm and an O(log2 n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use O(n2) processors. Two problems associated with the MAT are also studied. These are the area and perimeter reporting problem. We develop an O(log n) time hypercube algorithm for both of these problems. Here n is the number of squares in the MAT and the algorithms use O(n2) processors.",
keywords = "Hypercube algorithms, image processing, medial axis, serial and parallel algorithms, transform",
author = "John Jenq and Sartaj Sahni",
year = "1992",
month = "12",
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.12.1992, p. 1218-1224.

Research output: Contribution to journalConference article

TY - JOUR

T1 - Serial and Parallel Algorithms for the Medial Axis Transform

AU - Jenq, John

AU - Sahni, Sartaj

PY - 1992/12/1

Y1 - 1992/12/1

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

AB - We develop an O(n2) time serial algorithm to obtain the medial axis transform (MAT) of an n×n image. An O(log n) time CREW PRAM algorithm and an O(log2 n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use O(n2) processors. Two problems associated with the MAT are also studied. These are the area and perimeter reporting problem. We develop an O(log n) time hypercube algorithm for both of these problems. Here n is the number of squares in the MAT and the algorithms use O(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 - Conference article

AN - SCOPUS:0026978922

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 -