The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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 
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.