A good algorithm for finding subsets of point sets

Question

I am trying to find suitable algorithms for finding subsets of two-dimensional points in a larger set. An image is worth a thousand words, therefore:

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

It seems that the registration of a set of points [1] is the most difficult problem. I experimented with implementing CPD and other hard and soft algorithms, but they don't seem to be too good at finding small subsets in large sets of points.

Another approach may be to use star tracking algorithms, such as the angle method mentioned in [2], or more robust methods, such as [3]. But then again, they all seem to be designed for large input sets and target sets. I am 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 are some docs probably related to your question:

• The geometric correspondence of samples under the Euclidean motion (1993) L. Paul Chu, Michael T. Goodrich, Daniel P. Hattenlocher, Klara Kedem, John M. Kleinberg, Dina Kravets.
• Fast Expected Time Algorithm for Two-Dimensional Dot Pattern (2004) Wamelena, Iyengarb.
• Simple Algorithms for Matching Pairwise Point Dialing under Rigid Motion (2006) Bishnua, Dasba, Nandyba, Bhattacharyaba.
• Exact and approximate geometric correspondence of samples for sets of points in the plane during similarity transformations (2007) by Aiger and Kedem.

and by the way, your last link reminded me:

• Application of the correspondence of a point pattern in astronautics (1994) by G. Weber, L. Noping and H. Alt.

Answer 2

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

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

I think you can also try to match a subset of the three input points, knowing that the angles of the triangle will be invariant with respect to scaling and rotation.

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

Answer 3

I would try the Iterative Nearest Clause algorithm. A simple version, such as the one you need, should be easy to implement.

Answer 4

Look at geometric hashing . It allows you to find geometric patterns in various transformations. If you use only rotation and scale, it will be quite simple.

The main idea is to encode the template in "native" coordinates, which is invariant with respect to transformations.

Answer 5

You can try geohash. Translate the dots into binary code and move it. Measure the distance and compare it with the original. You can also try to rotate geohash, i.e. Curve z-curve or curve.