Editing Scale-invariant feature transform (section)

=== Model verification by linear least squares ===
Each identified cluster is then subject to a verification procedure in which a [[linear least squares (mathematics)|linear least squares]] solution is performed for the parameters of the [[affine transformation]] relating the model to the image. The affine transformation of a model point [x y]<sup>T</sup> to an image point [u v]<sup>T</sup> can be written as below

:<math>
\begin{bmatrix} u \\ v \end{bmatrix} = \begin{bmatrix} m_1 & m_2 \\ m_3 & m_4 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} + \begin{bmatrix} t_x \\ t_y \end{bmatrix}
</math>

where the model translation is [t<sub>x</sub> t<sub>y</sub>]<sup>T</sup> and the affine rotation, scale, and stretch are represented by the parameters m<sub>1</sub>, m<sub>2</sub>, m<sub>3</sub> and m<sub>4</sub>. To solve for the transformation parameters the equation above can be rewritten to gather the unknowns into a column vector.

:<math>
\begin{bmatrix} x & y & 0 & 0 & 1 & 0 \\ 0 & 0 & x & y & 0 & 1 \\ ....\\ ....\end{bmatrix} \begin{bmatrix}m1 \\ m2 \\ m3 \\ m4 \\ t_x \\ t_y \end{bmatrix} = \begin{bmatrix} u \\ v  \\ . \\  . \end{bmatrix}
</math>

This equation shows a single match, but any number of further matches can be added, with each match contributing two more rows to the first and last matrix. At least 3 matches are needed to provide a solution.
We can write this linear system as

:<math>A\hat{\mathbf{x}} \approx \mathbf{b},</math>

where ''A'' is a known ''m''-by-''n'' [[Matrix (mathematics)|matrix]] (usually with ''m'' > ''n''), '''x''' is an unknown ''n''-dimensional parameter [[vector space|vector]], and '''b''' is a known ''m''-dimensional measurement vector.

Therefore, the minimizing vector <math>\hat{\mathbf{x}}</math> is a solution of the '''normal equation'''
:<math> A^T \! A \hat{\mathbf{x}} = A^T \mathbf{b}. </math>

The solution of the system of linear equations is given in terms of the matrix <math>(A^TA)^{-1}A^T</math>, called the [[Moore–Penrose inverse|pseudoinverse]] of ''A'', by

:<math> \hat{\mathbf{x}} = (A^T\!A)^{-1} A^T \mathbf{b}. </math>

which minimizes the sum of the squares of the distances from the projected model locations to the corresponding image locations.