6

我正在寻找一些关于识别三种手写形状的建议——圆形、菱形和矩形。我尝试了不同的方法,但它们失败了,所以也许你可以为我指出另一个更好的方向。

我尝试了什么:

1)基于手写形状点与理想形状点之间的点积的简单算法。它在识别矩形方面效果不错,但在圆形和菱形上却失败了。问题是即使对于理想的形状,圆形和菱形的点积也非常相似。

2)相同的方法,但使用动态时间规整作为相似度的度量。类似的问题。

3)神经网络。我尝试了一些方法 - 将点数据提供给神经网络(前馈和 Kohonen)或提供光栅化图像。对于 Kohonen,它总是将所有数据(用于训练的样本事件)归为同一类别。带点的前馈更好(但与方法 1 和 2 处于同一水平),并且对于光栅化图像,它非常慢(我需要至少 size^2 输入神经元,对于小尺寸的光栅圆,即使对我来说也无法区分;))而且也没有成功。我想是因为所有这些形状都是封闭的数字吗?我不是 ANN 的大专家(有 1 个学期的课程)所以也许我用错了?

4)将形状保存为弗里曼链码,并使用一些算法计算相似度。我认为在 FCC 中,形状会彼此不同。这里没有成功(但我还没有深入探索这条路)。

我正在为此构建适用于 Android 的应用程序,但我认为该语言在这里无关紧要。

4

11 回答 11

6

这是形状分类器的一些工作代码。http://jsfiddle.net/R3ns3/我从以太中提取了阈值数字(代码中的*阈值变量),所以当然可以调整它们以获得更好的结果。

我使用边界框、子部分中的平均点、点之间的角度、边界框中心的极角和角识别。它可以对手绘矩形、菱形和圆形进行分类。代码在鼠标按下时记录点,并在您停止绘图时尝试分类。

HTML

<canvas id="draw" width="300" height="300" style="position:absolute; top:0px; left:0p; margin:0; padding:0; width:300px; height:300px; border:2px solid blue;"></canvas>

JS

