Watershed hierarchy

watershed_hierarchy_by_attribute(graph, …)

Watershed hierarchy by a user defined attributes.

watershed_hierarchy_by_minima_ordering(…)

Watershed hierarchy for the given minima ordering.

watershed_hierarchy_by_area(graph, edge_weights)

Watershed hierarchy by area.

watershed_hierarchy_by_volume(graph, …[, …])

Watershed hierarchy by volume.

watershed_hierarchy_by_dynamics(graph, …)

Watershed hierarchy by dynamics.

watershed_hierarchy_by_number_of_parents(…)

Watershed hierarchy by number of parents.

watershed_hierarchy_by_attribute(graph, edge_weights, attribute_functor, canonize_tree=True)[source]

Watershed hierarchy by a user defined attributes.

The definition of hierarchical watershed follows the one given in:

The algorithm used is described in:

Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in Edge-Weighted Graphs. ISMM 2013: 135-146.

The attribute functor is a function that takes a binary partition tree and an array of altitudes as argument and returns an array with the node attribute values for the given tree.

Example:

Calling watershed_hierarchy_by_area is equivalent to:

tree = watershed_hierarchy_by_attribute(graph, edge_weights, lambda tree, _: hg.attribute_area(tree))
Parameters:
  • graph – input graph

  • edge_weights – edge weights of the input graph

  • attribute_functor – function computing the regional attribute

  • canonize_tree – if True (default), the resulting hierarchy is canonized (see function canonize_hierarchy()), otherwise the returned hierarchy is a binary tree

Returns:

a tree (Concept CptHierarchy is True and CptBinaryHierarchy otherwise) and its node altitudes

watershed_hierarchy_by_minima_ordering(graph, edge_weights, minima_ranks, minima_altitudes=None, canonize_tree=True)[source]

Watershed hierarchy for the given minima ordering.

The definition used follows the one given in:

and in,

J. Cousty, L. Najman, B. Perret. Constructive links between some morphological hierarchies on edge-weighted graphs.. ISMM 2013: 86-97.

The algorithm used is adapted from the algorithm described in:

Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in Edge-Weighted Graphs. ISMM 2013: 135-146.

The ranking ranking of the minima of the given edge weighted graph \((G,w)\) is given as vertex weights with values in \(\{0, \ldots, n\}\) with \(n\) the number of minima of \((G,w)\). It must satisfy the following pre-conditions:

  • each minimum of \((G,w)\) contains at least one non zero vertex,

  • all non zero vertices in a minimum have the same weight,

  • there is no non zero value vertex outside minima, and

  • no two minima contain non zero vertices with the same weight.

minima_altitudes is an optional non decreasing 1d array of size \(n + 1\) with non negative values such that \(minima\_altitudes[i]\) indicates the altitude of the minima of rank \(i\). Note that the first entry of the minima altitudes array, ie. the value at index 0, does not represent a minimum and its value should be 0.

The altitude of a node of the computed watershed corresponds to the altitude (respectively the rank) of the minima it is associated to if minima_altitudes is provided (respectively not provided).

Parameters:
  • graph – input graph

  • edge_weights – edge weights of the input graph

  • minima_ranks – input graph vertex weights containing the rank of each minima of the input edge weighted graph

  • minima_altitudes – array mapping each minima rank to its altitude (optional)

  • canonize_tree – if True (default), the resulting hierarchy is canonized (see function canonize_hierarchy()), otherwise the returned hierarchy is a binary tree

Returns:

a tree (Concept CptHierarchy is True and CptBinaryHierarchy otherwise) and its node altitudes

watershed_hierarchy_by_area(graph, edge_weights, vertex_area=None, canonize_tree=True)[source]

Watershed hierarchy by area.

The definition of hierarchical watershed follows the one given in:

The algorithm used is described in:

Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in Edge-Weighted Graphs. ISMM 2013: 135-146.

Parameters:
  • graph – input graph

  • edge_weights – input graph edge weights

  • vertex_area – area of the input graph vertices (provided by attribute_vertex_area())

  • canonize_tree – if True (default), the resulting hierarchy is canonized (see function canonize_hierarchy()), otherwise the returned hierarchy is a binary tree

Returns:

a tree (Concept CptHierarchy is True and CptBinaryHierarchy otherwise) and its node altitudes

watershed_hierarchy_by_volume(graph, edge_weights, vertex_area=None, canonize_tree=True)[source]

Watershed hierarchy by volume.

The definition of hierarchical watershed follows the one given in:

The algorithm used is described in:

Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in Edge-Weighted Graphs. ISMM 2013: 135-146.

Parameters:
  • graph – input graph

  • edge_weights – input graph edge weights

  • vertex_area – area of the input graph vertices (provided by attribute_vertex_area())

  • canonize_tree – if True (default), the resulting hierarchy is canonized (see function canonize_hierarchy()), otherwise the returned hierarchy is a binary tree

Returns:

a tree (Concept CptHierarchy is True and CptBinaryHierarchy otherwise) and its node altitudes

watershed_hierarchy_by_dynamics(graph, edge_weights, canonize_tree=True)[source]

Watershed hierarchy by dynamics.

The definition of hierarchical watershed follows the one given in:

The algorithm used is described in:

Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in Edge-Weighted Graphs. ISMM 2013: 135-146.

Parameters:
  • graph – input graph

  • edge_weights – input graph edge weights

  • canonize_tree – if True (default), the resulting hierarchy is canonized (see function canonize_hierarchy()), otherwise the returned hierarchy is a binary tree

Returns:

a tree (Concept CptHierarchy is True and CptBinaryHierarchy otherwise) and its node altitudes

watershed_hierarchy_by_number_of_parents(graph, edge_weights, canonize_tree=True)[source]

Watershed hierarchy by number of parents.

The definition of number of parents was proposed in:

B. Perret, J. Cousty, S. J. F. Guimarães and D. S. Maia, Evaluation of Hierarchical Watersheds , in IEEE Transactions on Image Processing, vol. 27, no. 4, pp. 1676-1688, April 2018. doi: 10.1109/TIP.2017.2779604

The definition of hierarchical watershed follows the one given in:

The algorithm used is described in:

Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in Edge-Weighted Graphs. ISMM 2013: 135-146.

Parameters:
  • graph – input graph

  • edge_weights – edge weights of the input graph

  • canonize_tree – if True (default), the resulting hierarchy is canonized (see function canonize_hierarchy()), otherwise the returned hierarchy is a binary tree

Returns:

a tree (Concept CptHierarchy is True and CptBinaryHierarchy otherwise) and its node altitudes