快速找到点云中的特定形状

Question

我有一个点云,并希望在我的代码中检测出某些点模式的出现.

假设我在3d空间中有1000个点,并且我想检测形成"L"形状的3个点的所有实例,其中L的每个段具有特定长度.点云可能没有完全匹配,但可能非常接近(即在点云中,"L"段的长度可能比理想值略长/短)

我最初的想法是这样的:

1. 记录我们试图检测的形状中所有点之间的距离
2. 创造一个空的'潜在形状'
3. 对于我们潜在形状中的每个点,检查在第1部分中找到的距离处/附近的所有点
4. 如果我们找到一个点,将它添加到我们的潜在形状,并重复第3部分,直到我们得到所有点.然后检查点之间的角度以验证形状确实是正确的.如果不正确,我们继续下一点再重新开始

问题是这种方法的运行时间最糟糕.理想情况下,我希望有一些数据结构来加速我的查询'查找距离给定点之间的distanceMin和distanceMax之间的所有点.有人能指出一些可能有用的有用数据结构.

我想把所有的点都放在一个八叉树中以加快访问时间.

关于如何改善运行时间的其他建议？启发式方法可以加快速度吗？

注意:我想要找到的形状是可变的.他们不会总是'L'.我尝试查看霍夫变换,但它们似乎仅用于检测特定的预定形状,如线条/圆圈.

Answer 1

在 PCL 库中有示例共识模块，直接引用自文档：

拥有 SAmple Consensus (SAC) 方法（如 RANSAC）以及模型（如平面和圆柱体）。这些可以自由组合，以检测点云中的特定模型及其参数。

也许您可以创建一些组合这些基元的形状并在云中搜索它们？