Hypercube and Shuffle-Exchange Algorithms for Image Component Labeling
- 1 April 1987
- report
- Published by Defense Technical Information Center (DTIC)
Abstract
This paper presents algorithms for labeling the connected components of a binary image using a hypercube or shuffle-exchange computer. The algorithms label the components of an sq 1 + N x sq 1 + N pixel image in O(long sq of N) time using a hypercube or shuffle-exchange computer with N processors and a constant amount of memory per processor. The algorithms that are presented are the first to solve this problem in O(log sq of N) time. 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 to the 3/4 power) processors and memory cells. Keywords: Parallel algorithms; Image processing; Hypercube; Shuffle exchange; Connected component labeling.Keywords
This publication has 0 references indexed in Scilit: