The Tree of Shapes Turned into a Max-Tree: A Simple and Efficient Linear Algorithm

Authors

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

Where

Proceedings of the 24th IEEE International Conference on Image Processing (ICIP)

Place

Athens, Greece

Type

inproceedings

Projects

Olena

Keywords

Image

Date

2018-05-10

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

Documents

• Paper

Software

Source code for linear time ToS and benchmark reproduction is available here:

https://gitlab.lrde.epita.fr/olena/pylene-apps/tree/master/carlinet.2017.icip

Bibtex (lrde.bib)

@InProceedings{	  carlinet.18.icip,
  author	= {Edwin Carlinet and Thierry G\'eraud and S\'ebastien Crozet},
  title		= {The Tree of Shapes Turned into a Max-Tree: {A} Simple and
		  Efficient Linear Algorithm},
  booktitle	= {Proceedings of the 24th IEEE International Conference on
		  Image Processing (ICIP)},
  year		= {2018},
  month		= oct,
  pages		= {1488--1492},
  address	= {Athens, Greece},
  doi		= {10.1109/ICIP.2018.8451180},
  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.}
}