Fast image labeling using local operators on mesh-connected computers

Hussein M. Alnuweiri*, V. K. Prasanna Kumar

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

1 Citation (Scopus)

Abstract

A parallel algorithm is proposed for fast image labeling on mesh-connected computers using only local operators on image pixels. The algorithm requires O(kn1/k) bits of memory per processor and takes O(kn) time, for any integer k in the range [1, log n]. Bit-serial communication can be used among processors without affecting the asymptotic time complexity of the algorithm. The algorithm has a very small constant factor for the computation time, which makes it superior to previous mesh-computer labeling algorithms for most practical image sizes (e.g., up to 4096 × 4096 images). The algorithm is based on the use of stacks, which can be easily realized by using very fast shift registers within each PE. When k is a constant, the algorithm takes O(n) time and uses Θ(n1/k) bits of memory per processor, which is quite small for most practical applications.

Original languageEnglish
Pages (from-to)32-39
Number of pages8
JournalProceedings of the International Conference on Parallel Processing
Volume3
Publication statusPublished - 1989
Externally publishedYes
EventProceedings of the 1989 International Conference on Parallel Processing - University Park, PA, USA
Duration: 8 Aug 198912 Aug 1989

Fingerprint

Dive into the research topics of 'Fast image labeling using local operators on mesh-connected computers'. Together they form a unique fingerprint.

Cite this