Minimize Distance between 3D Point Sets with Rotation and Translation

Date: 07/15/2007 at 14:32:21
From: Juan
Subject: find a rot-translation matrix for fitting two 3D point sets

I need to fit two sets of 3D points (a, b, c... n) and (a', b', c'...
n') in such a way that the Euclidean distances between the point
pairs (a,a'), (b,b') ...(n,n') is minimum.  I can apply only rotations
and translations but no scale changes.

Is it possible to find a least-squares solution to this problem? There 
are lots of web pages describing methods for fitting the least-squares 
solution between points and functions but I was unable to find 
anything between two sets of points. 

I suppose that if I represent X as the first dataset and Y as the
second dataset the classic least-squares method 

Xt = Y
...
t = (X^TX)-1 X^T Y

should be able to provide a t matrix.  However, this matrix can 
contain scaling and I need that the transformation involves only
rotation and translation.

I have tried to use an iterative algorithm that applies rotations and
translations.  It works fine, but it's time consuming and I am
convinced that there are far more efficient methods.

Date: 07/16/2007 at 06:46:54
From: Doctor George
Subject: Re: find a rot-translation matrix for fitting two 3D point sets

Thanks for writing to Doctor Math.

The algorithm that you need is in the following journal article by R.
J. Hanson and M. J. Norris.

Analysis of Measurements Based on the Singular Value Decomposition,
SIAM J. of Sci. and Stat. Comp. (September 1981)

Write again if you need more help.

- Doctor George, The Math Forum
  http://mathforum.org/dr.math/