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.Gilles Bertrand received his Ingénieurs degree from the École Centrale des Arts et Manufactures in 1976. Until 1983 he was with the Thomson-CSF company, where he designed image processing systems for aeronautical applications. He received his Ph.D. from the École Centrale in 1986. He is currently teaching and doing research with the Laboratoire Algorithmique et Architecture des Systémes Informatiques, ESIEE, Paris, and with the Institut Gaspard Monge, Université de Marne-la-Vallée. His research interests are image analysis, discrete topology and mathematical morphology.