var state = {
    width: 300,
    height: 300,
    pointRadius: 2,
    cornerThreshold: 125,
    circleThreshold: 145,
    rectangleThreshold: 45,
    diamondThreshold: 135,
    canvas: document.getElementById("draw"),
    ctx: document.getElementById("draw").getContext("2d"),
    drawing: false,
    points: [],
    getCorners: function(angles, pts) {
        var list = pts || this.points;
        var corners = [];
        for(var i=0; i<angles.length; i++) {
            if(angles[i] <= this.cornerThreshold) {
                corners.push(list[(i + 1) % list.length]);
            }
        }
        return corners;
    },
    draw: function(color, pts) {
        var list = pts||this.points;
        this.ctx.fillStyle = color;
        for(var i=0; i<list.length; i++) {
            this.ctx.beginPath();
            this.ctx.arc(list[i].x, list[i].y, this.pointRadius, 0, Math.PI * 2, false);
            this.ctx.fill();
        }
    },
    classify: function() {
        // get bounding box
        var left = this.width, right = 0, 
            top = this.height, bottom = 0;
        for(var i=0; i<this.points.length; i++) {
            var pt = this.points[i];
            if(left > pt.x) left = pt.x;
            if(right < pt.x) right = pt.x;
            if(top > pt.y) top = pt.y;
            if(bottom < pt.y) bottom = pt.y;
        }
        var center = {x: (left+right)/2, y: (top+bottom)/2};
        this.draw("#00f", [
            {x: left, y: top},
            {x: right, y: top},
            {x: left, y: bottom},
            {x: right, y: bottom},
            ]);
        // find average point in each sector (9 sectors)
        var sects = [
            {x:0,y:0,c:0},{x:0,y:0,c:0},{x:0,y:0,c:0},
            {x:0,y:0,c:0},{x:0,y:0,c:0},{x:0,y:0,c:0},
            {x:0,y:0,c:0},{x:0,y:0,c:0},{x:0,y:0,c:0}
            ];
        var x3 = (right + (1/(right-left)) - left) / 3;
        var y3 = (bottom + (1/(bottom-top)) - top) / 3;
        for(var i=0; i<this.points.length; i++) {
            var pt = this.points[i];
            var sx = Math.floor((pt.x - left) / x3);
            var sy = Math.floor((pt.y - top) / y3);
            var idx = sy * 3 + sx;
            sects[idx].x += pt.x;
            sects[idx].y += pt.y;
            sects[idx].c ++;
            if(sx == 1 && sy == 1) {
                return "UNKNOWN";
            }
        }
        // get the significant points (clockwise)
        var sigPts = [];
        var clk = [0, 1, 2, 5, 8, 7, 6, 3]
        for(var i=0; i<clk.length; i++) {
            var pt = sects[clk[i]];
            if(pt.c > 0) {
                sigPts.push({x: pt.x / pt.c, y: pt.y / pt.c});
            } else {
                return "UNKNOWN";
            }
        }
        this.draw("#0f0", sigPts);
        // find angle between consecutive 3 points
        var angles = [];
        for(var i=0; i<sigPts.length; i++) {
            var a = sigPts[i],
                b = sigPts[(i + 1) % sigPts.length],
                c = sigPts[(i + 2) % sigPts.length],
                ab = Math.sqrt(Math.pow(b.x-a.x,2)+Math.pow(b.y-a.y,2)),
                bc = Math.sqrt(Math.pow(b.x-c.x,2)+ Math.pow(b.y-c.y,2)),
                ac = Math.sqrt(Math.pow(c.x-a.x,2)+ Math.pow(c.y-a.y,2)),
                deg = Math.floor(Math.acos((bc*bc+ab*ab-ac*ac)/(2*bc*ab)) * 180 / Math.PI);
            angles.push(deg);                
        }
        console.log(angles);
        var corners = this.getCorners(angles, sigPts);
        // get polar angle of corners
        for(var i=0; i<corners.length; i++) {
            corners[i].t = Math.floor(Math.atan2(corners[i].y - center.y, corners[i].x - center.x) * 180 / Math.PI);
        }
        console.log(corners);
        // whats the shape ?
        if(corners.length <= 1) { // circle
            return "CIRCLE";
        } else if(corners.length == 2) { // circle || diamond
            // difference of polar angles
            var diff = Math.abs((corners[0].t - corners[1].t + 180) % 360 - 180);
            console.log(diff);
            if(diff <= this.circleThreshold) {
                return "CIRCLE";
            } else {
                return "DIAMOND";
            }
        } else if(corners.length == 4) { // rectangle || diamond
            // sum of polar angles of corners
            var sum = Math.abs(corners[0].t + corners[1].t + corners[2].t + corners[3].t); 
            console.log(sum);
            if(sum <= this.rectangleThreshold) {
                return "RECTANGLE";
            } else if(sum >= this.diamondThreshold) {
                return "DIAMOND";
            } else {
                return "UNKNOWN";
            }
        } else {
            alert("draw neater please");
            return "UNKNOWN";
        }
    }
};
state.canvas.addEventListener("mousedown", (function(e) {
    if(!this.drawing) {
        this.ctx.clearRect(0, 0, 300, 300);
        this.points = [];
        this.drawing = true;
        console.log("drawing start");
    }
}).bind(state), false);
state.canvas.addEventListener("mouseup", (function(e) {
    this.drawing = false;
    console.log("drawing stop");
    this.draw("#f00");
    alert(this.classify());
}).bind(state), false);
state.canvas.addEventListener("mousemove", (function(e) {
    if(this.drawing) {
        var x = e.pageX, y = e.pageY;
        this.points.push({"x": x, "y": y});
        this.ctx.fillStyle = "#000";
        this.ctx.fillRect(x-2, y-2, 4, 4);
    }
}).bind(state), false);
于 2013-12-03T13:16:55.517 回答
3

考虑到手写输入的可能变化,我建议采用神经网络方法。您会发现很难或不可能手动准确地对这些类建模。LastCoder 的尝试在一定程度上是可行的,但它无法应对太多的变化,或者如果进一步研究,它也有望获得高精度——这种手工设计的方法很久以前就被放弃了。

