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 metadatas

Cited literature [48 references]  Display  Hide  Download

https://hal.inria.fr/hal-01113462
Contributor : Jean Cousty <>
Submitted on : Thursday, February 5, 2015 - 3:03:42 PM
Last modification on : Thursday, July 5, 2018 - 2:25:24 PM
Long-term archiving on : Wednesday, May 6, 2015 - 10:25:48 AM

File

WSCut-rapportLIGM.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01113462, version 1

Citation

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

Share

Metrics

Record views

551

Files downloads

1388