Optimal Hypercube Algorithms for Labeled Images (Preliminary Version)

摘要: Optimal hypercube algorithms are given for determining properties of labeled figures in a digitized black/white image stored one pixel per processor on fine-grained hypercube. A figure (i.e., connected component) is maximally set black pixels an image. The said to be if every the has label, with two having same label and only they figure. We show that input consisting image, systematic use divide-and-conquer into subimages n c pixels, coupled global operations such as parallel prefix semigroup reduction over figures, can used rapidly determine many figures. Using this approach, we Θ(log n) worst-case time extreme points, area, perimeter, centroid, diameter, width smallest enclosing rectangle determined. These times optimal, superior best previously published Θ(log2n).