… Affine Transformations.

Note to myself (0).

### 1. problem

Let’s say here are 2 sets of 2D points and , . Besides, corresponds to for each . What I want here is a nice affine transform that maps each to , such that sum of distances between mapped and is minimised. That is an affine transform that minimise this:

,

where

.

### 2. go calculus

In order for to take minimal value, it is necessary that is stationary, i.e. all 1st partial derivatives of with respect to must be . Writing down the necessary conditions, I get:

.

Computing partial derivatives and simplifying (a bit tedious) lead to the 2 separate systems of 1st order equations:

,

,

(sums are over i = 0 to n-1).

Solving for gives me what I wanted, the “nice” affine transform.

### 3. go linear algebra

Let’s imagine an ideal situation where the mapped points coincide with , i.e.

for each . This can be rewritten as 2 systems of equations as follows:

,

.

Except for this ideal situation, the equations above do not hold. I cannot equate LHS with RHS.

But the systems can give me a clue for looking at the problem from a different view point. Namely, LHS can be seen as a linear combination of 3 column vectors which spans 3-dimensional subspace of n-dimensional space. RHS is a vector also resides in the same n-dimensional space, but it is not, in general, on the 3-dimensional space spanned by LHS.

In the 3-dimensional space, the closest possible point to RHS is given by orthogonal projection from the RHS vector to the 3-dimensional space spanned by LHS. This projection line must be orthogonal to 3 column vectors of LHS matrix. Putting this condition into math expressions, I get:

,

.

These can be rewritten as

,

.

Computing matrix products, these equations result in the ones given in section 2.

As a computer programmer myself, a nice thing about this approach is that I can do away with some computation by hand which is a bit error prone, provided that I have a basic matrix operators and solvers at hand. Further more, with Householder transformer at hand, I can even dispose of matrx multiplier, which is my favourite way to go actually.

lll

Pingback: Least Square Fitting of… (1) | 0909