IEEE Trans Pattern Anal Mach Intell. 2018 Mar;40(3):513-526. doi: 10.1109/TPAMI.2017.2689765. Epub 2017 Mar 30.
Max-trees, or component trees, are graph structures that represent the connected components of an image in a hierarchical way. Nowadays, many application fields rely on images with high-dynamic range or floating point values. Efficient sequential algorithms exist to build trees and compute attributes for images of any bit depth. However, we show that the current parallel algorithms perform poorly already with integers at bit depths higher than 16 bits per pixel. We propose a parallel method combining the two worlds of flooding and merging max-tree algorithms. First, a pilot max-tree of a quantized version of the image is built in parallel using a flooding method. Later, this structure is used in a parallel leaf-to-root approach to compute efficiently the final max-tree and to drive the merging of the sub-trees computed by the threads. We present an analysis of the performance both on simulated and actual 2D images and 3D volumes. Execution times are about better than the fastest sequential algorithm and speed-up goes up to on 64 threads.
最大树，或组件树，是以层次方式表示图像连通分量的图结构。如今，许多应用领域都依赖于具有高动态范围或浮点值的图像。存在有效的顺序算法来构建树并计算任何位深度的图像的属性。然而，我们表明，当前的并行算法已经在像素的位深度高于 16 位时表现不佳。我们提出了一种结合洪水和合并最大树算法两个世界的并行方法。首先，使用洪水方法并行构建图像的量化版本的试点最大树。之后，该结构用于并行的叶到根方法中，以有效地计算最终的最大树，并驱动由线程计算的子树的合并。我们对模拟和实际的 2D 图像和 3D 体进行了性能分析。执行时间大约优于最快的顺序算法，并且加速高达 64 个线程。
