Serial and Parallel Algorithms for the Medial Axis Transform

Jing Fu Jenq, Sartaj Sahni

Research output: Contribution to journalConference articlepeer-review

32 Scopus citations


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
Issue number12
StatePublished - 1 Dec 1992
EventProceedings of the 6th International Parallel Processing Symposium - Beverly Hills, CA, USA
Duration: 23 Mar 199226 Mar 1992


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


Dive into the research topics of 'Serial and Parallel Algorithms for the Medial Axis Transform'. Together they form a unique fingerprint.

Cite this