A metaheuristic approach for efficient and effective sketch-to-metric map alignment

ABSTRACT

Sketching as a natural mode for human communication and creative processes presents opportunities for improving human–computer interaction in geospatial information systems. However, to use a sketch map as user input, it must be localized within the underlying spatial data set of the information system, the base metric map. This can be achieved by a matching process called qualitative map alignment in which qualitative spatial representations of the two input maps are used to establish correspondences between each sketched object and one or more objects in the metric map. The challenge is that, to the best of our knowledge, no method for matching qualitative spatial representations suggested so far is applicable in realistic scenarios due to excessively long runtimes, incorrect algorithm design or the inability to use more than one spatial aspect at a time. We address these challenges with a metaheuristic algorithm which uses novel data structures to match qualitative spatial representations of a pair of maps. We present the design, data structures and performance evaluation of the algorithm using real-world sketch and metric maps as well as on synthetic data. Our algorithm is novel in two main aspects. Firstly, it employs a novel system of matrices known as local compatibility matrices, which facilitate the computation of estimates for the future size of a partial alignment and allow several types of constraints to be used at the same time. Secondly, the heuristic it computes has a higher accuracy than the state-of-the-art heuristic for this task, yet requires less computation. Our algorithm is also a general method for matching labelled graphs, a special case of which is the one involving complete graphs whose edges are labelled with spatial relations. The results of our evaluation demonstrate practical runtime performance and high solution quality.

KEYWORDS:

• Sketch-to-metric map alignment
• graph matching
• compatibility matrix
• metaheuristics
• qualitative constraint networks

Notes

1. www.sketchmapia.de.

2. This is not a tight bound since all non-empty cells in some rows may become empty because other pairs that are incompatible with them may be selected before them.

3. http://www.uni-muenster.de/Geoinformatics/en/sketchmapia/sketch-map-database.php.

Additional information

Funding

This work was partially supported by the German Research Foundation (DFG) through the project ‘SketchMapia: A Framework for Collaborative Mapping’ [Grant SCHW 1372/7-1] and by Westfälische Wilhelms-Universität Münster.