Mapping Irregular Quadrilateral to a Rectangle

Question

I have a camera looking at a computer monitor from varying angles. Since the camera is a grid of pixels, I can define the bounds of the monitor in the camera image as:

I hope that makes sense. What I want to do is come up with an algorithm to translate points within this shape to this:

I have points within the same domain as ABCD, as determined from the camera, but I need to draw these points in the domain of the monitor's resolution.

Does that makes sense? Any ideas?

Answer 1

In general there is no affine transformation that maps an arbitrary quadrangle onto a rectangle. But there is (exactly one) projective transformation $T$ that maps a given quadrangle $(A, B, C, D)$ in the projective plane onto a given quadrangle $(A', B', C' D')$ in the same or another projective plane. This $T$ is ${\it collinear}$, i.e., it maps lines to lines. To do the calculations you have to introduce homogeneous coordinates $(x,y,z)$ such that $D=(0,0,1)$, $C=(1,0,1)$, $A=(0,1,1)$, $B=(1,1,1)$ and similarly for $A'$, $B'$, $C'$, $D'$. With respect to these coordinates the map $T$ is linear and its matrix is the identity matrix.

Answer 2

I've been wrestling with a very similar problem in order to determine gradients in an irregular quad grid and needing to map points within arbitrary quadrilaterals to a unit square. In addition, I require the inverse mapping of the x and y axis at the mapped normalized coordinate location back into the quad so I can determine the orientation of the quad grid at that point. i.e. if [x',y'] are the transformed coordinates, I need to be able to do an inverse transform on [0,y'],[1,y'] and [x',0],[x',1]. Here is what I've come up with:

You can divide the quad into two tris, and use affine maps on these individually. This is not difficult. This will create a noticable effect at the division between the two tris, however.

If you want a smooth mapping from a quad to a square (or rectangle), you need to use a non-affine transform such as a projective transform. There are other transforms other than projective that will also work, and also be colinear (preserve straight lines).

If [x1,y1],[x2,y2],[x3,y3],[x4,y4] are the four points in the quad, then the 4x4 matrix B in the the following will yield a mapping into the square (on the RHS) that seems to work and may be easier to compute than the proper 3x3 projective matrix.

%     [x1 y1 x1*y1 1]              [0 0 0 1]
%     [x2 y2 x2*y2 1]   X  B  =    [1 0 0 1]
%     [x3 y3 x3*y3 1]              [0 1 0 1]
%     [x4 y4 x4*y4 1]              [1 1 1 1]

The question I have is that if one does this, and then wants to use the inverse of B to do the inverse transform, how do you calculate the third elements of the location vectors for the orthogonal coordinates. (They are no longer x*y.)

NOTE: If you want to map into any other (arbitrary) quadrilateral (such as a rectangle), then just replace the RHS of what I have above with the new coordinates.

%     [x1 y1 x1*y1 1]              [x1' y1' x1'*y1' 1]
%     [x2 y2 x2*y2 1]   X  B  =    [x2' y2' x2'*y2' 1]
%     [x3 y3 x3*y3 1]              [x3' y3' x3'*y3' 1]
%     [x4 y4 x4*y4 1]              [x4' y4' x4'*y4' 1]

Answer 3

Try this solution, it worked for me.

Answer 4

The best solution I've found so far on a forum lost in the sea of forums is to decompose your problem like this :

From $P0$, $P1$, $P2$ & $P3$ we can easily compute the normalized normal vectors $N0$, $N1$, $N2$ & $N3$. Then, it's easy to see that : $$u = \frac{dU0}{dU0 + dU1} = \frac{(P-P0) \cdot N0}{(P-P0).N0 + (P-P2) \cdot N2} \\ v = \frac{dV0}{dV0 + dV1} = \frac{(P-P0) \cdot N1}{(P-P0).N1 + (P-P2) \cdot N3}.$$

This parametrization works like a charm and is really easy to compute within a shader for example. What's tricky is the reverse: finding $P(x,y)$ from $(u,v)$ so here is the result:

$$x = \frac{vKH \cdot uFC - vLI \cdot uEB}{vJG \cdot uEB - vKH \cdot uDA}, \\ y = \frac{vLI \cdot uDA - uFC \cdot vJG}{vJG \cdot uEB - vKH \cdot uDA},$$

where: $$uDA = u \cdot (D-A), \quad uEB = u \cdot (E-B), \quad uFC = u \cdot (F-C), \\ vJG = v \cdot (J-G), \quad vKH = v \cdot (K-H), \quad vJG = v \cdot (J-G),$$

and finally: $$A = N0_x, \qquad \qquad B = N0_y, \quad C = -P0 \cdot N0, \qquad \\ D = N0_x + N2_x, \quad E = N0_y + N2_y, \quad F = -P0 \cdot N0 - P2 \cdot N2, \\ G = N1_x, \qquad \qquad H = N1_y, \quad I = -P0 \cdot N1, \qquad \\ J = N1_x + N3_x, \quad K = N1_y + N3_y, \quad L = -P0 \cdot N1 - P2 \cdot N3.$$

I've been using this successfully for shadow mapping of a deformed camera frustum mapped into a regular square texture and I can assure you it's working great! :D

Answer 5

Take a look on Gernot Hoffmann's tutorial on image rectification. There are also the special cases (rectangle to quadrilateral) explained.

Another page that helped me discusses 2D perspective transformation (i.e. planar homography).

For a deep understanding of the topic and more numerically stable algorithms, I can only recommend Hartley & Zisserman: Multi-View Geometry in Computer Vision.