9

I'm trying to find suitable algorithms for searching subsets of 2D points in larger set. A picture is worth thousand words, so:

enter image description here

Any ideas on how one could achieve this? Note that the transformations are just rotation and scaling.

It seems that the most closely problem is Point set registration [1]. I was experimenting with CPD and other rigid and non-rigid algorithms' implementations, but they don't seem to perform too well on finding small subsets in larger sets of points.

Another approach could be using star tracking algorithms like the Angle method mentioned in [2] or more robust methods like [3]. But again, they all seem to be meant for large input sets and target sets. I'm looking for something less reliable but more minimalistic...

Thanks for any ideas!

[1]: http://en.wikipedia.org/wiki/Point_set_registration

[2]: http://www.acsu.buffalo.edu/~johnc/star_gnc04.pdf

[3]: http://arxiv.org/abs/0910.2233

Improve this question
7
  • Can you give more details on the context ? For instance, are you assuming 2D points only, or should the algorithm work in higher dimension as well ? What would be the typical size of the point set in which you search for a match ? Do you have a single template to find or will you be searching for many templates one after the other ? Commented Jan 7, 2015 at 16:15
  • The input set would be around 5 to 15 points. The target set would be around 1000 points, but could be splitted to smaller regions... Eventually, I would like to find the most similar match, so the input set could be imperfect. Commented Jan 7, 2015 at 16:22
  • @RobSis I am curious to know how you managed to solve your problem. I have a similar problem to solve and would appreciate it if you could let me know which algorithm is the most suitable for this class of problems based on your experience. I have looked at RPM, ICP and CPD methods but could not produce satisfactory results for my type of data (which is in 3D). Commented Feb 19, 2015 at 15:35
  • @RobSis, sorry to resurrect such an old thread.. But I am looking to do the same thing, except with translation and rotation. Did you find an accurate way to point match a subset with a set? Thanks! Commented Mar 24, 2017 at 19:47
  • @RobSis I am dealing with the same problem, matching a small set of points (typically around 3-10) to a large map of poitns (from 30 to 100). All the papers and works aer related to large scale matching with huge computations. I was wondering if you came accross any method for this implementation. Thanks! Commented Aug 8 at 6:42

5 Answers 5

Reset to default
2

here's some papers probably related to your question:

  • Geometric Pattern Matching under Euclidean Motion (1993) by L. Paul Chew , Michael T. Goodrich , Daniel P. Huttenlocher , Klara Kedem , Jon M. Kleinberg , Dina Kravets.
  • A fast expected time algorithm for the 2-D point pattern (2004) by Wamelena, Iyengarb.
  • Simple algorithms for partial point set pattern matching under rigid motion (2006) by Bishnua, Dasb, Nandyb, Bhattacharyab.
  • Exact and approximate Geometric Pattern Matching for point sets in the plane under similarity transformations (2007) by Aiger and Kedem.

and by the way, your last reference reminded me of:

  • An Application of Point Pattern Matching in Astronautics (1994) by G. Weber, L. Knipping and H. Alt.
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

I think you should start with a subset of the input points and determine the required transformation to match a subset of the large set. For example:

  • choose any two points of the input, say A and B.
  • map A and B to a pair of the large set. This will determine the scale and two rotation angles (clockwise or counter clockwise)
  • apply the same scaling and transformation to a third input point C and check the large set to see if a point exists there. You'll have to check two positions, one for each of rotation angle. If the point C exists where it should be in the large set, you can check the rest of the points.
  • repeat for each pair of points in the large set

I think you could also try to match a subset of 3 input points, knowing that the angles of a triangle will be invariant under scaling and rotations.

Those are my ideas, I hope they help solve your problem.

Improve this answer

Comments

0

I would try the Iterative Closest Point algorithm. A simple version like the one you need should be easy to implement.

Improve this answer

2 Comments

Not sure the ICP would be appropriate, since it must be initialized close to a solution in order to converge.
You are completely right! the ICP is extremly sensitive to the initial guesses when it is used to match millons of 3D points, but I assume in this simple scenario it should be able to "brute force" through all the points. Guess he can try it... if worst comes to worst, he can try 1000 random initial positions :D
0

Take a look at geometric hashing. It allows finding geometric patterns under different transformations. If you use only rotation and scale, it will be quite simple.

The main idea is to encode the pattern in "native" coordinates, which is invariant under transformations.

enter image description here

Improve this answer

Comments

0

You can try a geohash. Translate the points to a binary and interleave it. Measure the distance and compare it with the original. You can also try to rotate the geohash, i.e. z-curve or morton curve.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.