Concurrent computation of attribute filters on shared memory parallel machines.
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.
Wilkinson
Michael H F
MH
Institute for Mathematics and Computing Science, University of Groningen, AK Groningen, The Netherlands. m.h.f.wilkinson@rug.nl
Gao
Hui
H
Hesselink
Wim H
WH
Jonker
Jan-Eppo
JE
Meijster
Arnold
A
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*