P. Arbelaez, M. Maire, C. Fowlkes, and J. Malik, Contour detection and hierarchical image segmentation, IEEE PAMI, vol.33, issue.5, pp.898-916, 2011.

R. Audigier and R. Lotufo, Seed-relative segmentation robustness of watershed and fuzzy connectedness approaches, XX Brazilian Symposium on Computer Graphics and Image Processing, pp.61-70, 2007.

S. Beucher, Watershed, hierarchical segmentation and waterfall algorithm, ISMM, pp.69-76, 1994.

S. Beucher and F. Meyer, The morphological approach to segmentation: the watershed transformation, vol.34, pp.433-433, 1992.

Y. Boykov, O. Veksler, and R. Zabih, Fast approximate energy minimization via graph cuts, Proceedings of the Seventh IEEE International Conference on Computer Vision, vol.1, pp.377-384, 1999.

C. Couprie, L. Grady, L. Najman, and H. Talbot, Power watershed: A unifying graph-based optimization framework. IEEE transactions on pattern analysis and machine intelligence, vol.33, pp.1384-1399, 2010.

J. Cousty, G. Bertrand, L. Najman, and M. Couprie, Watershed cuts: Minimum spanning forests and the drop of water principle, IEEE PAMI, vol.31, issue.8, pp.1362-1374, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00622410

J. Cousty and L. Najman, Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts, ISMM, pp.272-283, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00622505

J. Cousty, L. Najman, Y. Kenmochi, and S. Guimarães, Hierarchical segmentations with graphs: quasi-flat zones, minimum spanning trees, and saliency maps, JMIV, vol.60, issue.4, pp.479-502, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01344727

J. Cousty, L. Najman, and B. Perret, Constructive links between some morphological hierarchies on edgeweighted graphs, ISMM, pp.86-97, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00798622

A. X. Falcão, J. Stolfi, R. De-alencar, and . Lotufo, The image foresting transform: Theory, algorithms, and applications. IEEE transactions on pattern analysis and machine intelligence, vol.26, pp.19-29, 2004.

P. F. Felzenszwalb and D. P. Huttenlocher, Efficient graph-based image segmentation, International journal of computer vision, vol.59, issue.2, pp.167-181, 2004.

L. Grady, Random walks for image segmentation, IEEE Transactions on Pattern Analysis & Machine Intelligence, issue.11, pp.1768-1783, 2006.

R. Lotufo and W. Silva, Minimal set of markers for the watershed transform, Proceedings of ISMM, vol.2002, pp.359-368, 2002.

D. S. Maia, A. D. Araujo, J. Cousty, L. Najman, B. Perret et al., Evaluation of combinations of watershed hierarchies, ISMM, pp.133-145
URL : https://hal.archives-ouvertes.fr/hal-01552420

. Springer, , 2017.

D. S. Maia, J. Cousty, L. Najman, and B. Perret, Recognizing hierarchical watersheds, International Conference on Discrete Geometry for Computer Imagery, pp.300-313, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01948502

D. S. Maia, J. Cousty, L. Najman, and B. Perret, Watersheding hierarchies, ISMM, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02180478

D. Martin, C. Fowlkes, D. Tal, and J. Malik, A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics, Proc. 8th Int'l Conf. Computer Vision, vol.2, pp.416-423, 2001.

F. Meyer, Minimum spanning forests for morphological segmentation, Mathematical morphology and its applications to image processing, pp.77-84, 1994.

F. Meyer, The dynamics of minima and contours, ISMM, pp.329-336, 1996.

F. Meyer and P. Maragos, Morphological scale-space representation with levelings, International Conference on Scale-Space Theories in Computer Vision, 1999.

F. Meyer, C. Vachier, A. Oliveras, and P. Salembier, Morphological tools for segmentation: Connected filters and watersheds, Annales des télécommunications, vol.52, pp.367-379, 1997.

M. Nagao, T. Matsuyama, and Y. Ikeda, Region extraction and shape analysis in aerial photographs, CGIP, vol.10, issue.3, pp.195-223, 1979.

L. Najman, On the equivalence between hierarchical segmentations and ultrametric watersheds, JMIV, vol.40, issue.3, pp.231-247, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00419373

L. Najman, J. Cousty, and B. Perret, Playing with kruskal: algorithms for morphological trees in edgeweighted graphs, ISMM, pp.135-146, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00798621

L. Najman and M. Schmitt, Geodesic saliency of watershed contours and hierarchical segmentation, IEEE PAMI, vol.18, issue.12, pp.1163-1173, 1996.
URL : https://hal.archives-ouvertes.fr/hal-00622128

B. Perret, J. Cousty, S. J. Guimaraes, and D. S. Maia, Evaluation of hierarchical watersheds, IEEE TIP, vol.27, issue.4, pp.1676-1688, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01430865

P. Salembier and L. Garrido, Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval, IEEE transactions on Image Processing, vol.9, issue.4, pp.561-576, 2000.

D. Santana-maia, J. Cousty, L. Najman, and B. , Perret. Properties of combinations of hierarchical watersheds, 2019.

