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
2007
Liste complète des métadonnées


https://hal.inria.fr/hal-01113462
Contributeur : Jean Cousty <>
Soumis le : jeudi 5 février 2015 - 15:03:42
Dernière modification le : jeudi 11 juin 2015 - 19:11:05
Document(s) archivé(s) le : mercredi 6 mai 2015 - 10:25:48

Fichier

WSCut-rapportLIGM.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01113462, version 1

Collections

Citation

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

Partager

Métriques

Consultations de
la notice

436

Téléchargements du document

266