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...]
0
Shape recognition
Started by Son of Cain, Jun 22 2006 05:57 AM
17 replies to this topic
Sponsor:
#2 Members - Reputation: 220
Posted 22 June 2006 - 09:55 AM
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!
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!
#3 Members - Reputation: 247
Posted 22 June 2006 - 10:04 AM
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
#4 Members - Reputation: 480
Posted 22 June 2006 - 11:50 PM
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!
#5 Moderators - Reputation: 2959
Posted 23 June 2006 - 12:43 AM
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.
#6 Members - Reputation: 220
Posted 23 June 2006 - 05:44 AM
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.
#7 GDNet+ - Reputation: 1412
Posted 23 June 2006 - 12:26 PM
Quote: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).
Original post by Kylotan
[...]You may need to merge lines together where the change of direction between them is small[...]
#8 Members - Reputation: 220
Posted 23 June 2006 - 04:52 PM
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.
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.
#9 Members - Reputation: 266
Posted 23 June 2006 - 10:54 PM
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
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
#11 Members - Reputation: 127
Posted 24 June 2006 - 02:07 AM
If you check with Google Scholar, the paper mentioned by MDI is also available for free download here.
-Raven
-Raven
#12 Anonymous Poster_Anonymous Poster_* Guests - Reputation:
Posted 04 July 2006 - 02:11 PM
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
Dave
#13 Members - Reputation: 220
Posted 04 July 2006 - 03:22 PM
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.
#14 Anonymous Poster_Anonymous Poster_* Guests - Reputation:
Posted 04 July 2006 - 03:47 PM
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.
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.
#16 Anonymous Poster_Anonymous Poster_* Guests - Reputation:
Posted 04 July 2006 - 04:12 PM
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
#17 Anonymous Poster_Anonymous Poster_* Guests - Reputation:
Posted 04 July 2006 - 06:06 PM
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
#18 Members - Reputation: 146
Posted 05 July 2006 - 12:03 PM
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).
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).