J. Shi and J. Malik, Normalized cuts and image segmentation. Departmental Papers (CIS), p.107, 2000.

A. G. Silva, R. De-alencar, and . Lotufo, New extinction values from efficient construction and analysis of extended attribute component tree, SIBGRAPI, pp.204-211, 2008.

P. Soille, Constrained connectivity for hierarchical image partitioning and simplification. IEEE transactions on pattern analysis and machine intelligence, vol.30, pp.1132-1145, 2008.

C. Vachier and F. Meyer, Extinction value: a new measurement of persistence, IEEE Workshop on nonlinear signal and image processing, vol.1, pp.254-257, 1995.

, Since f is one-side increasing for ?, by the statement 3 of Definition 3, there is a child Y of parent(X) such that f (u) ? ?{f (v) | R v ? Y }. Hence, there is a child Y of parent(X) such that f (u) ? (Y ). Then, we have f (u) ? (X) or f (u) ? (sibling(X)), Thus, we have (X) ? (sibling(X))

, We will prove by induction that this lemma holds true for any dominant region for f and ?. In the base step, we consider that parent(X) is V . In the inductive step, we show that, if the property holds true for parent(X), then it also holds true for X. Please note that, if parent(X) is not a dominant region for f and ?, the property holds for parent(X) as proven in the previous case. (a) Base step: if parent(X) is V , then ?(X) = ?(V ) = (V ) + 1 (first case of Definition 10). We can see that (V ) ? (X) because

, Since ?(X) = ?(parent(X)), we have ?(X) ? (parent(X)). We can affirm that, for any edge v in E ? such that R v ? X, we also have R v ? parent(X). Hence, (parent(X)) ? (X). Therefore, ?(X)

, Given the following propositions: (a) u is a watershed-cut edge (b) ?(H)(u) > 0 we will prove that (a) implies (b), and that not (b) implies not (a)

, one minimum of w. Therefore, the extinction value of both children of R u is non-zero and, consequently, the persistence value ?(u) of u is non-zero. Moreover, by Lemma 20, in this case we have ?(H)(e) = ?(e) for any building edge e for ?. Thus, ?(H)(u) is nonzero. On the other hand, if u is not a watershed-cut edge for ?, then there is a child X of R u which does not contain any minimum of w. Therefore, the extinction value of X is equal to 0: (X) = 0. Since, by definition ?(u) = min{ (X), (sibling(X))} and the minimal extinction value is zero

, Let v be the building edge of a region Z ? X. Then, we can say that the extinction value of both children of Z is less than or equal to the extinction value (X). Hence, ?(v) ? (X) and, then, ?(v) ? ?(u), By Lemma, vol.20

, Let H be a hierarchy on V and let ? be an altitude ordering such that ?(H) is one-side increasing for ?. Then the hierarchy H is a hierarchical, Lemma, vol.46

V. and E. ,

, Let ? be an altitude ordering for w and let H be a hierarchy on V such that ?(H) is one-side increasing for ?

, As ?(H) is order to prove that (V, E ? ) is a MST of (G, ?(H)), we will prove that, for any MST G of (G, ?(H)), the sum of the weight of the edges in G is greater than or equal to ?. Let G be a MST of (G, ?(H)). As G is a MST of (G, ?(H)), by the condition 1 of Lemma 21, Proof Let ? denote the sum of the weight of the edges in E ? in the map ?(H): ? = e?E ? ?(H)(e)

