square to trapezoid

I know that transforming a square into a trapezoid is a linear transformation, and can be done using the projective matrix, but I'm having a little trouble figuring out how to construct the matrix.

Using the projective matrix to translate, scale, rotates, 开发者_JAVA百科and shear is straightforward. Is there a simple projective matrix which will transform a square to a trapezoid?

a,b,c,d are the four corners of your 2D square.

a,b,c,d are expressed in homogeneous coordinate and so they are 3x1 matrices.

alpha, beta, gamma, delta are the four corners of your 2D trapezoid.

alpha, beta, gamma, delta are expressed in homogeneous coordinate and so they are 3x1 matrices.

H is the 3x3 matrix you are looking for, it is also called an homography

    h1 h2 h3
H = h4 h5 h6
    h7 h8 h9

H maps a,b,c,d into alpha, beta, gamma, delta and so you have the following four equations

alpha=H*a
beta=H*b
gamma=H*c
delta=H*d

Assuming you know a,b,c,d and alpha, beta, gamma, delta you can solve the previous four equation system for the nine unknowns h1, h2, h3, h4, h5, h6, h7, h8, h9.

Here I have just described a "raw" solution to the problem, that, in principle, can work; for a detailed explanation of the above mentioned method you can see for example this page http://www.corrmap.com/features/homography_transformation.php where they put h9=1 (since H can be expressed just with 8 parameters) and then solve a linear system of eight equations in eight unknowns. You can find a similar explanation in section 2 of the thesis Homography Estimation by Elan Dubrofsky.

Another explanation is Using Projective Geometry to Correct a Camera by David Austin in the 2013 March issue of Feature Column from the AMS.

The above mentioned method, with its disadvantages, is described in chapter 4 "Estimation - 2D Projective Transformation" in the second edition of Multiple view geometry in computer vision by Richard Hartley and Andrew Zissermann where they also describe different and better algorithms; you can check this link http://www.cse.iitd.ac.in/~suban/vision/geometry/node24.html which seems to follow the same book.

You can find another explanation of the homography in section 15.1.4, "Projective transformation model" of the book Computer Vision: Models, Learning, and Inference by Simon J.D. Prince. The algorithm Algorithm 15.4: maximum likelihood learning of projective transformation (homography) is outlined in his Algorithms booklet: the problem is solved by means of a non-linear minimization.

Maybe you could use a quadrilateral? See my answer here:

https://stackoverflow.com/a/12820877/202451

Then you will have full control over each point and can easily make any four-cornered shape. :)

Java implementation with minimal dependencies

For those with limited knowledge and time looking for a quick and dirty solution there is a working and quite reliable Java implementation in the Wii-interact project.

The transormation is in the The Homography source file. It boils down to constructing and solving the matrix:

/**
* Please note that Dr. John Zelle assisted us in developing the code to
* handle the matrices involved in solving for the homography mapping.
* 
**/
Matrix A = new Matrix(new double[][]{
                {x1, y1, 1, 0,  0,  0, -xp1*x1, -xp1*y1},
                {0,  0,  0, x1, y1, 1, -yp1*x1, -yp1*y1},
                {x2, y2, 1, 0,  0,  0, -xp2*x2, -xp2*y2},
                {0,  0,  0, x2, y2, 1, -yp2*x2, -yp2*y2},
                {x3, y3, 1, 0,  0,  0, -xp3*x3, -xp3*y3},
                {0,  0,  0, x3, y3, 1, -yp3*x3, -yp3*y3},
                {x4, y4, 1, 0,  0,  0, -xp4*x4, -xp4*y4},
                {0,  0,  0, x4, y4, 1, -yp4*x4, -yp4*y4}
        });

        Matrix XP = new Matrix(new double[][]
                          {{xp1}, {yp1}, {xp2}, {yp2}, {xp3}, {yp3}, {xp4}, {yp4}});
        Matrix P = A.solve(XP);
        transformation = new Matrix(new double[][]{
                {P.get(0, 0), P.get(1, 0), P.get(2,0)},
                {P.get(3, 0), P.get(4, 0), P.get(5,0)},
                {P.get(6, 0), P.get(7, 0), 1}
        });

Usage: the following method does the final transformation:

public Point2D.Double transform(Point2D.Double point) {
    Matrix p = new Matrix(new double[][]{{point.getX()}, {point.getY()}, {1}});
    Matrix result = transformation.times(p);
    double z = result.get(2, 0);
    return new Point2D.Double(result.get(0, 0) / z, result.get(1, 0) / z);
}

The Matrix class dependency comes from JAMA: Java Matrix Package

License

1. Wii-interact GNU GPL v3
2. JAMA public domain