如今,手写字符分类的最新成果通常是通过卷积神经网络 (CNN)实现的。鉴于您只有 3 个类别,这个问题应该比数字或字符分类更容易,尽管根据MNIST手写数字数据集的经验,我预计您的圆圈、正方形和菱形有时可能最终甚至人类都难以区分。

所以,如果由我决定,我会使用 CNN。我将从绘图区域获取的二进制图像输入到网络的第一层。这些可能需要一些预处理。如果绘制的形状覆盖了输入空间的一个非常小的区域,您可能会受益于将它们放大(即增加线条粗细),以使形状对于小的差异更加不变。将图像中的形状居中也可能是有益的,尽管化步骤可能会减轻对此的需求。

我还要指出,训练数据越多越好。人们经常面临增加数据集大小和改进模型之间的权衡。综合更多示例(例如,通过倾斜、旋转、移动、拉伸等)或花几个小时绘制形状可能比您在尝试改进模型的同时获得的好处更多。

祝你的应用好运!

于 2013-12-03T17:30:23.550 回答
2

正方形或菱形的线性霍夫变换应该很容易识别。它们都将产生四点质量。正方形将成对出现在 0 度和 90 度处,两对的 y 坐标相同;换句话说,一个矩形。钻石将在其他两个角度对应于钻石的细度,例如 45 和 135,或者 60 和 120。

对于圆形,您需要一个圆形霍夫变换,它将在 3d (x,y,r) 霍夫空间中产生一个单一的亮点簇。

线性和循环霍夫变换都在 OpenCV 中实现,并且可以在 Android 上运行 OpenCV。这些实现包括识别线和圆的阈值。见第 4 页。329 和 pg。331的文档在这里

如果你不熟悉霍夫变换,维基百科页面也不错。

关于多边形相似性的这篇论文中给出了另一种您可能会觉得有趣且可能有用的算法。我多年前就实现了它,它仍然在这里。如果您可以将图形转换为向量循环,则该算法可以将它们与模式进行比较,并且相似性度量将显示匹配度。该算法忽略旋转方向,因此如果您对正方形和菱形的定义是相对于绘图表面的轴,您将不得不稍微修改算法以区分这些情况。

于 2013-12-06T04:21:47.800 回答
1

你在这里拥有的是一个相当标准的分类任务,在一个可以说是视觉领域。您可以通过多种方式做到这一点,但最好的方法是未知的,有时可能取决于问题的细节。

所以,这本身并不是一个答案,但有一个网站 - Kaggle.com 运行分类竞赛。他们列出的示例/实验任务之一是阅读单手写数字。这与这个问题非常接近,几乎可以肯定相同的方法会很好地应用。

我建议你去https://www.kaggle.com/c/digit-recognizer看看。

但是如果这太模糊了,我可以从我的阅读中告诉你,并使用那个问题空间,随机森林是比神经网络更好的基本起点。

于 2013-11-30T11:20:42.203 回答
1

在这种情况下(您的 3 个简单对象),您可以尝试 RanSaC 拟合椭圆(得到圆形)和线条(得到矩形或菱形的边) - 如果有多个对象同时分类,则在每个连接的对象上. 根据实际设置(预期大小等),必须调整 RanSaC 参数(点必须多接近才能算作选民,最少需要多少选民)。当您找到一条具有 RanSaC 拟合的线时,删除“靠近”它的点并转到下一条线。线条的角度应该很容易区分菱形和矩形。

于 2013-12-01T21:44:52.993 回答
1

我认为已经存在的答案是好的,但也许更好的思考方式是你应该尝试将问题分解成有意义的部分。

  1. 如果可能的话,完全避免这个问题。例如,如果您正在识别手势,只需实时分析手势即可。使用手势,您可以向用户提供有关您的程序如何解释他们的手势的反馈,并且用户将适当地改变他们正在做的事情。
  2. 清理有问题的图像。在你做任何事情之前,先想出一个算法来尝试选择你正在尝试分析的正确事物。在开始该过程之前,还可以使用适当的过滤器(也许是卷积)来去除图像伪影。
  3. 一旦你弄清楚你要分析的东西是什么,然后分析它并返回一个分数,一个代表圆,一个代表噪音,一个代表线,最后一个代表金字塔。
  4. 对下一个可行的候选者重复此步骤,直到找到非噪声的最佳候选者。

