<title>MapSnapper: engineering an efficient algorithm for matching images of maps from mobile phones</title>

Jonathon Hare, Paul Lewis, Layla Gordon, Glen HartProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 2007 · DOI

TL;DR

This paper introduces MapSnapper, an efficient algorithm for matching low-quality mobile phone images of paper maps to high-quality digital map representations. It tackles the challenge of image degradation and transformations common in mobile photography, offering a robust solution for location-aware information retrieval.

What Problem Does This Paper Address?

The ubiquity of camera-equipped mobile devices presents an opportunity for novel information retrieval systems. Imagine pointing your phone at a paper map and instantly getting information about the surrounding area – events, facilities, or opening times. However, achieving this requires accurately identifying where on the map the photo was taken. This is a significant challenge because images captured by mobile phones are often low-resolution, noisy, and subject to various distortions (lighting, perspective, etc.). Traditional image matching techniques struggle with these degraded inputs. MapSnapper aims to bridge this gap by developing a system that can reliably match these imperfect mobile map images to a precise digital map, enabling location-based services.

Methods

MapSnapper employs a multi-stage computer vision pipeline. The core of the system involves:

  • Interest Point Extraction: Identifying "interesting" or salient regions within both the query image and the digital map. The paper opts for Lowe's difference-of-Gaussian (DoG) detector, which is known for its stability across different scales.
  • Local Descriptor Generation: Describing the visual content of each identified interest point. The Scale-Invariant Feature Transform (SIFT) descriptor is used, which is robust to changes in scale, rotation, and illumination.
  • Interest Point Matching: Finding corresponding interest points between the query image and the digital map. Initially, a brute-force nearest-neighbor approach was used, with a refinement to accept matches only if the nearest neighbor was significantly closer than the second nearest.
  • Geometric Consistency Estimation: This is a crucial step to ensure that the matched points represent a plausible geometric transformation between the query image and the map. The system initially used a planar homography, but later transitioned to an affine transform, which proved more suitable given the limited out-of-plane rotation expected from mobile map photography. The RANSAC (Random Sample Consensus) algorithm is employed for robust estimation of these geometric parameters, even in the presence of outliers.
  • Location Determination: Once a consistent geometric transform is established, it's used to project the center of the query image onto the map's coordinate system, yielding the precise grid reference.

The development process was heavily evaluation-driven, with iterative improvements based on performance analysis.

Datasets

The paper describes the creation of a test dataset consisting of 118 photos captured from a 1:25000 scale Ordnance Survey Landranger series map, covering an area of 20 x 60 kilometers. These images were taken using two mobile phones: a Sony-Ericsson T630 (first-generation camera phone) and a Sony-Ericsson K750 (second-generation, 2-megapixel camera). All images were shot at the lowest resolution (120 x 160 pixels) and at a distance of approximately 10cm from the map, capturing 1-2 grid squares per photo. Ground truth was established by manually matching each test image to the map and recording the corresponding 6-figure grid reference.

Key Insights and Ideas

  • Affine Transform Superiority: For the specific use case of matching mobile phone images to maps, an affine transform proved to be a more robust and efficient geometric model than a planar homography, primarily due to the limited out-of-plane rotation.
  • Evaluation-Driven Development is Key: The paper highlights the importance of a systematic, evaluation-driven approach. By analyzing failures and errors at each stage, the researchers were able to incrementally improve the algorithm's robustness and speed.
  • Trade-offs in Speed vs. Robustness: Initial attempts to speed up the algorithm by using a smaller matching sample or a cruder scale-space search introduced some vulnerabilities, emphasizing the need for careful balancing of performance metrics.
  • SIFT's Enduring Relevance: The continued reliance on SIFT descriptors underscores their effectiveness in handling real-world image variations, even with the advent of newer techniques.

Key Results

The paper details significant improvements across several iterations:

  • Initial Prototype: Suffered from high failure rates (around 53%) and a substantial percentage of errors (over 30% with more than two grid squares distance). The average time for a non-failure result was about 48 seconds.
  • Robustness-Improved Algorithm: Achieved a dramatic reduction in failures (overall 13%, K750 4%, T630 16%) and errors. The average processing time dropped to under 40 seconds.
  • Sped-Up Robust Algorithm: Further optimized for speed, achieving average non-failure run times of approximately 5 seconds for K750 and 6 seconds for T630. This version also showed improved performance, with overall failures at 10% and K750 failures at only 2%.

Limitations and Future Work

  • Limitations:
    • The initial prototype's performance was not satisfactory for practical deployment.
  • The "sped-up" scale-space search, while fast, was described as "a little crude" and could potentially be tricked by queries from entirely different maps.
  • The paper notes that images falling into the failure category in the robust algorithm were often very difficult to locate even by hand for ground truth generation.
  • Future Work:
    • The paper suggests that the scale-space search approach could be improved by incorporating constraints and sanity checks to validate the geometric transform.
  • Optimizing the off-the-shelf algorithms for interest point detection and descriptor calculation (e.g., at the source code level) was beyond the project's scope but could offer further speed improvements.
  • The authors imply that further refinement of the matching and geometric consistency stages could lead to even greater robustness and speed.

Summary updated

Abstract

The MapSnapper project aimed to develop a system for robust matching of low-quality images of a paper map taken from a mobile phone against a high quality digital raster representation of the same map. The paper presents a novel methodology for performing content-based image retrieval and object recognition from query images that have been degraded by noise and subjected to transformations through the imaging system. In addition the paper also provides an insight into the evaluation-driven development process that was used to incrementally improve the matching performance until the design specifications were met.
BibTeX
@inproceedings{hare2007lt,
  author = {Jonathon Hare and Paul Lewis and Layla Gordon and Glen Hart},
  title = {{\<title\>MapSnapper: engineering an efficient algorithm for matching images of maps from mobile phones\</title\>}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {2007},
  doi = {10.1117/12.767207},
}
Figure