Tree energy optimization

labelisation_optimal_cut_from_energy(tree, …)

Labelisation of the input tree leaves corresponding to the optimal cut according to the given energy attribute.

hierarchy_to_optimal_energy_cut_hierarchy(…)

Transforms the given hierarchy into its optimal energy cut hierarchy for the given energy terms.

hierarchy_to_optimal_MumfordShah_energy_cut_hierarchy(…)

Transform the given hierarchy into an optimal energy cut hierarchy using the piecewise constant Mumford-Shah energy (see function hierarchy_to_optimal_energy_cut_hierarchy()).
labelisation_optimal_cut_from_energy(tree, energy_attribute, accumulator=<Accumulators.sum: 6>, leaf_graph=None)[source]

Labelisation of the input tree leaves corresponding to the optimal cut according to the given energy attribute.

Given a node \(i\), the value \(energy(i)\) represents the energy fo the partial partition composed of the single region \(i\). Given a node \(i\), the energy of the partial partition composed of the children of \(i\) is given by \(accumulator(energy(children(i)))\) This function computes the partition (ie. a set of node forming a cut of the tree) that has a minimal energy according to the definition above.

Supported accumulators are hg.Accumulators.sum, hg.Accumulators.min, and hg.Accumulators.max.

The algorithm used is based on dynamic programming and runs in linear time \(\mathcal{O}(n)\) w.r.t. to the number of nodes in the tree.

See:

Laurent Guigues, Jean Pierre Cocquerez, Hervé Le Men. Scale-sets Image Analysis. International Journal of Computer Vision, Springer Verlag, 2006, 68 (3), pp.289-317

and

Bangalore Ravi Kiran, Jean Serra. Global-local optimizations by hierarchical cuts and climbing energies. Pattern Recognition Letters, Elsevier, 2014, 47 (1), pp.12-24.

Parameters:

  • tree – input tree (Concept CptHierarchy)

  • energy_attribute – energy value of each node of the input tree

  • accumulator – see Accumulators

  • leaf_graph – leaf graph of the input tree (deduced from CptHierarchy)

Returns:

a labelisation of the leaves of the tree

hierarchy_to_optimal_energy_cut_hierarchy(tree, data_fidelity_attribute, regularization_attribute, approximation_piecewise_linear_function=10)[source]

Transforms the given hierarchy into its optimal energy cut hierarchy for the given energy terms. In the optimal energy cut hierarchy, any horizontal cut corresponds to an optimal energy cut in the original hierarchy.

Each node \(i\) of the tree is associated to a data fidelity energy \(D(i)\) and a regularization energy \(R(i)\). The algorithm construct a new hierarchy with associated altitudes such that the horizontal cut of level lambda is the optimal cut for the energy attribute \(D + \lambda * R\) of the input tree (see function labelisation_optimal_cut_from_energy()). In other words, the horizontal cut of level \(\lambda\) in the result is the cut of the input composed of the nodes \(N\) such that \(\sum_{r \in N} D(r) + \lambda * R(r)\) is minimal.

PRECONDITION: the regularization energy \(R\) must be sub additive: for each node \(i\): \(R(i) \leq \sum_{c\in Children(i)}R(c)\)

The algorithm runs in linear time \(\mathcal{O}(n)\)

See:

Laurent Guigues, Jean Pierre Cocquerez, Hervé Le Men. Scale-sets Image Analysis. International Journal of Computer Vision, Springer Verlag, 2006, 68 (3), pp.289-317

Parameters:

  • tree – input tree

  • data_fidelity_attribute – 1d array representing the data fidelity energy of each node of the input tree

  • regularization_attribute – 1d array representing the regularization energy of each node of the input tree

  • approximation_piecewise_linear_function – Maximum number of pieces used in the approximated piecewise linear model for the energy function (default 10).

Returns:

a tree (Concept CptHierarchy) and its node altitudes

hierarchy_to_optimal_MumfordShah_energy_cut_hierarchy(tree, vertex_weights, leaf_graph, approximation_piecewise_linear_function=10)[source]

Transform the given hierarchy into an optimal energy cut hierarchy using the piecewise constant Mumford-Shah energy (see function hierarchy_to_optimal_energy_cut_hierarchy()).

In this context:

  • the data fidelity energy assumes a piecewise constant model in each node and is given by the variance of the vertex values inside the node (see function attribute_gaussian_region_weights_model()) multiplied by its area,

  • the regularity energy is given by the length of the contour of the node (see function attribute_contour_length()).

Parameters:

  • tree – input tree (Concept CptHierarchy)

  • vertex_weights – vertex weights of the leaf graph of the input tree

  • leaf_graph – leaf graph of the input tree (deduced from CptHierarchy)

  • approximation_piecewise_linear_function – Maximum number of pieces used in the approximated piecewise linear model for the energy function (default 10).

Returns:

a tree (Concept CptHierarchy) and its node altitudes