Watershed cuts
Résumé
We study the watersheds in edge-weighted graphs. Contrarily to previous works, we define the watersheds following the intuitive idea of drops of water flowing on a topographic surface. We establish the consistency (with respect to characterizations of the catchment basins and dividing lines) of these watersheds, prove their optimality (in terms of minimum spanning forests) and derive a linear-time algorithm. To our best knowledge, similar properties are not verified in other frameworks and the proposed algorithm is the most efficient existing algorithm.