Quadrilateral of Best Fit

[rp181]

Our team is attempting to have functioning vision. At this point, we have an algorithm to detect blobs, compute the convex hull of the blobs, and calculate the area score and AR score.

Assuming I can pick out which polygon represents the square, how do I go about extracting the 4 corners of it? The computed polygon has around 20 vertices every time, and in order to do the necessary calculations, I need the 4 vertices of a quadrilateral that best describes the shape.

How would i go about this?

[theprgramerdude]

Assuming your computed polygon actually is a quadrilateral, and the larger number of vertices is simply due to slight camera error, you could run an algorithm that groups nearby vertices into a single point, creating 4 points that are a rough quadrilateral.

[CodeYeti]

I guess you could check the angle between each of the vertices and cherrypick out the vertex with the angle closest to 180 and repeat until there are only 4 vertices left. Just an idea though. I haven't actually tried that.

[EricVanWyk]

I think it will be easier to find a solution if you think in terms of slope and intercept, instead of x and y.

This might help (or terrify): http://www.cse.unr.edu/~bebis/CS791E...esentation.pdf

[Greg McKaskle]

One of the things you might attempt is to visit the vertices and connect lines that almost touch and are almost the same slope. This will eliminate collinear line segments.

Years ago I implemented some decimation routines for a pen plotter. The algorithm involved looking at a progression of points and determining if they were within an error cone that extended from the first point. The purpose was to only transmit the points needed to draw the shape and leave out the points that barely wiggled the pen or were just segments of a straight line.

To find a corner, a similar routine could identify points roughly shared between two segments where the angle is between say 60 and 120 degrees.

Finally, while this will help to eliminate collinear points, you will then want to determine if it is a quadrilateral. Sounds like a fun challenge.

Greg McKaskle

[rp181]

I think eliminating co-linear segments and certain vertices is the hint I needed. After that, I believe looking at the angles will work.

I tried to simply measure the angle between points and pick the best one, but it was almost good. I believe the jaggedness of the line resulted in a false positive. If two points are very close and differ by a small amount, the angle gets very steep very quickly, with resolution limited by the pixels.

Has anyone else gotten good vision tracking in Java done? Another problem we are finding is an excessive glare, making the target unrecognizable. Hopefully, it will be different with competition lighting (very low ceilings in our build space).

[Greg McKaskle]

Can you share the images with the glare? I'd love to give it a shot.

Greg McKaskle