How to align shapes together? (Geometrical Best-Fit Algorithm)

I'm working with mecanical engineers who rely on 3D modeling software. These softwares have a "Best Fit" feature. It allows you to acquire data with a sensor (like a 3D scanner) and align the mesured data with a CAD Drawing.

I'd like to know how such an algorithm can work!

In simpler words, imagine that you have 2 NEARLY identical triangles inside a 2D space. One is a 60-60-60 degrees triangle and the other is 60-59-61. The best-fit algorithm would find the best transformation that would align one triangle over the other.

I'm not even sure what I'm searching for here. I've done some research on Best-Fit algorithms but it mostly refer to bin packing and I'm not sure how this relates to my problem. Any advice would be welcome

Best fit algorithms boil down to optimization algorithms. You define a cost function from the space of possible fits to real numbers and then try to minimize this function. When you find the minimum you say that you found the best fit. Of course this fit may be not the best one with some other cost function (like two cost functions may lead to different best fits with your triangle example).

Of course the cost function and the algorithm used to minimize it depend on the problem. Finding a good algorithm for a specific problem which has a good performance is a subject for Ph.D in computer science. That's what some researchers do.

I think that the simplest example of best-fit is linear regression: fitting a line over a set of points. The cost function usually used is sum of square of differences, and there are simple mathematical methods to minimize it.

Bin packing has nothing to do with best fit algorithms in general. It's just one optimization problem that tries to minimize the cost function "the number of bins used".

I think the problem here is that you don't know which point transforms into which one

belisarius 2010-10-01 18:17:05

@belisarius it's even worse than that. The number of samples a 3d scanner produces is MUCH larger than the vertices of the nice CAD model, so finding the right mapping between the CAD and scan is non-trivial.

awesomo 2010-10-01 18:20:39

@belisarius: Of course you don't know. So your cost function is something complicated (match of Fourier spectra?) which makes it even harder to minimize.

ybungalobill 2010-10-01 18:21:09

No, this is taking 2-d images and processing them to solve the object registration problem. Scale-Invariant Feature Transform (SIFT) is a good example of a similar approach. The poster has a 3-d point cloud, not 2-d images, so this isn't exactly applicable.

awesomo 2010-10-01 18:32:48

@awesomo The OP example is 2D ...

belisarius 2010-10-01 18:35:28

@belisarius If the OP is working with 2-d data, I think SIFT is the way to go. If he has data from a 3-d scanner, then it is isn't a sensical approach.

awesomo 2010-10-01 18:37:43

ansaurus

tags:

views:

answers:

How to align shapes together? (Geometrical Best-Fit Algorithm)

related questions