About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Algorithms
Paper
Hypercube and shuffle-exchange algorithms for image component labeling
Abstract
This paper presents O(log2 N) time algorithms for labeling the connected components of an N 1 2 × N 1 2 pixel binary image using an N processor hypercube or shuffle-exchange computer. The algorithms that are presented are the first to solve this problem in O(log2 N) time using the given models of parallel computers. The algorithms are based on a divide-and-conquer approach and use as a subroutine an O(log N) time PRAM algorithm for labeling the connected components of a graph. The simulation of the PRAM by the hypercube and shuffle-exchange computers is particularly efficient because the PRAM that is being simulated has only O(N 3 4) processors and memory cells. © 1989.