# Source code for higra.hierarchy.watershed_hierarchy

############################################################################
# Copyright ESIEE Paris (2018)                                             #
#                                                                          #
# Contributor(s) : Benjamin Perret                                         #
#                                                                          #
#                                                                          #
# The full license is in the file LICENSE, distributed with this software. #
############################################################################

import higra as hg
import numpy as np

[docs]def watershed_hierarchy_by_area(graph, edge_weights, vertex_area=None, canonize_tree=True):
"""
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 <https://hal-upec-upem.archives-ouvertes.fr/hal-00622505/document>_.
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 <https://hal.archives-ouvertes.fr/file/index/docid/798621/filename/ismm2013-algo.pdf>_.
ISMM 2013: 135-146.

:param graph: input graph
:param edge_weights: input graph edge weights
:param vertex_area: area of the input graph vertices (provided by :func:~higra.attribute_vertex_area)
:param canonize_tree: if True (default), the resulting hierarchy is canonized (see function :func:~higra.canonize_hierarchy),
otherwise the returned hierarchy is a binary tree
:return: a tree (Concept :class:~higra.CptHierarchy is True and :class:~higra.CptBinaryHierarchy otherwise)
and its node altitudes
"""
if vertex_area is None:
vertex_area = hg.attribute_vertex_area(graph)

vertex_area = hg.linearize_vertex_weights(vertex_area, graph)

return watershed_hierarchy_by_attribute(graph, edge_weights,
lambda tree, _: hg.attribute_area(tree, vertex_area, graph),
canonize_tree)

[docs]def watershed_hierarchy_by_volume(graph, edge_weights, vertex_area=None, canonize_tree=True):
"""
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 <https://hal-upec-upem.archives-ouvertes.fr/hal-00622505/document>_.
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 <https://hal.archives-ouvertes.fr/file/index/docid/798621/filename/ismm2013-algo.pdf>_.
ISMM 2013: 135-146.

:param graph: input graph
:param edge_weights: input graph edge weights
:param vertex_area: area of the input graph vertices (provided by :func:~higra.attribute_vertex_area)
:param canonize_tree: if True (default), the resulting hierarchy is canonized (see function :func:~higra.canonize_hierarchy),
otherwise the returned hierarchy is a binary tree
:return: a tree (Concept :class:~higra.CptHierarchy is True and :class:~higra.CptBinaryHierarchy otherwise)
and its node altitudes
"""
if vertex_area is None:
vertex_area = hg.attribute_vertex_area(graph)

vertex_area = hg.linearize_vertex_weights(vertex_area, graph)

return watershed_hierarchy_by_attribute(graph, edge_weights,
lambda tree, altitudes:
hg.attribute_volume(tree,
altitudes,
hg.attribute_area(tree, vertex_area)),
canonize_tree)

[docs]def watershed_hierarchy_by_dynamics(graph, edge_weights, canonize_tree=True):
"""
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 <https://hal-upec-upem.archives-ouvertes.fr/hal-00622505/document>_.
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 <https://hal.archives-ouvertes.fr/file/index/docid/798621/filename/ismm2013-algo.pdf>_.
ISMM 2013: 135-146.

:param graph: input graph
:param edge_weights: input graph edge weights
:param canonize_tree: if True (default), the resulting hierarchy is canonized (see function :func:~higra.canonize_hierarchy),
otherwise the returned hierarchy is a binary tree
:return: a tree (Concept :class:~higra.CptHierarchy is True and :class:~higra.CptBinaryHierarchy otherwise)
and its node altitudes
"""
return watershed_hierarchy_by_attribute(graph, edge_weights,
lambda tree, altitudes:
hg.attribute_dynamics(tree,
altitudes,
"increasing"),
canonize_tree)

[docs]def watershed_hierarchy_by_number_of_parents(graph, edge_weights, canonize_tree=True):
"""
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 <https://hal.archives-ouvertes.fr/hal-01430865/file/PCGM%20-%20TIP%202018%20-%20Evaluation%20of%20hierarchical%20watersheds.pdf>_ ,
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 <https://hal-upec-upem.archives-ouvertes.fr/hal-00622505/document>_.
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 <https://hal.archives-ouvertes.fr/file/index/docid/798621/filename/ismm2013-algo.pdf>_.
ISMM 2013: 135-146.

:param graph: input graph
:param edge_weights: edge weights of the input graph
:param canonize_tree: if True (default), the resulting hierarchy is canonized (see function :func:~higra.canonize_hierarchy),
otherwise the returned hierarchy is a binary tree
:return: a tree (Concept :class:~higra.CptHierarchy is True and :class:~higra.CptBinaryHierarchy otherwise)
and its node altitudes
"""

