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

From LRDE

Abstract

The tree of shapes is an useful image transform used to process digital images in a self-dual way. An (unpublished) algorithm working on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} -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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \theta(n\log(n))} 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.