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

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

• Paper

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