def num_parents(bpt_tree, altitudes):
# construct quasi flat zone hierarchy from input bpt
tree, node_map = hg.simplify_tree(bpt_tree, altitudes == altitudes[bpt_tree.parents()])

# determine inner nodes of the min tree, i.e. nodes of qfz having at least one node that is not a leaf
num_children = tree.num_children(np.arange(tree.num_vertices()))
num_children_leaf = np.zeros((tree.num_vertices(),), dtype=np.int64)
inner_nodes = num_children != num_children_leaf

# go back into bpt space
inner_nodes_bpt = np.zeros((bpt_tree.num_vertices(),), dtype=np.int64)
inner_nodes_bpt[node_map] = inner_nodes
inner_nodes = inner_nodes_bpt

# count number of min tree inner nodes in the subtree rooted in the given node
inner_nodes,
inner_nodes[:tree.num_leaves()],
hg.Accumulators.sum)

# add 1 to avoid having a zero measure in a minima
res[bpt_tree.num_leaves():] = res[bpt_tree.num_leaves():] + 1

return res

return hg.watershed_hierarchy_by_attribute(graph, edge_weights, num_parents, canonize_tree)

[docs]def watershed_hierarchy_by_attribute(graph, edge_weights, attribute_functor, canonize_tree=True):
"""
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 <https://hal-upec-upem.archives-ouvertes.fr/hal-00622505/document>_.
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 <https://hal.archives-ouvertes.fr/file/index/docid/798621/filename/ismm2013-algo.pdf>_.
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:

.. code-block:: python

tree = watershed_hierarchy_by_attribute(graph, edge_weights, lambda tree, _: hg.attribute_area(tree))

:param graph: input graph
:param edge_weights: edge weights of the input graph
:param attribute_functor: function computing the regional attribute
:param canonize_tree: if True (default), the resulting hierarchy is canonized (see function :func:~higra.canonize_hierarchy),
otherwise the returned hierarchy is a binary tree
:return: a tree (Concept :class:~higra.CptHierarchy is True and :class:~higra.CptBinaryHierarchy otherwise)
and its node altitudes
"""

def helper_functor(tree, altitudes):

return attribute_functor(tree, altitudes)

tree, altitudes, mst_edge_map = hg.cpp._watershed_hierarchy_by_attribute(graph, edge_weights, helper_functor)

if canonize_tree:
tree, altitudes = hg.canonize_hierarchy(tree, altitudes)
else:
mst = hg.subgraph(graph, mst_edge_map)

return tree, altitudes

[docs]def watershed_hierarchy_by_minima_ordering(graph, edge_weights, minima_ranks, minima_altitudes=None, canonize_tree=True):
"""
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 <https://hal-upec-upem.archives-ouvertes.fr/hal-00622505/document>_.
ISMM 2011: 272-283.

and in,

J. Cousty, L. Najman, B. Perret.
Constructive links between some morphological hierarchies on edge-weighted graphs <https://hal.archives-ouvertes.fr/file/index/docid/806851/filename/ismm2013.pdf>_..
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 <https://hal.archives-ouvertes.fr/file/index/docid/798621/filename/ismm2013-algo.pdf>_.
ISMM 2013: 135-146.

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

- each minimum of :math:(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.

:attr:minima_altitudes is an optional non decreasing 1d array of size :math:n + 1 with non negative values such that
:math:minima\_altitudes[i] indicates the altitude of the minima of rank :math: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 :attr:minima_altitudes is provided (respectively not provided).

:param graph: input graph
:param edge_weights: edge weights of the input graph
:param minima_ranks: input graph vertex weights containing the rank of each minima of the input edge weighted graph
:param minima_altitudes: array mapping each minima rank to its altitude (optional)
:param canonize_tree: if True (default), the resulting hierarchy is canonized (see function :func:~higra.canonize_hierarchy),
otherwise the returned hierarchy is a binary tree
:return: a tree (Concept :class:~higra.CptHierarchy is True and :class:~higra.CptBinaryHierarchy otherwise)
and its node altitudes
"""

minima_ranks = hg.cast_to_dtype(minima_ranks, np.uint64)
tree, altitudes, mst_edge_map = hg.cpp._watershed_hierarchy_by_minima_ordering(graph, edge_weights, minima_ranks)