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

-Raven

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

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.

Outline recognition systems work like this -

Find the edges of the shape (skip this if the shape is allredy made of lines).

Now you have a shape made out of lines / points.

You want each point around the shape to be about equal distance apart, so insert some more points along the lines if needs be.

Measure the angle from each point to the next point.

Assuming only 4 directions are used (N,S,E,W), then the following picture (drawn clockwise starting at the top left) -
+--+
| |
+--+

will give you E,E,E,S,S,W,W,W,N,N

you can then compare this string with a target string.

You also might have to come up with a way to shorten strings to the same length - this uses simmilar principles to resizing images.

This technique should be very suitable for recognising shapes drawn by a user using a continuous line.

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.

Quote: Original post by Steadtler
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 sensitive to noise.

When comparing strings, I dont mean strings as the text "N, S, E" and strcmp, etc...

The string might be something more like - 90º, 93º, 81º, 160º, 195º, 270º etc..

then if we're comparing to the shape 90, 90, 90, 180, 180, 270,
we get an error of - 0, 3, 9, 20, 15, 0
or an average error of ~8º per vertex which is low enough to assume the user was trying to draw that shape.
You can compare to several shapes and if the error is below a certain threshold then it is recognised as that shape.

Also if you know how to do bilinear filtering or something simmilar then you can resize shapes very easily too.

As for advantages over other techniques, im not sure.. as I just came across this technique when researching Content Based Image Retrieval systems. I think it was from a paper written back in the 60's

Quote: Original post by Steadtler
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.

Exactly :) ALWAYS use the right tool for the job. But depending on the number and complexity of shapes being recognised a NN may be a good design. Mucking around isn't a problem with neural nets for me, I run a program in the background of my computer for a few weeks and it spits out a pretty good solution at the end. It picks the neuron type, network topogogy, as well as adding in extra layers and neurons as required. I must admit I have a strong bias for neural nets though as I have a strong electrical background and they can easily be implemented in circuitry for use in robots. Lots of good ideas in this thead :)

Dave

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).