# URSIM: Unique Regions for Sketch Map Interpretation and Matching
## 3 Related Work
[7] aligned an occupancy grid map with a floor map to obtain semantic information about the environment. They segmented the environment using morphological operations and created a graph out of the segmentation. Using the shape of each region, they aligned the graph of the occupancy map and the floor map using graph matching [16] and a similarity transform matrix computed from correspondences of the regions. They tested their method in two environments and obtained an error rate in scale, rotation, and translation of less than 4% compared to the alignment given by a user. However, their method needs both maps to have similarly shaped regions after segmentation since the region comparison is based on the Hu moments. Thus, URSIM can handle maps with higher disparity than their method. [PERSON] et al. [5] used schematic maps for interaction between a human and a robot, and between a robot and its environment. A schematic map corresponds to a user-provided map depicting a simplified version of the topology of the environment. Corner correspondences between the environment and the schematic map are found by mapping features detected in sensor space to features in the schematic map. They tested their method on a simulated environment with three rooms. By definition, their matching method depends on the ability to find spatial features and, since those features are not always present in sketch maps, our method does not rely on them for matching. In addition, in the work of [PERSON] et al. [5], correct interpretation of the spatial relationships is only possible because the schematic map creation step is highly restricted, e.g., walls need to be straight and features easy to detect. On the other hand, our method handles high disparity between the maps and is less restrictive about the way the input is supposed to be drawn. [PERSON] et al. [4] studied navigation in an indoor environment using a map provided by a user as input. They used the crossings and dead-ends of the Voronoi diagram as landmarks. While correct corridor length was not needed, the walls in the map had to be straight and the existence and connectivity of corridors had to be correct. Hence, their method assumes a sufficiently accurate representation of the environment. Our method is able to match regions of two maps almost independently of local scaling and does not require a metrically accurate representation. [PERSON] et al. [17] developed a method to align a user given layout map and a sensor-built map. A layout map is defined as a simplified representation of a building that can have errors in local scaling and representation. As such, compared to other related works, the work of [PERSON] et al. [17] is the most similar to ours in terms of its aim and the types of map used. However, their alignment method is based on finding features such as walls and corners, which is not easy to achieve on sketch maps. We evaluate the performance of URSIM compared to the method of [PERSON] et al. [17] in Section 6.5. [PERSON] and [PERSON] [18] performed navigation using a sketch map of obstacles provided by the user. They extracted waypoints from the Voronoi diagram and estimated the transformation between the sketch map and the environment using a weighted least square affine matrix. The sketches were scaled and rotated to fit the environment, and errors in local scale and representation were handled by the path planner. However, obstacles and landmarks are not always represented in maps and our method handles that case. [PERSON] and [PERSON] [19; 20], [PERSON] et al. [21], and [PERSON] et al. [22; 23] developed a sketch-map interface for robot control on a PDA and used it for navigation of one or a team of robots in an indoor environment. They conducted a usability study which gave an average rating of 4.2 on a Likert scale [24] to the sketch interface, with 5 being the maximum, showing that sketch maps are an intuitive interface.