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

Question

我正在编写一些代码，这些代码需要识别一些基于节点云的相当基本的几何图形。我有兴趣检测：

• 板（简单有界平面）
• 圆柱体（两个节点循环）
• 半圆柱（弧线+弧线+弧线+线）
• 圆顶（n*loop+顶部节点）

我尝试搜索“来自节点云的几何”、“从节点获取几何”，但我找不到很好的参考。这可能有一个完整的领域，有人可以指点我吗？我已经开始编写一些东西了，但我想重新发明轮子......

Answer 1

一个好的开始是使用Grahams 算法或QuickHull 获取节点的凸包（可以围绕节点云的最紧密拟合多边形） 。请注意，QuickHull 更容易编码并且可能更快，除非你真的很倒霉。这里有一个 QuickHull 的纯 python实现。但我确信快速谷歌搜索会显示许多其他结果。

通常凸包是大多数其他形状识别算法的起点，如果你的云可以描述为一系列笔画，那么有很多算法和方法：

识别多笔画几何形状：实验评估

这可能会更好，一旦你有了凸包，将多边形分解为顶点对并运行此算法以根据与训练数据的相似性进行匹配：

使用多边形逼近和动态对齐的分层形状识别

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

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

无论哪种方式，使用凸包算法从点云中生成多边形是第一步，通常会输入到更复杂的算法中。

编辑：

我没有考虑 3D 案例，因为他们在计算机图形学中有很多非常有趣的工作，都专注于这一点，例如这篇论文Efficient RANSAC for Point-Cloud Shape Detection

摘自摘要：

我们提出了一种自动算法来检测无组织点云中的基本形状。该算法将点云分解为一个简洁的、由固有形状和一组剩余点组成的混合结构。每个检测到的形状都充当一组对应点的代理。我们的方法基于随机采样并检测平面、球体、圆柱体、圆锥体和环面……我们证明了即使存在许多异常值和高度噪声的情况下，该算法也是稳健的……此外，该算法在概念上很简单并且易于实施...

Answer 2

为了补充 Josiah 的回答——因为你没有说在你的点云中是否有一个这样的对象被检测到——一个好的解决方案可以是使用（广义）霍夫变换。

这个想法是每个点都会在您正在考虑的形状的参数空间中投票给一组候选者。例如，如果您认为当前对象是一个圆柱体，那么您有一个 7D 参数空间，由圆柱体中心 (3D)、方向 (2D)、高度 (1D) 和半径 (1D) 以及点云中的每个点组成将投票给与该点观察一致的所有参数。这样做允许通过获取具有最高票数的参数集来找到实际圆柱体的参数。对平面、球体等做同样的事情，会给你最好的匹配形状。

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