Personal tools

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

From LRDE

Jump to: navigation, search

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.


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		= {October},
  address	= {Athens, Greece},
  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.},
  note		= {}
}