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

Question

我正在编写一些代码，需要从节点云中识别一些基本的几何形状。我有兴趣检测：

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

我尝试搜索“从节点云获取几何形状”，“从节点获取几何形状”，但找不到一个好的参考资料。可能整个领域都在研究这个问题，有人能指点一下吗？我已经开始编写代码了，但感觉自己是在重复发明轮子...

- Mac

Answer 1

一个好的开始是获取凸包（能够围绕节点云最紧密适配的多边形），使用Graham算法或QuickHull。请注意，除非你真的很不幸，否则 QuickHull 更容易编写且可能更快。这里有一个纯 Python QuickHull的实现。但我相信快速的谷歌搜索将显示许多其他结果。

通常，凸包是大多数其他形状识别算法的起点，如果您的云可以描述为一系列笔画，则有许多算法和方法： 识别多笔画几何形状：实验评估 一旦您拥有凸包，可以将多边形分解为顶点对，并根据与训练数据的相似性运行此算法进行匹配，这可能会更好：

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

这两篇论文都相当古老，因此您可以使用Google学术查看谁引用了这些论文，从而获得一个很好的文献路径来尝试解决这个问题。

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

无论如何，使用凸包算法将点云生成多边形是非常基本的第一步，通常是更复杂算法的输入。

编辑：

我没有考虑3D情况，对此，在计算机图形学领域有很多非常有趣的工作专注于此，例如这篇论文用于点云形状检测的高效RANSAC。

选自摘要：

我们提出了一种自动算法，用于检测无序点云中的基本形状。该算法将点云分解为固有形状和一组剩余点的简洁混合结构。每个检测到的形状作为相应点集的代理。我们的方法基于随机采样，可以检测平面、球体、圆柱体、圆锥体和环面... 我们证明该算法即使在存在许多离群点和高噪声程度的情况下也很鲁棒 ...此外，该算法概念简单，易于实现...

- Josiah Hester

Answer 2

为了补充Josiah的回答——因为你没有说你的点云中是否只有一个这样的对象需要检测——一个好的解决方案是使用（广义）Hough transform。

这个想法是每个点将为你正在考虑的形状的一组候选参数投票。例如，如果你认为当前对象是一个圆柱体，你有一个由圆柱体中心（3D）、方向（2D）、高度（1D）和半径（1D）组成的7D参数空间，你的点云中的每个点都将为与该点观察相符的所有参数投票。这样做可以通过取得到最高票数的参数集来找到实际圆柱体的参数。 对于平面、球体等进行同样的操作，将会给出最佳匹配的形状。

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

- nbonneel