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

Citations Over TimeTop 1% of 2009 papers

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 linear-time 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 in 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.

Related Papers

• → Watershed Pollution and Preservation: The Awareness–Appraisal Model of Environmentally Positive Intentions and Behaviors(2004)31 cited
• → Watershed Algorithm Based Image Segmentation Using Moment Preserving Bilevel Thresholding and Extended-Maxima Transform for Kernels(2015)5 cited
• → The Bear Brook Watershed in Maine: A Paired Watershed Experiment(1999)14 cited
• → A study on partnership of regional management activity by Sagami Watershed(2005)
• → Analysis of the Effect of Land Cover Changes on the Runoff Dynamics Using the HEC-HMS Model in Gajahwong Watershed, Yogyakarta(2023)