Russ Miller
Dept. of Computer Science, State University of New York at Buffalo
Quentin F. Stout
EECS Department, University of Michigan
Abstract: Optimal hypercube algorithms are given for determining properties of labeled figures in a digitized black/white image stored one pixel per processor on a fine-grained hypercube. A figure (i.e., connected component) is a maximally connected set of black pixels in an image. The figures of an image are said to be labeled if every black pixel in the image has a label, with two black pixels having the same label if and only if they are in the same figure. We show that for input consisting of a labeled digitized image, a systematic use of divide-and-conquer into subimages of nc pixels, coupled with global operations such as parallel prefix and semigroup reduction over figures, can be used to rapidly determine many properties of the figures. Using this approach, we show that in Θ(log n) worst-case time the extreme points, area, perimeter, centroid, diameter, width and smallest enclosing rectangle of every figure can be determined. These times are optimal, and are superior to the best previously published times of Θ(log2 n)
Keywords: parallel algorithms, hypercube computer, convexity, area, perimeter, diameter, smallest enclosing rectangle, image analysis, divide-and-conquer, parallel computing, digital geometry, computer science
Complete paper. This paper appears in Algorithms and Data Structures: Proc. WADS '89, Springer-Verlag Lec. Notes in Computer Science 382 (1989), pp. 517-528.
|
Copyright © 2005-2017 Quentin F. Stout |