2

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.

  • for 50 to 150 points brute-forcing is viable – ratchet freak Oct 21 '13 at 11:57
  • @ratchetfreak I do not have any specific logic to brute-force with. I simply have two point sets with 3D coordinates. – Pavlo Dyban Oct 21 '13 at 12:01
  • 1
    What quantity are you trying to optimize? The sum-square distance of the matched pairs? Or something else? – kevin cline Nov 5 '13 at 16:21
  • @kevincline Yes, sum-squared distance. – Pavlo Dyban Nov 6 '13 at 7:24
0

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.

  • Points in both sets are not located on the same spot. Think of them as some markers in different time points. I would need some metric to decide which points belong together, which points have shifted, which points have disappeared and which points have appeared anew. – Pavlo Dyban Oct 21 '13 at 14:02
  • @Pavlo Dyban Assume the point pi in the first set is the same as the point pj in the second set. Then shift all the points in the second set by (pi.x-pj.x,pi.y-pj.y,pi.z-pj.z). Then find all the points in both sets. Sort first. It will cost O(nln(n) + mln(m) + mn*(m+n))= O(m*n*(m+n)), I think it will be fast enough for sets with 50 to 150 points. – Zhiwen Fang Oct 21 '13 at 15:43
  • The case is a flexible deformation of space, so that relative position of points will have changed between two sets. Which point should i choose if i have two or more candidates? How do I know that a point is an outlier and should not be coupled? – Pavlo Dyban Oct 22 '13 at 7:21
  • 1
    @Pavlo Dyban, you should choose all points from the first set and all points from the second one. There will be N * M pairs, and each pair will const O(M+N) time to find the maximum match. Of course, the optimal solution will be one of them. – Zhiwen Fang Oct 22 '13 at 8:07
  • The question is how. What you suggest is closest-point search, but it is not guaranteed to create the most suitable matching. I am looking for alternative algorithms, maybe global optimization (like in ICP, but not as sophisticated). Besides, I need a method to decide which points are outliers and not simply leave those that have not been coupled in the end. – Pavlo Dyban Oct 22 '13 at 11:39
0

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.

  • For this sort of greedy algorithm, it might be better to start with the most extreme points of the smaller set. – kevin cline Nov 5 '13 at 16:23
  • @kevincline Could you please elaborate? By extreme do you mean the farthest? – Pavlo Dyban Nov 6 '13 at 7:24
  • Farthest from the centroid. – kevin cline Nov 6 '13 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.