# URSIM: Unique Regions for Sketch Map Interpretation and Matching
## 6 Experiments
### Evaluation of the \(F_{1}\) Scores  
We calculated the \(F_{1}\) scores over the sketch dataset using URSIM and evaluated the correspondences in terms of both the mean and median \(F_{1}\) scores. While the mean enabled us to evaluate the general quality of the correspondences, the median gave a measure that disregards potential outliers. For example, a high median with a low mean value shows that, while most correspondences are correct, some incorrect correspondences returned low scores. On the other hand, a high mean with a low median means that most correspondences were wrong but correct ones scored very high. An efficient matching algorithm should have both mean and median as high as possible. As for the previous experiment, the matching algorithm was run with different values of \(m\) ranging from 0 to 1 by steps of 0.025, and the highest \(F_{1}\) score over all possible \(m\) was kept as the final matching \(F_{1}\) score. As a baseline, we used the graph description proposed in our previous work [3] where regions are matched depending on their type: regions can either be crossings when they have more than one edge or dead-ends when they only have one edge. The results of the baseline are presented in the first column of Table 1. Furthermore, to test the effectiveness of URSIM's graph matching method presented in Section 5.2, we replaced it by two different matching algorithms, the Hungarian matching and the VF2 algorithm developed by [PERSON] et al. [36], and compared their respective \(F_{1}\) scores. While URSIM's planar matching algorithm expands correspondences between vertices one neighborhood at the time, the Hungarian algorithm finds the solution of the assignment problem between the vertices. On the other hand, VF2 was developed to quickly find the largest common sub-graph between two large graphs. We also incrementally tested the usefulness of each attribute used to create the region descriptors by progressively building the descriptors and calculating the matching accuracy at each step. The second column of Table 1 presents the \(F_{1}\) scores obtained when using only the topology to build the descriptors: anchors and weights on the vertices were not used to calculate the LFS. We refer to this test as \(T_{1}\) and the flowchart of the algorithm can be seen in Figure 9a. The third column presents the test \(T_{2}\) whose flowchart is illustrated in Figure 9b. For \(T_{2}\), the topology and positions of anchors in the graph were taken into account when calculating the LFS. However, vertices had equal weights and, thus, the relative sizes of regions were not taken into account. The fourth column shows the matching results of the test \(T_{3}\), where, when calculating the LFS, the weights on the vertices were the standardized region's sizes but the positions of anchors in the graph were not taken into account (see Figure 9c). Finally, test \(T_{4}\), in the last column, corresponds to the full graph representation used by the URSIM method and used the topology, the positions of anchors in the graph, and the standardized size as weights for the vertices when calculating the LFS (see Figure 9d). Figure 8: Mean \(F_{1}\) score using a different number of time samples ranging from 1 to 25 on the sketch map dataset. One can see that the score stays relatively stable and does not depend much on the number of time samples. Using at least 14 time samples leads to slightly better results. In all cases, the planar matching scored higher than both VF2 and the Hungarian matching. This result highlights the importance of using the topology as much as possible during the matching.