Parallel approach for the computation of the tree of shapes on n-dimensional images



The tree of shapes is an useful image transform used to process digital images in a self-dual way. An (unpublished) algorithm working on -dimensional cellular complexes allows us to compute a tree of shapes with a quasi-linear time complexity. However, due to the great number of cells added to the initial image, it is still usually slower than other approaches specialized for 2D or 3D images. We present an approach to parallelize the quasi-linear algorithm in any dimension exhibiting interesting algorithmic and topological properties which can not be obtained from other approaches. The aim is to improve its computation time without breaking its theoretical complexity.