# The waterfall hierarchy on weighted graphs

Fernand Meyer

► To cite this version:

Fernand Meyer. The waterfall hierarchy on weighted graphs. International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing, 2015, Reykjavik, Iceland. 10.1007/978-3-319-18720-4_28. hal-01111747

HAL Id: hal-01111747

https://minesparis-psl.hal.science/hal-01111747

Submitted on 30 Jan 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The waterfall hierarchy on weighted graphs

Fernand Meyer

CMM-Centre de Morphologie Mathématique,
Mathématiques et Systèmes, MINES ParisTech, PSL Research University, Paris,
France fernand.meyer@mines-paristech.fr

**Abstract.** We study and present two new algorithms for constructing the waterfall hierarchy of a topographic surface. The first models a topographic surface as a flooding graph, each node representing a lake filling a catchment basin up to its lowest pass point ; each edge representing such a pass point. The second algorithm produces the waterfall partition in one pass through the edges of a minimum spanning tree of the region adjacency graph associated to a topographic surface.

**KEYWORDS:** waterfall, watershed, edge and node weighted graphs, 1 pass waterfall algorithm

## 1 Introduction

The waterfall hierarchy represents the nested structure of the catchment basins of a topographic surface [3]. Consider a series of increasing floodings of a topographic surface. The associated watershed partitions form a hierarchy, as each catchment basin of a higher flooding is the union of catchment basins of a lower flooding of the surface. The waterfall hierarchy is obtained when a topographic surface is submitted to the highest flooding possible without any overflow from one catchment basin to a neighboring basin. This situation happens by flooding each catchment basin up to its lowest pass point. Fig.1 presents a topographic surface with 3 successive levels of waterfall flooding. The associated waterfall partitions are indicated below each flooded surface.

The waterfall hierarchy in independent from any parameter. For this reason, it has been used with success for reducing the oversegmentation which is inherent to the watershed segmentation. The lowest levels of the waterfall hierarchy are often linked to noise creating a manifold of meaningless minima and catchment basins. For this reason, the waterfall hierarchy has been used with success for segmenting not only gray tone images [11], but also color and texture images [18]. It has been used not only on images but also on probability distribution functions used for the stochastic watershed of multipektral images [2] or on triangular meshes [9]. The domain of application is broad going from multimedia images [21] to SAR imagery [19].

After a rapid discussion of the classical constructions of the waterfall hierar-
chy, we present two new methods having each its merits.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** 4 levels of the waterfall hierarchy. The watershed partition is presented below each topographic surface. Each topographic surface has been flooded up to the lowest pass point of the catchment basins associated to the preceding surface.</figcaption></figure>

The first method models the topographic surface as a particular graph, perfectly representing the waterfall flooding, where all lakes are full, at the verge of overflow. The nodes of the graph represent the full lakes and their weight equals the altitude of the lake. A drop of water added to a full lake provokes an overflow into a neighboring lake, called exhaust lake of the first one. An edge links each lake with its exhaust lakes; its weight is equal to the altitude of the lake which overflows through this edge. Such node and edge weighted graphs are called flooding graphs. On such a graph the trajectory of a drop of water is the same, whether one considers the edge weights alone or the node weights alone. Efficient, precise and fast algorithms based on the node weights only permit to construct the watershed partitions [15,16,17].

The second method constructs a complete waterfall hierarchy in one pass through the edges of the minimum spanning tree of the region adjacency graph

# 2 The waterfall hierarchy: state of the art.

## 2.1 An algorithm based on successive image floodings

The waterfall hierarchy has been defined by Serge Beucher for grey tone images [3]. A first algorithm works at the image level [4]. Each catchment basin is flooded up to its lowest pass point. As the pass points are regional minima of the watershed line, the solution consists in the following steps:

* constructing the watershed line of the topographic surface *f*, producing the level 1 of the waterfall hierarchy.

* constructing a ceiling function equal to *f* on the watershed line and $\infty$ elsewhere

* constructing the highest flooding of *f* under this ceiling function

