Hypercube and Shuffle-Exchange Algorithms for Image Component Labeling

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1987
Accession Number
ADA197574

Entities

People

  • J. L. Sanz
  • L. Snyder
  • R. E. Cypher

Organizations

  • University of Washington

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computer Architecture
  • Computer Science
  • Computers
  • Computing System Architectures
  • Databases
  • Image Processing
  • Information Systems
  • Military Research
  • Parallel Computing
  • Parallel Processing
  • Procedures (Computers)
  • Simulations
  • Two Dimensional

Fields of Study

  • Computer science
  • Engineering

Readers

  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.