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.

project_fine_to_coarse_labelisation(...[, ...])

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.

See: project_fine_to_coarse_labelisation()

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