Transform quadrilateral into a rectangle?

Question

I have scene composed of one arbitrary quadrilateral. I need to be able to transform that quadrilateral into a rect. Each quad is in 2d coordinates, so they have 4 vertex (x_i, y_i).

The transformation need to have an inverse because the idea is to go back to the original quad after manipulating the rectangle.

What would be the easiest way to perform this operation ? I've heard it's called a perspective transformation, but I've found some small clues that lead me to think this could be quite easy to do.

Answer 1

Do you know what the size of the desired rectangle is? You can map any convex quadrilateral to a rectangle with an invertible transformation with a perspective transformation if this is the case. All you have to do is get 4 corresponding points (between the quadrilateral and the rectangle), say, (X₁,Y₁), (X₂,Y₂), (X₃,Y₃), (X₄,Y₄) for the quadrilateral and correspondingly (x₁,y₁), (x₂,y₂), (x₃,y₃), (x₄,y₄) for the rectangle. Then plug it into the final equation in Borealid's link and you're set:

The solution of the above equation (where n = 4) will give you the elements (a,b,c,d,e,...,h) of the invertible perspective transformation matrix,

This will allow you to transform the points on the rectangle to the points on the quadrilateral. For the reverse transformation, just invert the transformation matrix.

Also note that once you obtain the vector [XW YW W]^T of transformed coordinates, you need to normalize it such that W = 1. I.e., your final answer is [XW/W YW/W W/W]^T which is equal to [X Y 1]^T, the desired answer.

Answer 2

Not all quadrilaterals are rectangles. There is no invertible transformation from a quad to a rectangle for this reason; there exist more quads than rects, so you cannot produce an invertible mapping from quads to rects.

However, you can generate an invertible transformation for a particular quadrilateral. As you surmise, it's about rotating the perspective so the quadrilateral "appears" as a rectangle in your new coordinate space. See http://alumni.media.mit.edu/~cwren/interpolator/ , which contains Matlab source code for this problem.