Public Lab Research note


The Magic Behind MapKnitter: Leaflet.DistortableImage

by justinmanley | May 21, 2015 03:24 21 May 03:24 | #11826 | #11826

justinmanley was awarded the Basic Barnstar by stevie for their work in this research note.


Leaflet.DistortableImage is a new plugin for the JavaScript mapping library Leaflet, written by Public Lab contributors to make MapKnitter better. Here's why we wrote Leaflet.DistortableImage, the challenges we faced, and how you can participate in developing Public Lab's open-source software tools for environmental research.

The Problem

Turning grassroots, citizen-gathered aerial imagery into legible maps is a challenge. Balloons bob, kites swoop, and the resulting aerial photographs don't always fit together neatly. Nevertheless, citizen mapmakers and scientists can produce legible maps from aerial images by stretching (rubbersheeting) and rotating images, a process called georectification. Leaflet.DistortableImage is a new plugin by Public Lab contributors for the JavaScript mapping library Leaflet that makes georectifying images fast, smooth, and simple.

MapKnitter, created by Public Lab, has long been one of the best tools for doing georectification in the browser. Under the hood, MapKnitter relies on a JavaScript library for rendering base maps and handling user interactions. For a long time, MapKnitter relied on OpenLayers for rendering maps and Cartagen for positioning and warping aerial photographs. During the summer of 2014, with help from Google Summer of Code students, Public Lab began porting MapKnitter over to the Leaflet mapping library.

Leaflet.DistortableImage is a Leaflet plugin, developed as part of this port, for resizing, rotating, and stretching images on top of Leaflet maps. Try it out here:

The math under the hood

Basic georectification can be done by composing a few simple image transformations: rotation, scaling, and distortion. Built-in CSS functions made it easy to add rotating and scaling functionality to the Leaflet plugin. Distorting images, the third component of georectification, was much more difficult. Ideally, a rectangular aerial photograph should correspond to a rectangular outline on the surface of the earth. This is roughly the case if the camera's orientation can be fixed so that it is pointed straight down at the surface of the earth. In practice, the movement of the supporting kite or balloon and the vagaries of the wind deflect the camera from this ideal angle. The resulting oblique orientation of the camera to the ground causes the field of view of the camera to intersect the surface of the earth in an irregular quadrilateral, rather than a rectangle. The purpose of distorting images during georectification is to recover the irregular geographic outline from the rectangular form of the image.

There are many distortion algorithms that might be used to transform rectangular into irregular quadrilaterals. We chose to use a projective transformation, which is well-suited to georectification because it captures the perspectival nature of the distortion introduced by the swinging of the camera.

Kite_Mapping_Distortions.png

Mathematically, a projective transformation is a function which acts on the projective plane, a two-dimensional space which captures many of the features of perspectival vision. In the projective plane, two parallel lines can converge, just as railroad tracks converge in our own vision. We can apply a projective transformation to shapes in the Euclidean (ordinary) plane by embedding them in 3-dimensional space, multiplying by a 3 * 3 square matrix. This accords with the commonsense observation that our everyday perspectival experience is the result of fitting the 3-dimensional world we occupy into the two-dimensional picture plane of our vision.

Cartagen, built before the adoption of 3d CSS transformations (first proposed in 2009), approximated the perspectival distortion of the projective transformation by placing the image in an HTML canvas element, subdividing the image into many small quadrilateral tiles, and applying a slightly different affine transformation to each tile. It wasn't possible for Cartagen to use the two-dimensional matrix transform because the matrix() function, designed to apply affine transformations, lacks the degrees of freedom necessary for the projective transformation.

We implemented the projective transformation for Leaflet.DistortableImage using the CSS transform property and the matrix3d function. Leaflet.DistortableImage does the hard work of calculating a 4*4 projective transformation matrix mapping each corner of the aerial photograph to a geographic coordinate on the map. This matrix is then handed off to the matrix3d function, which applies the transformation. This approach allowed us to delegate the pixel-pushing mechanics of the transformation to the browser's renderer. Because we're using a three-dimensional transformation, the browser delegates much of the work, in turn, to the GPU. The speed of the browser's renderer, combined with the hardware acceleration of the GPU, combined to produce smoother, faster distortions.

Challenges

