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



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.