How to solve geometric (nonlinear) least-square problem?

Hi, there!

I am a new user of Maxima in the hope I can find a solution how to
calculate my least-squares fitting algorithm with it. Unfortunately, I
had to realize that I am not so much of a math-geek so I am asking you
for help with this problem since I spent already days figuring out how
to solve the (IMHO nonlinear) systems of equations.

Intro:
Imagine a perfect (2dimensional) square with known dimensions. The
four corner points are Q1 to Q4.

I have to do a best fit alignment of a somehow (in the same plane)
distorted square with the four courner points P1 to P4.
The two squares should be alinged on top of each other as good
as possible. The idea is to do a least-square minimization of the four
vectors P->Q by doing a matrix transformation which consists of a
translation followed by a rotation of the P vectors to the Q vectors.

I know all the 8 corner points P and Q. And I want to know the translation
vector (tx,ty) and the rotation (w) that the sum( (P->Q)^2 ) is minimal.

The approach:
Translation
T: matrix(
  [1,0,tx],
  [0,1,ty],
  [0,0,1]
);
Rotation:
R: matrix(
  [cos(w),-sin(w),0],
  [sin(w),cos(w),0],
  [0,0,1]
);

Transformation matrix:
A: T.R;
(%o4) matrix([cos(w),-sin(w),tx],[sin(w),cos(w),ty],[0,0,1]);

Vector of the coordinates of P(px,py):
x: matrix([px], [py], [1]);

Vector of the coordinates of Q(qx,qy);
b: matrix([qx], [qy], [1]);

Now I can setup a bunch equations:
A.x=b;
(%o9) matrix(
  [-py*sin(w)+px*cos(w)+tx],
  [px*sin(w)+py*cos(w)+ty],
  [1])
=matrix([qx],[qy],[1])

Or I can write that the residual vectors are:
(%i10) r: b-A.x;
(%o10) matrix([py*sin(w)-px*cos(w)-tx+qx],[-px*sin(w)-py*cos(w)-ty+qy],[0])

sum(r^2,h,1,4) needs to be minimized now.

If that's a linear system, I think I would be able to solve it by using the
jacobian transformation. But I cannot get rid of sin() and cos() to deal with
it properly.

I thought I could substitute the sin(w) with s, cos(w) with c and add
the equation c^2 + s^2=1. But then I have to solve a quadratic system.

Can some of you please help me with this math exercise?
Thank you very much in advance. Please feel free to ask any more
questions if anything is unclear.

Best regards,

Clemens


PS: Please find attached the equations as shown above...
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: CornerAlignment.wxm
Url: http://www.math.utexas.edu/pipermail/maxima/attachments/20090522/d2790a5e/attachment.diff