Shape Recognition

Question

I need to implement a simple Android application that allows users to draw a "simple" shape (circle, triangle etc) on their phone and then ask a server if the drawn shape matches one of the shapes in its database, which consists of a low number of shapes (let's say < 100, but can be more). In order to make this application work, I was thinking to use the following steps (we assume that the input image consists only of black & white pixels);

A. re-size & crop the input image in order to bring it to the same scale as the ones in the DB

B. rotate the input image by a small angle (let's say 15 degrees) x times (24 in this case) and try to match each of these rotations against each shape in the DB.

Questions:

1. For A, what would be the best approach? I was thinking to implement this step in the Android application, before sending the data to the server.
2. For B, what would be a decent algorithm of comparing 2 black & white pixel images that contain only a shape?
3. Is there any better / simpler way of implementing this? A solution that also has an implementation is desirable.

PS: I can see that many people have discussed similar topics around here, but I can't seem to find something that matches my requirements well enough.

Answer 1

Machine learning approach

You choose some features which describe contours, choose some classification method, prepare a training set of tagged contours, train the classifier, use it in the program.

Contour features. Given a contour(detected in the image or constructed from the user input), you can calculate rotation-invariant moments. The oldest and the most well known is a set of Hu moments.

You can also consider such features of the contour as eccentricity, area, convexity defects, FFT transform of the centroid distance function and many others.

Classifiers. Now you need to train a classifier. Support Vector Machines, Neural Networks, decision trees, Bayes classifiers are some of the popular methods. There are many methods to choose from. If you choose SVM, LIBSVM is a free SVM library, which works also in Java, and it works on Android too.

Ad-hoc rule approach

You can also approximate contour with a polygonal curve (see Ramer-Douglas-Peucker algorithm, there is a free implementation in OpenCV library, now available on Android). For certain simple forms like triangles or rectangles you can easily invent some ad-hoc heuristic rule which will "recognize" them (for example, if a closed contour can be approximated with just three segments and small error, then it is likely to be a triangle; if the centroid distance function is almost constant and there are zero convexity defects, then it is likely to be a circle).