A new topographic surface is produced, which is then submitted to the same process, producing the next level of the waterfall hierarchy.
**Discussion:** Using the watershed line is an advantage, as the ceiling function is easily constructed. It also is a disadvantage, as the watershed line has no meaning in terms of image content. It "takes place" to the detriment of thin and narrow structures which cannot be represented. It makes the construction of a hierarchy more difficult. Below we present a method where each level of the waterfall hierarchy is a partition, without watershed line separating neighboring tiles.

## 2.2 A watershed algorithm on the region adjacency graph

A second algorithm [5] constructs the catchment basins of the topographic surface at the pixel level. They constitute the finest level of the waterfall hierarchy. The higher levels of the waterfall hierarchy are then constructed on the region adjacency graph, whose nodes are the catchment basins, whose edges represent the pass points between neighboring basins, weighted by the altitude of the pass point. B.Marcotegui et al use construct the watershed partition of this graph by constructing a minimum spanning forest rooted in its regional minima [13]. The edge inside each tree are then contracted within the MST, producing a new tree on which the same process is repeated. This has been the first watershed algorithm on edge weighted graphs. More recent alternative algorithms could be used for the construction of the watershed on edge weighted graphs [8,10,16].

**Discussion:** The minimum spanning tree of the region adjacency graph is not unique and with a unlucky choice, the results could be poor. This is due to the fact that the watershed algorithms on an edge weighted graph are myopic and evaluate the steepness of the flooding on the immediate neighboring edges of each node. Below we present a watershed algorithm in which the steepness of the flooding is better taken into account.

# 3 Construction of the waterfall hierarchy, thanks to the flooding graph

## 3.1 Reminders on node and/or edge weighted graphs

A *non oriented graph* $G = [N, E]$ contains a set $N$ of vertices or nodes and a set $E$ of edges; an edge being a pair of vertices. The nodes are designated with small letters: $p, q, r...$. The edge linking the nodes $p$ and $q$ is designated by $e_{pq}$.

A *path*, $\pi$, is a sequence of vertices and edges, interweaved in the following way: $\pi$ starts with a vertex, say $p$, followed by an edge $e_{pq}$, incident to $p$, followed by the other endpoint $q$ of $e_{pq}$, and so on.

Edges and/or nodes may be weighted. Denote by $\mathcal{F}_e$ and $\mathcal{F}_n$ the sets of non negative weight functions on the edges and on the nodes respectively. The function $\eta \in \mathcal{F}_e$ takes the value $\eta_{pq}$ on the edge $e_{pq}$, and the graph holding only edge weights is designated by $G(\eta, \text{nil})$. The function $\nu \in \mathcal{F}_n$ takes the weight $\nu_p$ on the node $p$ and the graph holding only these node weights is designated by $G(\text{nil}, \nu)$. If both nodes and edges are weighted we write $G(\eta, \nu)$.
Images defined on a grid may also be modelled by such a graph : the pixels of the image become the nodes of the graph, with the same weight ; neighboring pixels are linked by an unweighted edge.

We define two operators between the node and edge weights:

* an operator $\delta_{en}$ associating to the function $\nu \in \mathcal{F}_n$ the function $\delta_{en}\nu \in \mathcal{F}_e$
taking the value $(\delta_{en}\nu)_{pq} = \nu_p \lor \nu_q$ on the edge $e_{pq}$.

* an operator $\varepsilon_{ne}$ associating to the function $\eta \in \mathcal{F}_e$ the function $\varepsilon_{ne}\eta \in \mathcal{F}_n$
taking the value $(\varepsilon_{ne}\eta)_p = \bigwedge_{(s \text{ neighbors of } p)} \eta_{ps}$ on the node $p$.
(s neighbors of $p$)

The pair of operators $(\delta_{en}, \varepsilon_{ne})$ form an adjunction : $\forall \eta \in \mathcal{F}_e, \forall \nu \in \mathcal{F}_n : \delta_{en}\nu < \eta \Leftrightarrow \nu < \varepsilon_{ne}\eta$. It follows that ([20]):

