Georeferencing with QR Codes

Generate a World File for scanned or faxed paper maps

UPDATE: See here for more recent tests. I plan to move this article to the domain where I will be keeping examples of my work from now on.

 A few years ago at the first WhereCamp, I was thinking about ways to bring data in and out of paper maps. It seemed that there would some interesting advantages to being able to mark up paper maps and then have the annotations converted into geospatial data. First and foremost, it would allow data collection without having to have expensive dataloggers, which are either simply unaffordable, or so expensive that not enough units can be purchased to supply to a team of fieldworkers. The units are also attractive to thieves and bandits.

So the idea would be to have a system that can print out paper maps which can be marked up, and then scanned back it and the system would recognize and georeference the markup. Annotations could be alphanumeric, recognized with OCR, or perhaps symbolic, recognized with something like SIFT.  A number written on the footprint of a building could be recognized and that value be automatically entered into a data field for that building. Symbols could even be stickers that could applied to the map, which could be useful for field workers of limited literacy. Potentially the system could recognize different colors, so a green line would signify a line that needed to be added to a polyline feature class, while a red X through a line would indicate that that line feature needs to be removed. Some sort of barcoding system would store georeferencing information about that particular map.

As I thought more about it, this would still require a computer, a printer, and a scanner, which still might be either unaffordable or have high theft value. They also could require more technical expertice than is available in some areas. Then I realized there was another alternative - fax machines. They are further down the technological ladder and can handle scanning and printing. The processing could be located in a safer area and could centralize the data collection. They are also easy to use. The catch is that you lose resolution and the option to use color as a signifier, but for certain applications perhaps that would be OK.

At first, I thought the project was kind of a gag hack - GIS over Fax! But then other possibilities came up - you could automate the distribution of maps using the Asterisk PBX software. Field workers could call in to a number and with an automated menu system request assignments and have them faxed to their nearest fax machine. In this system, since maps are doled out from a central server each map session could be recorded in a database and store information about the fieldworker, the map georeferencing information, layers, etc, and less data would have to be barcoded into the paper map, just some sort of unique identifier.

 I did some research here and there but never got to the point of actually trying to get something to work until I read this post by Michal Migurski. He was thinking along the same lines but had a slightly different application - allowing people to mark up paper maps of OpenStreetMap data so that they or someone else could change or update the OSM base later.

Mike had gotten further than I had and had come up with a novel system that used SIFT and some cool-looking gargoyles to use as a basis for positioning the map.  In the ensuing discussion in the comments I realized that the positioning information in the QR Code might be able to work for positioning the map.

So I threw together a simple proof-of-concept experiment. First, I output a basic map of know extents and resolution from Mapserver. Then using the Google Graphs API I made a QR code that contained the coordinates of the top-left corner of the map and its resolution. I made two QR codes, one 80 pixels wide and one 120 pixels wide, to experiment with. I then dropped them into the 640 x 640 pixel map image with Photoshop, aligning the QR to the top-left of the map. For testing, I made two modified versions of the map, one with larger extents and one with the image rotated 5 degrees.

 I then used a script based on Zxing to find the QR Code's positioning and alignment marks. Those were then manually entered into a that outputs a world file to go with the original image. I would have preferred to do it all in one script but none of the Python QR libraries output position, so I had to use the Java Zxing library for now.

The Python script takes the coordinates for the QR finder points, and uses them to calculate the new scale and rotation of the map. It's all basic stuff - some trigonometry to figure out the orientation and some list sorting to figure out which of the finder points is which.

Here are the results. The base map (base80.jpg) is just the raw image, and the script should basically just transform the location from the QR finder point back to the corner of the image. The map with different extents (zoomedout80.jpg) lines up very well since there is no rotation involved. The map with the rotation (rotate5deg120.jpg) gets the scale very close but the rotation is off by 0.25 degrees. I think there is enough slop in the detection of the QR location points that it will always be slightly inaccurate, even though we average the angle from three measurements between alignment points. One could probably get better results by using two QR codes on opposite corners of the image to get a lower cosine error.

One advantage to using only one QR code is that you could crop the image before searching for the QR code to make it easier for the software to find. I had to use the 120 pixel QR on the rotation test because it would not detect the 80 pixel QR initially. I have not tried cropping yet to see if I can get the 80 pixel image to work. Also, since my map is black and white maybe I'm not making it as easy for the software as it could be. If you crop out the top-left quarter-quarter of the image the world file you generate for it will also be valid for the uncropped image. If you can't find a QR in the top-left, then the image is probably scanned upside-down, so crop the lower quarter-quarter, turn it 180 degrees, and check that instead.

A few other notes: The values I encoded into the QR for the image location are for the top-left corner of the image, and they really should be for the top-left QR alignment point. I entered the correct value into the script. The generated TFW file in the examples is also slightly incorrect  - it needs to describe the location of the center of the top-left pixel and in the examle it's actually the top-left extent of the pixel. That has been fixed in the code, though.

Next up for research is to get a better sense of QR code generation. I'm not sure how consistent the geometry of the QR codes is when a given pixel size is requested but with varying contents. It might be useful to encode more information about the map into the QR. I also need to try some prints and scans instead of digital mockups. Finally, I'd like to get the whole thing working together in an automated manner.