Shape recognition

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

If you check with Google Scholar, the paper mentioned by MDI is also available for free download here.

-Raven

Quote:

Original post by Anonymous Poster You might also want to look into neural networks a bit. I got bored at uni one day and started training up a neural network to tell the difference between squares, circles, and rectangles. By the end of the class it was working fairly well. Just need to make sure you use the right sort of neurons and then the outputs from the network will provide weightings (3% circle, 70% square, 98% rectangle). One advantage of this method is it can be set up to learn as the program is used, and one downside is it may not be able to work efficiently for large numbers of shapes. Dave

Just...

That you can train a neural network to recognize basic shapes doesnt mean its a good idea. If you want to do automatic classification, which isnt bad in itself, use the right tool: a classification learning machine, not a regression scheme. A support vector machine would work perfect, its pretty much the state of the art in classification. And instead of juggling with network topology, you just have a few kernels to try to see which works best.

Original method AP, but I fail to see what is the advantage over a simple correlation, or over an edge orientation histogram comparison? Why the hassle of comparing strings? Seems to me this would be extremely sensible to noise.

I think Kylotan's idea about angles is a good one.

Find all possible angles in the figure. So any bend is an angle. Compute it's angle and let's say if it's bigger than 170 drop it. Keep searching for angles and store those that are less than 170. Add all of them up and find the closest real shape to it. If there are no angles it's a circle. If it's 180, it's a triangle. 360 - square. 540 - pentagon. And so on. I would think that if the shape decided upons was higher than oh let's say a decagon or maybe even an octogon, just assume it's a circle (prolly a really poorly drawn one).