Transform that maps points from any quad to an reactangle

[Estanho]

Hello,
This question might seem silly, but I've tried some approaches and none of them seemed to work.
Here's my problem:
I need some sort of transform that maps points from any quad to an rectangle. I will be using this on a computer graphics software, so you can think of this rectangle as my viewport or something like that.
Below is an image to illustrate the problem:

The points 1, 2, 3 and 4, and the w and h values are parameters. The point P is the input, and I'd like to know P'. The point 1 should map to (0,0), the point 2 should map to (w,0) and so on...
Sorry if this is confusing. Please tell me if you need more information.

As I said, I've tried several approaches. The first one is to use the most basic matrix transform:
<br /> \left( \begin{array}{c} x&#039; \\ y&#039; \end{array} \right) =<br /> \left( \begin{array}{cc} a &amp; b\\ c &amp; d \end{array} \right)<br /> \left( \begin{array}{c} x \\ y \end{array} \right)<br />
Where x' and y' would be the coordinates of the output point P', and x and y would be the input point P.
Obviously this would never work (I think), because I have 4 points (1, 2, 3, 4) that should be considered, and therefore I have to build a system with all of them. That would give me 8 equations and 4 unknowns (a, b, c, d), which I believe implies that I need more degrees of freedom.

So I've tried something like that:
<br /> \left( \begin{array}{c} x&#039; \\ y&#039; \end{array} \right) =<br /> \left( \begin{array}{cc} a &amp; b\\ c &amp; d \end{array} \right)<br /> \left( \begin{array}{cc} e &amp; f\\ g &amp; h \end{array} \right)<br /> \left( \begin{array}{c} x \\ y \end{array} \right)<br />
Which actually gives me 8 equations and 8 unknowns. So I tried building my system.
I've considered that these are the values for points 1, 2, 3, 4:
<br /> P_1 = (k,l);<br /> P_2 = (m,n);<br /> P_3 = (o, p);<br /> P_4 = (q, r);<br />

Which, by multiplying on the previous equation, led me to these equations:
<br /> (a*e + b*g)*k + (a*f + b*h)*l = 0 \\<br /> (c*e + d*g)*k + (c*f + d*h)*l = 0 \\<br /> (a*e + b*g)*m + (a*f + b*h)*n = w \\<br /> (c*e + d*g)*m + (c*f + d*h)*n = 0 \\<br /> (a*e + b*g)*o + (a*f + b*h)*p = 0 \\<br /> (c*e + d*g)*o + (c*f + d*h)*p = h \\<br /> (a*e + b*g)*q + (a*f + b*h)*r = w \\<br /> (c*e + d*g)*q + (c*f + d*h)*r = h<br />
The first two represents the point 1, which maps to (0,0), the second one represents point 2, which maps to (w,0), and so on.
But when I input this in Mathematica or Matlab, I get no solutions:

in := Solve[(a*e+b*g)*k+(a*f+b*h)*l==0&&(c*e+d*g)*k+(c*f+d*h)*l==0&&(a*e+b*g)*m+(a*f+b*h)*n==w&&(c*e+d*g)*m+(c*f+d*h)*n==0&&(a*e+b*g)*o+(a*f+b*h)*p==0&&(c*e+d*g)*o+(c*f+d*h)*p==h&&(a*e+b*g)*q+(a*f+b*h)*r==w&&(c*e+d*g)*q+(c*f+d*h)*r==h,{a,b,c,d,e,f,g,h}]

out = {}

>> syms a b c d e f g h k l m n o p q r w h;

>> S = solve(...
'(a*e + b*g)*k + (a*f + b*h)*l = 0',...
'(c*e + d*g)*k + (c*f + d*h)*l = 0',...
'(a*e + b*g)*m + (a*f + b*h)*n = w',...
'(c*e + d*g)*m + (c*f + d*h)*n = 0',...
'(a*e + b*g)*o + (a*f + b*h)*p = 0',...
'(c*e + d*g)*o + (c*f + d*h)*p = h',...
'(a*e + b*g)*q + (a*f + b*h)*r = w',...
'(c*e + d*g)*q + (c*f + d*h)*r = h', a, b, c, d, e, f, g, h);

Warning: Explicit solution could not be found.
> In solve at 179

What is wrong with my approach?
Can someone tell me some way to solve this?

Thanks.

 

[andrewkirk]

Why do you want to map between a rectangle and an arbitrary quadrilateral for graphics? The most dramatic transformation I can think of for graphics is from rectangle to trapezium, which has two parallel sides. The loss of parallelism of the other two sides comes from perspective.

I imagine there is a natural way to map from rectangle to trapezium, that uses the laws of perspective. It should not be too hard to work that out. There is no natural way to map a rectangle to an arbitrary quadrilateral. There may be multiple ways possible, that would provide different answers.

 

[Estanho]

Why do you want to map between a rectangle and an arbitrary quadrilateral for graphics? The most dramatic transformation I can think of for graphics is from rectangle to trapezium, which has two parallel sides. The loss of parallelism of the other two sides comes from perspective.

I imagine there is a natural way to map from rectangle to trapezium, that uses the laws of perspective. It should not be too hard to work that out. There is no natural way to map a rectangle to an arbitrary quadrilateral. There may be multiple ways possible, that would provide different answers.

Hi, thanks for your answer.
Yes, this problem is about perspective, but not the way you're thinking (or maybe I'm wrong).
To make things more clear, this problem is going to be used on a computer vision technique. I want to be able to map pixels from a projection (edit: NOT EVERY PIXEL, just one point at a time. I don't want to obtain an undistorted image from the camera, I want to obtain a mapping from the camera to screen coordinates), obtained from a camera, into an actual viewport. Here is an example of an image obtained of a projection by a camera:

The image projector may not be perpendicular to the white screen, which would generate images with different perspectives. Also, the camera may be in any position, capturing the image. As you can see, the outline has no parallel sides:

 

[andrewkirk]

OK, that makes sense. Note that this is not just 'any quad' but a very particular one that is defined by the laws of perspective. Amongst other things it excludes concave quads. Your picture suggests a nice natural way of doing the mapping.

The quadrilateral is the intersection of the spaces between two pairs of rays, where the members of each pair meet at infinity in the distance. Those two infinite points can be given coordinates in the flat screen frame - which will probably be off the screen, but that doesn't matter. Using those two 'infinity' points as centres for measuring angles enables us to define a natural coordinate system for the quadrilateral.

First, using a Cartesian coordinate system for the screen, get the equations of the lines in which the quad's four sides lie. Then find the screen co-ords of the two points at which the lines from opposite sides intersect, call them O(1) and O(2). They wil probably be off the screen, but that doesn't matter. Call the one that is first in an anticlockwise direction from the top left corner of the screen O(1). Each has two diverging rays emanating from it that pass through two opposite sides of the quad. Let t(i) be the angle between the two rays of O(i) that sweeps out the quad. It will be less than 180 degrees.
Let l(i,1) label the first and l(i,2) the second of the two rays from O(i) when we sweep out the quad from O(i) moving in an anticlockwise direction.

Now we can give coordinates for every point in the quad. For every point P in the quad, define its 'angle coordinates' as (a(1),a(2)) such that a(i) is the angle that O(i)P makes with O(i)l(i,1).

Now we just map the point with angle coordinates (a(1),a(2)) to (L(1)*a(1)/t(1), L(2)*a(2)/t(2) ) in a Cartesian coordinate system for the rectangle where L(1) is the true length of the rectangle side that is first encountered by the rays from O(2) and L(2) is the true length of the rectangle side that is first encountered by the rays from O(1) and the direction of the two coordinate axes for the rectangle corresponds with the direction of the angle coordinates for the quad. Note that this coordinate system may not be the same as the one in your diagram above.

I think the mathematical manipulation for this will be quite straightforward, and may not even need matrices.

 

[andrewkirk]

Addendum. If a pair of sides of the quad is parallel, a point of convergence O(i) at infinity will not exist, so we modify the approach by replacing L(i)*a(i)/t(i) by d(i) where L(i)*d(i)/M(i) is the distance of the point from the lower of the two sides (or the leftmost, if the sides are vertical) and M(i) is the distance between the two sides in the quad.

This can happen for one or two pairs of sides, but if it happens for both, the quad will already be a rectangle, so no transformation is needed (I'm pretty sure there's no way one can get a parallelogram shape from a rectangle via perspective).