[Math] Get Transformation Matrix from Points

algorithmslinear algebramatricestransformation

I have built a little C# application that allows visualization of perpective transformations with a matrix, in 2D XYW space. Now I would like to be able to calculate the matrix from the four corners of the transformed square. Here is a screenshot to help you understand what I am working with:

Screenshot

The idea is to allow the user to move the corners of the square and update the matrix. The corners are currently located at (1,1), (1,-1), (-1,-1), (-1,1). Is there an algorithm that will calculate a 3×3 matrix given four 2D points?

If I understand this correctly, every matrix corresponds to a set of four points, and every set of four points corresponds to one or more equivalent matrices ('equivalent' meaning 'producing identical transformations').

I searched for an algorithm to do this, but didn't have much luck.

I figured out that I could do it by creating eight equations, one for each variable in the four points, and then setting one of the matrix values to one, and solving for the other eight with algebra. However, the equations grow much too complicated to do this all successfully on pencil and paper.

This is the process I used to try to get it working.

So this is the basic matrix transformation formula.

$\begin{pmatrix}a & b & c\\
d & e & f\\
g & h & i
\end{pmatrix}\begin{pmatrix}x\\
y\\
z
\end{pmatrix}=\begin{pmatrix}ax+by+cz\\
dx+ey+fz\\
gx+hy+iz
\end{pmatrix}$

The resulting point is then converted from homogeneous to Euclidean coordinates.

$\begin{pmatrix}x\\
y\\
z
\end{pmatrix}$=$\begin{pmatrix}\frac{x}{z}\\
\frac{y}{z}
\end{pmatrix}$

So given a collection of points, we transform them like this.

$\begin{pmatrix}a & b & c\\
d & e & f\\
g & h & i
\end{pmatrix}\begin{pmatrix}x_{n}\\
y_{n}\\
z_{n}
\end{pmatrix}=\begin{pmatrix}x'_{n}\\
y'_{n}
\end{pmatrix}$

These are the formulas used for the transformation.

$x'_{n}=$$\frac{ax_{n}+by_{n}+cz_{n}}{gx_{n}+hy_{n}+iz_{n}}$

$y'_{n}=$$\frac{dx_{n}+ey_{n}+fz_{n}}{gx_{n}+hy_{n}+iz_{n}}$

We then define four base points, which are the corners of our square.

$x'_{0}=1$

$y'_{0}=1$

$z'_{0}=1$

$x'_{1}=1$

$y'_{1}=-1$

$z'_{1}=1$

$x'_{2}=-1$

$y'_{2}=-1$

$z'_{2}=1$

$x'_{3}=-1$

$y'_{3}=1$

$z'_{3}=1$

This gives us the following system of equations, in the form that lets us determine the transformed points from the matrix.

$x'_{0}=$$\frac{a+b+c}{g+h+i}$

$y'_{0}=$$\frac{d+e+f}{g+h+i}$

$x'_{1}=$$\frac{a-b+c}{g-h+i}$

$y'_{1}=$$\frac{d-e+f}{g-h+i}$

$x'_{2}=$$\frac{-a-b+c}{-g-h+i}$

$y'_{2}=$$\frac{-d-e+f}{-g-h+i}$

$x'_{3}=$$\frac{-a+b+c}{-g+h+i}$

$y'_{3}=$$\frac{-d+e+f}{-g+h+i}$

Now we want to reverse the transformation, and find the matrix that produces the above points. Since we have 9 unknowns and 8 equations, we need to add another equation.

$i=1$

Now all that is left is to solve the system equations to find the formulas for the matrix values. I'm not patient enough nor good enough with algebra to do this myself, so I used an online calculator to solve the system of equations. The formulas it gave almost worked, but had some glitches with y-coordinates.

I think this can be narrowed down to 2 questions:

  1. Are the above calculations wrong, or does the online calculator have a bug?

  2. Is there an easier algorithm for this?

Best Answer

Let T be the unknown transformation matrix (3X3).

Let A be the matrix of original co-ordinates (4X3).

Let B be the matrix of new co-ordinates (4X3).

Now A*T = B. Solve for 9 unknowns using 12 equations to get the transformation. As you can see you need only 3 points, not 4 to fully define the transformation.

Related Question