The Taub Faculty of Computer Science Events and Talks

The watershed algorithm, as proposed by Ch. Lantuéjoul in 1978 and as implemented by L. Vincent and P. Soille in 1991 for image segmentation has been in applications an extremely popular tool ever since, but it is nowadays not so popular at the research level in computer vision. Indeed, whereas it is an efficient algorithm that provides good segmentation results, it is difficult to build new work on this heuristic tool. One of the major issues is that there is some discrepancy between the classical definition of the watershed and all past algorithms. Over the last ten years, we revisited the watershed from a discrete point of view, providing efficient algorithms that correspond to their definitions and expanding the use of watershed beyond image segmentation.

In this talk, we focus on 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.

The link between watershed and optimality is the cornerstone of a framework that generalizes several state-of-the-art, graph-based segmentation algorithms, namely graph cuts, the random walker, shortest path forests, and the watershed. This generalization allowed us to exhibit a heretofore undiscovered case, for which we developed a globally optimal optimization method, which we termed “power watershed”. Our proposed power watershed algorithm computes a unique global solution to multilabeling problems, and is very fast. We further generalize and extend the framework to applications beyond image segmentation, for example image filtering optimizing an L0-norm energy, stereovision and fast and smooth surface reconstruction from a noisy cloud of 3D points.