# URSIM: Unique Regions for Sketch Map Interpretation and Matching
## 6 Experiments  
We evaluated our dataset on 25 sketches presented in our previous work [26] and available online [35].  
The sketch map dataset corresponds to the ground truth of the KTH dataset for SLAM ([[http://www.nada.kth.se/%7](http://www.nada.kth.se/%7) Ejohnf/kthdata/dataset.html]([http://www.nada.kth.se/%7](http://www.nada.kth.se/%7) Ejohnf/kthdata/dataset.html)). Twenty-five anonymous users explored a 3D environment online ([[http://mro.oru.se/wp-content/material/sketchmap-web/](http://mro.oru.se/wp-content/material/sketchmap-web/)]([http://mro.oru.se/wp-content/material/sketchmap-web/](http://mro.oru.se/wp-content/material/sketchmap-web/))) and were asked to draw a 2D map from memory. The metric map representing the environment and four sketch maps are shown in Figure 1.  
The correct correspondences, i.e., ground truth correspondences, between each sketch map and the metric map were manually annotated by both an expert in mobile robotics and an architect.  
Given two segmented maps, the ground truth correspondences annotate which regions are equivalent. However, due to factors such as map resolution, level of detail, or noise in the measurements, the segmentation of the sketch and metric maps can differ and regions in the sketch  
Figure 6: Illustration of the calculation of the Levenshtein edit distance for correspondences between the neighbors of two vertices in red, where vertex attributes are represented by colors. The blue and black vertices are correctly matched and do not increase the Levenshtein edit distance. On the other hand, the olive and grey vertices are matched but need to change color attribute, thus increasing the Levenshtein distance by one. Finally, the empty vertex on top of the left neighbor needs to be removed, increasing the Levenshtein edit distance by 2: one for the removal of the vertex and one for the removal of the edge. The final edit distance of this matching is 3.  
map can be matched to more than one region in the metric map. Similarly, regions in the metric map can be matched to multiple regions in the sketch map, as illustrated in Figure 7.  
We refer to such groups of correspondences as ground truth cliques.  
We evaluated the set of correspondences returned by URSIM by calculating its \(F_{1}\) score:  
\[F_{1}=2\frac{p\cdot r}{p+r} \tag{12}\]  
with the precision \(p\):  
\[p=\frac{tp}{tp+fp} \tag{13}\]  
and the recall \(r\):  
\[r=\frac{tp}{tp+fn} \tag{14}\]  
The \(F_{1}\) score ranges between 0 and 1, with 0 being the worst possible score and 1 being the best. The precision and recall are calculated using the number of true positives \(tp\), false positives \(fp\), and false negatives \(fn\). Given a set of correspondences between a sketch map and a metric map, true positives are correspondences where both vertices are present in the same ground truth clique. False positives are all correspondences for which both vertices are not present in the same ground truth clique. Finally, false negatives are all ground truth cliques for which no correspondence in the set corresponds to a true positive.  
All results reported in this section were calculated over both ground truth sets.