On Topological Watersheds

In this paper, we investigate topological watersheds (Couprie and Bertrand, 1997). One of our main results is a necessary and sufficient condition for a map G to be a watershed of a map F, this condition is based on a notion of extension. A consequence of the theorem is that there exists a (greedy) polynomial time algorithm to decide whether a map G is a watershed of a map F or not. We introduce a notion of “separation between two points” of an image which leads to a second necessary and sufficient condition. We also show that, given an arbitrary total order on the minima of a map, it is possible to define a notion of “degree of separation of a minimum” relative to this order. This leads to a third necessary and sufficient condition for a map G to be a watershed of a map F. At last we derive, from our framework, a new definition for the dynamics of a minimum.