We present an algorithm to construct the binary partition tree by altitude ordering based on Borvka’s minimum spanning tree strategy. The binary partition tree by altitude ordering is a data structure to represent an image in the form of a hierarchy of segmentations that is widely used in mathematical morphology processing. Recently, the authors of PANDORA have proposed a novel parallel algorithm for computing single linkage clustering from the minimum spanning tree of a point cloud on a GPU. We show that their method can indeed be nicely cast in the framework of watershed cuts and waterfalls for computing the binary partition tree by altitude ordering. More precisely, the method consists in performing a sequence of watershed cuts-basins contractions, seen as a variant of Borvka’s algorithm with a complexity of O(n log(n)), followed by a dedicated postprocessing. Furthermore, we show that this algorithm can be extended to process any edge-weighted graphs and not only minimum-spanning trees. These results open a new path towards massively parallel algorithms for hierarchical watershed algorithms
Localisation
Salle de réunion 4B172 (bâtiment Copernic)