Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [48 references]  Display  Hide  Download
Contributor : Jean Cousty Connect in order to contact the contributor
Submitted on : Thursday, February 5, 2015 - 3:03:42 PM
Last modification on : Saturday, January 15, 2022 - 3:56:50 AM
Long-term archiving on: : Wednesday, May 6, 2015 - 10:25:48 AM


Files produced by the author(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⟩



Record views


Files downloads