
As part of the project I’m working on, I had to develop a system that recognizes and assesses the quality of a small number of shapes drawn with the mouse.
By choosing only shapes that could be easily defined mathematically, I was able to quickly code the recognition logic for each of them as special cases.
First, I convert the mouse gesture into a set of evenly spaced points. Then I figure out how well the points match all of the possible shapes using special case logic, and return that shape that fits best.
Here are some outlines of the algorithms I used:
Circle: * Calculate the average position of all the points and treat that as the center. * Calculate the average distance each point is away from the center and treat that as the radius. * Calculate the standard deviation of the distance of each point against the average distance. * Normalize the standard deviation against the average distance, and return that as the quality. One potential problem with this algorithm is that multiple identical circles drawn on top of each other will receive a high quality rating. To prevent this, you could figure out the circumference of the circle the user is trying to make and compare it against the number of points in the data set over the sampling rate. If the two values were approximately equal, you’d know you had a single circle.
Line: * Just run a linear regression on the points and return the R squared value (make sure your regression tests for actual distances from the line, not just vertical distances).
Triangles, Quadrangles, etc.: * Detect corners. I use a system where I basically go through each sample and compute the dot product between the vector pointing at the current sample from the previous one, and the vector pointing from the current sample at the next. If the dot product is low, that means the angle between the vectors is sharp, which means the sample is a corner. * The number of corners determines what kind of polygon you’re looking for (3=triangle, 4=quadrangle, etc.). * Finally, perform linear regressions on all of the lines between the corners. Return the average of the R squared values. Depending on what you’re going for, you may want to make sure that none of the lines between corners intersect before returning a high quality value.
5Sided Star: * Perform the above test for a pentagon. * The lines forming a star intersect in a certain way. Return the pentagon quality value if the lines forming the userinput shape intersect in that way. Return 0 otherwise.
I also did one for a spiral, but you get the idea.
The nice thing about this system is that it can recognize and differentiate the shapes pretty well, even if they are rotated are skewed. The big (potentially fatal) disadvantage is that all the shapes you use have to be procedurally defined, which limits the types of shapes you can recognize, and costs a nontrivial amount of time for each shape you add.
