@article {15009, title = {Parallel algorithms for image histogramming and connected components with an experimental study (extended abstract)}, journal = {ACM SIGPLAN Notices}, volume = {30}, year = {1995}, month = {1995/08//}, pages = {123 - 133}, abstract = {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.}, keywords = {connected components, histogramming, IMAGE PROCESSING, image understanding, Parallel algorithms, scalable parallel processing}, isbn = {0362-1340}, doi = {10.1145/209937.209950}, url = {http://doi.acm.org/10.1145/209937.209950}, author = {Bader,David A. and JaJa, Joseph F.} }