# A Quasi-Linear Algorithm to Compute the Tree of Shapes of n-D Images

### From LRDE

- Authors
- Thierry Géraud, Edwin Carlinet, Sébastien Crozet, Laurent Najman
- Where
- Mathematical Morphology and Its Application to Signal and Image Processing – Proceedings of the 11th International Symposium on Mathematical Morphology (ISMM)
- Place
- Uppsala, Sweden
- Type
- inproceedings
- Publisher
- Springer
- Projects
- Olena
- Keywords
- Image
- Date
- 2013-03-14

## 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 continuitywhile remaining discrete.

## Documents

## Bibtex (lrde.bib)

@InProceedings{ geraud.13.ismm, author = {Thierry G\'eraud and Edwin Carlinet and S\'ebastien Crozet and Laurent Najman}, title = {A Quasi-Linear Algorithm to Compute the Tree of Shapes of {$n$-D} Images}, booktitle = {Mathematical Morphology and Its Application to Signal and Image Processing -- Proceedings of the 11th International Symposium on Mathematical Morphology (ISMM)}, year = 2013, editor = {C.L. Luengo Hendriks and G. Borgefors and R. Strand}, volume = 7883, series = {Lecture Notes in Computer Science Series}, address = {Uppsala, Sweden}, publisher = {Springer}, pages = {98--110}, 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.} }