PROCESSOR-TIME OPTIMAL PARALLEL ALGORITHMS FOR DIGITIZED IMAGES ON MESH-CONNECTED PROCESSOR ARRAYS Academic Article

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(n2) words. The number of processors p 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. 1991 Springer-Verlag New York Inc.

authors

• Alnuweiri, Hussein

published proceedings

• ALGORITHMICA

author list (cited authors)

• ALNUWEIRI, H. M., & KUMAR, V.

citation count

• 7

complete list of authors

• ALNUWEIRI, HM||KUMAR, VKP

publication date

• June 1991

publisher

• Springer Nature  Publisher

published in

• Algorithmica: an international journal in computer science  Journal

keywords

• Digitized Image Problems
• Mesh Arrays
• Parallel Algorithms
• Processor-time Tradeoffs

Digital Object Identifier (DOI)

• 10.1007/BF01759068

start page

• 698

end page

• 733

volume

• 6

issue

• 5

URL

• http%3A%2F%2Fdx.doi.org%2F10.1007%2Fbf01759068