Fork me on GitHub
Math for the people, by the people.

User login

Simple pattern recognition --- find a particular polygon on ...

Primary tabs

Simple pattern recognition --- find a particular polygon on ...

Hi folks,

I'm processing hundreds of "dot clouds" (i.e. a list of (x, y) coords.) for a very simple pattern recognition. The clouds are takes from an instrument which records the location of objects (imagining taking a photo of a lot of stars). The objects do not change their places but the *instrument* does. Hopefully, the instrument only does translational movements on the plane perpendicular to its line of view, and only negligible rotation/zooming/distortion is present. Now I have a "template" which records a few reference points' positions, and I try to find these points "amid the crowd of stars" by using their relative positions/configurations.

Of course I can try the brute-force search but there are caveats:
* The measurements contain errors, both random error and optical aberration, even bogus points when there really weren't anything.
* The instrument is not very reliable. One or a few of the targets may be shifted out of the Field of View.
* The "template" is sparse while the "clouds" are crowded. If there are more than one group of matching objects, all of them should be found.

I think this is not quite a big algorithm challenge, but I'm not familiar with this kind of problems. I don't know where to get started. If you have links, search keywords or any related ideas, I would be very glad to hear from you.

Thanks in advance.


In case you find my post ambiguous (I'm not a native speaker), here is a metaphor which may help you understand the problem:

In the day, you are given a map of a few stars and you somehow remember it. In the night, you are out to look at the real sky without the map. The problem is that your memory is not exact, your may have illusions, and you see a lot more stars than the map has, among them may be fireflies, light bubbles, or satellites. And the only information you can make use of is the position (not color/brightness/etc). And unfortunately, there may be trees in your field of view blocking the light.

Now your task is to identify which of them are the stars shown on the map.

Subscribe to Comments for "Simple pattern recognition --- find a particular polygon on ..."