A graph-based memetic approach to sketch geolocation

This paper presents a memetic algorithm for the task of sketch geolocation. Small sets of 2D objects having real-world origin are depicted as sketches, which capture their spatial configuration. These are matched to a much larger geospatial reference scene using a memetic algorithm, which combines both global and local search strategies. Sets are represented as attributed relational graphs in which objects are graph nodes and the spatial relationships between objects, defined by the histograms of forces, are graph edges. We define a similarity measure between two such graphs and describe two local search operators. The first is a greedy operator based on our previous work and the second is a new approach based on the VF2 subgraph isomorphism algorithm. Our experiments show that both methods can be successfully applied to this domain.