Watersheds, minimum spanning forests, and the drop of water principle

Abstract : In this paper, we study the watersheds in edge-weighted graphs. Contrarily to previous work, we define the watersheds following the intuitive idea of drops of water flowing on a topographic surface. We establish the consistency of these watersheds and proved their optimality in terms of minimum spanning forests. We introduce a new local transformation on maps which equivalently define these watersheds and derive two linear-time algorithms. To our best knowledge, similar properties are not verified in other frameworks and the two proposed algorithms are the most efficient existing algorithms, both in theory and practice. Afterward, we investigate the mathematical links and differences with two other segmentation methods, i.e., the Image Foresting Transform and the topological watershed. Finally, the defined concepts are illustrated in image segmentation leading to the conclusion that the proposed approach improves the quality of watershed-based segmentations.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [48 références]  Voir  Masquer  Télécharger

Contributeur : Jean Cousty <>
Soumis le : jeudi 5 février 2015 - 15:03:42
Dernière modification le : jeudi 5 juillet 2018 - 14:25:24
Document(s) archivé(s) le : mercredi 6 mai 2015 - 10:25:48


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01113462, version 1


Jean Cousty, Gilles Bertrand, Laurent Najman, Michel Couprie. Watersheds, minimum spanning forests, and the drop of water principle. 2007. 〈hal-01113462〉



Consultations de la notice


Téléchargements de fichiers