# URSIM: Unique Regions for Sketch Map Interpretation and Matching
## 6 Experiments
### Comparison with a Metric Map Matching Algorithm  
We also evaluated the results of URSIM in comparison to a recent state-of-the-art map matching method proposed by [PERSON] et al. [17], that we refer to as the decomposition alignment method (DAM). DAM focuses on sensor map to layout map matching, where a layout map represents the layout of the environment without much details and with possible errors in representation. Hence, in the related work, DAM is the method closest to URSIM in terms of its purpose: matching maps with high disparities. Furthermore, [PERSON] et al. [17] showed that DAM scores better when working with sensor maps than other recent works by [PERSON] [37] and [PERSON] et al. [38]. They also found that those two matching methods [37; 38] cannot match layout maps to sensor maps due to the large disparity in representation, even after correctly scaling the layout map. Since the sketch maps we used have an even higher level of disparity than layout maps, and since DAM performed better on both layout to sensor map and sensor to sensor map matching than the methods of [PERSON] [37] and [PERSON] et al. [38], we focused on comparing our results to DAM's.  
DAM starts by segmenting two maps into regions and calculates the oriented minimum bounding box for each region. Segmentation is done using the morphological region segmentation presented by [PERSON] et al. [27]. For every pair of bounding boxes with similar shapes, a matching hypothesis is generated in the form of affine transformations. The shape descriptor of regions used to perform the matching is an ordered sequence of vertex-edge tuples where vertices denote corners, i.e., places where the region's boundary has an angle other than \(\pi\). For each possible hypothesis, by applying the associated affine transform, the correspondences between all bounding boxes are found and a matching score is calculated. The transformation that leads to the highest score is used to perform the matching. Thus, DAM takes into account metric information of the maps and uses a different set of features than our method.  
[PERSON] et al. [17] reported a success rate of 50.54% on the subset of the partial map dataset used in this article. However, that number alone did not allow us to compare their method to ours since the \(F_{1}\) score cannot be compared to the success rate. To be able to compare the affine transformation returned by DAM with the ground truth correspondences given by the users, we  
Figure 13: \(F_{1}\) scores when using URSIM with \(m\) ranging from 0 to 0.5 on the partial map dataset. Above \(m=0.1\) the \(F_{1}\) scores are rather stable but are again not as good as when using different values of \(m\) tailored for particular maps. Again, \(m\) must be carefully chosen on a per map basis.  
created correspondences between the largest overlapping MAORIS regions in both maps after having applied DAM's affine transformation. We compared those correspondences to the ground truth correspondences using the method presented at the beginning of this section.  
Over the partial sensor map dataset, DAM has a mean \(F_{1}\) score of \(0.78\pm 0.31\) and a median of \(0.94\) performing better than URSIM. However, over the sketch map dataset, DAM is not able to return correct correspondences due to the highly schematic nature of sketch maps and the large errors in local scale. Indeed, corners and walls are hard to find in sketches and [PERSON] et al. showed that the absence of these two features would result in incorrect correspondences. Two of the best map alignment returned by DAM are shown in Figure 14 where the sketch maps are overlaid on the metric map. One can see that since the maps cannot be locally scaled and translated to fit each other, the results are incorrect. Hence, while using DAM to match partial sensor maps returns more accurate matching results, URSIM performs better at matching maps which structural differences and a high level of abstraction in the representation.