title: Concurrent computation of attribute filters on shared memory parallel machines.
abstract: Morphological attribute filters have not previously been parallelized, mainly because they are both global and non-separable. We propose a parallel algorithm that achieves efficient parallelism for a large class of attribute filters, including attribute openings, closings, thinnings and thickenings, based on Salembier's Max-Trees and Min-trees. The image or volume is first partitioned in multiple slices. We then compute the Max-trees of each slice using any sequential Max-Tree algorithm. Subsequently, the Max-trees of the slices can be merged to obtain the Max-tree of the image. A C-implementation yielded good speed-ups on both a 16-processor MIPS 14000 parallel machine, and a dual-core Opteron-based machine. It is shown that the speed-up of the parallel algorithm is a direct measure of the gain with respect to the sequential algorithm used. Furthermore, the concurrent algorithm shows a speed gain of up to 72 percent on a single-core processor, due to reduced cache thrashing.
authors.affiliation: Institute for Mathematics and Computing Science, University of Groningen, AK Groningen, The Netherlands. m.h.f.wilkinson@rug.nl
authors.forename: Michael H F
authors.initials: MH
authors.lastname: Wilkinson
authors.forename: Hui
authors.initials: H
authors.lastname: Gao
authors.forename: Wim H
authors.initials: WH
authors.lastname: Hesselink
authors.forename: Jan-Eppo
authors.initials: JE
authors.lastname: Jonker
authors.forename: Arnold
authors.initials: A
authors.lastname: Meijster
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D016000:Cluster Analysis; D007089:Image Enhancement / Q000295:instrumentation / Q000379:methods; D007090:Image Interpretation, Computer-Assisted / Q000295:instrumentation / Q000379:methods*; D021621:Imaging, Three-Dimensional / Q000295:instrumentation / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods*