CS-TR-3384, UMIACS-TR-94-133

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.

HTML or PostScript or Compressed PostScript Version of this report.

Release 3.0 of the software
Release 1.0.1 of the software
README (Send e-mail request for latest version)

University of Maryland

Department of Computer Science and Department of Electrical Engineering, and

The University of Maryland Institute for Advanced Computer Studies

For more infomation on any of the these topics, click on the hotlink.
Any queries, comments, or inquiries to:

David A. Bader (Click here for personal info!) E-mail: dbader@umiacs.umd.edu

Office phone: (301)405-6755

FAX: (301)314-9658

Return to the Experimental Parallel Algorithmics page.