Hi, Can anyone recommend me some papers on shape recognition? I have to implement it in a game - the player draws either a triangle, square or a circle shape in orthogonal projection, and the game must recognize which pattern was drawn. I'm also interested in how I could measure the accuracy of the drawing. I'll show the player a sketch of the pattern he must draw, and he scores diferent results depending on how well he can perform the drawing. Thanks in advance, Son Of Cain {edit: ugly typos...]

Simple idea, assuming no rotation: Take a perfect shape as a reference. Detect the enclosing box of the drawing, and re-scale the reference shape to the same size. Then, for each pixel of the drawing (or a subset of pixels), compute the distance to the closest part of the reference shape.

Then, you can use the total sum of distance as a criterion to determine which shape was drawn, and evaluate the accuracy of the drawing.

If not, there are two most popular classes of image recognition scheme.
The first one is correlation. pretty straight-forward.

The second one is using a registration of detected features. Most often, those features are corners, because corners are invariants. Check out the Kanade-Lucas-Tomasi paper. Sadly, it doesnt work on circles ;) But circles are easiest to detect with correlation.

Good luck!

Quote: Original post by Son of Cain
the player draws either a triangle, square or a circle shape in orthogonal projection, and the game must recognize which pattern was drawn.

You want shape recognition or gesture recognition?

For gesture recognition I know nothing but for shape/pattern recognition in an image maybe I can help. I don't know any papers though...

JFF

Gesture recognition. But I narrowed it to shape recognition because I was hoping to analyze the image outputted by the player's gestures.

@Steadtler: Thank you for the tip, I think it might work! About the classes of image recognition, the second class you mentioned uses a statistical approach, doesn't it?

Thanks again!

Sorry, no paper recommendations. But with gesture recognition, I would attempt to work out where the straight lines were, then check the relative angles between them to determine what sort of shape has been formed. You may need to merge lines together where the change of direction between them is small, and perform rounding on the vertices to give you a closed shape.

Quote: Original post by Son of Cain

About the classes of image recognition, the second class you mentioned uses a statistical approach, doesn't it?

KLT? I dont think so... Certainly not for the corner detection, which is just Harris's method revisited in order to use a single threshold. In your case, you dont need to use their registration. Since you would have a fairly low number of corners to match, brute force will work just right.

Quote: Original post by Kylotan
[...]You may need to merge lines together where the change of direction between them is small[...]

The function you want to perform is data clustering(on the deltas between recorded mouse positions, perhaps?), and then create a line from the first (in temporal order) and last point in each group (associating each point with the delta generated using it and the next{temporal order again} point).

Here is a simple clustering method for your problem, if you want to to it by gesture recognition:

For each mouse hit, take the orientation between this point and the previous. Make an histogram of those orientation.

For the triangle, you will have 3 big spikes on the histogram.
For the rectangle, you will have 4 big spikes.
For the circle, you will have a roughly flat histogram.

Quality can be evaluated by the sharpness of the spikes, or the flatness, in case of the circle.

Computer vision is fun.

If you want shape recognition, use the algorithm presented in this paper: A new shape transformation approach to handwritten character recognition.

It also gives a "score" as to how close to an idealised shape a particular example is. I've implemented the algorithm (for handwriting recognition) - it's simple but effective (~75% recognition rate on purposefully distorted character samples, it should be fine for simple shapes).

HTH

Thank you guys for all the help! It certainly seems easier than what I first thought it would be (yes, now it starts to sound possible for me to do it =).

Son Of Cain