2D Shape recognition algorithm - looking for guidance

Question

I need the ability to verify that a user has drawn a shape correctly, starting with simple shapes like circle, triangle and more advanced shapes like the letter A.

I need to be able to calculate correctness in real time, for example if the user is supposed to draw a circle but is drawing a rectangle, my hope is to be able to detect that while the drawing takes place.

There are a few different approaches to shape recognition, unfortunately I don't have the experience or time to try them all and see what works.

Which approach would you recommend for this specific task?

Your help is appreciated.

Answer 1

We may define "recognition" as the ability to detect features/characteristics in elements and compare them with features of known elements seen in our experience. Objects with similar features probably are similar objects. The higher the amount and complexity of the features, the greater is our power to discriminate similar objects.

In the case of shapes, we can use their geometric properties such as number of angles, the angles values, number of sides, sides sizes and so forth. Therefore, in order to accomplish your task you should employ image processing algorithms to extract such features from the drawings.

Below I present a very simple approach that shows this concept in practice. We gonna recognize different shapes using the numbers of corners. As I said: "The higher the amount and complexity of the features, the greater is our power to discriminate similar objects". Since we are using just one feature, the number of corners, we can differentiate a few different kinds of shapes. Shapes with the same number of corners will not be discriminated. Therefore, in order to improve the approach you might add new features.

---

UPDATE:

In order to accomplish this task in real time you might extract the features in real time. If the object to be drawn is a triangle and the user is drawing the fourth side of any other figure, you know that he or she is not drawing a triangle. About the level of correctness you might calculate the distance between the feature vector of the desired object and the drawn one.

---

Input:

The Algorithm

1. Scale down the input image since the desired features can ben detected in lower resolution.
2. Segment each object to be processed independently.
3. For each object, extract its features, in this case, just the number of corners.
4. Using the features, classify the object shape.

The Software:

The software presented below was developed in Java and using Marvin Image Processing Framework. However, you might use any programming language and tools.

import static marvin.MarvinPluginCollection.floodfillSegmentation;
import static marvin.MarvinPluginCollection.moravec;
import static marvin.MarvinPluginCollection.scale;

public class ShapesExample {

    public ShapesExample(){
        // Scale down the image since the desired features can be extracted
        // in a lower resolution.
        MarvinImage image = MarvinImageIO.loadImage("./res/shapes.png");
        scale(image.clone(), image, 269);

        // segment each object
        MarvinSegment[] objs = floodfillSegmentation(image);
        MarvinSegment seg;

        // For each object...
        // Skip position 0 which is just the background
        for(int i=1; i<objs.length; i++){
            seg = objs[i];
            MarvinImage imgSeg = image.subimage(seg.x1-5, seg.y1-5, seg.width+10, seg.height+10);
            MarvinAttributes output = new MarvinAttributes();
            output = moravec(imgSeg, null, 18, 1000000);
            System.out.println("figure "+(i-1)+":" + getShapeName(getNumberOfCorners(output)));
        }
    }

    public String getShapeName(int corners){
        switch(corners){
            case 3: return "Triangle";
            case 4: return "Rectangle";
            case 5: return "Pentagon";
        }
        return null;
    }

    private static int getNumberOfCorners(MarvinAttributes attr){
        int[][] cornernessMap = (int[][]) attr.get("cornernessMap");
        int corners=0;
        List<Point> points = new ArrayList<Point>();
        for(int x=0; x<cornernessMap.length; x++){
            for(int y=0; y<cornernessMap[0].length; y++){
                // Is it a corner?
                if(cornernessMap[x][y] > 0){
                    // This part of the algorithm avoid inexistent corners
                    // detected almost in the same position due to noise.
                    Point newPoint = new Point(x,y);
                    if(points.size() == 0){
                        points.add(newPoint); corners++;
                    }else {
                        boolean valid=true;
                        for(Point p:points){
                            if(newPoint.distance(p) < 10){
                                valid=false;
                            }
                        }
                        if(valid){
                            points.add(newPoint); corners++;
                        }
                    }
                }
            }
        }
        return corners;
    }

    public static void main(String[] args) {
        new ShapesExample();
    }
}

The software output:

figure 0:Rectangle
figure 1:Triangle
figure 2:Pentagon