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.