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 language | English |
---|---|
Pages (from-to) | 698-733 |
Number of pages | 36 |
Journal | Algorithmica |
Volume | 6 |
Issue number | 1-6 |
DOIs | |
Publication status | Published - Jun 1991 |
Externally published | Yes |
Keywords
- Digitized image problems
- Mesh arrays
- Parallel algorithms
- Processor-time tradeoffs