# URSIM: Unique Regions for Sketch Map Interpretation and Matching
## 3 Related Work  
Few methods have been developed to match maps with a high level of abstraction. Instead, most works focus on matching partial metric maps or limit the extent to which maps can differ by using particular types of maps such as CAD models, aerial images, or blueprint layouts [4; 5; 6; 7; 8]. It is easy to understand why that is: similar maps can use easily describable similarity measures based on direct sensor measurements or some classic descriptors such as SIFT. On the other hand, sketch maps have a high level of abstraction in the representation and one needs to understand their implicit characteristics, such as their topology, to be able to use them: a matching method that depends on correct metric information will lead to incorrect correspondences when used on sketch maps. Figure 2: Flowchart of the Unique Region for Sketch map Interpretation and Matching (URSIM) method. Looking at the example maps, one can see that understanding the sketch map and how it relates to a metric representation of the environment is not straight forward. However, sketch maps are used to convey information about the world and, thus, while they are abstract representations of an environment, there is still a _logic_ to how they are related to the real world. That logic is conveyed through the topology of the environment and by putting emphasis on accurate representation of important information; important information being decided in a subjective manner by the person drawing. A common way to find the topology of a map is to use its Voronoi diagram. The Voronoi diagram is the set of all points at equal distance from at least two obstacles, and, as such, represents the topology of the environment through its skeleton [9; 10]. Working on metric maps with errors due to drift or sensor noise, [PERSON] and [PERSON] [11; 12] evaluated map quality by matching topology graphs derived from the Voronoi diagrams of two grid maps. They used the wavefront propagation algorithm to find a matching between the graphs. Correspondences are determined based on a similarity measure between vertices and ICP [13] using the local maps around the vertices. They tested their method on maps obtained by multiple robots during the RoboCup Rescue. While their method leads to good matching results on sensor maps, it did not work well with sketch maps due to the multiple parameters that needed tuning on a per map basis [3]. In this article, we propose to use a different similarity measure that needs less parameters and is more robust to large differences in scale or representation between the maps. [PERSON] et al. [14] merged maps using rectangular features to estimate the largest shared area. They assumed that the environment was made of polygons with orthogonal angles. Their method is able to handle rotations and different global scales but cannot handle deformations of the map. While the idea of segmenting the map into similar regions for matching is also used in URSIM, URSIM is more robust to local changes. Some works use CAD maps representing a building in a metrically correct way. For example, [PERSON] et al. [8] presented a method for localization using a CAD floor plan as prior map. They performed matching between maps from different modalities by using maximum a posteriori pose-graph-based SLAM system [15]. They reported better localization results than Monte-Carlo localization on seven datasets. Although the method can handle some clutter in the environment, the paper states that \"significant or even full occlusion due to clutter or large installations have a substantial effect on the method\". It should be also noted that associations can be hard to find between maps with a high level of disparity and performing pose graph optimization using sensor measurements might be impossible if the map built by the robot and the sketch differ too much. On the other hand, our method is able to find correspondences between maps with large structural differences. [PERSON] et al.