* $\delta_{en}$ is a dilation from $\mathcal{F}_n$ into $\mathcal{F}_e$

* $\varepsilon_{ne}$ is an erosion from $\mathcal{F}_e$ into $\mathcal{F}_n$

This section is based on the flooding graph, whose nodes represent the full lakes of a topographic surface when the flooding of each basin reaches its lowest pass points. We first rigorously establish the altitude of a full lake. The flooding graph is completed by adding the edges linking each lake with its exhaust lakes. The remarkable properties of flooding graphs permit a fast and highly accurate construction of watershed partitions.

## 3.2 The lowest pass point of a catchment basin

Consider a watershed partition $\pi$ of a topographic surface, verifying the following condition : if $s$ and $p$ are two neighboring nodes belonging to the catchment basins of two distinct minima $m_1$ and $m_2$, then there exists a non increasing path going from $s$ to $m_1$ and a non increasing path from $p$ to $m_2$.

Our aim is to figure out the level of the full lakes on such a topographic surface, given this watershed partition.

Consider a catchment basin $CB_1$ filled by a lake up to its lowest pass point, leading to an unflooded neighboring basin $CB_2$. The regional minima of $CB_1$ and $CB_2$ are respectively $m_1$ and $m_2$.

Consider among all paths linking the minimum $m_1$ with the minimum $m_2$, a path whose highest altitude is the lowest. Such a path crosses the pass point between both basins $CB_1$ and $CB_2$. The highest altitude of the path is equal to the altitude of the pass point.

Consider the altitude of the flooded relief $g$ along one such path $p$ (there may be several of them). The altitude is constant and equal to the altitude of the full lake covering $m_1$ until it reaches the last node with this altitude, say $p$ ; the next node $q$ having a lower altitude. But $g_p > g_q \Rightarrow g_p = f_p$, an implication which characterizes floodings indicating that the node $p$ is dry and has the altitude of the full lake. Three cases are to be considered:

* $p \in CB_1$ and $q \in CB_2$. Then $f_p = g_p > g_q \ge f_q$ and the altitude of the lake is $f_p \lor f_q = f_p$

* $p \in CB_2$ and $q \in CB_2$. If the node $s$ preceding $p$ on the path $p$ belongs to $CB_1$, then $f_s \le g_s = g_p = f_p$. The altitude of the lake is $f_s \lor f_p = f_p$
* $p \in CB_2$ and $q \in CB_2$. The full lake to which belongs $p$ has been cut in two by the watershed partition. The last pixel of the path $p$ belonging to $CB_1$ is a pixel $s$, followed by a series of pixels $t_1, t_2, \dots, p$ belonging to $CB_2$. All these pixels belong to the full lake : $g_s = g_{t_1} = \dots = g_p$. On the other hand $t_1, t_2, \dots, p$ constitutes a non ascending path for the function $f : f_{t_1} \ge f_{t_1} \ge \dots \ge f_p$. As $g_p = g_{t_1} \ge f_{t_1} \ge f_p = g_p$, all internal inequalities are in fact equalities and $f_{t_1} = g_p$. Here again the level of the lake is $f_s \lor f_{t_1}$ for two pixels belonging one to $CB_1$ and the other to $CB_2$.

This gives a clue for determining the altitude of the full lake which will cover the minimum $m_1$. One considers all couples of neighboring pixels which form the boundary of $CB_1$, with $p \in CB_1$ and $q \notin CB_1$. The altitude of the full lake is then the smallest value taken by $f_p \lor f_q : \lambda(CB_1) = \bigwedge_{\substack{p \in CB_1 \\ q \notin CB_1 \\ p, q \text{ neighbors}}} f_p \lor f_q$.

Each exhaust passport of the catchment basin $CB_1$ towards a basin $CB_2$ is thus a pair of nodes $p \in CB_1$ and $q \in CB_2$ verifying $f_p \lor f_q = \lambda(CB_1)$. We say that $CB_2$ is an exhaust basin of $CB_1$, as each additional drop of water falling in the full lake occupying $CB_1$ provokes an overflow into $CB_2$.

