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: 272-283.
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 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: 272-283.
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 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: 272-283.
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 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: 272-283.
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 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: 272-283.
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 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. 1676-1688, 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: 272-283.
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 functioncanonize_hierarchy()
), otherwise the returned hierarchy is a binary tree
- Returns:
a tree (Concept
CptHierarchy
isTrue
andCptBinaryHierarchy
otherwise) and its node altitudes