From: Dave Rusin <rusin@math.niu.edu>
Subject: Re: help needed about spatial balancement
Date: Tue, 23 Mar 1999 00:50:58 -0600 (CST)
Newsgroups: sci.math.research
To: vergez@wanadoo.fr
Keywords: Finding Euclidean isometry best matching n pre- and post-point pairs

In article <7cc0u0$8as$1@platane.wanadoo.fr> you write:
>
>I am looking for an isometric + translation transformation (3X4) beetwenn
>deux sets of
>n points (n>3). The first set is composed by  theoretical points and the
>second sets represents the
>same points but real : which was measured on a real piece . The main is to
>fit as near as possible the second set of points by transforming the first
>set.
>
>The difficulty I encountered is because of the nature of the transformation
>: preserve the norm.
>To my mind, the solution is not unique and it is a approximation problem
>with the constraint of the nature of the matrice (minimisation of a distance
>criterium ..).  But, I don't know how to solve
>this problem. If you can help me to find an algorithm, thank you very much

Let me see if I understand this. You have a set of points  P1, ..., Pn
in  R^3. You also have another set of points  Q1, ..., Qn  in  R^3 -- you
did not say this but I hope you mean that the second set is also _ordered_,
that is, there is a _first_ point, which we will try to make correspond
to  P1  in a moment; then there is a _second_ point, etc.  Now you
seek an isometry  F : R^3 -> R^3  which comes as close as possible to
sending  F(P_i) = Q_i  for every  i=1, 2, ..., n.  Is that the question?

If so, you need to explain how you will measure closeness. You could,
for example, ask to choose  F  so as to minimize
     S = Sum( dist(P_i, Q_i)^2,  i=1, ..., n)
However you choose to measure closeness, it seems you could treat this
as a simple numerical optimization problem. You could even parameterize the set
of isometries with  6  variables  v_i ; then the 6 equations  dS/dv_i = 0 
would not be too complicated, and so you could treat them as a set of
6 algebraic equations in 6 unknowns -- again, not too hard of a
problem. (You could even make a good initial guess for the values of the
variables, e.g. choose to 3 translation variables so that the center of
mass of the  P's  is carried to the center of mass of the  Q's.)


For your parameterization, you might want to use the function
     F(H) = (I+H)*(I-H)^(-1)
which pairs off the skew-symmetric matrices  H =
      [ 0  -a  -b ]
      [ a   0  -c ]
      [ b   c   0 ]
with the orthogonal matrices not having  -1  as an eigenvalue. Then you
are seeking  H  and a displacement vector  w  so that for each  i,
    (I-H)^(-1) * (I+H) * P_i  +  w
is very close to  Q_i. You can think of this as asking for the  H  and  w
so that  (I+H)*P_i ~=~ (I-H)*(Q_i + w), although this distorts the
previous measure of how close your fit is. The reason I suggest this
change is that the 6 variables appear only quadratic in here, and indeed
if  w  is known (or guessed) then this proposed equation is _linear_ in H.
So the optimal  H  can be found exactly as for least-squares.

You might want to ask in  sci.math.num-analysis  if you have a specific
question about how to perform the computations efficiently.

I am sorry if I have not understood your question. Vous pouvez ecrire a moi
en francais -- je le peut lire mais, comme on peut voir, je ne le peut ecrire.

dave