Algorithm for trees¶

Given two binary markers \(o\) (object) and \(b\) (background) (given by their indicator functions) on the leaves of a tree \(T\), the corresponding binary labelization of the leaves of \(T\) is defined as the union of all the nodes intersecting \(o\) but not \(b\): 

Filter the given tree according to a functor telling if nodes are relevant or not. 

Filter the given tree according to node size: 

Filter the given tree according to the frontier strength. 

Labelize the tree leaves into supervertices. 

Each leaf of the tree takes the altitude of its closest non deleted ancestor. 

Sort the nodes of a tree according to their altitudes. 

Test if the altitudes of the given tree are increasing; i.e. 

Test if 2 trees \(t_1\) and \(t_2\) are isomorph assuming that they share the same leaves. 

Depth map associated to the fusion of the given list of trees. 

Monotonic regression on the given tree altitudes. 

binary_labelisation_from_markers
(tree, object_marker, background_marker, leaf_graph=None)[source]¶ Given two binary markers \(o\) (object) and \(b\) (background) (given by their indicator functions) on the leaves of a tree \(T\), the corresponding binary labelization of the leaves of \(T\) is defined as the union of all the nodes intersecting \(o\) but not \(b\):
\[res = \bigcup \{R \in T \mid R \cap o \neq \emptyset, \textrm{ and } R \cap b = \emptyset\}\] Parameters:
tree – input tree (Concept
CptHierarchy
)object_marker – indicator function of the object marker: 1d array of size tree.num_leaves() where non zero values correspond to the object marker
background_marker – indicator function of the background marker: 1d array of size tree.num_leaves() where non zero values correspond to the background marker
leaf_graph – graph on the leaves of the input tree (optional, deduced from
CptHierarchy
)
 Returns:
Leaf labels

filter_non_relevant_node_from_tree
(tree, altitudes, non_relevant_functor, leaf_graph, canonize_tree=True)[source]¶ Filter the given tree according to a functor telling if nodes are relevant or not.
In a binary a tree, each inner node (non leaf node) is associated to the frontier separating its two children. If the frontier associated to a node is considered as nonrelevant (for example because on of the two children of the node is too small) then the corresponding frontier is removed effectively merging its two children.
This function returns a binary partition tree such that:
the frontiers associated to nodes marked nonrelevant do not exist anymore;
the regions of the new tree are either regions of the initial tree or regions obtained by merging adjacent regions of the initial tree.
If
tree
does not satisfy the conceptCptBinaryHierarchy
, the given tree is first transformed into a binary tree (arbitrary choices are made).non_relevant_functor
must be a function that accepts two arguments, a binary tree and its node altitudes, and must return a boolean node attribute for the given tree (ie a 1d array of booleanish values of sizetree.num_vertices()
. A value ofTrue
is interpreted as this node is not relevant and its associated frontier must be removed. See:
filter_small_nodes_from_tree()
filter_weak_frontier_nodes_from_tree()
 Parameters:
tree – input tree (Concept
CptHierarchy
)altitudes – node altitudes of the input tree
non_relevant_functor – a function that computes an attribute on a binary tree
leaf_graph – graph of the tree leaves (deduced from
CptHierarchy
)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

filter_small_nodes_from_tree
(tree, altitudes, size_threshold, leaf_graph, canonize_tree=True)[source]¶ Filter the given tree according to node size:
This function returns a binary partition tree such that:
it does not contain any region whose size is below the given threshold;
the regions of the new tree are either regions of the initial tree or regions obtained by merging adjacent regions of the initial tree.
 See:
 Parameters:
tree – input tree (Concept
CptHierarchy
)altitudes – node altitudes of the input tree
size_threshold – regions whose size is smaller than this threshold will be removed (see
attribute_area()
)leaf_graph – graph of the tree leaves (deduced from
CptHierarchy
)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

filter_weak_frontier_nodes_from_tree
(tree, altitudes, edge_weights, strength_threshold, leaf_graph, canonize_tree=True)[source]¶ Filter the given tree according to the frontier strength.
The strength of a frontier is defined as the mean weights of the edges crossing the frontier (see
attribute_frontier_strength()
).This function returns a binary partition tree such that:
it does not contain any contour whose strength is lower than the given threshold;
the regions of the new tree are either regions of the initial tree or regions obtained by merging adjacent regions of the initial tree.
 See:
 Parameters:
tree – input tree (Concept
CptHierarchy
)altitudes – node altitudes of the input tree
leaf_graph – graph of the tree leaves (deduced from
CptHierarchy
)edge_weights – edge weights of the leaf graph
strength_threshold – regions whose associated frontier strength is smaller than the given threshold are removed (see
attribute_frontier_strength()
)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

labelisation_hierarchy_supervertices
(tree, altitudes, leaf_graph=None, handle_rag=True)[source]¶ Labelize the tree leaves into supervertices. The altitudes must be increasing, i.e. for any nodes \(i, j\) such that \(j\) is an ancestor of \(i\), then \(altitudes[i] \leq altitudes[j]\). Two leaves are in the same supervertex if they have a common ancestor at altitude 0.
If we consider that the pair \((tree, altitudes)\) represents a dendrogram, i.e. that it defines a pseudoultrametric on the set of leaves, a supervertex is a maximal cluster such that the distance between any pair of points in the cluster is equal to 0.
This functions guaranties that the labels are in the range \([0, num\_supervertices1]\).
 Parameters:
tree – input tree (Concept
CptHierarchy
)altitudes – node altitudes of the input tree
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)handle_rag – if True and the provided tree has been built on a region adjacency graph, then the labelisation corresponding to the rag regions is returned.
 Returns:
