The alpha-tree, also known as the quasi-flat zone hierarchy is a widely used representation of images in Mathematical Morphology. This structure organizes the regions according to a similarity criterion into a tree, that eases the multiscale analysis of images. Many alpha-tree algorithms exist and computing this structure efficiently is still an active field of research. Indeed, the alpha-tree is commonly used in remote sensing where there is an urge for fast processing of large terabytes images. In this paper, we propose the first massively parallel alpha-tree algorithm that leverages concurrent union-find data structures to exploit the SIMT (Single Instruction Multiple Threads) programming model of GPUs. Our algorithm outperforms the State-of-the-Art parallel CPU algorithms by a factor of 10 on average on desktop computers and servers. It also opens new perspectives for using Mathematical Morphology methods on GPU pipelines.

In Mathematical Morphology, the max-tree is a region-based representation that encodes the inclusion relationship of the threshold sets of an image. This tree has proved useful in numerous image processing applications. For the last decade, work has led to improving the construction time of this structure; mixing algorithmic optimizations, parallel and distributed computing. Nevertheless, there is still no algorithm that benefits from the computing power of the massively parallel architectures. In this work, we propose the first GPU algorithm to compute the max-tree. The proposed approach leads to significant speed-ups, and is up to one order of magnitude faster than the current State-of-the-Art parallel CPU algorithms. This work paves the way for a max-tree integration in image processing GPU pipelines and real-time image processing based on Mathematical Morphology. It is also a foundation for porting other image representations from Mathematical Morphology on GPUs.