Sébastien Crozet

The tree of shapes turned into a max-tree: A simple and efficient linear algorithm

By Edwin Carlinet, Thierry Géraud, Sébastien Crozet

2018-05-10

In Proceedings of the 24th IEEE international conference on image processing (ICIP)

Abstract

The Tree of Shapes (ToS) is a morphological tree-based representation of an image translating the inclusion of its level lines. It features many invariances to image changes, which makes it well-suited for a lot of applications in image processing and pattern recognition. In this paper, we propose a way of turning this algorithm into a Max-Tree computation. The latter has been widely studied, and many efficient algorithms (including parallel ones) have been developed. Furthermore, we develop a specific optimization to speed-up the common 2D case. It follows a simple and efficient algorithm, running in linear time with a low memory footprint, that outperforms other current algorithms. For Reproducible Research purpose, we distribute our code as free software.

Continue reading

Un algorithme de complexité linéaire pour le calcul de l’arbre des formes

By Edwin Carlinet, Sébastien Crozet, Thierry Géraud

2018-05-04

In Actes du congrès reconnaissance des formes, image, apprentissage et perception (RFIAP)

Abstract

L’arbre des formes (AdF) est une représentation morpho- logique hiérarchique de l’image qui traduit l’inclusion des ses lignes de niveaux. Il se caractérise par son invariance à certains changement de l’image, ce qui fait de lui un outil idéal pour le développement d’applications de reconnaissance des formes. Dans cet article, nous proposons une méthode pour transformer sa construction en un calcul de Max-tree. Ce dernier a été largement étudié au cours des dernières années et des algorithmes efficaces (dont certains parallèles) existent déjà. Nous proposons également une optimisation qui permet d’accélérer son calcul dans le cas classique des images 2D. Il en découle un algorithme simple, efficace, s’exécutant linéairement en fonction du nombre de pixels, avec une faible empreinte mémoire, et qui surpasse les algorithmes à l’état de l’art.

Continue reading

Self-duality and digital topology: Links between the morphological tree of shapes and well-composed gray-level images

By Thierry Géraud, Edwin Carlinet, Sébastien Crozet

2015-04-07

In Mathematical morphology and its application to signal and image processing – proceedings of the 12th international symposium on mathematical morphology (ISMM)

Abstract

In digital topology, the use of a pair of connectivities is required to avoid topological paradoxes. In mathematical morphology, self-dual operators and methods also rely on such a pair of connectivities. There are several major issues: self-duality is impure, the image graph structure depends on the image values, it impacts the way small objects and texture are processed, and so on. A sub-class of images defined on the cubical grid, well-composed images, has been proposed, where all connectivities are equivalent, thus avoiding many topological problems. In this paper we unveil the link existing between the notion of well-composed images and the morphological tree of shapes. We prove that a well-composed image has a well-defined tree of shapes. We also prove that the only self-dual well-composed interpolation of a 2D image is obtained by the median operator. What follows from our results is that we can have a purely self-dual representation of images, and consequently, purely self-dual operators.

Continue reading

A first parallel algorithm to compute the morphological tree of shapes of $n$D images

By Sébastien Crozet, Thierry Géraud

2014-05-26

In Proceedings of the 21st international conference on image processing (ICIP)

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.

Continue reading

A quasi-linear algorithm to compute the tree of shapes of $n$-D images

By Thierry Géraud, Edwin Carlinet, Sébastien Crozet, Laurent Najman

2013-03-14

In Mathematical morphology and its application to signal and image processing – proceedings of the 11th international symposium on mathematical morphology (ISMM)

Abstract

To compute the morphological self-dual representation of images, namely the tree of shapes, the state-of-the-art algorithms do not have a satisfactory time complexity. Furthermore the proposed algorithms are only effective for 2D images and they are far from being simple to implement. That is really penalizing since a self-dual represen- tation of images is a structure that gives rise to many powerful operators and applications, and that could be very useful for 3D images. In this paper we propose a simple-to-write algorithm to compute the tree of shapes; it works for nD images and has a quasi-linear complexity when data quantization is low, typically 12 bits or less. To get that result, this paper introduces a novel representation of images that has some amazing properties of continuity, while remaining discrete.

Continue reading

Search

Tags