title: Building the component tree in quasi-linear time.
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(n ln(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 map.
authors.affiliation: Institut Gaspard-Monge, Groupe ESIEE, Laboratoire A2SI, BP99, 93162 Noisy-le-Grand, France. l.najman@esiee.fr
authors.forename: Laurent
authors.initials: L
authors.lastname: Najman
authors.forename: Michel
authors.initials: M
authors.lastname: Couprie
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D003198:Computer Simulation; D003199:Computer Systems; D007089:Image Enhancement / Q000379:methods*; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D016014:Linear Models; D010363:Pattern Recognition, Automated / Q000379:methods*