Quasilinear algorithm for the component tree

Laurent Najman; Michel Couprie

doi:10.1117/12.526592

19 April 2004 Quasilinear algorithm for the component tree

Laurent Najman, Michel Couprie

Proceedings Volume 5300, Vision Geometry XII; (2004) https://doi.org/10.1117/12.526592
Event: Electronic Imaging 2004, 2004, San Jose, California, United States

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.

Citation Download Citation

Laurent Najman and Michel Couprie "Quasilinear algorithm for the component tree", Proc. SPIE 5300, Vision Geometry XII, (19 April 2004); https://doi.org/10.1117/12.526592

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available