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

### From LRDE

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## 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.

## Figures

### Fig. 1

Sample uses of the tree of shapes.

(a) Denoising (self-dual grain removal). x

### 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.

### 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.

(a) Input (b) Subdivided ~ ~ ~ ~

### 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).

### 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.

## 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]

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

Reproducible research:

## 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,
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.}
}```