Building the Component Tree in Quasi-Linear Time
Top Cited Papers
- 16 October 2006
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Image Processing
- Vol. 15 (11), 3531-3539
- https://doi.org/10.1109/tip.2006.877518
Abstract
The level sets of a map are the sets of points with level above a given threshold. The connected components of the level sets, thanks to the inclusion relation, can be organized in a tree structure, that is called the component tree. This tree, under several variations, has been used in numerous applications. Various algorithms have been proposed in the literature for computing the component tree. The fastest ones (considering the worst-case complexity) have been proven to run in O(nln(n)). In this paper, we propose a simple to implement quasi-linear algorithm for computing the component tree on symmetric graphs, based on Tarjan's union-find procedure. We also propose an algorithm that computes the n most significant lobes of a mapKeywords
This publication has 15 references indexed in Scilit:
- Building the Component Tree in Quasi-Linear TimeIEEE Transactions on Image Processing, 2006
- Quasi-Linear Algorithms for the Topological WatershedJournal of Mathematical Imaging and Vision, 2005
- On Topological WatershedsJournal of Mathematical Imaging and Vision, 2005
- Simple and optimal output-sensitive construction of contour trees using monotone pathsComputational Geometry, 2005
- A comparison of algorithms for connected set openings and closingsIeee Transactions On Pattern Analysis and Machine Intelligence, 2002
- Attribute Openings, Thinnings, and GranulometriesComputer Vision and Image Understanding, 1996
- Two linear time Union-Find strategies for image processingTheoretical Computer Science, 1996
- Sorting in linear time?Published by Association for Computing Machinery (ACM) ,1995
- A general approach to connected-component labeling for arbitrary image representationsJournal of the ACM, 1992
- Statistical theory in clusteringJournal of Classification, 1985