Good algorithm for finding subsets of point sets

Question

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

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

Answer 1

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.

Answer 2

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.