Public Lab Research note


GSoC Update- Leaflet.draw and Non affine transformations

by anishshah101 | June 02, 2014 22:21 02 Jun 22:21 | #10524 | #10524

Work done till now:

1) Used Leaflet to create a toolbar which could draw polylines, polygons, rectangles, circles and markers to a map and then edit or delete those objects as desired. This was done using a leaflet plugin Leaflet.draw which has a github source here. Although this was not a part of my project, I thought it was important to get familiar with the use of a leaflet plugin as I plan to prepare one myself. The main image and the following one demonstrates it's use.

draw-02.png

2) Understanding and preparing mathematical equations for non-affine/projective transformations of images.

The different kinds of transformations are as follows:

geometric-transformations.jpg

Problems faced:

1) All the above transformations are a part of the Mapknitter tool currently. While the transformations involving translation, rotation and scaling are easy to implement and are also currently available in the form of Leaflet plugins, projective transformations are difficult to implement because of the mathematics involved. To prepare the javascript code from the existing algorithms is a difficult task which I am struggling with.

Community help:

1) In case somebody is familiar with the mathematics of non-affine/projective transformations, it would be really handy if I could have a quick hangout on the topic.


6 Comments

Thanks Anish. This was a bit outside the scope of your project, but I'm glad you learned from it. Sharing this might help some other Google Summer of Code students who are working on similar problems, for sure!

I thought the projective distortion was something known in the GIS domain, but I guess Jeff found an implementation of it on some guy's website. The example from acko.net is missing, but he talks about it at a very high level without any mathemathics here: http://acko.net/blog/projective-texturing-with-canvas

Neither Jeff (in his thesis) nor that guy actually discuss the mathematics behind a projective distortion. It is assumed to be already known or a task left to the reader. So, as a reader, let's see what we can find out!

We'll learn this together. Here are some links I have found just now.

"A transformation that maps lines to lines (but does not necessarily preserve parallelism) is a projective transformation. Any plane projective transformation can be expressed by an invertible 3×3 matrix in homogeneous coordinates; conversely, any invertible 3×3 matrix defines a projective transformation of the plane. Projective transformations (if not affine) are not defined on all of the plane, but only on the complement of a line (the missing line is ``mapped to infinity'')." http://www.geom.uiuc.edu/docs/reference/CRC-formulas/node16.html

From that, I get that projective distortions represent a very, very wide class of mathematical mappings. Which means we aren't going to learn much about it for our use case without being a bit more specific.

Here is a related wikipedia article discussing projective texture mapping, which is precisely what we want to do, but it is spoken about in terms of graphics processing. I mean, graphics processors. No math or anything, just pipelines. https://en.wikipedia.org/wiki/Projective_texture_mapping

Wikipedia says that "projective transformation" is another way to talk about "homography." https://en.wikipedia.org/wiki/Homography

That same wiki entry has some very arcane mathematics which is sadly lacking examples. https://en.wikipedia.org/wiki/Homography#Definition_and_expression_in_homogeneous_coordinates

Now that we know "homography", let's see how homography has been implemented!

Here's some code (in Action Script 3) that converts a homography (defined as a 3x3 matrix) into a rotation matrix and translation vector. The rotation matrix and translation vector are concepts I understand and know how to apply to graphical programming. https://gist.github.com/inspirit/740979

Related comment about how to decompose a given homography into rotation, translation, and also shear. http://stackoverflow.com/questions/15420693/how-to-get-rotation-translation-shear-from-a-3x3-homography-matrix-in-c-sharp

That above question forwards on to a mathematical answer which I can finally understand, but of course I haven't learned anything more about the original homography matrix. http://math.stackexchange.com/questions/78137/decomposition-of-a-nonsquare-affine-matrix

It seems like each person referring to a homography matrix either "has one" or "found one", but I can't any information about where the matrix comes from.

Given the mathematics, homography can be represented by rotation and translation (and maybe shear). Here's a page explaining some of the mathematics using computer science language. (Coincidentally I went to school at mtu.edu). http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/geometry/geo-tran.html

Oh hey, I just saw that the page above actually discusses projective transformations in a helpful way! I missed that when I first posted this comment, but I have edited the comment. Check this out: http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/geometry/geo-tran.html#projective

That page says clearly and directly that projective transforms are more general than affine transformations. So maybe we cannot truly represent a projective transform with only affine transformations.

At some point maybe Jeff will hop into this conversation and tell us where to look to find how four points chosen on an image relate to the matrices we are learning about.

Reply to this comment...


I suppose I could go read the source code. I suppose I should go read the source code.

All the math is right there. Maybe there will be comments!

Reply to this comment...


That's true - projective distortion cannot be achieved with an affine transformation.

The existing Cartagen/MapKnitter 1.0 code is just a wrapper around some existing code (using that matrix class) which I convinced someone to open source (the guy you found, Bryan). You can probably just clip that code out of Cartagen and hook it up to a Leaflet 4-sided poly.

https://github.com/publiclab/mapknitter/tree/master/public/cartagen/src/warper/

Here I call "update()": https://github.com/publiclab/mapknitter/blob/master/public/cartagen/src/warper/image.js#L109

This sets up the polygon and starts the recursive "divide" code: https://github.com/publiclab/mapknitter/blob/master/public/cartagen/src/warper/image.js#L344

The "divide" function: https://github.com/publiclab/mapknitter/blob/master/public/cartagen/src/warper/image.js#L399

Actually drawing the image for the subdivided patch: https://github.com/publiclab/mapknitter/blob/master/public/cartagen/src/warper/image.js#L514

Reply to this comment...


This subdividing is "shoehorning" a projective distortion into a system (canvas) that only has scale, transform, and rotate. Bryan, maybe here's not a bad place to paste in some selections from our epic email thread...

Reply to this comment...


The divide function is the real meat and potatoes of the image warping. The Warper library is certainly helpful.

A quick mathematical review of what Warper does for us. It creates a mapping from homogenous coordinates (used to simplify projective transform calculations) to cartesian coordinates (the x and y of the original image). The homogenous coordinates are defined on the "unit square" for the mathematics implemented in divide, and the homogenous coefficient w is set to 1 in all cases.

The divide function breaks down the large image into smaller subimages. The subimages are broken down further until a very small rectangular selection is chosen. An affine transform of that small section is performed using graphics libraries (Canvas in this case). Although each maximally divided piece of the image has an affine transform, when the pieces are put together, the result approximates a discretized projective distortion.

This comment is a summary of what Anish and I came to realize after looking over the maths together. Maybe it will help others.

Anish and I agree that the Warper library needs more documentation.

Reply to this comment...


Hi, Bryan - thanks for the post. Much of the original warp function was copied in from a web demo, and it took me a while (way back when) to decipher it. I agree it could use more documentation -- perhaps a few code comments could be part of Anish's work in porting it?

Thanks!

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

Reply to this comment...


Login to comment.