Image Remapping Algorithm

Question

Hi all,

I have been developing (for the last 3 hours) a small project I'm doing in C# to help me choose a home.

Specifically, I am putting crime statistics in an overlay on Google maps, to find a nice neighborhood.

Here is an example: http://otac0n.com/Demos/prospects.html

Now, I manually found the Lat and Lng to match the corners of the map displated in the example, but I have a few more maps to overlay.

My new application allows me to choose a landmark and point at the image to tie the Pixel to a LatLng. Something like:

locations.Add(new LocationPoint(37.6790f, -97.3125f, "Kellogg and I-135"));

// and later...

targetPoint.Pixel = FindPixel(mouseEvent.Location);

So, I've gathered a list of pixel/latlng combinations, and now would like to transform the image (using affine or non-affine transformations).

The goal here is to make every street line up. Given a good map, the only necessary transformation would be a rotation to line the map up north-to-south (and for now I would be happy with that). But I'm not sure where to start.

Does anybody have any experience doing image transformations in C#? How would I find the proper rotation to make the map level?

After the case of well-made maps is resolved, I would eventually like to be able to overlay hand drawn maps. This would obviously entail heavy distortion of the final image, and may be beyond the scope of this first iteration. However, I would not like to develop a system that would be un-expandable to this system in the future.

Answer 1

In 2D space affine transformation can be specified by two sets of three nonlinear 2D points. In C# you can use the following routine to compute appropriate Matrix:

 public static Matrix fit(PointF[] src, PointF[] dst) {
  Matrix m1 = new Matrix(new RectangleF(0, 0, 1, 1), src);
  m1.Invert();
  Matrix m2 = new Matrix(new RectangleF(0, 0, 1, 1), dst);
  m2.Multiply(m1);
  return m2;
 }

It works for both array arguments having 3 elements.

If you only need rotation and translation, then you can use the following routine:

 public static Matrix fitOrt(PointF src1, PointF src2, PointF dst1, PointF dst2) {
  return fit(new PointF[] { src1, src2, ort(src1, src2) },
    new PointF[] { dst1, dst2, ort(dst1, dst2) });
 }

 public static PointF ort(PointF p, PointF q) {
  return new PointF(p.X + q.Y - p.Y, p.Y - q.X + p.X);
 }

If you would like to find the best approximation between two sets of multiple points then you can start with this http://elonen.iki.fi/code/misc-notes/affine-fit/

Answer 2

I'm unsure of what exactly do you want to accomplish, but if you want to fit more than three points on one map to more than three points on another one, there are basically two ways you can go:

1. You could try to create a triangular mesh over your points, and then apply a different affine transformation within each triangle, and get a piecewise linear transformation. To get the meshing right, you'll probably need to do something like a Delaunay triangulation of the points, for which qhull should probably be your preferred option.
2. You can go for a higher order transform, such as quad distortion, but it will probably be hard to find a solution that works for any number of points in a generic position. Find yourself a good finite element method book, and read the chapter(s) on higher order isoparametric elements, either lagrangian or serendipity ones, which will provide you with well-behaved mappings of many point to many points. Here are a couple of links(1 and 2) to set you on your way. But be aware that the math content is intensive...

Answer 3

Beautiful.

So, thanks To Jamie's direction, I have found this:

Delaunay Triangulation in .NET 2.0

http://local.wasp.uwa.edu.au/~pbourke/papers/triangulate/morten.html

At this point, this is pretty much simplified to lerping.