Parallel Computation of Component Trees on Distributed Memory Machines

From LRDE

Abstract

Component trees are region-based representations that encode the inclusion relationship of the threshold sets of an image. These representations are one of the most promising strategies for the analysis and the interpretation of spatial information of complex scenes as they allow the simple and efficient implementation of connected filters. This work proposes a new efficient hybrid algorithm for the parallel computation of two particular component trees—the max- and min-tree—in shared and distributed memory environments. For the node-local computation a modified version of the flooding-based algorithm of Salembier is employed. A novel tuple-based merging scheme allows to merge the acquired partial images into a globally correct view. Using the proposed approach a speed-up of up to 44.88 using 128 processing cores on eight-bit gray-scale images could be achieved. This is more than a five-fold increase over the state-of-the-art shared-memory algorithm, while also requiring only one-thirty-second of the memory.

Documents

Bibtex (lrde.bib)

@Article{	  goetz.18.tpds,
  author	= {Markus G\"otz and Gabriele Cavallaro and Thierry G\'eraud
		  and Matthias Book and Morris Riedel},
  title		= {Parallel Computation of Component Trees on Distributed
		  Memory Machines},
  journal	= {IEEE Transactions on Parallel and Distributed Systems},
  year		= 2018,
  volume	= {29},
  number	= {11},
  pages		= {2582--2598},
  month		= may,
  doi		= {10.1109/TPDS.2018.2829724},
  abstract	= {Component trees are region-based representations that
		  encode the inclusion relationship of the threshold sets of
		  an image. These representations are one of the most
		  promising strategies for the analysis and the
		  interpretation of spatial information of complex scenes as
		  they allow the simple and efficient implementation of
		  connected filters. This work proposes a new efficient
		  hybrid algorithm for the parallel computation of two
		  particular component trees---the max- and min-tree---in
		  shared and distributed memory environments. For the
		  node-local computation a modified version of the
		  flooding-based algorithm of Salembier is employed. A novel
		  tuple-based merging scheme allows to merge the acquired
		  partial images into a globally correct view. Using the
		  proposed approach a speed-up of up to 44.88 using 128
		  processing cores on eight-bit gray-scale images could be
		  achieved. This is more than a five-fold increase over the
		  state-of-the-art shared-memory algorithm, while also
		  requiring only one-thirty-second of the memory.}
}