手绘图形识别方法（算法）_手绘图形识别方法(算法)

          本文所讲的内容已经开源，你可以在 这里 找到源代码。 

---

        一些工具软件有手绘图形功能，手画一个三角形、平行四边形，虽然画的歪歪扭扭，但是工具内部能够自动转换为数字化的几何图形。

        然而，这部分功能很少有开源代码，网上也找不到相关的算法说明，所以只能自己尝试实现。但是几个月来，一直没有一个完整的思路。

        前几天，突然发现 OpenCV 的一个函数 approxPolyDP，它能将一个曲线，转换为一个多边形（近似拟合）。

        其中的原理也很简单，就是计算所有点到起点、终点连线的距离，如果最大值超过一个设定值，就以最大值对应的点分割曲线，然后分别在两段曲线中递归上述算法；如果最大值不超过设定值，那么上述连线就是结果多边形的一部分。

        有了上面这个算法工具，实现手绘图形识别的思路，就豁然开朗了。

关键思路

        如果输入是一张图片，那么需要先二值化（cv2.threshold），然后寻找轮廓（cv2.findContours），得到一个曲线（离散点）。

        如果是实时手绘（画笔），那么就是收集到一系列坐标点。

        将上面的一系列坐标点，用 approxPolyDP 近似为一个多边形。

        判断多边形首位是否相接，必须相接才能继续。

        根据多边形的边数，可以确定作为结果的几何图形是三角形、四边形，五边形 .......，如果边数 >=8，一般就可以认为是圆形（椭圆）了。

算法细节

        关于 approxPolyDP  的设定距离阈值，可以用曲线长度的 1% 作为经验值。不同比例值的实验的效果是：

        1%：手绘时需要比较认真，手必须稳定，算法的抗抖动性不强

        2%：比较适中，绘图时可以稍微随意些，但是绘制圆形要小心，不是太圆的话，可能处理后的多边形会少于 8 条边

        3%：明明画的弯弯的也变成直边了

特殊几何图形识别

        识别出一些特殊的图形，比如直角三角形，长方形等等，而不是普通的三角形、四边形。

        识别这些特殊图形，主要依赖各条边的长度，各个顶角的度数。

特殊三角形

• 等边三角形

        三条边相等，近似条件，边长两两之间的比例（短的:长的）都大于 0.9

• 等腰三角形

        边长两两之间的比例，有一个超过 0.9

• 等腰直角三角形

        边长两两之间的比例，有一个超过 0.9，且两边的夹角的 cos 值小于 0.15（大于 81°）

• 直接三角形

        有一个顶角的 cos 值小于 0.15（81°）

特殊四边形

• 平行四边形

        两条对边都平行，方向矢量的夹角 cos 小于 -0.95 （反方向小于 11°）

• 长方形

        在平行四边形的基础上，四个顶角中 cos值最大的一个小于 0.15（大于 81°）

• 正方形

        在长方形的基础上，一个相对边的长度和与另一个对边的长度和的比例大于 0.9

• 菱形

          在平行四边形的基础上，两个相邻边的长度比例大于 0.9

• 梯形

        有一个对边平行，方向矢量的夹角 cos 小于 -0.95 （反方向小于 11°）

• 直角梯形

        在梯形的基础上，四个顶角中 cos 值最小的一个小于 0.1（大于 84°），且与另一个平行线的夹角的 cos 值也小于 0.1（大于 84°）

• 等腰梯形

        在梯形的基础上，非平行的一对边的边长比例大于 0.9

特殊多边形

        边数大于等于 5，小于8，正多边形。一般手绘只能绘制五条边，但是这里面有一个特殊的：那就是五角星。

        判断是正多边形，可以用里面两个条件：

• 最小边长与最大边长的比例大于 0.7
• 最小夹角与最大的差小于 20°

        另外，正多边形有不同 Span 的区别，比如五角星是正五边形（Span = 2）。怎么计算 Span 呢？

• 先计算中心点，即所有点的平均值
• 计算所有以中心点为顶点，中心点到两个相邻点为边的角的角度
• 角度的和是 360° 的多少倍，Span 就是多少

椭圆（圆形）

        椭圆需要计算出中心点和长短轴的长度。用下面的方法（如下图）：

•  取任意边作为投影轴（它的垂线作为另一个投影轴）
• 计算所有顶点在投影轴的位置，位置范围形成一个包围长方形
• 长方形的长短边长即椭圆的长短轴的长度
• 长方形的中心点就是椭圆的中心点
• 取所有边作为投影轴时，长短轴的长度比最大的

        如果椭圆的长短轴的长度的比例大于 0.8，就作为圆处理，圆的半径是长短轴的长度的平均值。