A First Parallel Algorithm to Compute the Morphological Tree of Shapes of nD Images
From LRDE
- Authors
- Sébastien Crozet, Thierry Géraud
- Where
- Proceedings of the 21st International Conference on Image Processing (ICIP)
- Place
- Paris, France
- Type
- inproceedings
- Projects
- Olena
- Keywords
- Image
- Date
- 2014-05-26
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.
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.
(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.
~ ~ | ~ ~ | |
(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).
(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.
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:
- http://reproducibleresearch.net/index.php/Main_Page
- http://en.wikipedia.org/wiki/Reproducibility#Reproducible_research
Contact
- Homepage: http://www.lrde.epita.fr/wiki/User:Theo
- Email: thierry.geraud@lrde.epita.fr
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.}, doi = {10.1109/ICIP.2014.7025593} }