views:

578

answers:

4

Let's say I have 3 point clouds: first that has 3 points {x1,y1,z1}, {x2,y2,z2}, {x3,y3,z3} and second point cloud that has same points as {xx1, yy1, zz1}, {xx2,yy2,zz2}, {xx3,yy3,zz3}... I assume to align second point cloud to first I have to multiply second one's points by T[3x3matrix].

1) So how do I find this transform matrix(T) ? I tried to do the equations by hand, but failed to solve them. Is there an solution somewhere, cause I'm pretty sure I'm not the first one to stumble into the problem.

2) I assume that matrix might include skewing and shearing. Is there a way to find matrix with only 7 degrees of freedom (3translation, 3rotation, 1scale)?

+3  A: 

The transformation matrix T1 that takes the unit vectors {1, 0, 0}, {0, 1, 0}, and {0, 0, 1} to {x1, y1, z1}, {x2, y2, z2}, {x3, y3, z3} is simply

     | x1 x2 x3 |
T1 = | y1 y2 y3 |
     | z1 z2 z3 |

And likewise the transformation T2 that takes those 3 unit vectors to the second set of points is

     | xx1 xx2 xx3 |
T2 = | yy1 yy1 yy3 |
     | zz1 zz2 zz3 |

Therefore, the matrix that takes the first three points to the second three points is given by T2 * T1-1. If T1 is non-singular, then this transformation is uniquely determined, so it has no degrees of freedom. If T1 is a singular matrix, then there could be no solutions, or there could be infinitely many solutions.

When you say you want 7 degrees of freedom, this is somewhat of a misuse of terminology. In the general case, this matrix is composed of 3 rotational degrees of freedom, 3 scaling degrees, and 3 shearing degrees, making a total of 9. You can figure out these parameters by performing a QR factorization. The Q matrix gives you the rotational parameters, and the R matrix gives you the scaling parameters (along the diagonal) and the shearing parameters (above the diagonal).

Adam Rosenfield
Absolutely fantastic!
Slava N
+1  A: 

Approach of Adam Rosenfield is correct. But solution as T2 * Inv (T1) is wrong. Since in Matrix multiplication A * B != B * A : Hence result is Inv(T1) * T2

lakshmanaraj
No, it depends on your convention for matrix-vector multiplication. If you're multiplying your (column) vectors on the right, then my formula is correct. If you're multiplying your (row) vectors on the left, then yours is correct, but you also have to transpose T1 and T2.
Adam Rosenfield
+1  A: 

The seven parameter transformation that you are talking about is referred to as a 3d conformal transformation, or sometimes a 3d similarity transformation given that the two clouds are similar. If the two shapes are identical, Adam Rosenfields solution is good. Where there are small differences, and you wish to get a best fit, the most commonly used solution is a Helmert transformation which uses a least squares approach to minimise the residuals. The wikipedia and google stuff on this doesn't seem great at a glance. My reference on this is Ghilani & Wolf's adjustment computations, p345. This is also a great book on matrix math as applied to spatial problems and a good addition to the library.

edit: Adam's 9 parameter version of this transformation is referred to as an affine transformation

Shane MacLaughlin
Do you a pointer to some code /library for the Helmert solution? All I can throw up are implementations that use it to convert with known transforms.
Martin Beckett
A: 

Here is an example of computing least-squares estimates of the parameters of a 2D affine transformation in R.

Dylan