2D Shape recognition algorithm - looking for guidance [closed]

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.

Adahadaha

Could you add some sample data? – Greenish

@nikie not sure I understand what you mean, but if you're asking if I can supply the program data, then sure. – Adahadaha

Related question #22876851 – Lanellelanette

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

Irreversible

I have a question based your code. Would it be possible to take a look here: #52549993 ? – Stanford

Answer 2

The other way is you can use math with this problem using the average of each point that are smallest distance from the one your'e comparing it from, first you must resize shape with the ones in your library of shapes and then:

      function shortestDistanceSum( subject, test_subject ) {

         var sum = 0;

         operate( subject, function( shape ){

            var smallest_distance = 9999;

            operate( test_subject, function( test_shape ){
                var distance = dist( shape.x, shape.y, test_shape.x, test_shape.y );

                smallest_distance = Math.min( smallest_distance, distance );
            });

            sum += smallest_distance;

        });

            var average = sum/subject.length;

            return average;
       }

       function operate( array, callback ) {
          $.each(array, function(){
              callback( this );
          });
       }

       function dist( x, y, x1, y1 ) {
            return Math.sqrt( Math.pow( x1 - x, 2) + Math.pow( y1 - y, 2) );
        }

        var square_shape = Array; // collection of vertices in a square shape
        var triangle_shape = Array; // collection of vertices in a triangle
        var unknown_shape = Array; // collection of vertices in the shape your'e comparing from

        square_sum = shortestDistanceSum( square_shape, unknown_shape );
        triangle_sum = shortestDistanceSum( triangle_shape, unknown_shape );

Where the lowest sum is the closest shape.

Maturate

Is it possible to get isomorphism with an approach like this? For example, recognizing a diamond as a square? – Yuki

Nope, it depends on the vertices and initial position, a circle would be likely to match a diamond than a square, unless you tilt the diamond at a right angle first to match the square – Maturate

Answer 3

You have two inputs - the initial image and the user input - and you are looking for a boolean outcome.

Ideally you would convert all your input data to a comparable format. Instead, you could also parameterize both types of input and use a supervised machine learning algorithm (Nearest Neighbor comes to mind for closed shapes).

The trick is in finding the right parameters. If your input is a flat image file, this could be a binary conversion. If user input is a swiping motion or pen stroke, I'm sure there are ways to capture and map this as binary but the algorithm would probably be more robust if it used data closest to the original input.

Unlikely