Supercomputing Research Center Colloquium Talk: Scalable and Portable Parallel Algorithms for Image Processing

Abstract

This talk presents efficient and portable implementations for several useful primitives in image processing algorithms, such as histogramming, noise estimation, and connected components. An image segmentation process which makes use of these primitives, an enhancement filter called the Symmetric Neighborhood Filter, and a variant of the conventional connected components algorithm, which we call Delta-Connected Components, will also be presented. 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 performance drastically limited updating during iterative steps, and concludes with a total consistency update at the final step. This algorithms have been coded in Split-C and run on a variety of platforms, including the TMC CM-5, IBM SP-1 and SP-2, Intel Paragon, Cray T3D, Meiko CS-2, and workstation clusters. Our experimental results are consistent with the theoretical analysis and provide the best known execution times for several of these operations, even when compared with machine specific implementations. More efficient implementations of Split-C will likely result in even faster execution times. The suppoert by NASA Graduate Student Researcher Fellowship No. NGT-50951 is gratefully acknowledged.

David A. Bader

Distinguished Professor and Director of the Institute for Data Science

David A. Bader is a Distinguished Professor in the Department of Computer Science at New Jersey Institute of Technology.