Share Email Print

Proceedings Paper

Quasilinear algorithm for the component tree
Author(s): Laurent Najman; Michel Couprie
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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 have been proved to run in 0(nln(n)) complexity. 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 principle.

Paper Details

Date Published: 19 April 2004
PDF: 10 pages
Proc. SPIE 5300, Vision Geometry XII, (19 April 2004); doi: 10.1117/12.526592
Show Author Affiliations
Laurent Najman, Groupe ESIEE (France)
Michel Couprie, Groupe ESIEE (France)

Published in SPIE Proceedings Vol. 5300:
Vision Geometry XII
Longin Jan Latecki; David M. Mount; Angela Y. Wu, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?