Finding Affine Transformations

[nomad421]

So this is my problem... I have two unstructured point clouds, containing different numbers of points, which have been sampled in a noisy manner. I want to find the "best" affine transformation between these sets of points. I've tried ICP, but the points are too noisy and I often fail to find enough pairs of points for the algorithm to succeed. I have a procedure to combine the sets once they are registered as closely as possible, but solving the registration problem in the presence of noise is very difficult. Does anyone have any suggestions, ideas, code? Thanks!

[Reedbeta]

Maybe you could do some kind of PCA of the data and derive the affine transformation that maps one's principal components into the others. If that's not good enough, it could be a starting point for some kind of refinement. I'm not sure what ICP is.

[nomad421]

That's a good idea, maybe I'll give it a try. ICP stands for Iterative Closest Point; a Google search will provide a ton of references. Basically, however, you find pairs of points from the different point clouds, and then find a transformation the minimizes the sum of squared distances. If you iterate this process (find close pairs of points, estimate the transformation in a least-squares sense, transform the points and repeat) you will eventually converge on a transformation. The problem is that when the point sets are noisy, as in my case, the independence of the sample noise makes it difficult to find pairs of points that agree on a distance minimizing transformation.

[Reedbeta]

Yeah, that sounds like it would be difficult to tune. Perhaps using the PCA approach to provide the initial guess for ICP will yield better results.

[roel]

I recently read something about obtaining a matrix with noisy data as input, and then creating the best (orthonormal) rotation matrix from it. To behonest, I skipped that part, maybe it is totally unrelated to your problem, but if you care I can try to find the text.

[nomad421]

That sounds interesting... do you remember the title or the authors ?

[roel]

Yes, I found it: A Flexible New Technique for Camera Calibration (http://research.microsoft.com/research/pubs/view.aspx?tr_id=212), Appendix C. Now that I re-read it, I'm even less sure that it will be useful, anyway:

The problem considered in this section is to solve the best rotation matrix R to approximate a given
3 x 3 matrix Q. Here, “best” is in the sense of the smallest Frobenius norm of the difference R-Q.

[MrFrankly]

Did you try combining your method with a flexible optimization technique? Algorithms like Levenberg-Marquardt are quite accepting with regard to noise.