## 3.3 Modelling the catchment basins of a topographic surface as a flooding graph.

**Modeling a topographic surface as a flooding graph** Consider a topographic surface in which each catchment basin has been flooded up to its exhaust pass point. We create a graph $G = [N, E]$ in which each node $n_i$ represents a full lake occupying a catchment basin, with a weight $\nu_i$ equal to the altitude of this lake. An edge $e_{ij}$ with the same weight $\eta_{ij} = \nu_i$ links this node $n_i$ with the node $n_j$ if the catchment basin $CB_j$ is an exhaust catchment basin of $CB_i$. We say that $e_{ij}$ is an exhaust edge of $n_i$. We call this node and edge weighted graph a flooding graph of $f$, as it models the highest flooding of $f$ without overflow.

**Properties of a flooding graph** As each catchment basin has one or several lowest pass points, each node $n_k$ of $G = [N, E]$ has one or several exhaust edges. All other adjacent edges of $n_k$ correspond to higher pass points of $CB_k$ and represent the exhaust edges of neighboring catchment basins. Hence each exhaust edge of a node has the lowest weight among all adjacent edges of this node: $\nu = \epsilon_{ne}\eta$. In particular, if a node $n_i$ is linked with $n_k$ through an exhaust edge $e_{ik}$ of $n_k$, we have $\nu_k = \eta_{ik} \ge \nu_i$. It follows that each node is linked by an exhaust edge with its neighboring nodes whose weight is lower or equal; and the weight of each edge is equal to the highest weight of its extremities : $\eta_{ik} = \nu_i \lor \nu_k$. Hence $\eta = \delta_{en}\nu$.

A graph where the node and edge weights are coupled by $\nu = \epsilon_{ne}\eta$ and $\eta = \delta_{en}\nu$ is called a flooding graph [17].

**Flooding paths and regional minima** Adding a drop of water to a full lake provokes an overflow through an exhaust pass point into a neighboring full lake
with a lower or equal altitude, which itself provokes an overflow and so on until, ultimately, a regional minimum lake is reached. Such a trajectory of a drop of water is modelled on the flooding graph as a flooding path.

**Definition 1.** A path $p - e_{pq} - q - e_{qs} - s...$ is a flooding path if each node except the last one is followed by one of its exhaust edges.

By construction we then have $\nu_p = \eta_{pq} \ge \nu_q = \eta_{qs} \ge \nu_s$. Considering only the node weights, the path will be a flooding path if $\nu_p \ge \nu_q \ge \nu_s$. Considering only the edge weights it is a flooding path if each edge is an exhaust edge of the preceding node. A drop of water following a flooding path ultimately is trapped in a regional minimum. It arrives to a node whose exhaust lead to adjacent nodes with the same weight. There is no possibility to reach a deeper node as each neighboring node of a regional minimum has a higher weight and is linked with the regional minimum by an exhaust edge also with a higher weight.

The catchment zone of a regional minimum is the set of nodes linked with this minimum through a flooding path. Minimum and flooding path being the same whether one considers the node weights only or the edge weights only.

Having the same flooding paths and the same regional minima, both graphs also have the same catchment zones.

**Theorem 1.** For a flooding graph $G(\eta, \nu)$, the flooding paths, regional minima and catchment zones of the graphs $G(nil, \nu)$ and $G(\eta, nil)$ are identical.

**An order relation between flooding paths** A drop of water following a flooding path reaching a regional minimum node $p$ can quit this node through one of its exhaust edges and reach another node $q$ with the same altitude. From this node, it may then come back. Going hence and forth between $p$ and $q$, the flooding path is thus artificially prolonged as a path of infinite length. A lexicographic preorder relation compares the infinite paths $\pi = (p_1, p_2, ...p_k, ...)$ and $\chi = (q_1, q_2, ...q_k, ...)$:

