The Tree of Shapes Comparative Review of Component Tree Computation Algorithms.

Authors

Sébastien Crozet

Type

techreport

Year

2013

Abstract

The Tree of Shapes is an useful image transform used to process digital images in a self-dual way. It can be computed using several approaches available on the literature though no comparison of those algorithms exists yet. We provide a comparison of the existing algorithms from the computation time and space occupation point of view. We also study further the quasi-linear algorithm based on the union-find providing a parallel version and use a slight modification of the intermediate representation of images it manipulates to improve both its practical computation times and space requirements.