Concurrent computation of attribute filters on shared memory parallel machines

Research output: Contribution to journalArticleAcademicpeer-review

68 Citations (Scopus)
197 Downloads (Pure)

Abstract

Morphological attribute filters have not previously been parallelized mainly because they are both global and nonseparable. 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.
Original languageEnglish
Pages (from-to)1800-1813
Number of pages14
JournalIeee transactions on pattern analysis and machine intelligence
Volume30
Issue number10
DOIs
Publication statusPublished - Oct-2008
EventIEEE Conference on Computer Vision and Pattern Recognition - , Mongolia
Duration: 17-Jun-200722-Jun-2007

Keywords

  • attribute filters
  • connected filters
  • mathematical morphology
  • parallel computing
  • algorithms
  • LINEAR-TIME
  • CONNECTED OPERATORS
  • IMAGE-ANALYSIS
  • ALGORITHM
  • RECONSTRUCTION
  • OPENINGS
  • TREES

Cite this