Understanding the mathematics behind the projective transformation was one of the most challenging aspects of designing Leaflet.DistortableImage. This was truly a team effort; Anish, Bryan, Jeff, and Vidun all contributed to making sense of projective distortions. Franklin Ta's outstandingly clear blog post, Computing CSS matrix3d transforms, was also invaluable in helping us understand the mathematics of the transformation.

Mathematics aside, applying custom CSS transforms to Leaflet map layers turned out to be tricky in practice. Leaflet uses CSS translations to position image overlays on the base map and CSS scaling to animate images while the map is zooming. All CSS transformations are set via a single CSS transform property. This means that complex transformations must be set by combining rotations, translations, scalings, and other primitive transformations into a single transform string. for example:

.crazy-transformation {
    transform: matrix(1, -0.2, 0, 1, 0, 0) scale(5) translate(100);
}

This translates an element, then scales it, then skews it according to a (two-dimensional) affine transformation. Once set, it is difficult to selectively update the components of the CSS transform property. We wanted to be able to exclusively update the matrix3d component of the transform when a distorted the image, leaving Leaflet's translate transform alone. We opted to combine rotation and scaling (each conceptually distinct transformations) into the 4*4 distortion matrix and to recalculate the base translation for the image (ordinarily handled by Leaflet core), then completely overwrite the CSS transform property each time the image was modified. Such a degree of interference with the Leaflet backend seems inevitable as long as we rely on CSS transforms to carry out image distortions (although there are other approaches - see this Github issue).

Future development

Theoretically, a perspectival distortion should be sufficient to georectify even the most distorted aerial images depicting a relatively flat landscape. In practice, it can be easier to visually georectify images using distortion methods which provide even more flexibility than the projective transformation - and, of course, not all interesting land is flat! It might be helpful to provide users with more powerful warping algorithms, such as Shepard's Distortion and spline mesh distortions. CSS transforms, while convenient, might not be sufficiently powerful to implement these transformations, so this would likely involve a return to a canvas-based approach.

There's also room for improvement in the image editing interface. We designed Leaflet.DistortableImage to support all of MapKnitter's image manipulation functionalities, which, in addition to image rotation, scaling, and distortion, include toggling image outline and transparency, and locking images in place. We've experimented with various static and contextual toolbars (now using Leaflet.toolbar!) for exposing these options to users, but we haven't yet found a presentation which is intuitive and unobtrusive.

Get Involved!

If this project interests you, we encourage you to get involved, either as a developer by contributing on GitHub, or, as a user, by telling us in the comments, or on GitHub issues how Leaflet.DistortableImage is useful to you and how it might be improved. Public Lab is a community of citizen environmental researchers and activists, and we always welcome technical and non-technical contributors to help build the software tools we use to make change in the world! Come join us!


4 Comments

I was thinking today of the idea from a couple years ago of reimplementing full map export in the client side, and had a thought -- these matrix transforms could be reused in WebGL, which is saved to a virtual pixel buffer (a canvas). This could be downloaded as a PNG, if the browser can handle that...

It was interesting to me that for reasons I don't really understand, most rubbersheeting in the GIS tradition uses polynomial transforms with GCPs, which are run (in GDAL, or ImageMagick, for example) on the CPU. One reason our warping is so fluid and fast is that it's run on the GPU, as is WebGL. So because we've taken a different (and as Justin explains above, more commonsense) approach to "undoing the perspectival distortions in our images," we may be able to take advantage of the GPU -- and of client-side rendering -- to do the heavy lifting of exporting, or merging, maps into large rasters. This would make the Mapknitter project much more scalable and efficient, if we could pull it off!

We could call it gdal.js, maybe?

Is this a question? Click here to post it to the Questions page.

Reply to this comment...


There are two problems: JavaScript generating the image file (with canvas.toDataURL()), which maybe could be done in a web worker...

Next, ensuring that the browser doesn't try to open the image, but just downloads it. Some discussion of that here: http://greenethumb.com/article/1429/user-friendly-image-saving-from-the-canvas/

Reply to this comment...


Thanks for all the work the development puts into these tools.

Reply to this comment...


I finally circled back and implemented download of full-resolution distorted images using WebGL, here: https://github.com/jywarren/webgl-distort

I'd love to integrate that into Leaflet.DistortableImage; I made an issue here: https://github.com/publiclab/Leaflet.DistortableImage/issues/63

Reply to this comment...


Login to comment.