A Tree of Shapes Computation Algorithm for Massively Parallel Architectures

The tree of shapes of an image (ToS) is a powerful hierarchical representation of image. Being self-dual and contrast invariant, it is well-suited for several image processing tasks such as filtering, segmentation or object detection. It is a must-have tool in the toolbox of image processing practitioners, if only as a pre-or post-processing usage. Nevertheless, the ToS computation is a complex task, so far, limited to CPU. This is a major bottleneck in any deep-learning or real-time image processing pipeline that requires GPUs for speed. This limitation is due to a front propagation algorithm, used in the ToS construction, that is intrinsically sequential and not well-suited for massively parallel architectures. In this paper, we present a new approach to compute, end-to-end, the tree of shapes on massively parallel architectures that outperforms the existing algorithms. The parallelization strategies introduced in this paper can further be used to speed up many propagation-based algorithms such as distance transforms.