Re^2: Interesting problem fitting points to a template (algorithm?)

I like this solution because it is simple and clever, but the three problems that I see (and I may be wrong) are as follows:

1. I have seven vertices making up a 2d shape, this shape may have suffered rotational and translational displacement. I have a rough idea of the maximum displayment, so I look at a given size ROI around where the points would be with no displacement. After discriminating the noise for size of points I am usually left with 1-2 possible points (not bad), but I have seen as many as twelve. So looking at a worse case (but very possible), if I am left with 10 points in each ROI, then starting with one ROI and working through each set of points I have 10^7 possible geometric objects that roughly look like my template. lots of checks....

2. The distance between the points in the ROI << then the distance to the calculated centroid, so I am concerned about the ability to consistantly choose the seven correct points and not seven almost true points (similar to what you were saying about infinite number of shapes containg the same centroid). In your example it only looks at rotational displacement, there will be translation displacement, but that is easily delt with looking at the relative distances from the points to the centroid....so still valid.

3. What if the ROI contains points, but does not contain the True point?

This does give me some thoughts that I will work through. I am going to take all of the suggestions, try to hash something out in the next couple of days, and repost what I have done.

Cameron

Comment on Re^2: Interesting problem fitting points to a template (algorithm?)

Replies are listed 'Best First'.
Re^3: Interesting problem fitting points to a template (algorithm?) by tachyon (Chancellor) on Oct 06, 2004 at 23:06 UTC
The method copes fine with 360 degrees of rotation or any ammount x-y translation (there is an even an example of that). This is simple a function of mapping from 2D to 1D space. In one dimensional space the concepts or rotation and x-y tranlation simply have no meaning. However the method shown relies on having all the points, no extra points and no missing points. This is because it is using the centriod to create the vector. A single missing or additional point will result in a different centroid, and vastly different vector. It is not clear what the real problem you are dealing with is. Curious? It seems now that missing and additional points are an issue. If so you can modify the method as follows. Without an accurate centroid we must choose one (or more) arbitrary points to use for our 2D->1D mapping. You could choose x_min, or y_min or any other arbitrary point but given templates with ~ 10 points I would just choose all of them in sequence, ie arbitratily declare each point the 'centroid' in turn and calculate the 1D distance mapping vector as before. Insert this data into some sort of easy lookup hash structure. You probably won't need the sort anymore which is O(logn) anyway. You now have all 10 possible 1D mappings of your template object from every possible point, thus rotation, translation, and added/missing points are not an issue. For any given point set you can rapidly check that sets correlation against all the templates in O(n) time. I will be interested to hear how you get on. cheers tachyon	[reply]

Replies are listed 'Best First'.

Re^3: Interesting problem fitting points to a template (algorithm?)
by tachyon (Chancellor) on Oct 06, 2004 at 23:06 UTC

The method copes fine with 360 degrees of rotation or any ammount x-y translation (there is an even an example of that). This is simple a function of mapping from 2D to 1D space. In one dimensional space the concepts or rotation and x-y tranlation simply have no meaning.

However the method shown relies on having *all* the points, no extra points and no missing points. This is because it is using the centriod to create the vector. A single missing or additional point will result in a different centroid, and vastly different vector.

It is not clear what the real problem you are dealing with is. Curious? It seems now that missing and additional points are an issue. If so you can modify the method as follows.

Without an accurate centroid we must choose one (or more) arbitrary points to use for our 2D->1D mapping. You could choose x_min, or y_min or any other arbitrary point but given templates with ~ 10 points I would just choose all of them in sequence, ie arbitratily declare each point the 'centroid' in turn and calculate the 1D distance mapping vector as before. Insert this data into some sort of easy lookup hash structure. You probably won't need the sort anymore which is O(logn) anyway. You now have all 10 possible 1D mappings of your template object from every possible point, thus rotation, translation, and added/missing points are not an issue. For any given point set you can rapidly check that sets correlation against all the templates in O(n) time.

I will be interested to hear how you get on.

cheers

tachyon

[reply]