locating a point in a 2d image that was warped

Question

I have an original image that has been "warped". Can someone help me with the math to calculate where a given point from the original image would show up in the warped one?

I have an image with a rectangle inside of it. I know where, in the flat image the points A, B, C, D, E and F are.

+------------------------------------------------+
|                                                |
|          A                     B               |
|           +-------------------+                |
|           |                   |                |
|           |     •F            |                |
|           |                   |                |
|           |                   |                |
|           |                   |                |
|           |    •E             |                |
|           +-------------------+                |
|          C                     D               |
|                                                |
+------------------------------------------------+

The new image (A') was create due to an imperfect setup of a camera, which has warped the image. I now have A',B',C'D',E',F'.

I don't necessarily want to "unwarp" the image, I just want the coordinates in the new coordinate space, where the point has ended up. Given that I know where A, B, C, D, E, F, A', B', C', D' and E' (in their respective image), is that enough information to simply calculate where the new E' point should be in the image?

I feel that this is a 3D matrix transformation, but the math is beyond me and I'm trying to figure out the equations that would just solve for (E')s new coordinates. I guess technically this is a 2D object that was projected through 3D space onto a 2D surface.

+------------------------------------------------+
|                                                |
|         A'                                     |
|          +---------            B'              |
|           |        -----------+                |
|           |                   |                |
|           |     •F'            |               |
|            |                   |               |
|            |                    |              |
|            |                    |              |
|            |    •E'             |              |
|             |            -------+              |
|             +------------        D'            |
|            C'                                  |
|                                                |
+------------------------------------------------+

If I need to add another point (G and G'), in order to solve for E', I could add it.

What I've been able to understand is that this would be solving a series of simultaneous equations, but I'm not sure how many "knowns" are needed to solve for E'(x,y).

I'm doing this in iOS (Objective C), but I'm not so concerned with the actual coding, I'm really just trying to find the solution matrix (if that is the right term).

Answer 1

This transformation (2D to 2D with a perspective effect) is a so-called homography, which can be described with 8 coefficients (a to h):

X = (a.x + b.y + c) / (g.x + h.y + 1)
Y = (d.x + e.y + f) / (g.x + h.y + 1)

You can easily linearize these equations as:

a.x + b.y + c                 - g.x.X - h.y.X = X
                d.x + e.y + f - g.x.Y - h.y.Y = Y

You solve them by taking four points (the four corners), which give you eight equations in eight unknowns, and from there you can transform any new point.

As the inverse of an homography is also an homography, you can apply this resolution in two ways (upright to distorted or conversely). Make sure that the unknown coordinates that you are looking for appear as (X, Y) (rather than (x, y)) in the above developments.

Answer 2

You need perspective transformations.

There is implementation of perspective transformations (mapping of arbitrary convex quad to rectangle and vice versa) in Anti-Grain Geometry library (exe example).

With agg_trans_perspective you can calculate the matrix of perspective transformation (using your points A, B, C, D, A', B', C', D') and then apply it to map coordinates from one quad to another (E to E' or E' to E).