11

Say you have a collection of points with coordinates on a Cartesian coordinate system.

an unwarped grid

You want to plot another point, and you know its coordinates in the same Cartesian coordinate system.

However, the plot you're drawing on is distorted from the original. Imagine taking the original plane, printing it on a rubber sheet, and stretching it in some places and pinching it in others, in an asymmetrical way (no overlapping or anything complex).

a warped grid (source)

You know the stretched and unstretched coordinates of each of your set of points, but not the underlying stretch function. You know the unstretched coordinates of a new point.

How can you estimate where to plot the new point in the stretched coordinates based on the stretched positions of nearby points? It doesn't need to be exact, since you can't determine the actual stretch function from a set of remapped points unless you have more information.

other possible keywords: warped distorted grid mesh plane coordinate unwarp

endolith
  • 25,479
  • 34
  • 128
  • 192

4 Answers4

5

Ok, so this sounds like image warping. This is what you should do:

  1. Create a Delaunay triangulation of your unwarped grid and use your knowledge of the correspondences between the warped and unwarped grid to create the triangulation for the warped grid. Now you know the corresponding triangles in each image and since there is no overlapping, you should be able to perform the next step without much difficulty.

  2. Now, to find the corresponding point A, in the warped image:

    1. Find the triangle A lies in and use the transformation between the triangle in the unwarped grid and the warped grid to figure out the new position.

This is explained explicitly in detail here.

Another (much more complicated) method is the Thin Plate Spline (which is also explained in the slides above).

Kartik Madhira
  • 23
  • 1
  • 8
Jacob
  • 34,255
  • 14
  • 110
  • 165
  • This method is most like what I was visualizing. – endolith Oct 21 '09 at 17:41
  • 1
    There is no one-to-one correspondence between the Delauay triangles of the unwrapped and wrapped grid points. Actually already the regular grid has no unique Delaunay triangulation and even if it would have, the deformation might induce flips for certain edges... – balint.miklos Oct 22 '09 at 01:34
  • 2
    There is a one-to-one correspondence since the OP knows this in advance. Since this correspondence is already known, and there is no overlapping during the warping (as per the OP) then any Delaunay triangulation on the unwarped grid can be used for the warped grid and thus corresponding triangles can be found. – Jacob Oct 22 '09 at 02:55
  • 1
    There is one-to-one correspondence between the vertices, but not between the two Delaunay triangulations. See the example here: http://img8.imageshack.us/i/counternn.png/ These are the two Delaunay triangulations and the colors represent the correspondence between the vertices. There is no triangle between the red-green-blue vertices on the right side because of the deformation. This is why I proposed in my solution to compute only one Delaunay triangulation and deduce the other triangulation based on the vertex correspondence. – balint.miklos Oct 22 '09 at 22:42
  • 1
    I see what you mean now. The approach proposed in my comment to you and my original answer is different and I'll change that - thanks. – Jacob Oct 23 '09 at 00:53
  • now you changed it such that is exactly the solution I described :) – balint.miklos Oct 23 '09 at 02:00
  • sorry, actually, it is slightly different, you compute the Delaunay of the unwrapped grid, I do it for the wrapped... if the unwrapped grid is really a uniform grid your solution has worse quality of approximation. You compute the Delaunay triangulation of a regular grid and don't take into account what the deformation is for the triangulation therefore you will have skinnier triangles than in my solution which leads to less pleasant interpolation. Actually one choses Delaunay because one wants nice triangles otherwise one could just take any triangulation. – balint.miklos Oct 23 '09 at 02:26
  • You could use any triangulation, but Delaunay is easily usable in packages like MATLAB. – Jacob Oct 23 '09 at 02:59
  • As far as the deformation is concerned, it is **better** to use the triangulation on the unwarped grid because (as you said) skinny triangles will not be chosen in the warped grid and therefore, the triangles formed in the unwarped grid may contain other triangles making the mapping very difficult. Of course, all this is only valid if there is no overlap. – Jacob Oct 23 '09 at 03:00
  • **You are wrong**. The Delaunay triangles maximize the minimum angle of all existing triangulations. Therefore if you compute it on the wrapped grid you insure that the wrapped triangulation is the best possible. Then the unwrapped (as long as it is regular grid) will be some diagonals added to every square. If you do it the other way around, the Delaunay on the unwrapped will be again some diagonals, but the wrapped has no guarantee. Your method would chose red-greed diagonal, mine the blue purple in this image: http://img8.imageshack.us/i/counternn.png – balint.miklos Oct 23 '09 at 03:36
  • I can't see your image. Also, it's beside the point since if you use the triangulation on the warped grid will have no guarantee on the unwarped grid that triangles *will not overlap* - and this is very important. – Jacob Oct 23 '09 at 04:59
  • It's the same image like in my previous comment. And if the deformation is large no matter which grid you triangulate with Delauna you can get get overlapping triangles in the other domain if you just construct the corresponding triangles. From that point of view i don't think it makes any difference which point set you triangulate with Delaunay. – balint.miklos Oct 23 '09 at 07:56
  • My application isn't actually a grid. It's just a collection of random points. – endolith Oct 28 '09 at 04:09
  • Which I think means the Delaunay won't necessarily be the same for warped and unwarped? – endolith Oct 28 '09 at 04:10
  • 1
    Do you know the mapping between the warped and unwarped points? – Jacob Oct 28 '09 at 04:14
  • 1
    If you compute the Delaunay of the two point sets (wrapped and unwrapped) there won't be necessarily a correspondence between triangles. Could you give an idea of what is the tipical input? How many points, how densely sample the area of interest and how strong is the deformation you have typically? – balint.miklos Oct 28 '09 at 08:22
  • Yeah, I know which points map to which, and I can tweak the triangles by hand if necessary. The main question is how to map the contents of one region to the corresponding region in the warped output, which you've both answered: Form a triangulation on the known points and then map additional points using barycentric coordinates. – endolith Nov 11 '09 at 19:37
