For an affine transformation in two dimensions defined as follows:
$$
p_i'=\mathbf{A}p_i \Leftrightarrow \\
\left[
\begin{matrix}
x_i' \\ y_i'
\end{matrix}
\right]
=
\left[
\begin{matrix}
a & b & e \\
c & d & f
\end{matrix}
\right]
\left[
\begin{matrix}
x_i \\ y_i \\ 1
\end{matrix}
\right]
$$
Where $(x_i,y_i), (x_i',y_i')$ are corresponding points, how can I find the parameters $\mathbf A$ efficiently?
Rewriting this as a system of linear equations, given three points (six knowns, six unknowns):
$$
\textbf{P}\alpha=\textbf{P}' \Leftrightarrow \\
\left[
\begin{matrix}
x_0 & y_0 & 0 & 0 & 1 & 0 \\
0 & 0 & x_0 & y_0 & 0 & 1 \\
x_1 & y_1 & 0 & 0 & 1 & 0 \\
0 & 0 & x_1 & y_1 & 0 & 1 \\
x_2 & y_2 & 0 & 0 & 1 & 0 \\
0 & 0 & x_2 & y_2 & 0 & 1 \\
\end{matrix}
\right]
\left[
\begin{matrix}
a \\ b \\ c \\
d \\ e \\ f
\end{matrix}
\right]
=
\left[
\begin{matrix}
x_0' \\ y_0' \\x_1' \\ y_1' \\x_2' \\ y_2'
\end{matrix}
\right]
$$
Allows the use of an LU decomposition, which can be computed in $O(M(n))$ time, where $M(n)$ is the time to multiply two n×n matrices (according to 1).
Can the specific structure of the $\mathbf P$ matrix be exploited to utilize the Gaussian elimination to reach the reduced row echelon form (thus solving the system) more efficiently?
Is there a way to symbolically derive the required operations? By hand seems rather cumbersome
Thanks
Best Answer
From three point pairs in general position, we can derive an explicit expression for $A$, namely, $$A = \begin{bmatrix}x_0'&x_1'&x_2'\\y_0'&y_1'&y_2'\\1&1&1\end{bmatrix} \begin{bmatrix}x_0&x_1&x_2\\y_0&y_1&y_2\\1&1&1\end{bmatrix}^{-1}.$$ There might be some efficiencies to be gained by examining ways to compute that.