我正在使用 PCL 1.10(安装 Ubuntu 20.04 和 ROS Noetic 的二进制版本)中的稀疏点云。我的云代表独立的对象,所以我在云中有许多独立的密集集群,我正在尝试使用凹壳按它们的接近程度对它们进行分组。但是,我得到的结果有时是无效的,并且结果可以从视觉上有效转变为无效,只需添加几个点。我将无效定义为其中一些自相交的多边形集,并将不包含所有点的多边形定义为一组。以下是一些在彼此相距几帧内拍摄的结果示例,其中连续帧的不同之处仅在于每帧增加了几个(2 或 3)个点。
我的云是 3D 的,但我将 ConcaveHull 对象明确设置为在 2 维中工作。将我的云投影到 2D 平面上以消除额外的尺寸没有效果,并且我确认多边形的顶点都在 XY 平面上。
上面的第一张图片显然是凹壳的一组无效多边形。上面的第二张图片是在大约 100 毫秒后拍摄的,只增加了几个点。由于黄色的小多边形,它也可能无效,但更接近正确。
我一直在梳理 PCL /surface/include/pcl/surface/impl/concave_hull.hpp 文件试图理解算法。显然,QHull 库被用于计算整个云的凸包,然后 PCL 拥有的代码处理凸包以确定凹多边形或一组多边形。我不知道那里正在实施什么算法,所以没有一些逆向工程就无法评论它。
我的猜测是,在真正的多边形又窄又长的区域中,有某种最近邻检查会在多边形的另一侧抓取一个顶点。您可以通过比较第一张和第二张图像来想象它们找到了相同的顶点,但是在第一帧中,一些不正确的逻辑正在抓取错误的顶点,这导致算法选择关闭多边形,从而导致很长的直线以及螺旋形的错误刻面。
我的计划是尝试更好地理解代码并导出我的数据以尝试其他一些凹壳算法,但为了每个人的利益而修复这个会很好。我的需求是无人值守的操作,所以它必须每次都能正常工作。
我正在寻找有关 PCL 算法的任何信息、其他从事此代码工作或遇到此问题的人的建议,或有关如何更好地满足我的需求的建议。感谢所有输入!
更新:我发现了另一个在幕后利用 QHull 的凹壳库 (concaveman-cpp),当我自己调用 QHull 但使用 SciPy.spatial 的 QHull 实现时,它也会在我的系统上产生不正确的结果,而 concaveman-cpp 使用它演示应用程序。这导致我调查 QHull 的输出。
在直接执行 QHull 的 C++ 中,我发现当凹壳对我的数据集无效时,当以 PCL 的方式可视化时,来自 QHull 的凸包(即按其 qID 排序顶点)是无效的。我发现使用 Qhull 的 Geomview 输出每次都会产生正确的凸包。进一步的调查表明,QHull 并不总是将其顶点输出为有序集,它也没有声称如此。但是,询问 QHull 的有序输出是可能的,现在我 100% 的时间得到了正确的船体。这并不优雅,因为没有 C++ 接口可以这样做,但是您可以向 QHull 发送“Fx”标志以使其打印有序顶点并将标准输出重定向到字符串缓冲区,然后解析字符串以获取数据。该解决方案在使用也输出数据的其他标志方面不可扩展。有趣的是,
在几乎相同的数据集上运行的 PCL 凸包的两个示例图像,“ok”数据集与“bad”数据集具有相同的点,除了存在于云内部的 2 个点(即不影响包的点多边形)。
更新 2:Scipy 揭示了一种遍历和排序方面以确定有序点的方法。这个概念很简单,但由于 QHull 中疯狂的命名约定,实现有点难以理解。然而,它是针对凸包失效问题的通用解决方案,并导致 concaveman-cpp 产生 100% 良好的凹包。所以现在是时候弄清楚如何将这样的解决方案集成到 PCL 凹壳算法中了。
更新 3:我开始调试 PCL 凹壳代码,发现它发送到 qhull(特别是“d QJ”)的标志正在返回一个无效的凸壳。我发现添加“Fx”标志会导致返回一个有效的凸包,但我仍然必须使用从 SciPy 借来的重新排序代码来可视化它。无论是否对构面重新排序,来自 PCL 的 alpha 形状代码都会产生无意义的输出。我对用于在 PCL 中实现的 alpha 形状算法的 Delaunay 三角形和 Voronoi 中心没有任何了解,所以我认为这对我来说是一个死胡同。我希望这至少可以帮助某人。
更新 4:我得出结论,凹壳故障是与凸壳故障不同的错误。这是从完全相同的数据集(与上述不同的数据)生成的两个图像,其中两个图像之间的唯一区别是将 alpha 值从 0.56(有效)更改为 0.55(自相交船体失败)。在这种情况下,凸包是有效的。