### Abstract

We develop an Q(n^{2}) 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(log^{2} n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use 0(n^{2}) 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(n^{2}) 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 | |

State | Published - 1 Jan 1992 |

### Fingerprint

### Keywords

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

### Cite this

*IEEE Transactions on Pattern Analysis and Machine Intelligence*,

*14*(12), 1218-1224. https://doi.org/10.1109/34.177389

}

*IEEE Transactions on Pattern Analysis and Machine Intelligence*, vol. 14, no. 12, pp. 1218-1224. https://doi.org/10.1109/34.177389

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

Research output: Contribution to journal › Article › Research › peer-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 -