@inproceedings{eb9336a78f8c4f14bf42a272f6bc10a7,
title = "Optimal hypercube algorithms for labeled images",
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 Θ(log2n).",
keywords = "Area, Convexity, Diameter, Divide-and-conquer, Hypercube computer, Image analysis, Parallel algorithms, Perimeter, Smallest enclosing rectangle",
author = "Russ Miller and Stout, \{Quentin F.\}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1989.; Workshop on Algorithms and Data Structures, WADS 1989 ; Conference date: 17-08-1989 Through 19-08-1989",
year = "1989",
doi = "10.1007/3-540-51542-9\_43",
language = "English",
isbn = "9783540515425",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "517--528",
editor = "Frank Dehne and Jorg-Rudige Sack and Nicola Santoro",
booktitle = "Algorithms and Data Structures - Workshop, WADS 1989, Proceedings",
address = "Germany",
}