Serial and Parallel Algorithms for the Medial Axis Transform

Jing Fu Jenq; Sartaj Sahni

doi:10.1109/34.177389

Serial and Parallel Algorithms for the Medial Axis Transform

Jing Fu Jenq, Sartaj Sahni

Computer Science

Research output: Contribution to journal › Conference article › peer-review

32 Scopus citations

Abstract

We develop an O(n²) 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(log² n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use O(n²) 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(n²) processors.

Original language	English
Pages (from-to)	1218-1224
Number of pages	7
Journal	IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume	14
Issue number	12
DOIs	https://doi.org/10.1109/34.177389
State	Published - 1 Dec 1992
Event	Proceedings of the 6th International Parallel Processing Symposium - Beverly Hills, CA, USA Duration: 23 Mar 1992 → 26 Mar 1992

Keywords

Hypercube algorithms
image processing
medial axis
serial and parallel algorithms
transform

Access to Document

10.1109/34.177389

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 = "Jenq, {Jing Fu} and Sartaj Sahni",

year = "1992",

month = dec,

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",

note = "Proceedings of the 6th International Parallel Processing Symposium ; Conference date: 23-03-1992 Through 26-03-1992",

}

TY - JOUR

T1 - Serial and Parallel Algorithms for the Medial Axis Transform

AU - Jenq, Jing Fu

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

SN - 0162-8828

VL - 14

SP - 1218

EP - 1224

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

IS - 12

T2 - Proceedings of the 6th International Parallel Processing Symposium

Y2 - 23 March 1992 through 26 March 1992

ER -

Serial and Parallel Algorithms for the Medial Axis Transform

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this