# URSIM: Unique Regions for Sketch Map Interpretation and Matching
## 5 Graph Matching  
Computing Vertex Descriptors that Express Topological Similarity with Respect to the Anchors and the Standardized Size of Regions  
After reducing the set of unique regions as described in Section 4.3, we have two sets of equal length containing the most similar unique regions between the maps, i.e., the anchors. However, those anchors typically only concern a subset of all regions in the environment. The remaining regions not included in the anchor sets do not have attributes that distinguish them from most of the other regions in the map. To be able to express the similarity between all regions, and not just the anchors, the next step of the URSIM method creates region descriptors for all regions in both the sketch map and the metric map. From a segmented map, we build a graph where each vertex corresponds to a region and edges connect regions in contact. The graph creation process is illustrated in Figure 5. We then compute a descriptor for each vertex. We built on the Laplacian Family Signature (LFS) presented by [PERSON] and [PERSON] [30]. The LFS of a vertex \(v_{u}\) with index \(u\) is the vertex descriptor describing a given vertex's structural relationship to its extended neighborhood:  
Figure 4: Examples of correspondences between anchors identified using the Hungarian matching between different map types. Correct correspondences are in grey while incorrect correspondences are in red. While the Hungarian matching algorithm allows determining a reduced set of anchor regions most likely to correspond to each other, one can see that it is often unable to find sufficiently many correct associations between the vertices since the topology of the map is not yet taken into account. (**a**) shows correspondences between a sketch map and a metric map; the use case of URSIM. While the main room is correctly matched, the smaller regions are incorrectly matched. (**b**) shows correspondences between two sketch maps. One out of two of the anchor correspondences is correct. (**c**) shows the correspondences between two sensor maps. Two out of three correspondences are correct. \[s_{u}(t)=\sum_{k}h(t,\lambda_{k})\phi_{k}(u)^{2} \tag{3}\]  
The expression of the LFS depends on the eigenpairs \(\{\lambda_{k},\phi_{k}\}_{k=1}^{|V|}\) of the graph Laplacian \(\mathcal{L}\) with \(\phi_{k}(u)\) representing the \(u\)th element of the eigenvector \(k\), and where \(h(t,\lambda_{k})\) is a real-valued function. The calculation of \(s_{u}(t)\) depends on the \(u\)th elements of \(\phi_{k}\) due to the ordering of the vertices used when calculating \(\mathcal{L}\). While the calculation of the graph Laplacian \(\mathcal{L}\) is described in more detail below, it should be noted that \(\mathcal{L}\) is a matrix representation of the graph. More precisely, \(\mathcal{L}\) measures the extent to which a graph differs at one vertex from its values at nearby vertices. Given a graph with \(V\) vertices, the vertices are ordered from \(v_{1}\) to \(v_{V}\) to calculate \(\mathcal{L}\) as follow:  
\[\mathcal{L}= \begin{bmatrix}\mathcal{L}_{v_{1}v_{1}}&\mathcal{L}_{v_{1}v_{2}}& \ldots&\mathcal{L}_{v_{1}v_{V}}\\ \mathcal{L}_{v_{2}v_{1}}&\mathcal{L}_{v_{2}v_{2}}&\ldots&\mathcal{L}_{v_{2}v_{ V}}\\ \vdots&\vdots&\ddots&\vdots\\ \mathcal{L}_{v_{V}v_{1}}&\mathcal{L}_{v_{V}v_{2}}&\ldots&\mathcal{L}_{v_{V}v_ {V}}\end{bmatrix}  \tag{4}\]  
where \(\mathcal{L}_{v_{V}v_{1}}\) relates vertex \(n\) to vertex \(m\). When calculating the eigenpairs of \(\mathcal{L}\), a given vertex \(v_{u}\) is directly related to the element \(u\) of each eigenvector \(k\), according to the ordering used to calculate \(\mathcal{L}\). For a given eigenvector \(\phi_{k}\), we have:  
\[\phi_{k}= \begin{bmatrix}\phi_{k}(1)\\ \phi_{k}(2)\\ \vdots\\ \phi_{k}(V)\end{bmatrix}  \tag{5}\]  
where \(\phi_{k}(u)\) relates to \(v_{u}\). In our work, we use the heat kernel signature (HKS) as the real-valued function \(h(t,\lambda_{k})\). The HKS was presented by [PERSON] et al.