12

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, and shear is straightforward. Is there a simple projective matrix which will transform a square to a trapezoid?

Andrew Prock
  • 6,900
  • 6
  • 40
  • 60

3 Answers3

11

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.

Alessandro Jacopson
  • 18,047
  • 15
  • 98
  • 153
  • After actually trying this, I got a set of equations that could not be solved. [This answer](http://math.stackexchange.com/questions/169176/2d-transformation-matrix-to-make-a-trapezoid-out-of-a-rectangle) seems to support this -- a trapezoid can't be made from a rectangle with a linear transformation. – Marijn Jun 08 '13 at 11:06
  • @Marijn Hello, what are your input data? – Alessandro Jacopson Jun 08 '13 at 11:24
  • In the simple case, I want to transform the rectangle between (0, 0) and (1, 1) to a trapezoid (0, 0) (0, 1) (1, A) (1, B), so A and B are the input parameters. If I solve that, I get B = A + 1, i.e. the resulting matrix will only produce parallelograms. At first I also tried to make the Y of the left (X=0) points a parameter, and that got me a system that couldn't be solved -- though it may be that I just made a mistake in reducing the equations (I don't have a lot of practice with this stuff). – Marijn Jun 11 '13 at 09:41
  • @Marijn Hello, I edited the answer with some links that explain in details the method. For what regard the parallelograms you mentioned: the key point is that, once you know `H`, you go, in general, from `a` to `alpha` with a non linear function; `a=[x1,y1,1]` `alpha=[X1,Y1,1]` where `X1=(x1*h1+y1*h2+h3)/(x1*h7+y1*h8+h9)` and `Y1=(x1*h4+y1*h5+h6)/(x1*h7+y1*h8+h9)` – Alessandro Jacopson Jun 11 '13 at 19:25
  • 1
    Thanks for the clarification. I was trying to create a 3×3 matrix to use in a CSS transform rule. From what I can see, this technique won't apply there. – Marijn Jun 12 '13 at 08:56
  • @Marijn You can also have a look at "Using Projective Geometry to Correct a Camera" by David Austin at http://www.ams.org/samplings/feature-column/fc-2013-03 – Alessandro Jacopson Oct 20 '13 at 12:16
  • As "Using Projective Geometry to Correct a Camera" explains, it's not linear transformation, although the numerators and denominators are simply linear. BTW, thank you for pointing out the solution! – Huang Dongsung Feb 15 '18 at 18:58
3

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. :)

Community
  • 1
  • 1
hfossli
  • 22,616
  • 10
  • 116
  • 130
0

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
Rekin
  • 9,731
  • 2
  • 24
  • 38