# Source code for higra.algo.alignment

############################################################################
# Copyright ESIEE Paris (2018)                                             #
#                                                                          #
# Contributor(s) : Benjamin Perret                                         #
#                                                                          #
# Distributed under the terms of the CECILL-B License.                     #
#                                                                          #
# The full license is in the file LICENSE, distributed with this software. #
############################################################################

import higra as hg
import numpy as np

[docs]def align_hierarchies(graph, vertex_labels, other_hierarchies):
"""
Align hierarchies boundaries on the boundaries of the provided super-vertex decomposition of a graph

Given:

- a graph :math:G=(V,E)
- a fine labelisation :math:l_1 of the vertices of :math:G;
- a tree :math:T on :math:G whose supervertices corresponds to the coarse labelisation :math:l_2
of the vertices of :math:G; and
- the altitudes :math:a of the nodes of :math:T.

Let us denote:

- given a vertex :math:x of :math:G and a labelisation :math:l, :math:l(x) is the region of :math:l
that contains :math:x
- given a region :math:r of :math:l_1, :math:s(r, l_2) is the region :math:R of :math:l_2 that has
the largest intersection with :math:r, ie, :math:s(r, l_2) = \\arg \max_{R \in l_2} | R \cap r |

The projection of :math:T onto :math:l_1 is a hierarchy given by the saliency map :math:sm on :math:G
defined by:

.. math::

\\forall e_{xy} \in E, sm(e_{xy}) = a(lca_T(s(l_1(x), l_2), s(l_1(y), l_2)))

where :math:lca_T(x, y) is the lowest common ancestor of nodes :math:x and :math:y in :math:T.

:param graph: the domain graph
:param vertex_labels: 1d array of positive integers, labeling of the graph vertices into super-vertices
:param other_hierarchies: a hierarchy or a list of hierarchies: hierarchies can be given either as valued trees
(pairs (tree, altitudes) ) or as saliency maps (pairs (graph, edge_weights)), defined on the pixel graph or
on a region adjacency graph (Concept :class:~higra.CptRegionAdjacencyGraph).
:return: a hierarchy or a list of hierarchies as saliency maps
"""
result = []
list_input = True
if not hg.is_iterable(other_hierarchies):
raise TypeError("bas format for other hierarchies.")

first_element = other_hierarchies[0]
if not hg.is_iterable(first_element):
list_input = False
other_hierarchies = (other_hierarchies,)

aligner = hg.HierarchyAligner.from_labelisation(graph, vertex_labels)

for hierarchy in other_hierarchies:
obj, values = hierarchy
if type(obj) is hg.Tree:
leaf_graph = hg.CptHierarchy.get_leaf_graph(obj)
if leaf_graph is not None and hg.CptRegionAdjacencyGraph.validate(leaf_graph):
r = aligner.align_hierarchy(vertex_map, obj, values)
else:
r = aligner.align_hierarchy(obj, values)

elif type(obj) is hg.UndirectedGraph:
bpt, altitudes = hg.bpt_canonical(obj, values)
r = aligner.align_hierarchy(vertex_map, bpt, altitudes)
else:
r = aligner.align_hierarchy(obj, values)

else:
raise Exception("Hierarchy format not recognized: " + str(hierarchy))
result.append(r)
if not list_input:
return result[0]
return result

[docs]def project_fine_to_coarse_rag(fine_rag, coarse_rag):
"""
Find for each region of the fine rag, the region of the
coarse rag that maximises the intersection with the "fine" region.

See: :func:~higra.project_fine_to_coarse_labelisation

:param fine_rag: reference region adjacency graph (Concept :class:~higra.CptRegionAdjacencyGraph)
:param coarse_rag: region adjacency graph to align (Concept :class:~higra.CptRegionAdjacencyGraph)
:return: a 1d array of size fine_rag.num_vertices()
"""
return hg.project_fine_to_coarse_labelisation(
hg.get_attribute(fine_rag, "vertex_map"),
hg.get_attribute(coarse_rag, "vertex_map"),
fine_rag.num_vertices(),
coarse_rag.num_vertices())

[docs]def project_fine_to_coarse_labelisation(labelisation_fine, labelisation_coarse, num_regions_fine=0, num_regions_coarse=0):
"""
Find for each label (ie region) of the fine labelisation, the label of the region in the
coarse labelisation that maximises the intersection with the fine region.

Pre-condition:

- :math:range(labelisation\_fine) = [0, \ldots, num\_regions\_fine[
- :math:range(labelisation\_coarse) = [0, \ldots, num\_regions\_coarse[

Then, for all label :math:i \in [0, \ldots, num\_regions\_fine[,

.. math::

result(i) = \\arg \max_{j \in [0, \ldots, num\_regions\_coarse[} | (fine\_labelisation == i) \cap (coarse\_labelisation == j) |

If :attr:num_regions_fine or :attr:num_regions_coarse are not provided, they will be determined as
:math:max(labelisation\_fine) + 1 and  :math:max(labelisation\_coarse) + 1

:param labelisation_fine: 1d array of positive integers
:param labelisation_coarse: 1d array of positive integers (same length as :attr:labelisation_fine)
:param num_regions_fine: optional, number of different labels in :attr:labelisation_fine
:param num_regions_coarse: optional, number of different labels in :attr:labelisation_coarse
:return: a 1d array mapping fine labels to coarse labels
"""
labelisation_fine, labelisation_coarse = hg.cast_to_common_type(labelisation_fine, labelisation_coarse)

return hg.cpp._project_fine_to_coarse_labelisation(labelisation_fine, labelisation_coarse, num_regions_fine, num_regions_coarse)