$$ \begin{array}{l} * \pi < \chi \text{ if } \nu_{p_1} < \nu_{q_1} \text{ or there exists } t \text{ such that } \quad \begin{array}{l} \forall l < t : \nu_{p_l} = \nu_{q_l} \\ \nu_{p_t} < \nu_{q_t} \end{array} \\ * \pi \le \chi \text{ if } \pi < \chi \text{ or if } \forall l : \nu_{p_l} = \nu_{q_l}. \end{array} $$

The preorder relation $\le$ is total, as it permits to compare all paths with the same origin $p$. The lowest of them are called the *steepest* paths of origin $p$.

**Constructing the steepest watershed partition** A node may be linked by flooding paths with 2 or more distinct regional minima. In this case the watershed zones overlap. If one considers only the *steepest* paths, this will rarely happen, as the weights all along the paths should be absolutely identical. In particular, steepest paths reaching regional minima with different altitude necessarily have a distinct steepness. One obtains like that highly accurate watershed partitions, whereas the classical algorithms, being myopic as they use only the adjacent edges of each node, pick one solution out of many.
The classical algorithm for constructing a watershed partition in which the flooding of a node weighted graph is governed by a hierarchical queue [12] propagates the labels of the minima along the steepest flooding paths of the graph. We start detecting and labeling the node regional minima.

**Initialisation:** Create a hierarchical queue $HQ$. Put the outer boundary nodes of the regional minima in the queue corresponding to their weight. Assign to each regional minimum a distinct label

**Repeat until the HQ is empty:**

Extract the node $p$ with the highest priority from the queue.

For each node $q$ without label, such that $(p, q)$ neighbors:

$$ * label(q) = label(p) $$

* put $q$ in the queue with priority $n_q$

At the end of the process, we obtain a watershed partition $\Pi_1$ of the nodes. By merging all basins corresponding to nodes belonging to the same tile of $\Pi_1$, we obtain a new partition of the domain $D$. The boundaries of this partition are a subset of the boundaries of the initial watershed partition of $f$.

The complete process is repeated: creating the flooding graph of the new partition, constructing the watershed partition $\Pi_2$ on the nodes etc.

**The flooding graph of a region adjacency graph.** An alternative solution consists in constructing the region neighborhood graph $G = [N, E]$ associated to the initial watershed partition. The subsequent processing is done on this graph and illustrated in fig.2. The flooding graph $G'$ is constructed first: for each node $p$ of $G$, one retains in $G'$ only its exhausts edges, i.e. the adjacent edges with minimal weight. The node $p$ gets the same weight as its exhaust edges. The watershed partition of $G'$ is constructed as above, producing a number of connected components. Contracting the inside edges of each component within the graph $G$, produces a new edge weighted graph, to which the same process may be applied.

# 4 The waterfall partition in one run

We start with a minimum spanning tree $T$, with edge weights $\eta > 0$. The waterfall hierarchy will be expressed as another tree $\Theta$, having the same structure, i.e. nodes and edges as the tree $T$ but not the same weights. We associate to the tree $\Theta$ the ultrametric distance $\chi$: the distance between two nodes $n_1$ and $n_2$ is equal to the highest edge on the unique path inside $\Theta$ linking these two nodes.

Initially all edges are assigned a weight equal to $\infty$. Hence the ultrametric distance between any two node also is equal to $\infty$.

We define the open ball $\text{Ball}(p, \lambda) = \{q | \chi(p, q) < \lambda\}$ (which is identical with the nodes belonging to the connected subtree of $\Theta$ containing $p$) and $\text{diam}(p)$ its diameter, i.e. the weight of the highest edge linking two nodes of $\text{Ball}(p, \infty)$. Initially no such edge is present and we set $\text{diam}(p) = 0$.
We start with the minimum spanning tree T of the neighborhood graph. We treat the edges in ascending order of weight. Let $u = (p, q)$ the current edge to be processed :

$$- \Theta = \Theta \cup \{u\}$$

$$- \theta(u) = 1 + (\text{diam}(p) \wedge \text{diam}(q))$$

