Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Higher-Dimensional Geometry

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search