Processor-time optimal parallel algorithms for digitized images on mesh-connected processor arrays

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

We present processor-time optimal parallel algorithms for several problems on n ×n digitized image arrays, on a mesh-connected array having p processors and a memory of size O(n 2) words. The number of processors p can vary over the range [1, n 3/2] while providing optimal speedup for these problems. The class of image problems considered here includes labeling the connected components of an image; computing the convex hull, the diameter, and a smallest enclosing box of each component; and computing all closest neighbors. Such problems arise in medium-level vision and require global operations on image pixels. To achieve optimal performance, several efficient data-movement and reduction techniques are developed for the proposed organization.

Original languageEnglish
Pages (from-to)698-733
Number of pages36
JournalAlgorithmica
Volume6
Issue number1-6
DOIs
Publication statusPublished - Jun 1991
Externally publishedYes

Keywords

  • Digitized image problems
  • Mesh arrays
  • Parallel algorithms
  • Processor-time tradeoffs

Fingerprint

Dive into the research topics of 'Processor-time optimal parallel algorithms for digitized images on mesh-connected processor arrays'. Together they form a unique fingerprint.

Cite this