**Analysis of the algorithm (illustration in fig.3)** Before adding the edge $u$ to $\Theta$, $\text{Ball}(p, \infty)$ and $\text{Ball}(q, \infty)$ are disjoint, having respectively the diameters $d_p$ and $d_q$. After adding the edge $u$ to $\Theta$ with the weight $\theta(u)$, $\text{Ball}(p, \infty) = \text{Ball}(q, \infty)$ and the largest edge linking two nodes is either included in one of the previous balls $\text{Ball}(p, \infty)$ or $\text{Ball}(q, \infty)$ or it is the edge $u$ itself. Hence the new diameter of $\text{Ball}(p, \infty) = \text{Ball}(q, \infty)$ is equal to $\theta(u) \vee \text{diam}(p) \vee \text{diam}(q)$.

Let us analyze $\theta(u) = 1 + (\text{diam}(p) \wedge \text{diam}(q))$ :

- if for instance $\text{diam}(p) < \text{diam}(q)$ then $\text{diam}(p) \le \text{diam}(q) - 1$ and $1 + (\text{diam}(p) \wedge \text{diam}(q)) = 1 + \text{diam}(p) \le \text{diam}(q)$. The adjunction of the edge $u$ does not change the diameter of $\text{Ball}(q, \infty)$ ; it increases the diameter of $\text{Ball}(p, \infty)$ by 1.

- if $\text{diam}(p) = \text{diam}(q)$, then $\theta(u) = 1 + \text{diam}(p) = 1 + \text{diam}(q)$ and the ad- junction of the edge $u$ increases the diameter of $\text{Ball}(p, \infty)$ and of $\text{Ball}(q, \infty)$ by 1.

# 5 Conclusion

The waterfall hierarchy of a grey tone image is illustrated by the waterfall saliency of its contours in the following figure.

<figure><img src="image_3.png" /><figcaption>Initial image and the saliency of its waterfall contours.</figcaption></figure>
The waterfall hierarchy permits a structural analysis of a topographic surface as it explores the nested structure of the catchment basins, without any consideration of depth or size. It is in fact a purely ordinal process, as shown by the last algorithm presented above, which increases by one the waterfall level each time one encounters a deeper nested level.

The waterfall hierarchy has been invented, with floodings on a topographic surface in mind. It has then be, conceptually and algorithmically, extended to node or edge weighted graphs. It may be extremely useful for structuring large graphs representing complex interconnections in many domains, beyond the world of image processing.

Sometimes, there are only very few nested structures, and one may wish enriching the watershed hierarchy. B.Marcotegui and S.Beucher have shown how to prevent some regions from mergings. This domain of research merits further investigations.

## References

1. Jesús Angulo and Jean Serra. Color segmentation by ordered mergings. In *Image Processing, 2003. ICIP 2003. Proceedings. 2003 International Conference on*, volume 2, pages II-125. IEEE, 2003.

2. Jesus Angulo, Santiago Velasco-Forero, and Jocelyn Chanussot. Multiscale stochastic watershed for unsupervised hyperspectral image segmentation. In *Geoscience and Remote Sensing Symposium, 2009 IEEE International, IGARSS 2009*, volume 3, pages III-93. IEEE, 2009.

3. S. Beucher. *Segmentation d'Images et Morphologie Mathématique*. PhD thesis, E.N.S. des Mines de Paris, 1990.

4. Serge Beucher. Watershed, hierarchical segmentation and waterfall algorithm. In *Mathematical morphology and its applications to image processing*, pages 69-76. Springer, 1994.

5. B. Marcotegui and S. Beucher. Fast implementation of waterfalls based on graphs. *ISMM05 : Mathematical Morphology and its applications to Signal Processing*, pages 177-186, 2005.

6. Serge Beucher. Geodesic reconstruction, saddle zones and hierarchical segmentation. *Image Anal Stereol*, 20(2):137-141, 2001.

7. Serge Beucher, Beatriz Marcotegui, et al. P algorithm, a dramatic enhancement of the waterfall transformation. 2009.

8. Jean Cousty, Gilles Bertrand, Laurent Najman, and Michel Couprie. Watershed cuts: Minimum spanning forests and the drop of water principle. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 31:1362-1374, 2009.

