David A. Bader
IEEE Fellow
AAAS Fellow
Professor
College of Computing
Georgia Tech
Atlanta, GA 30332


 
 

 

Parallel Algorithms for Image Histogramming and Connected Components with an Experimental Study

This paper presents efficient and portable implementations of two useful primitives in image processing algorithms, histogramming and connected components. Our general framework is a single-address space, distributed memory programming model. We use efficient techniques for distributing and coalescing data as well as efficient combinations of task and data parallelism. Our connected components algorithm uses a novel approach for parallel merging which performs drastically limited updating during iterative steps, and concludes with a total consistency update at the final step. The algorithms have been coded in Split-C and run on a variety of platforms. Our experimental results are consistent with the theoretical analysis and provide the best known execution times for these two primitives, even when compared with machine specific implementations. More efficient implementations of Split-C will likely result in even faster execution times.

Publication History

Versions of this paper appeared as:
  1. University of Maryland CS-TR-3384, UMIACS-TR-94-133
  2. D. A. Bader and J. JáJá . `` Parallel Algorithms for Image Histogramming and Connected Components with an Experimental Study,'' Journal of Parallel and Distributed Computing, 35(2)173-190, June 1996.

Download this report in Adobe PDF

 

 
 

Last updated: July 25, 2004

 




Computational Biology



Parallel Computing



Combinatorics