从节点云中查找几何图形（形状）

Question

我正在研究一些需要识别基于节点云的基本几何图形的代码。我将有兴趣检测：

• 板（简单有界平面）
• 汽缸（2个节点环路）
• 半圆柱体（圆弧+线+圆弧+线）
• 圆顶（N *循环+顶部节点）

我试着搜索“从节点云的几何”，“从节点获取几何”，但我无法找到一个很好的参考。这可能是一个完整的领域，有人可以指点我吗？我已经开始编码的东西，但我觉得我重新发明轮子...

Answer 1

一个良好的开端是刚刚得到的凸包（最紧密配合多边形，可以围绕你的节点云）节点，请使用Grahams algorithm或QuickHull。请注意，QuickHull编码更容易，速度可能更快，除非你非常不走运。有一个纯python implementation of QuickHull here.但我敢肯定，一个快速的谷歌搜索将显示许多其他结果。

一般的凸包是大多数其他形状识别的算法的起点，如果云可以被描述为笔划的顺序，有许多算法和方法：

Recognizing multistroke geometric shapes: an experimental evaluation

这可能是更妙的是，一旦你有凸包，多边形分解到顶点对并运行此算法的匹配基于对相似的训练数据：

Hierarchical shape recognition using polygon approximation and dynamic alignment

这两篇论文都相当陈旧，所以你可以使用谷歌学者来查看谁引用了这些论文，并且在那里你有一个很好的文学尝试来解决这个问题。

有许多不同的方法和方法，这在文献中已得到很好的研究，你采用的方法实际上取决于你希望达到的精度水平以及你想要识别的形状的数量，以及您的输入数据集。

无论哪种方式，使用凸包算法，以产生多边形出点云的是第一个步骤，通常输入到更复杂的algorithmms。

编辑：

我没有考虑3D情况下，他们是很多计算机图形非常有趣的工作，一直专注于这一点，例如本文Efficient RANSAC for Point-Cloud Shape Detection

选择从摘要：

我们提出了一种自动算法来检测基本SHA在无组织的点云中。该算法将点云分解为固有形状和一组剩余点的简明混合结构。每个检测到的形状用作一组对应点的代理。我们的方法基于随机采样并检测平面，球体，圆柱体，圆锥体和圆锥体...我们表明，该算法是鲁棒的，即使在许多异常值的存在和高度的噪音......此外，该算法概念简单，易于实现...

Answer 2

为了补充约西亚的答案 - 因为你没有说出你的点云中是否有一个这样的对象被检测到 - 一个好的解决方案可以是使用（广义的）Hough transform。

这个想法是，每个点都会投票选出你正在考虑的形状参数空间中的一组候选人。例如，如果您认为当前物体是一个圆柱体，则会有一个由圆柱体中心（3D），方向（2D），高度（1D）和半径（1D）组成的7D参数空间以及点云中的每个点将投票赞成所有与这一观察结果相一致的参数。这样做可以通过获取具有最高票数的一组参数来查找实际气缸的参数。 为飞机，球体等做同样的事情，会给你最好的匹配形状。

这种方法的优点是它允许多个对象在同一个点云中。