Newsgroups: comp.parallel,comp.sys.super,comp.ai.vision From: dbader@Glue.umd.edu (David Bader) Subject: PARALLEL ALGORITHMS FOR IMAGE HISTOGRAMMING AND CONNECTED COMPONENTS Organization: Professional Student, University of Maryland, College Park Date: Wed, 28 Dec 1994 14:34:19 GMT Message-ID: <3cai3j$7uo@mojo.eng.umd.edu> ANNOUNCEMENT: -------------------------------------------------------------------- PARALLEL ALGORITHMS FOR IMAGE HISTOGRAMMING AND CONNECTED COMPONENTS WITH AN EXPERIMENTAL STUDY -------------------------------------------------------------------- We have released our technical report entitled ``Parallel Algorithms for Image Histogramming and Connected Components with an Experimental Study,'' by David A. Bader and Joseph Ja'Ja'. Technical Report Number: CS-TR-3384 and UMIACS-TR-94-133. Institute for Advanced Computer Studies (UMIACS) and the Department of Electrical Engineering, University of Maryland, College Park, December 1994. The paper is available in PostScript format via WWW: http://www.umiacs.umd.edu/~dbader or via anonymous ftp to: ftp.cs.umd.edu:/pub/papers/TRs/3384.ps.Z If you prefer a hardcopy, please reply to this message and send me your mailing address. 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. --- David A. Bader Electrical Engineering Department A.V. Williams Building University of Maryland College Park, MD 20742 Office: 301-405-6755 FAX: 301-314-9658 Internet: dbader@eng.umd.edu WWW: http://www.umiacs.umd.edu/~dbader