Processor-time optimal parallel algorithms for digitized images on mesh-connected processor arrays |
| |
Authors: | Hussein M. Alnuweiri and V. K. Prasanna Kumar |
| |
Affiliation: | (1) EEB-244, Department of Electrical Engineering Systems, University of Southern California, 90089-2562 Los Angeles, CA, USA |
| |
Abstract: | ![]() We present processor-time optimal parallel algorithms for several problems onn ×n digitized image arrays, on a mesh-connected array havingp processors and a memory of sizeO(n2) words. The number of processorsp can vary over the range [1,n3/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.This research was supported in part by the National Science Foundation under Grant IRI-8710836 and in part by DARPA under Contract F33615-87-C-1436 monitored by the Wright Patterson Airforce Base. |
| |
Keywords: | Digitized image problems Parallel algorithms Processor-time tradeoffs Mesh arrays |
本文献已被 SpringerLink 等数据库收录! |
|