Get Transformation Matrix from Points

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.

I'll use $f(x, y)$ to represent the 2D point $(x, y)$ multiplied by an assumed 3x3 transformation matrix:

$\begin{pmatrix} x'\\ y'\\ z' \end{pmatrix} := \begin{pmatrix} a & b & c\\ d & e & f\\ g & h & i \end{pmatrix} \begin{pmatrix} x\\ y\\ 1 \end{pmatrix}$

$f(x, y) := \begin{pmatrix} \frac{x'}{z'}\\ \frac{y'}{z'} \end{pmatrix} = \begin{pmatrix} \frac{ax + by + c}{gx + hy + i}\\ \frac{dx + ey + f}{gx + hy + i} \end{pmatrix}$

Given the transformation matrix, the corners of a square centered on $(0, 0)$ can be transformed:

$f(1, 1) = (x_1, y_1)\\ f(1, -1) = (x_2, y_2)\\ f(-1, -1) = (x_3, y_3)\\ f(-1, 1) = (x_4, y_4)$

Forgive me for using slightly different naming and notation than the original question. It was a long time ago.

The problem is to find a transformation matrix (values for $a$ through $i$) given these 8 output variables. I used the following equations to compute a solution.

First, some temporary variables to simplify the process:

$j = x_1 - x_2 - x_3 + x_4\\ k = -x_1 - x_2 + x_3 + x_4\\ l = -x_1 + x_2 - x_3 + x_4\\ m = y_1 - y_2 - y_3 + y_4\\ n = -y_1 - y_2 + y_3 + y_4\\ o = -y_1 + y_2 - y_3 + y_4$

Then values for the matrix elements, calculated in reverse order:

$i = 1\\ h = \frac{(jo - ml)i}{mk - jn}\\ g = \frac{kh + li}{j}\\ f = \frac{y_1(g + h + i) + y_3(-g - h + i)}{2}\\ e = \frac{y_1(g + h + i) - y_2(g - h + i)}{2}\\ d = y_1(g + h + i) - f - e\\ c = \frac{x_1(g + h + i) + x_3(-g - h + i)}{2}\\ b = \frac{x_1(g + h + i) - x_2(g - h + i)}{2}\\ a = x_1(g + h + i) - c - b$

I have a proof of concept implementation: https://jsfiddle.net/kendfrey/oxm5L6q0/5/

For the unhealthily curious, my working out was done in Lean: https://gist.github.com/kendfrey/28c49ebc1c28e543ca6322e167fb8fd8

Notes:

• Since there are 9 unknown variables and 8 equations, I'm free to choose a value for $i$.
• This works in the general case but has some degenerate cases where division by zero occurs.