# Algorithm for alignment problems¶

 align_hierarchies(graph, vertex_labels, …) Align hierarchies boundaries on the boundaries of the provided super-vertex decomposition of a graph 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. 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.
align_hierarchies(graph, vertex_labels, other_hierarchies)[source]

Align hierarchies boundaries on the boundaries of the provided super-vertex decomposition of a graph

Given:

• a graph $$G=(V,E)$$

• a fine labelisation $$l_1$$ of the vertices of $$G$$;

• a tree $$T$$ on $$G$$ whose supervertices corresponds to the coarse labelisation $$l_2$$ of the vertices of $$G$$; and

• the altitudes $$a$$ of the nodes of $$T$$.

Let us denote:

• given a vertex $$x$$ of $$G$$ and a labelisation $$l$$, $$l(x)$$ is the region of $$l$$ that contains $$x$$

• given a region $$r$$ of $$l_1$$, $$s(r, l_2)$$ is the region $$R$$ of $$l_2$$ that has the largest intersection with $$r$$, ie, $$s(r, l_2) = \arg \max_{R \in l_2} | R \cap r |$$

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

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

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

Parameters
• graph – the domain graph

• vertex_labels – 1d array of positive integers, labeling of the graph vertices into super-vertices

• 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 CptRegionAdjacencyGraph).

Returns

a hierarchy or a list of hierarchies as saliency maps

project_fine_to_coarse_rag(fine_rag, coarse_rag)[source]

Find for each region of the fine rag, the region of the coarse rag that maximises the intersection with the “fine” region.

Parameters
Returns

a 1d array of size fine_rag.num_vertices()

project_fine_to_coarse_labelisation(labelisation_fine, labelisation_coarse, num_regions_fine=0, num_regions_coarse=0)[source]

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:

• $$range(labelisation\_fine) = [0, \ldots, num\_regions\_fine[$$

• $$range(labelisation\_coarse) = [0, \ldots, num\_regions\_coarse[$$

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

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

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

Parameters
• labelisation_fine – 1d array of positive integers

• labelisation_coarse – 1d array of positive integers (same length as labelisation_fine)

• num_regions_fine – optional, number of different labels in labelisation_fine

• num_regions_coarse – optional, number of different labels in labelisation_coarse

Returns

a 1d array mapping fine labels to coarse labels