Connected component labeling on coarse grain parallel computers: An experimental study

A. Choudhary, R. Thakur

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


Connected component labeling is a fundamental task in computer vision. This paper presents parallel implementations of connected component labeling for grey level images on the iPSC/2 and iPSC/86O hypercubes, the CM-5, and on the shared memory Encore Multimax multiprocessor. Several partitioning and mapping strategies, including multidimensional divide and conquer, block decomposition, and scatter decomposition, for different multiprocessor sizes, are used. Implementation results, performance evaluation and comparison for all the mapping strategies are reported. The block and scatter decomposition methods are simple to implement given the sequential algorithm, but their performance is sensitive to the distribution of intensity values in the image. The multidimensional divide and conquer method is more difficult to implement, but it performs the best irrespective of the intensity value distribution.

Original languageEnglish (US)
Pages (from-to)78-83
Number of pages6
JournalJournal of Parallel and Distributed Computing
Issue number1
StatePublished - Jan 1994

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'Connected component labeling on coarse grain parallel computers: An experimental study'. Together they form a unique fingerprint.

Cite this