3

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.

Mihai Todor
  • 8,014
  • 9
  • 49
  • 86
  • 1
    Hi, try this solved SOF: http://stackoverflow.com/questions/11424002/how-to-detect-simple-geometric-shapes-using-opencv – Abid Rahman K Aug 04 '12 at 12:36

3 Answers3

3

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

sastanin
  • 40,473
  • 13
  • 103
  • 130
  • P.S. It is better to keep user input in vector form (as a sequence of points), if you choose to work with contours. There are contour extraction algorithms (one is implemented in OpenCV library), but you can avoid this pass and keep the raw input data. – sastanin Jul 27 '12 at 21:24
  • Thank you for taking the time to provide me with so many options. I'll work on this during the next week and I'll see how it goes. I'll try some simple heuristic approaches first, based on your suggestions, and if the results will be dissapointing, I'll give libsvm a try, since I've used it before. – Mihai Todor Jul 27 '12 at 21:27
  • @MihaiTodor I usually experiment with OpenCV, libsvm and Python on a PC, to find the method and features which work best, and then just put the trained model in the Android resources, and only calculate the same features in Java. – sastanin Jul 27 '12 at 21:33
1

Since this is very much related to hand writing recognition, you can use a simple hmm algorithm to compare shapes with pre-learnt db.

But for a much simpler approach you can detect the corners in the image and then count the corners to detect shapes.

The first approach can be used for any complicated shapes and the second only suits basic shapes.

codetiger
  • 2,650
  • 20
  • 37
1

You can use a supervised learning approach. For the problem you are trying to solve I think simple classifiers like Naive Bayes, KNN, etc. should give you good results.

You need to extract features from each of the images. For each image you can save the them in a vector. Lets call it the feature vector. For the images you have in your database you already know the type of shape so you can include the id of the type in the feature vector. This will serve as the training set.

Once you have your training set, you can train your classifier and every time you want to classify a new shape you just get its feature vector and use it to query the classifier.

I recommend you to use scale and size invariant features, so you will not have to re-size each image and you just need to compare it once instead of rotating it.

You can do a quick search for Scale/Rotate invariant features and try them.

Enrique
  • 9,920
  • 7
  • 47
  • 59