Leaf labels

reconstruct_leaf_data
(tree, altitudes, deleted_nodes=None, leaf_graph=None)[source]¶ Each leaf of the tree takes the altitude of its closest non deleted ancestor. The root node is never deleted. In a component tree, leaves are always deleted.
The result is an array of shape
[tree.num_leaves()] + altitudes.shape[1:]
such that \(result[i]\) is the altitude of the smallest node \(n\) containing \(i\) such that \(deleted\_nodes[n]\) is false and for all nodes \(j\) in the branch from \(i\) (included) to \(n\) (excluded), \(deleted\_nodes[j]\) is true.If
deleted_nodes
isNone
then its default value is set to np.zeros((tree.numvertices(),) (no nodes are deleted). Complexity:
This algorithms runs in linear time \(O(tree.num\_vertices())\).
 Example:
>>> tree = hg.Tree((5, 5, 6, 6, 6, 7, 7, 7)) >>> altitudes = np.asarray(((1, 8), (2, 7), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1)), dtype=np.int32) >>> condition = np.asarray((True, False, True, False, True, True, False, False), np.bool_) >>> hg.reconstruct_leaf_data(tree, altitudes, condition) array([[8, 1], [2, 7], [7, 2], [4, 5], [7, 2]])
 Parameters:
tree – input tree (Concept
CptHierarchy
)altitudes – node altitudes of the input tree
deleted_nodes – binary node weights indicating which nodes are deleted (optional)
leaf_graph – graph of the tree leaves (optional, deduced from
CptHierarchy
)
 Returns:
Leaf weights: array of shape
[tree.num_leaves()] + altitudes.shape[1:]
and of dtypealtitudes.dtype

sort_hierarchy_with_altitudes
(tree, altitudes)[source]¶ Sort the nodes of a tree according to their altitudes. The altitudes must be increasing, i.e. for any nodes \(i, j\) such that \(j\) is an ancestor of \(i\), then \(altitudes[i] \leq altitudes[j]\).
The result is a new tree and a node map, isomorph to the input tree such that for any nodes \(i\) and \(j\), \(i<j \Rightarrow altitudes[node\_map[i]] \leq altitudes[node\_map[j]]\)
The latter condition is stronger than the original condition on the altitudes as \(j\) is an ancestor of \(i\) implies \(i<j\) while the converse is not true.
The returned “node_map” is an array that maps any node index \(i\) of the new tree, to the index of this node in the original tree.
 Parameters:
tree – input tree
altitudes – node altitudes of the input tree
 Returns:
the sorted tree (Concept
CptHierarchy
), its node altitudes, and the node map

test_altitudes_increasingness
(tree, altitudes)[source]¶ Test if the altitudes of the given tree are increasing; i.e. if for any nodes \(i, j\) such that \(j\) is an ancestor of \(i\), then \(altitudes[i] \leq altitudes[j]\).
 Parameters:
