A First Parallel Algorithm to Compute the Morphological Tree of Shapes of nD Images

From LRDE

Abstract

The tree of shapes is a self-dual tree-based image representation belonging to the field of mathematical morphology. This representation is highly interesting since it is invariant to contrast changes and inversion, and allows for numerous and powerful applications. A new algorithm to compute the tree of shapes has been recently presented: it has a quasi-linear complexity; it is the only known algorithm that is also effective for nD images with n > 2; yet it is sequential. With the increasing size of data to process, the need of a parallel algorithm to compute that tree is of prime importance; in this paper, we present such an algorithm. We also give some benchmarks that show that the parallel version is computationally effective. As a consequence, that makes possible to process 3D images with some powerful self-dual morphological tools.

Documents


Figures

Fig. 1

Sample uses of the tree of shapes.

x x‎
(a) Denoising (self-dual grain removal).
x x
(b) Shape Filtering (keep round objects).
x
x
(c) Object Detection (energy-based method).
x
x
(d) Hierarchical Segmentation (saliency-based): click on the thumbnail (right).
x
x
(e) Hierarchical Segmentation: fine (left), coarse (right).


Fig. 2

An image (a) and its tree of shapes (b). The propagation of the level line λ ended, meaning that the nodes O and A have already been visited. The hierarchical queue contains the interior contour of B and C. Thus it can be partitioned in two sets S⁺λ = ∂B and S⁻λ = ∂C. The propagation can proceed on both parts in parallel.

Crozet14icip simpleimage.png Crozet14icip simpletos.png
(a) Image (b) Tree of shapes

Fig. 4

(a) is the input image. (b) is the result of the subdivision. (c) is the result of the immersion into the Khalimsky grid. 0-faces are represented by dots, 1-faces by segments and 2-faces by squares.

Crozet14icip Immerse f.png ~ Crozet14icip Immerse f subdivided.png ~ ~ Crozet14icip Immerse f immersed.png ~
(a) Input (b) Subdivided (c) Immersed


Fig. 8

The original image (a) and the associated F^{ord} (b); the max-tree of (b) coincides with the tree of shapes of (a).

Crozet14icip Simpleimage levels.png Crozet14icip Simpleimage revalued.png
(a) Original image (b) Re-valued image


Fig. 10

Computation times (in seconds) on a classical image test set of the following algorithms: FLLT, FLST, Géraud et al., and this paper proposal.

Crozet14icip Benchwo.png


Images

Images used for the benchmarks: [1]


Source Code

  • Code of the serial version: [2]
  • Code of the parallel version: [3]
  • Code of the milena image processing library: [4]


Useful links

The Olena platform for image processing: http://olena.lrde.epita.fr (containing the Milena C++ image processing library)

Reproducible research:


Contact

Bibtex (lrde.bib)

@InProceedings{	  crozet.14.icip,
  author	= {S\'ebastien Crozet and Thierry G\'eraud},
  title		= {A First Parallel Algorithm to Compute the Morphological
		  Tree of Shapes of {$n$D} Images},
  booktitle	= {Proceedings of the 21st International Conference on Image
		  Processing (ICIP)},
  year		= 2014,
  address	= {Paris, France},
  pages		= {2933--2937},
  abstract	= {The tree of shapes is a self-dual tree-based image
		  representation belonging to the field of mathematical
		  morphology. This representation is highly interesting since
		  it is invariant to contrast changes and inversion, and
		  allows for numerous and powerful applications. A new
		  algorithm to compute the tree of shapes has been recently
		  presented: it has a quasi-linear complexity; it is the only
		  known algorithm that is also effective for nD images with n
		  > 2; yet it is sequential. With the increasing size of data
		  to process, the need of a parallel algorithm to compute
		  that tree is of prime importance; in this paper, we present
		  such an algorithm. We also give some benchmarks that show
		  that the parallel version is computationally effective. As
		  a consequence, that makes possible to process 3D images
		  with some powerful self-dual morphological tools.}
}