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

This solution use JAI (Java Advance Image) API all the magic is in QuadToQuad method. here is the code sample.

try
     {
      BufferedImage img = UtilImageIO.loadImage(picName);
      ParameterBlock params = new ParameterBlock();
      params.addSource(img); //source is the input image
        int w = img.getWidth(); //Set to the original width of the image
        int h = img.getHeight(); //Set to the original height of image
        Point tl = new Point(x,y); //The new top left corner
        Point tr = new Point((x1,y1); //The new top right corner
        Point bl = new Point(x2,y2); //The new bottom left corner
        Point br = new Point(x3,y3); //The new bottom right corner
        PerspectiveTransform p = PerspectiveTransform.getQuadToQuad(0,0, 0, h, w, h, w, 0, tl.x, tl.y, bl.x, bl.y, br.x, br.y, tr.x, tr.y).createInverse();
        WarpPerspective wa = new WarpPerspective(p);
        params.add(wa);
        params.add(Interpolation.getInstance(Interpolation.INTERP_BICUBIC)); //Change the interpolation if you need more speed
        RenderedOp dest = JAI.create("warp", params); //dest is now the output
        File outputfile = new File(picName);
        ImageIO.write(dest, "jpg", outputfile); 

    }
    catch(Exception e){}

Hopefully it will help you. :)

Answer 2

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 3

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.