2D形状识别算法 - 寻求指导

Question

我需要能够验证用户正确地绘制了一个形状的能力，从简单的形状比如圆形、三角形，到更高级的形状比如字母A。

我需要能够实时计算正确性，例如如果用户应该画一个圆形但是却在画一个矩形，我的希望是能够在绘图过程中检测到这一点。

对于形状识别，有几种不同的方法，不幸的是我没有经验或时间来尝试它们并看看哪个有效。

您会为这个特定任务推荐哪种方法？

感谢您的帮助。

- Aviran

---

你能添加一些样本数据吗？ - Niki

@nikie，不太确定我理解你的意思，但如果你在问我是否可以提供程序数据，那当然可以。 - Aviran

相关问题 https://dev59.com/Dn7aa4cB1Zd3GeqPpmad#22876975 - Adrian

Answer 1

我们可以将“识别”定义为检测元素中的特征/特性并将其与我们经验中看到的已知元素的特征进行比较的能力。具有相似特征的对象可能是相似的对象。特征数量和复杂度越高，我们区分相似对象的能力就越大。

在形状的情况下，我们可以使用它们的几何属性，例如角数，角度值，边数，边长等。因此，为了完成您的任务，您应该使用图像处理算法从绘图中提取这些特征。

以下是一个非常简单的方法，展示了这个概念的实际应用。我们将使用角落数来识别不同的形状。正如我所说：“特征数量和复杂度越高，我们区分相似对象的能力就越大”。由于我们只使用了一个特征，即角数，因此我们可以区分一些不同种类的形状。具有相同角数的形状将不被区分。因此，为了改进这种方法，您可以添加新的特征。

---

更新：

为了在实时环境中完成此任务，您可以实时提取特征。如果要绘制的对象是三角形，而用户正在绘制其他图形的第四边，那么您就知道他或她没有绘制三角形。关于正确性水平，您可以计算所需对象的特征向量与所绘制对象之间的距离。

---

输入：

算法

1. 缩小输入图像，因为可以在较低分辨率下检测到所需特征。
2. 独立地处理每个要处理的对象段。
3. 对于每个对象，提取其特征，在这种情况下仅是角数。
4. 使用这些特征对对象形状进行分类。

软件：

下面呈现的软件是用Java开发的，并使用Marvin图像处理框架。但是，您可以使用任何编程语言和工具。

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();
    }
}

软件输出：

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

- Gabriel Archanjo

---

我有一个基于你的代码的问题。能否在这里看一下：https://stackoverflow.com/questions/52549493/2d-geometric-shape-vertices-coordinates-detection？ - gammay

Answer 2

另一种方法是，您可以使用数学来解决这个问题，使用与正在比较的点最小距离的每个点的平均值， 首先，您必须将形状与库中的形状进行调整，然后：

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

最小和是最接近形状的。

- PauAI

---

像这样的方法是否可以获得同构？例如，将钻石识别为正方形？ - ophilbinbriscoe

不，这取决于顶点和初始位置，一个圆形更可能与钻石匹配而不是正方形，除非你先将钻石旋转90度以匹配正方形。 - PauAI

Answer 3

你有两个输入 - 初始图像和用户输入 - 你正在寻找一个布尔结果。

理想情况下，你应该将所有的输入数据转换为可比较的格式。或者，你也可以对两种类型的输入进行参数化，并使用监督机器学习算法（最近邻算法适用于封闭形状）。

关键在于找到正确的参数。如果你的输入是一个平面图像文件，这可能是一个二进制转换。如果用户输入是滑动手势或笔画，我相信有方法可以捕捉和映射这些数据为二进制，但如果它使用最接近原始输入的数据，算法可能会更加稳健。

- freekvd