3D平面拟合算法

Question

所以我正在开展一个项目,我和我的伙伴使用KINECTv2扫描了一个房间并用它制作了一个3D模型.目标是使实时添加不同类型家具的3D模型成为可能.为了达到这个目标,我正在尝试不同的平面拟合算法,以便找到最快的工作方法.有人有什么建议吗？到目前为止,我只研究了PCL中包含的基本RANSAC算法的用法.

Answer 1

平面拟合的两种常用方法是RANSAC和Hough.这是一个性能比较:

与计算几何和图像处理中的许多问题一样,不考虑什么是"最快",而是考虑在性能,开发工作和成本方面最适合您的应用.搜索最快的算法可能会让您走上成本和复杂性可怕的道路,而您可能能够实现一个相对简单的算法的数据处理链,这些算法的运行速度足够快,可以为用户提供流畅,愉悦的体验.

长话短说,我建议从霍夫飞机开始.霍夫变换算法相对容易编写(一旦掌握了基础知识),调整参数就很直观.

编写自己的算法的原因之一是,您将能够更好地理解需要做出哪些更改(而不是如果)您发现点云数据比人们想要的更嘈杂且表现不佳.

实现良好的速度将取决于许多因素,包括:

预处理. 您不需要将任意大小的平面安装到任意点云:相反,您需要适合墙壁,可能需要地板和天花板.对于霍夫算法,这意味着您可以限制测试参数的范围,从而加快处理速度.

而不是试图找到完整的原始点云的所有平面拟合,找到将点云分解成子云的集群的方法,平面拟合测试可以更有效地运行.

PCL可以为您计算表面法线.如果您可以识别指向大致相同方向的曲面法线群,然后尝试针对各个群集的平面拟合,则应该能够大大加快速度.

此外,对于您的第一次通过,您可能希望对数据进行下采样,并尝试适应相对较少的点.这类似于为2D处理创建"图像金字塔".

八度是很好的,简单的方法来划分查询空间,碰撞测试等等.八叉树将空间划分为八个节点或"八分圆".这可以想象为将立方体切割成八个较小的立方体.然后每个八分圆进一步分为八个八分圆,依此类推.如果八分圆(一个节点)不包含点,则不需要进一步划分它.

参数. 上面的描述应该清楚地表明,如果您可以通过简化和/或分解原始原始点云来预处理数据,那么您将能够测试更加狭窄定义的搜索,这些搜索将更快地运行.

就此而言,您可能不需要高精度的平面拟合.您可以生成相当好的配合,然后调整这些配合,以生成彼此成直角的天花板,墙壁和地板.

3D数据质量. Kinect v2是一种飞行时间设备,具有一些固有的测量精度问题.例如,如果您拍摄平面墙的单个图像然后检查深度值,您会发现图像角落有一些非平面的愚蠢.如果您查看多个图像上每个(x,y)像素的深度值的范围(或标准偏差),那么您还会注意到中心像素和边缘像素之间的噪声差异.

执行平面拟合后,生成拟合质量的度量.这需要返回数据来计算用于计算的点的点到平面距离.(为了加快速度,只使用每个N点或随机采样点.)当您修改参数时,您将看到速度和适合质量方面的效果.

实时与感知顺畅. 如果您只需要用户实时移动家具,那么花费更长时间生成初始平面配合应该是可以的.

多线程/并行性 为了处理数据输入,平面拟合和用户界面,您几乎肯定必须仔细考虑多线程.要测试算法,您只需要开始使用UI线程,但这是有限的.

像这样的应用程序需要CUDA或OpenCL.对于3D显示器,无论如何您都将使用显卡.虽然您不需要立即跳转到GPU编程,但记住算法如何并行化是有帮助的.

3D显示. 您是否计划使用Direct3D或OpenGL进行3D显示和交互？实施软件以允许用户"实时添加不同类型家具的3D模型"表明您将不得不依赖图形卡.

如果您可以在3D视图中显示点云,也许您甚至不需要平面拟合.你甚至可以逃脱碰撞检测:如果椅子的3D模型撞到一组点(即一堵墙),那么你可能只是检测到碰撞而不是试图使飞机适合定义边界.Octants和其他空间分割技术将有助于加速碰撞测试.

Matterport公司(http://matterport.com/)已经开发出了与您所描述的非常相似的东西.如果没有别的,您可以试试他们的软件,并考虑可以根据您的需求改进/调整的内容.

Answer 2

我很欣赏 Rethunk 的详细评论，并提供了局部霍夫变换的变体。但首先，我要指出，有很多关于平面检测或相交平面检测的 stackoverflow / stackexchange 帖子。其中一些是：

我建议的方法在3DV 2015 的出版物中有详细解释：

用于 3D 基元检测的局部霍夫变换， Bertram Drost，Slobodan Ilic，IEEE 3D Vision 2015

这个想法基于选择两个有向点对。比较这些点的方向以确定这些点是否共同位于一个平面上。所有这些点对的贡献都组合在局部投票空间中，其中平面在 0 维投票空间中参数化（有向点完全确定平面）。该技术可扩展到不同的基元。

RANSAC 通常不如 Hough 变换，但所提出的方法可以被视为全局投票方案和 RANSAC 之间的混合。虽然 RANSAC 选择多个足以拟合目标基元的随机点，但所提出的方法仅选择单个点，即参考点。

我还有另一篇 stackexchange 帖子，解释了如何为正交平面开发类似的方法。