Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle

Abstract : We study the watersheds in edge-weighted graphs. We define the watershed cuts following the intuitive idea of drops of water flowing on a topographic surface. We first establish the consistency of these watersheds: they can be equivalently defined by their "catchment basins" (through a steepest descent property) or by the "dividing lines" separating these catchment basins (through the drop of water principle). Then we prove, through an equivalence theorem, their optimality in terms of minimum spanning forests. Afterward, we introduce a lineartime algorithm to compute them. To the best of our knowledge, similar properties are not verified in other frameworks and the proposed algorithm is the most efficient existing algorithm, both in theory and practice. Finally, the defined concepts are illustrated in image segmentation leading to the conclusion that the proposed approach improves, on the tested images, the quality of watershed-based segmentations.
Type de document :
Article dans une revue
IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, 2009, 31 (8), pp.1362-1374
Liste complète des métadonnées


https://hal-upec-upem.archives-ouvertes.fr/hal-00622410
Contributeur : Laurent Najman <>
Soumis le : dimanche 13 janvier 2013 - 22:36:31
Dernière modification le : lundi 14 janvier 2013 - 15:15:20
Document(s) archivé(s) le : dimanche 14 avril 2013 - 02:20:10

Fichier

flow_watershedPAMI.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00622410, version 1

Citation

Jean Cousty, Gilles Bertrand, Laurent Najman, Michel Couprie. Watershed Cuts: Minimum Spanning Forests and the Drop of Water Principle. IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, 2009, 31 (8), pp.1362-1374. <hal-00622410>

Partager

Métriques

Consultations de
la notice

205

Téléchargements du document

1043