.png){kind=icon}
Return
Waterfall-Borvka-Based Algorithm for Binary Partition Tree
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-09544-2_24.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This article presents 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 [21] have proposed a novel parallel algorithm for computing single linkage clustering from the minimum spanning tree of a point cloud on a GPU. In this paper, 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 post-processing. 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.
Keywords:
Binary partition tree
Watershed-cut
Waterfall Hierarchy
Borvka's algorithm
Minimum spanning tree
Journal
D
IF:
0
Papers:
37
Citations:
0
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSave
ShareSaveShareSave
ShareSave
View more