python - 从节点云中查找几何(形状)

Question

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

• 板(简单有界平面)
• 圆柱体(两个节点循环)
• 半圆柱(圆弧+直线+圆弧+直线)
• 圆顶(n*loop+top node)

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

Answer 1

一个好的开始是只获取节点的凸包(可以围绕您的节点云的最紧密的拟合多边形)，使用 Grahams algorithm或 QuickHull .请注意，QuickHull 更易于编码，而且可能速度更快，除非您真的很倒霉。有一个纯python implementation of QuickHull here.但我敢肯定，快速的 Google 搜索会显示许多其他结果。

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

Recognizing multistroke geometric shapes: an experimental evaluation

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

Hierarchical shape recognition using polygon approximation and dynamic alignment

这两篇论文都相当古老，因此您可以使用 google scholar 查看谁引用了这些论文，并且您可以找到解决该问题的尝试的很好的文献线索。

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

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

编辑:

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

摘自摘要:

We present an automatic algorithm to detect basic shapes in unorganized point clouds. The algorithm decomposes the point cloud into a concise, hybrid structure of inherent shapes and a set of remaining points. Each detected shape serves as a proxy for a set of corresponding points. Our method is based on random sampling and detects planes, spheres, cylinders, cones and tori...We demonstrate that the algorithm is robust even in the presence of many outliers and a high degree of noise...Moreover the algorithm is conceptually simple and easy to implement...