Transform arbitrary quadrangle into unit square

Can't always be done. Not all quads can be transformed by an affine transformation to a unit square. In fact, only parallelograms can...

Of course, here I'm assuming you want to map a 2d quad to a 2d square. Do you actually want to infer perspective or something? Then you have more degrees of freedom...

The perspective mapping between two *convex* quadrilaterals is described in this 1-page document: Perspective Mapping.

Quote:

Original post by Emergent Can't always be done. Not all quads can be transformed by an affine transformation to a unit square. In fact, only parallelograms can... Of course, here I'm assuming you want to map a 2d quad to a 2d square. Do you actually want to infer perspective or something? Then you have more degrees of freedom...

You assume correctly. :) A 3D quadrangle polygon has been transformed to the world center and 'placed' on the X-Z plane so that its y-values are 0.0f (essentially a 2D quadrangle). Now I want to matrix transform it to a unit square (on the same plane) for operations on geometry being placed on its surface (the geometry would be inverse transformed to fit the original quadrangle after the operations). I expect the polygon to be planar and convex (from polygonization by the supporting application).

Code from Qt (QTransform::quadToSquare) is the type of transformation I think that I'm seeking but I cannot make it work (for hours!). It is using a 2D transform whereas I am limited to 3D transform matrices with an assumed (0,0,0,1) homogeneous vector. Their projective transform looks to be setting the homogeneous vector to (g, h, 1). I'm in the process of testing a self-made 2D transform using this code but am still a bit wary of the results.

Thanks!

Quote:

Original post by Dave Eberly The perspective mapping between two *convex* quadrilaterals is described in this 1-page document: Perspective Mapping.

How would this relate to matrix transformation? As I stated, this must go both ways with an inversion of the quad-to-unitsquare after some processing.

Thanks!

Yes, there is a projective transformation (or homography) that will map your quadrilateral to a square. Notice that it will map homogeneous coordinates to homogeneous coordinates, so you may want to divide by the third coordinate at the end.

I can think of two ways to proceed:
1) Write the whole thing as a system of linear equations: 12 equations with 13 variables (you get an extra level of freedom because all scalings of the matrix represent the same homography). [EDIT: If I do it differently I get 8 equations with 9 variables directly: See section 2.1 here.]
2) Find the line that will be mapped to infinity first, and then find an affine transformation that will finish the job. You can see some details here: http://www.robots.ox.ac.uk/~vgg/publications/papers/liebowitz98.pdf

Quote:

Original post by Kuroyume0161 Quote: Original post by Dave Eberly The perspective mapping between two *convex* quadrilaterals is described in this 1-page document: Perspective Mapping. How would this relate to matrix transformation? As I stated, this must go both ways with an inversion of the quad-to-unitsquare after some processing. Thanks!

So write the equations using a homogeneous matrix. You still need to do the perspective divide (the denominators of the expression in the paper are your w-terms). The equations have (u,v) as functions of (x,y). The algebra to invert and solve for (x,y) as functions of (u,v) is straightforward, and this may also be written using a homogeneous matrix.

Quote:

Original post by Kuroyume0161 You assume correctly. :) A 3D quadrangle polygon has been transformed to the world center and 'placed' on the X-Z plane so that its y-values are 0.0f (essentially a 2D quadrangle). Now I want to matrix transform it to a unit square (on the same plane)

Perhaps I'm missing something, but I'm not sure that the posts about perspective are really on-topic... What you're talking about is entirely a 2d problem, right?

[EDIT: Indeed I was missing something! I needed to read up on homographies. I won't take this post down because it's not completely useless, but I think the homography method is better.]

Then, as I said, what you're describing is exactly the case that you can't do with a single affine transformation, unless the quad that you start with is a parallelogram. However, it also sounds like you'd be happy with any reasonable homeomorphism from 2d to 2d (more precisely: R^2 to R^2) that maps the edges of your quad to the edges of a unit square and "looks nice" in-between, right?

If that's the case, you could do it with a piecewise affine transformation by splitting your quad into a two triangles. Let's say you have a quad with vertices (u1,v2),...,(u4,v4), split down a diagonal to make two triangles, 'A' and 'B,' as shown below (note that although I've drawn it as a rectangle it needn't be):

(u1,v1)------(u2,v2)  | .       B   |  |      .      |  |  A        . |(u3, v3)-----(u4,v4)

Then to all points in triangle A you can perform the affine transformation

(x,y) |--> Ma^-1 ((x,y)-(u3,v3)) + (u3, v3)

where Ma is the matrix [(u4,v4)-(u3,v3) , (u1,v1)-(u3,v3)]. By this I mean that the vector (u4,v4)-(u3,v3) is its first column, etc. And to all points in triangle B you can perform the transformation

