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

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 ²) 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.