tree – input tree
altitudes – node altitudes of the input tree
 Returns:
True
ifaltitudes
are increasing fortree
,False
otherwise.

test_tree_isomorphism
(tree1: hg::tree_internal::tree, tree2: hg::tree_internal::tree) → bool¶ Test if 2 trees \(t_1\) and \(t_2\) are isomorph assuming that they share the same leaves.
By this definition \(t_1\) is isomorph to \(t_2\) if there exists a bijection \(f\) from the nodes of \(t_1\) to the nodes of \(t_2\) such that:
for any leaf node \(n\) of \(t_1\), \(f(n) = n\), and
for any node \(n\) of \(t_1\), \(f(t_1.parent(n)) = t_2.parent(f(n))\)
Note that the root node of \(r\) a tree \(t\) is defined by \(t.parent(r) = r\), thus 2) becomes for the root node \(r_1\) of \(t_1\), \(f(r_1) = t_2.parent(f(r_1))\), i.e. \(f(r_1)\) is the root node of \(t_2\)

tree_fusion_depth_map
(*trees)[source]¶ Depth map associated to the fusion of the given list of trees. This depth map can be used to compute a new tree representing the fusion of the input trees, eg. with
component_tree_max_tree()
.The method is described in:
E. Carlinet. A Tree of shapes for multivariate images. PhD Thesis, Université ParisEst, 2015.
All trees must be defined over the same domain, i.e. have the same number of leaves. Given a set of trees \((T_1, T_2, T_3,... T_n)\) composed of the set of nodes \((N_1, N_2, N_3, ... N_n)\). We define the fusion graph as the graph induced the inclusion relation \(\subseteq\) on the union of all the tree nodes \(\bigcup\{N_1, N_2, N_3, ... N_n\}\).
The result is a directed acyclic graph with a single root (corresponding to the roots of the input trees). The depth of a node in this graph is defined as the length of the longest path from the root this node. This function returns the depth of the leaves of this graph (which are the same as the leaves of the input trees).
 See:
A multivariate tree of shapes of a colour 2d can be computed with
component_tree_multivariate_tree_of_shapes_image2d()
. Complexity:
The worst case runtime complexity of this method is \(\mathcal{O}(N^2D^2)\) with \(N\) the number of leaves and \(D\) the number of trees. If we denote by \(K\) the depth of the deepest tree to merge, one can rewrite the runtime complexity as \(\mathcal{O}(NKD^2)\).
 Parameters:
trees – at least two trees defined over the same domain
 Returns:
a depth map representing the fusion of the input trees

tree_monotonic_regression
(tree, altitudes, mode, weights=None)[source]¶ Monotonic regression on the given tree altitudes. Computes new altitudes
naltitudes
that are close to the givenaltitudes
and that are increasing for the giventree
: i.e. for any nodes \(i, j\) such that \(j\) is an ancestor of \(i\), then \(naltitudes[i] \leq naltitudes[j]\).The definition of close depends of the value of
mode
:If
mode
is equal to"min"
thennaltitudes
is the largest increasing function belowaltitudes
.If
mode
is equal to"max"
thennaltitudes
is the smallest increasing function abovealtitudes
.If
mode
is equal to"least_square"
thennaltitudes
minizes the following minization problem:
\[naltitudes = \arg \min_x \sum_i (weights[i] * (altitudes[i]  x[i])^2)\]such that
naltitudes
is increasing fortree
. Complexity:
With \(n\) the number of nodes in the
tree
:For the modes
"min"
and"max"
, the runtime complexity is linear \(\mathcal{O}(n)\).For the mode
"least_square"
, the runtime complexity is linearithmic \(\mathcal{O}(n\log(n))\) and the space complexity is linear \(\mathcal{O}(n)\). The algorithm used is described in:P. Pardalos and G. Xue ‘Algorithms for a Class of Isotonic Regression Problems.’ Algorithmica (1999) 23: 211. doi:10.1007/PL00009258
 Parameters:
tree – input tree
altitudes – node altitudes of the input tree
mode – the regression mode :
"min"
,"max"
, or"least_square"
weights – node weights of the input tree (default to an array of 1s). This parameter is ignored if
mode
is not"least_square"
.
 Returns:
a 1d array