(x,y) |--> Mb^-1 ((x,y)-(u2,v2)) + (u2, v2)

where Mb is the matrix [(u2,v2)-(u1,v1) , (u2,v2)-(u4,v4)].

(About notation: My "|-->" notation means "maps to." So "|-->" is an infix operator that returns a function. For instance, the expression "x |--> x^2" evaluates to "the function that squares its argument." So it's kind of like 'lambda' in LISP.)

Hope that helps.

[Edited by - Emergent on July 1, 2009 9:12:20 AM]

Apologies... I wasn't familiar enough with homographies, so my whole previous post may be pointless. alvaro: I haven't thought about this much; can a homography map between any two quads in R^2? Are there any restrictions on the types of quads that can be mapped to each other?

[Edited by - Emergent on June 30, 2009 10:26:55 PM]

Already found a solution. Homography transforms was the correct direction - then on to collineation matrices and warps.

Yes, this is a 2D problem. And code exists everywhere - if you only know what the heck you're trying to find! It shows up a lot in scanner/projector/image correction and manipulation sources. This link code works absolutely perfectly (even on triangles!!! - if you treat it as a quad with two identical points - which is what I actually want to do).

http://code.google.com/p/wiimotetuio/source/browse/trunk/WiimoteTUIO/Warper.cs

The projective transform (or affine in limited cases) was only one part of the puzzle. To do this correctly every time, it needs to be a properly inverted matrix from unit-square to quad that then does quad to unit-square (through the inversion). And the matrix multiplication of the points was not a simple transform matrix operation (as this isn't a transform matrix and 'w' is not always (0,0,1)). Once I understood the process and stopped evaluating the crappy incorrect code out there, proper code was found.

Quote:

Original post by Emergent Apologies... I wasn't familiar enough with homographies, so my whole previous post may be pointless. alvaro: I haven't thought about this much; can a homography map between any two quads in R^2? Are there any restrictions on the types of quads that can be mapped to each other?

Hmmm... It's been too long since I was comfortable with this subject. You can convert any projective reference into any other projective reference. Projective references in the plane are sets of 4 points such that any 3 are not collinear. It might be the case that the homography will send a line that intersects the quadrilateral to infinity, which might not satisfy your idea of "mapping between two quads". My intuition tells me this would happen when you try to map a convex quad to a non-convex quad, but I am not completely sure.

I wouldn't even try a non-convex quad with the transform being built. Actually, even a triangle with an extra point along one of the sides (to fake a quad) fails the math (which I'll show in code shortly). Therefore the quad must be 'truly' convex (have internal angles less than 180d). A test triangle was working but no longer after some observational corrections so I'm stuck at trying to do the homography from unit square to triangle which might not be possible (ack!).

There will be two directions for the code: aspect-conserving and not. The latter is where the unit-square to quad applies the transformation to associated geometry - which will skew and shear it. The former will simply make sure that the geometry fits within the bounds of the quad without any homography transformation. This will be the case for circular geometries by default to avoid egg-shaped results that would occur in certain transformations.

Triangles have befuddled me here though. One solution, albeit rather contrived, is to simply truncate the triangle (which yields a quad) but this leaves the remaining area empty of geometry.

And the code:

// 2D Matrix for doing collineation between quad and unit-square
class Matrix2D
{
public:
Real m0;
Real m1;
Real m3;
Real m4;
Real m5;
Real m7;
Real m12;
Real m13;
Real m15;
Matrix2D()
{
// Unit Matrix
m0 = 1.0f;
m1 = 0.0f;
m3 = 0.0f;
m4 = 0.0f;
m5 = 1.0f;
m7 = 0.0f;
m12 = 0.0f;
m13 = 0.0f;
m15 = 1.0f;
}
// Copy this matrix to matrix M
void CopyTo(Matrix2D& M)
{
M.m0 = m0;
M.m1 = m1;
M.m3 = m3;
M.m4 = m4;
M.m5 = m5;
M.m7 = m7;
M.m12 = m12;
M.m13 = m13;
M.m15 = m15;
}
// Transform point p by matrix M: q = p*M
friend const Vector operator * (const Vector& p, const Matrix2D& M)
{
Real d = p.x*M.m3 + p.z*M.m7 + M.m15;
if (d) d = 1.0f/d;
else return Vector(0.0f);
Vector q;
q.x = (p.x*M.m0 + p.z*M.m4 + M.m12) * d;
q.z = (p.x*M.m1 + p.z*M.m5 + M.m13) * d;
q.y = p.y;
return q;
}
};

// Calculate matrix for unit-square to quad mapping
// - vertices - square->quad transform
//*---------------------------------------------------------------------------*
Bool GMPThread::SquareToQuad(Real quad[4][2], Matrix2D* SQ)
//*---------------------------------------------------------------------------*
{
Real x0 = quad[0][0];
Real x1 = quad[1][0];
Real x2 = quad[2][0];
Real x3 = quad[3][0];

Real y0 = quad[0][1];
Real y1 = quad[1][1];
Real y2 = quad[2][1];
Real y3 = quad[3][1];

Real dx3 = x0 - x1 + x2 - x3;
Real dy3 = y0 - y1 + y2 - y3;

// afine transform
if (!dx3 && !dy3)
{
SQ->m0 = x1-x0; SQ->m1 = y1-y0; SQ->m3 = 0.0f;
SQ->m4 = x2-x1; SQ->m5 = y2-y1; SQ->m7 = 0.0f;
SQ->m12 = x0; SQ->m13 = y0; SQ->m15 = 1.0f;
}
// projective transform
else
{
Real dx1 = x1 - x2;
Real dx2 = x3 - x2;
Real dy1 = y1 - y2;
Real dy2 = y3 - y2;

// determinants
Real gtop = dx3 * dy2 - dx2 * dy3;
Real htop = dx1 * dy3 - dx3 * dy1;
Real bottom = dx1 * dy2 - dx2 * dy1;

if (!bottom) return FALSE;
bottom = 1.0f / bottom;

Real g = gtop*bottom;
Real h = htop*bottom;

Real a = x1 - x0 + g * x1;
Real b = x3 - x0 + h * x3;
Real d = y1 - y0 + g * y1;
Real e = y3 - y0 + h * y3;

SQ->m0 = a; SQ->m1 = d; SQ->m3 = g;
SQ->m4 = b; SQ->m5 = e; SQ->m7 = h;
SQ->m12 = x0; SQ->m13 = y0; SQ->m15 = 1.0f;
}
return TRUE;
}
// Calculate matrix for quad to unit-square mapping
// - vertices - square->quad transform
//*---------------------------------------------------------------------------*
void GMPThread::QuadToSquare(Real quad[4][2], Matrix2D* SQ)
//*---------------------------------------------------------------------------*
{
if (!SquareToQuad(quad, SQ)) return;

// invert through adjoint
Real a = SQ->m0, d = SQ->m1, g = SQ->m3;
Real b = SQ->m4, e = SQ->m5, h = SQ->m7;
Real c = SQ->m12, f = SQ->m13;

Real A = e - f * h;
Real B = c * h - b;
Real C = b * f - c * e;
Real D = f * g - d;
Real E = a - c * g;
Real F = c * d - a * f;
Real G = d * h - e * g;
Real H = b * g - a * h;
Real I = a * e - b * d;

// Probably unnecessary since 'I' is also scaled by the determinant,
// and 'I' scales the homogeneous coordinate, which, in turn,
// scales the X,Y coordinates.
// Determinant = a * (e - f * h) + b * (f * g - d) + c * (d * h - e * g);
Real idet = 1.0f / (a * A + b * D + c * G);

SQ->m0 = A*idet; SQ->m1 = D*idet; SQ->m3 = G*idet;
SQ->m4 = B*idet; SQ->m5 = E*idet; SQ->m7 = H*idet;
SQ->m12 = C*idet; SQ->m13 = F*idet; SQ->m15 = I*idet;
}

The 2D matrix is about as simple as you can get and, yes, I've been lazy and just retained the pseudo-indices of the matrix elements from those that were removed because they have no impact.

Quote:

Original post by alvaro Hmmm... It's been too long since I was comfortable with this subject. You can convert any projective reference into any other projective reference. Projective references in the plane are sets of 4 points such that any 3 are not collinear. It might be the case that the homography will send a line that intersects the quadrilateral to infinity, which might not satisfy your idea of "mapping between two quads". My intuition tells me this would happen when you try to map a convex quad to a non-convex quad, but I am not completely sure.

That's why I'd asked... Now that I think about it, I'm relatively sure that you can't map between convex and non-convex quads (since the perspective transform preserves convexity).

Sounds like maybe the piecewise-affine method is useful after all (since it sounds like perspective is not inherent to the problem and we're just looking for a "nice" homeomorphism). The homography method has some really good features when convex quads are involved (it preserves lines); maybe this should be our "default" option but when non-convex quads are involved one could fall back on the piecewise-affine method. This violates my natural tendency to avoid special cases (it also would give you a homeomorphism that varies discontinuously as the vertices are moved, I think), but I think it'd satisfy most of OP's needs.

If I think of something smoother than piecewise affine homeomorphisms for the general case, I'll post back. Basically, it seems like any homeomorphism that maps the edges correctly and the inside of the quad "nicely" would be a suitable answer.