2

I understood that you have one-to-one correspondence between the wrapped and unwrapped grid points. And I assume that the deformation is not so extreme that you might have intersecting grid lines (like the image you show).

The strategy is exactly what Jacob suggests: Triangulate the two grids such that there is a one-to-one correspondence between triangles, locate the point to be mapped in the triangulation and then use barycentric coordinates in the corresponding triangle to compute the new point location.

Preprocess

  1. Generate the Delaunay triangulation of the points of the wrapped grid, let's call it WT.
  2. For every triangle in WT add a triangle between the corresponding vertices in the unwrapped grid. This gives a triangulation UWT of the unwrapped points.

Map a point p into the wrapped grid

  1. Find the triangle T(p1,p2,p3) in the UWT which contains p.
  2. Compute the barycentric coordinates (b1,b2,b3) of p in T(p1,p2,p3)
  3. Let Tw(q1,q2,q3) be the triangle in WT corresponding to T(p1,p2,p3). The new position is
    b1 * q1 + b2 * q2 + b3 * q3.

Remarks This gives a deformation function as a linear spline. For smoother behavior one could use the same triangulation but do higher order approximation which would lead to a bit more complicated computation instead of the barycentric coordinates.

balint.miklos
  • 1,867
  • 1
  • 19
  • 23
  • I like that you included the details here instead of just linking to a long external document, but this otherwise seems identical to Jacob's answer, which was first. – endolith Oct 28 '09 at 04:09
  • The details which Jacob missed and I brought up in the comments make a significant difference if one starts implementing such methods... but I know that on the first read it seems pretty much the same. I decided to write a separate answer because his description was rather confusing and I couldn't improve his solution (I do not have enough reputation) – balint.miklos Oct 28 '09 at 08:20
2

The other answers are great. The only thing I'd add is that you might want to take a look at Free form deformation as a way of describing the deformations.

If that's useful, then it's quite possible to fit a deformation grid/lattice to your known pairs, and then you have a very fast method of deforming future points.

tfinniga
  • 6,693
  • 3
  • 32
  • 37
0

A lot depends on how many existing points you have. If you have only one, there's not really much you can do with it -- you can offset the second point by the same amount in the same direction, but you don't have enough data to really do any better than that.

If you have a fair number of existing points, you can do a surface fit through those points, and use that to approximate the proper position of the new point. Given N points, you can always get a perfect fit using an order N polynomial, but you rarely want to do that -- instead, you usually guess that the stretch function is a fairly low-order function (e.g. quadratic or cubic) and fit a surface to the points on that basis. You then place your new point based on the function for your fitted surface.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111