Watershed hierarchy¶

Watershed hierarchy by a user defined attributes. 
Watershed hierarchy for the given minima ordering. 


Watershed hierarchy by area. 

Watershed hierarchy by volume. 

Watershed hierarchy by dynamics. 
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:
J. Cousty, L. Najman. Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. ISMM 2011: 272283.
The algorithm used is described in:
Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in EdgeWeighted Graphs. ISMM 2013: 135146.
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 functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns:
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
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:
J. Cousty, L. Najman. Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. ISMM 2011: 272283.
and in,
J. Cousty, L. Najman, B. Perret. Constructive links between some morphological hierarchies on edgeweighted graphs.. ISMM 2013: 8697.
The algorithm used is adapted from the algorithm described in:
Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in EdgeWeighted Graphs. ISMM 2013: 135146.
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 preconditions:
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 functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns:
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
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:
J. Cousty, L. Najman. Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. ISMM 2011: 272283.
The algorithm used is described in:
Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in EdgeWeighted Graphs. ISMM 2013: 135146.
 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 functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns:
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
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:
J. Cousty, L. Najman. Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. ISMM 2011: 272283.
The algorithm used is described in:
Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in EdgeWeighted Graphs. ISMM 2013: 135146.
 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 functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns:
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
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:
J. Cousty, L. Najman. Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. ISMM 2011: 272283.
The algorithm used is described in:
Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in EdgeWeighted Graphs. ISMM 2013: 135146.
 Parameters:
graph – input graph
edge_weights – input graph edge weights
canonize_tree – if
True
(default), the resulting hierarchy is canonized (see functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns:
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
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. 16761688, April 2018. doi: 10.1109/TIP.2017.2779604
The definition of hierarchical watershed follows the one given in:
J. Cousty, L. Najman. Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts. ISMM 2011: 272283.
The algorithm used is described in:
Laurent Najman, Jean Cousty, Benjamin Perret. Playing with Kruskal: Algorithms for Morphological Trees in EdgeWeighted Graphs. ISMM 2013: 135146.
 Parameters:
graph – input graph
edge_weights – edge weights of the input graph
canonize_tree – if
True
(default), the resulting hierarchy is canonized (see functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
 Returns:
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
otherwise) and its node altitudes