9. Sebastien Delest, Romuald Bone, and Hubert Cardot. Fast segmentation of triangular meshes using waterfall. In *VIIP*, volume 6, pages 308-312, 2006.

10. SM Golodetz, C Nicholls, ID Voiculescu, and SA Cameron. Two tree-based methods for the waterfall. *Pattern Recognition*, 2014.

11. Allan Hanbury and Beatriz Marcotegui. *Waterfall segmentation of complex scenes*. Springer, 2006.

12. F. Meyer. Un algorithme optimal de ligne de partage des eaux. *Actes du*, pages 847-859, 1991.
13. F. Meyer. Minimum spanning forests for morphological segmentation. *Procs. of the second international conference on Mathematical Morphology and its Applications to Image Processing*, pages 77–84, 1994.

14. Fernand Meyer and Jean Stawiaski. Morphology on graphs and minimum spanning trees. In *Mathematical Morphology and Its Application to Signal and Image Processing*, pages 161–170. Springer, 2009.

15. F. Meyer. The steepest watershed: from graphs to images. *arXiv preprint arXiv:1204.2134*, 2012.

16. F. Meyer. Watersheds, waterfalls, on edge or node weighted graphs. *arXiv preprint arXiv:1204.2837*, 2012.

17. Fernand Meyer. Watersheds on weighted graphs. *Pattern Recognition Letters*, 2014.

18. B. Ogor, V. Haese-coat, and J. Ronsin. Sar image segmentation by mathematical morphology and texture analysis. In *Geoscience and Remote Sensing Symposium, 1996. IGARSS '96. 'Remote Sensing for a Sustainable Future.'*, International, volume 1, pages 717–719 vol.1, May 1996.

19. L. Shafarenko, M. Petrou, and J. Kittler. Automatic watershed segmentation of randomly textured color images. *Image Processing, IEEE Transactions on*, 6(11):1530–1544, Nov 1997.

20. J. Serra, editor. *Image Analysis and Mathematical Morphology. II: Theoretical Advances*. Academic Press, London, 1988.

21. Julian Stottinger, Jana Banova, Thomas Ponitz, Nicu Sebe, and Allan Hanbury. Translating journalists' requirements into features for image search. In *Virtual Systems and Multimedia, 2009. VSMM'09. 15th International Conference on*, pages 149–153. IEEE, 2009.
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** A: the region adjacency edge weighted graph G; B: the flooding graph, by retaining for each node its exhaust edges; C: assigning to each node the weight of its exhaust edges and skipping the edge weights; D: watershed partition on the nodes obtained by the hierarchical queue algorithm; E: contraction of all edges which belong to the same tile of the watershed partition. These contracted edges are indicated as bold lines. At the same time, construction of the associated flooding graph: one retains for each node obtained by contraction its lowest adjacent edges within the graph G. Each node gets the weight of its exhaust edge; F: the watershed partition associated to the previous node weighted graph; G: new contraction of edges, and associated flooding graph. Each node gets the weight of its exhaust edge. There is only one regional minimum; H: the associated watershed partition has only one region, which marks the end of the process; I: the waterfall hierarchy of all edges which have been used as exhaust edges: each edge is indexed by the time when it has been introduced in a flooding graph.</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>**Fig. 3.** A: Minimum spanning tree; B: Initially $\Theta$ has only nodes, with a diameter 0; C: The first edge is introduced in $\Theta$ with a weight 1. Its extremities have a weight 1; D,E: Additional edges are introduced in $\Theta$ with a weight 1. Their extremities have a weight 1; F: First edge linking two subtrees of $\Theta$ with diameter 1. This edge gets a waterfall weight 2, and the diameter of its subtree is 1; G: Introduction of new edges with a waterfall level of 1. The diameters of the subtrees is 2; H: Introduction of an edge linking two subtrees with a diameter 2. The resulting edge gets a weight equal to 3 and its subtree a diameter 3; I: After introduction of the last edge, all edges got their waterfall index.</figcaption></figure>