PDA

View Full Version : Orthogonalizing a non-orthogonal transformation matrix



marcus256
09-02-2003, 09:10 PM
Not really OpenGL, but related anyway...

Background: I have two datasets (points in 3D cartesian coordinates) representing the same object, but with different rotations and translations. I solve the optimal transformation matrix for going from dataset A to dataset B with a least squares approximation, which works fine.

Problem: Due to inherent errors (measurment, numerical and algorithmical) the two datasets do not represent a 1:1 match, meaning that the transformation matrix does not represent an orthogonal coordinate system (i.e. the transformation is not only composed of rotation and translation, but also of scaling). Since I want to get the optimal rotation and translation, I need to get rid of the scaling somehow.

Solution: I figure that the best way is to find an orthogonal transformation matrix that best matches the non-orthogonal matrix that I get from the least squares solution. Here, "best matches" would probably mean the smallest sum of (squared?) distances of each of the three coordinate system axes.

Question: Is there a known method for doing this? I have not found any such solution in any book or on the net, and I have come up dry in my own attempts at finding an analytical solution to the problem.

My current strategy is to do a numerical solution in the following way (e'x, e'y, e'z are the normalized non-orthogonal coordinate system axes, and ex, ey, ez are the desired orthogonal coordinate system axes):

1) Calculate m = (e'x + e'y + e'z)/|e'x + e'y + e'z| (the "diagonal")
2) Create an orthogonal coordinate system that satisfies (ex + ey + ez)/|ex + ey + ez| = m
3) Rotate the orthogonal coordinate system about m until the smallest error, err=|e'x-ex|+|e'y-ey|+|e'z-ez|, is found

I figure this should be reasonably accurate and fast (only one degree of freedom, namely the rotational angle about m).

Eric Lengyel
09-02-2003, 10:24 PM
It sounds like you want to use Gram-Schmidt orthogonalization. This (pretty simple) algorithm is described in Chapter 1 of Mathematics for 3D Game Programming and Computer Graphics (http://www.terathon.com/books/mathgames.html) .

[This message has been edited by Eric Lengyel (edited 09-03-2003).]

marcus256
09-03-2003, 12:30 AM
Thank you Eric!

I did not know about that method.

I tried to understand Gram-Schmidt orthogonalization from some pages on the net that I found, but it seems to me that it will not produce an optimal orthogonal representation of the original basis vectors. In fact, the result of the orthogonalization process depends on in which order the basis vectors are orthogonalized.

I believe the same result can be achieved by doing this (X denotes cross product):

ex = normalize(e'x)
ey = normalize(e'z X e'x)
ez = ex X ey

What I am looking for is something like "least squares approximation of an orthogonal basis to a non-orthogonal basis". So, the question is still open.

Coconut
09-03-2003, 03:57 AM
http://www.ai.mit.edu/people/bkph/papers/Absolute_Orthonormal.pdf

may help.

marcus256
09-03-2003, 04:56 AM
Thanks Coconut!!

This was the document I was looking for! It even deals with the entire problem of mine, not just the orthonormalization. I will study it, and I will probably not bother you again with this problem http://www.opengl.org/discussion_boards/ubb/smile.gif