A Shared-memory Parallel Alpha-Tree Algorithm for Extreme Dynamic Ranges

The α-tree is an effective hierarchical image representation used for connected filtering or segmentation in remote sensing and other image applications. The α-tree constructs a tree based on the dissimilarities of the pixels in an image. Compared to other hierarchical image representations such as the component tree, the α-tree provides a better representation of the granularity of images and is easier to apply to multichannel images. The major drawback of the α-tree is its processing speed, due to the large amount of data to be processed and the lack of studies on an efficient algorithms, especially on multichannel and high dynamic range images. In this study, we introduce a novel adaptation of the hybrid component tree algorithm on the α-tree for fast parallel α-tree construction in any dynamic range of pixel dissimilarity. We tested the hybrid α-tree algorithm on Sentinel-2 remote sensing images from the European Space Agency (ESA) as well as randomly generated images, on the Hábrók high performance computing cluster. Experimental results show that the hybrid α-tree algorithm achieves the processing speed of 10--30Mpix/s and the speedup of 10--30 on a 128-core computer, proving the efficiency of the first parallel α-tree algorithm in high dynamic range, to the best of our knowledge.