我怀疑你会发现你不需要复杂的算法来找到圆、线、金字塔,但更重要的是要适当地构造你的代码。

于 2013-12-07T01:48:15.033 回答
1

为准确分类这 3 个对象而优化的一种非常简单的方法可能如下:

  1. 计算要分类的对象的重心
  2. 然后计算中心到对象点的距离作为角度的函数(从 0 到 2 pi)。
  3. 根据平滑度和/或方差以及局部最大值和最小值的位置和高度(可能在平滑图之后)对结果图进行分类。
于 2013-12-01T21:49:07.670 回答
1

我建议按照以下步骤进行操作:-

  1. 取图像的凸包(考虑形状是凸的)
  2. 使用聚类算法划分为段
  3. 尝试对其拟合曲线或直线,并使用可用于分类的训练集测量和阈值
  4. 对于您的应用程序,请尝试分成 4 个集群。
  5. 一旦您将集群分类为直线或曲线,您就可以使用该信息来得出曲线是圆形、矩形还是菱形
于 2013-12-06T17:20:30.620 回答
0

如果我是你,我会使用已经可用的图像处理库,比如“AForge”。
看看这篇示例文章:
http ://www.aforgenet.com/articles/shape_checker

于 2013-12-05T15:25:54.607 回答
0

我最近通过识别医学图像中的圆圈(骨骼中心)来做到这一点。

注意:步骤 1-2 是从图像中抓取的。

伪代码步骤

步骤 1. 突出边缘
edges = edge_map(of the source image)(使用边缘检测器)
(外行:显示线条/边缘——使它们可搜索)

步骤 2. 跟踪
我会(使用最近邻搜索 9x9 或 25x25)来识别/跟踪/跟踪每条边,将每个点收集到列表中(它们成为邻居),并记下gradient每个点的每个唯一边。
这一步产生:一组边。
(其中一个edge/curve/line = list of [point_gradient_data_structure]s
(外行:沿图像边缘收集一组点)

步骤 3. 分析每条边(的点和梯度数据)
对于每条边,
如果给定区域/邻居集的梯度相似(沿边的一系列点),那么我们有一个straight line.
如果梯度逐渐变化,我们有一个curve.
直线或曲线的每个区域/点的运行都具有平均值(中心)和其他梯度统计信息。

第 4 步:检测对象
我们可以使用第 3 步中的摘要信息来得出关于菱形、圆形或正方形的结论。(即 4 条直线,其端点彼此靠近且具有适当的梯度,是菱形或正方形。一条(或多条)具有足够点/梯度(具有共同焦点)的曲线构成一个完整的圆)。

注意:使用 animage pyramid可以提高算法性能,包括结果和速度。

这种技术(步骤 1-4)可以完成定义明确的形状的工作,并且还可以检测绘制得不够完美的形状,并且可以处理稍微断开的线条(如果需要)。


注意:使用一些机器学习技术(其他海报提到),拥有良好的“分类器”以将问题基本上分解为更小的部分/组件可能会有所帮助/重要,因此链条更下游的决策者可以使用更好理解/“看到”对象。我认为机器学习在这个问题上可能有点笨拙,但仍然可以产生合理的结果。PCA(人脸检测)也可能起作用。

于 2013-12-07T11:10:32.663 回答
0

在 github 上有一个 jar,如果你愿意解压它并遵守 apache 许可证,它可以提供帮助。您也可以尝试用任何其他语言重新创建它。

它是一个边缘检测器。从那里最好的一步可能是:

  1. 找到角落(90度的中位数)
  2. 找到平均中位数和最大半径
  3. 从水平方向找到倾斜/角度
  4. 让决策代理决定形状是什么

玩弄它,找到你想要的。

我的罐子在这个地址向公众开放。它尚未准备好生产,但可以提供帮助。

只是觉得我能帮上忙。如果有人想成为该项目的一部分,请这样做。

于 2013-12-07T02:07:18.433 回答