I need to match two sets of 3D points, however the number of points in each set can be different. It seems that most algorithms are designed to align images and trimmed to work with hundreds of thousands of points. My case are 50 to 150 points in each of the two sets.
So far I have acquainted myself with Iterative Closest Point and Procrustes Matching algorithms. Implementing Procrustes algorithms seems like a total overkill for this small quantity. ICP has many implementations, but I haven’t found any readily implemented version accounting for the so-called “outliers” – points without a matching pair.
Besides the implementation expense, algorithms like Fractional and Sparse ICP use some statistics information to cancel points that are considered outliers. For series with 50 to 150 points statistic measures are often biased or statistic significance criteria are not met.
I know of Assignment Problem in linear optimization, but it is not suitable for cases with unequal sets of points.
Are there other, small-scale algorithms that solve the problem of matching 2 point sets? I am looking for algorithm names, scientific papers or C++ implementations. I need some hints to know where to start my search.
4
You want to find the maximum points in both of the sets? Then the brute force search means for every point P in the first set, traverse the second set to find
the point that match with point P. It costs O(M*N), which will be suit for your case.
Of course, you can sort the points first(first by x-axis,then y-axis,then z-asix.)
Then you can traverse these two sorted set to search for the matching points.
5
In the end I had to resort to a naive algorithm.
Choose a random point. Find the closest point from the second set inside a given threshold range. Find the closest point from the first set which corresponds to the point in the second set. If the two are the same, store them as pair and eliminate them from list. Continue until no more candidate points can be found.
This is a simple and a straight-forward solution approach, since unfortunately I could not persuade my company to spend more time on implementing a scientific algorithm from scratch.
3