?. Qfz(g, As ?(H) is the saliency map of H, we have that

.. .. {1, ;. .. , and ,. , Since the partitions P i and P i?1 are distinct, then there exists a region in P i which is not in P i?1 . Therefore, there is a region X of P i which is composed of a several regions {R 1 , R 2 , . . . } of P i?1 . Then, there are two adjacent vertices x and y such that x and y are in distinct regions in {R 1, n ? 1} is a subset of the range of ?(H)

}. Hence, Thus, there exists an edge u = {x, y} in E ? such that ?(H)(u) = i. Hence, the sum of the weight of the edges of G is at least 1 + · · · + n ? 1, which is equal to ?. Therefore, the graph (V, E ? ) is a MST of (G, ?(H)). -side increasing maps established in Lemma 47. In order to prove Property 14, we establish some auxiliary lemmas on MSTs and saliency maps. In the following, we state a well-known property of spanning trees in Lemma 48. Let x and y be two vertices in V and let ? = (x 0, the lowest j such that x and y belong to the same region of P j is i

, Let u = {x, y} be an edge in E \ E(G ) and let ? be the path from x to y (resp. y to x) in G . The graph G is a MST of (G, f ) if and only if f (u) ? f (v) for any edge v in ?. The following lemma characterizes MSTs of saliency maps, Lemma 48. Let G be a spanning tree of a weighted graph (G, f )

, Let u = {x, y} be an edge in E \ E(G ) and let ? be the path from x to y (resp. y to x) in G . Let v be an edge of greatest weight in ?. The graph G is a MST of (G, f ) if and, Lemma 49. Let f be the saliency map of a hierarchy on V and let G be a spanning tree of (G, f )

, Proof We will first prove the forward implication of this lemma. Let G be a MST of (G, ?(H)). Then, by Lemma 48

, in the ?-level set of (G, ?(H)), the vertices x and y are connected, ?(H)(u). Then, given ? = ?(H)(v)

V. and E. ,

, by Definition 13, there is a hierarchical watershed H w of (G, w) such that H is a flattening of H w . By Theorem 4, there is an altitude ordering ? for w such that ?(H w ) is one-side increasing for ?. Let ? be the altitude ordering for w such that ?(H w ) is one-side increasing for ?, By Lemma, vol.22

, ?(H w )). Then, any partition of H is a partition of QF Z(G , ?(H w )). By the definition of saliency maps, we can affirm that any partition of QFZ(G, ?(H)) is a partition of QF Z(G , ?(H w )). In the following

, By contradiction, let us assume that G is not a MST of (G, ?(H)). Then, by Lemma 49, there is an edge u = {x, y} such that u is in E \ E(G ) and such that ?(H)(u) is different from the greatest weight among the edges in the path ? from x to y in (G , ?(H)). Let v be an edge of greatest weight in ?. As H is equal to QFZ(G, ?(H)), we may affirm that ?(H)(u) is lower than ?(H)(v) because, otherwise, the vertices x and y would be connected in the ?-level set of

, Lemma 51, as H is a flattening of H w , we may conclude that ?(H w )(u) < ?(H w )(v). Hence, the weight ?

, As H w is one-side increasing for ?, by the second condition of Definition 3, for any watershed-cut edge u = {x, y} for ?, we have ?(H w )(u) = 0. Then, for any partition P of H w , x and y belong to the same region of P. Therefore, as any partition of H is a partition of H w , we can say that, for any partition P of H, x and y belong to the same region of P. Hence, the lowest ? such, We will now prove the second condition for H to be a flattened hierarchical

, By the third statement of Definition 3, we have that, for any edge u in E ? , there exists a child R of R u such that ?(H w )(u) ? ?{?(H w )(v) | R v ? R}

V. and E. ,

, Then H is a flattened hierarchical watershed of (G, w)

, In order to prove Lemma 53, we first state two auxiliary lemmas. From Property 10 of [10], we can deduce the following lemma linking binary partition hierarchies and MSTs

, Let B be a binary partition hierarchy of (G, w), Lemma, vol.54

, By Property 12 of [10] linking hierarchical watersheds and hierarchies induced by an altitude ordering and a sequence of minima, and by Lemma 21, we infer the following lemma

, Let G be a MST of (G, w) and let H be a hierarchical watershed of (G , w). Then H is also a hierarchical

, Lemma 53) Let H be a hierarchy on V such that there is an altitude ordering ? for w such that

V. and E. ,

, To this end, we will prove that there is a hierarchical watershed H w of (G, w) such that any partition of H is also a partition of H w . Let G denote the graph (V, E ? )

, By the definition of f , we have f (u) = 0 and, for any edge v such that R v ? X, we have f (v) = 0. Hence, f (u) ? ?{f (v) such that R v is included in X}. Otherwise, let us assume that u is a watershed-cut edge for ?. Then there is at least one minimum of w included in each child of R u . By the hypothesis 3, there is a child X of R u such that ?(H)(u) ? ?{?(H)(v) such that R v is included in X}. Let X be the child of R u such that ?(H)(u) ? ?{?(H)(v) such that R v is included in X}, no minimum of w included in X. Hence, none of the building edges of the descendants of X is a watershed-cut edge for ?

, QFZ(G , f ) is a hierarchical watershed of (G , w) (resp. (G, w)). Now, we only need to prove that any partition of H is a partition of QF Z(G , f ), Hence, f is one-side increasing for ? and, as stated previously

.. .. |-u-?-e-?-}-=-{0 and }. , Let G ?,?(H) be the ?-level set of (G , ?(H)). Let ? be the greatest value in {f (u) | u ? E(G ?,?(H) )}. We will prove that the ?-level set of (G , f ) is equal to the ?-level set of (G , ?(H))

, Since the minimum value of ? is zero, we can say that ?(H)(u) > 0 and, by the hypothesis 2, u is a watershed-cut edge for ?. Let v be an edge in the ?-level set of (G , ?(H)). Since ?(H)(u) > ?(H)(v), if v is a watershed-cut edge for ?, then v ? 2 u and f (u) > f (v). Otherwise, if v is not a watershedcut edge for ?, by the definition of f , we have f (v) = 0 and f (u) > f (v). Thus, for any edge v in the ?-level set of, Then, ?(H)(u) > ? and, for any edge v in the ?-level set of (G , ?(H)), we have ?(H)(u) > ?(H)(v)

. Therefore, As the partitions of H are given by the set of connected components of the level sets of (G , ?(H)), we can affirm that any partition of H is also a partition of QFZ(G , f ). Therefore, there is a hierarchical watershed H w = QFZ(G , f ) of (G , w) (resp. (G, w)) such that any partition of H is also a partition of H w . Then