3D 平面拟合算法
3D Plane fitting algorithms
所以我正在做一个项目，我和我的一个伙伴使用 KINECTv2 扫描了一个房间，并用它制作了一个 3D 模型。目标是使实时添加不同种类家具的 3d 模型成为可能。为了这个目标，我正在尝试不同的平面拟合算法，以便找到最快的算法。有人有什么建议吗？到目前为止，我只研究了 PCL.
中包含的基本 RANSAC 算法的用法
两种常见的平面拟合方法是 RANSAC 和 Hough。这是一项性能比较：
与计算几何和图像处理中的许多问题一样，与其考虑什么是 "fastest,"，不如考虑在性能、开发工作量和成本方面对您的应用程序来说什么是最佳的。寻找尽可能快的算法可能会让您走上一条成本和复杂性都非常惊人的道路，而您可以实施一个相对简单的算法的数据处理链，运行 的速度刚好足以为用户。
长话短说，我建议从霍夫平面拟合开始。霍夫变换算法相对容易编写（一旦掌握了基础知识），调整参数也很直观。
https://en.wikipedia.org/wiki/Hough_transform
编写自己的算法的原因之一是，一旦（不是如果）您发现点云数据噪声更大且表现不佳，您将能够更好地了解需要进行哪些更改一个想要。
实现良好的速度将取决于许多因素，包括：
- 点云预处理。寻找将点云分解成可以更快处理的块的方法。
- 参数化。预处理数据后，您可以为平面拟合算法定义更窄的搜索范围。例如，仅尝试平面适合几度的垂直度。您还需要选择参数以在速度和拟合质量之间找到平衡点。
- 3D 数据的质量。这本身就是一个很大的话题，越早看清数据中的问题越好。
- "real time" 是什么意思。即使对于涉及用户交互的 3D 图形应用程序，实现严格基于规范的实时性（在 N frames/second 更新）可能不如呈现流畅和简单的界面重要。
- 多线程和并行。
- 3D显示。又是一个大话题。
预处理。
您不需要将任意大小的平面拟合到任意点云：相反，您需要拟合墙壁、地板和天花板。对于 Hough 算法，这意味着您可以限制测试参数的范围，从而加快处理速度。
与其尝试找到适合完整原始点云的所有平面，不如找到将点云分解为子云簇的方法，这样可以更有效地进行平面拟合测试 运行。
PCL 可以为您计算表面法线。如果您可以识别指向大致相同方向的表面法线簇，然后尝试对各个簇进行平面拟合，您应该能够大大加快速度。
此外，对于您的第一遍，您可能希望对数据进行下采样并尝试在相对较少的点上进行拟合。这类似于为 2D 处理创建 "image pyramid"。
Octrees 是很好的、简单的分割方法 space 用于查询、碰撞测试等。八叉树将一个 space 分成八个节点或 "octants." 这可以想象成将一个立方体切割成八个更小的立方体。然后每个八分圆进一步分为八个八分圆，依此类推。如果一个八分圆（一个节点）不包含点，则不需要进一步划分它。
https://en.wikipedia.org/wiki/Octree
参数化。
上面的描述应该清楚地表明，如果您可以通过简化 and/or 分解原始原始点云来预处理数据，那么您将能够测试更窄定义的搜索，这些搜索将 运行 更多很快。
就此而言，您可能不需要平面拟合的高精度。您可以生成相当好的配合，然后调整这些配合以生成彼此成直角的天花板、墙壁和地板。
3D 数据质量。
Kinect v2 是一种飞行时间设备，存在一些固有的测量精度问题。例如，如果您拍摄一张平坦墙壁的图像，然后检查深度值，您会注意到图像的角落有一些非平面的愚蠢之处。如果您查看多个图像上每个 (x,y) 像素的深度值范围（或标准差），您还会注意到中心像素和边缘像素之间的噪声差异。
执行平面拟合后，生成拟合质量的度量。这需要返回数据以计算用于计算的点的点到平面距离。 （为了加快速度，只使用每第 N 个点或对这些点进行随机采样。）当您修改参数时，您会看到速度和拟合质量方面的效果。
实时与明显平滑。
如果您只需要用户实时移动家具，那么花更长的时间来生成初始平面拟合应该没问题。
Multithreading/Parallelism
要处理数据输入、平面拟合和用户界面，您几乎可以肯定必须认真考虑多线程。要测试算法，您确实在 UI 线程上工作只是为了开始，但这是有限制的。
像这样的应用程序需要 CUDA 或 OpenCL。对于 3D 显示，无论如何您都将使用显卡。虽然您不需要立即跳入 GPU 编程，但记住如何并行化算法会很有帮助。
3D显示。
您打算使用 Direct3D 或 OpenGL 进行 3D 显示和交互吗？实施允许用户 "add 3d models of different kinds of furniture in real time" 的软件表明您将不得不依赖显卡。
如果您可以在 3D 视图中显示点云，也许您甚至不需要平面拟合。你甚至可以逃避碰撞检测：如果椅子的 3D 模型撞到一组点（即一堵墙），那么你可能只是检测碰撞而不是尝试拟合平面来定义边界。八分圆和其他 space 划分技术将有助于加速碰撞测试。
Matterport (http://matterport.com/) 公司开发了一些与您描述的非常相似的东西。如果不出意外，您可以尝试一下他们的软件，并考虑一下 improved/adapted 可能满足您的需求。
感谢 Rethunk 的详细评论并提供局部霍夫变换的变体。但首先，让我指出有一堆关于平面检测或相交平面检测的 Whosebug / stackexchange 帖子。其中一些是：
- Fit a plane to a 3D point cloud in C++
- Fit a plane to 3D point cloud using RANSAC
- Fast plane fitting to many points
- https://math.stackexchange.com/questions/1657030/fit-plane-to-3d-data-using-least-squares
- Best fit plane for 3D data
我建议的方法在 publication at 3DV 2015:
中有详细说明
Local Hough Transform for 3D Primitive Detection,
Bertram Drost, Slobodan Ilic, IEEE 3D Vision 2015
这个想法是基于选择两个有方向的点对。比较这些点的方向以确定这些点是否共同位于一个平面上。所有这些点对的贡献在局部投票 space 中组合，其中平面在 0 维投票 space 中参数化（定向点完全决定平面）。该技术可扩展到不同的基元。
RANSAC 通常不如 Hough 变换，但所提出的方法可以看作是全局投票方案和 RANSAC 之间的混合体。虽然 RANSAC 选择多个随机点，足以适合目标基元，但所提出的方法仅选择一个点，即参考点。
我还有 another stackexchange post 解释了如何为正交平面开发类似的方法。
所以我正在做一个项目，我和我的一个伙伴使用 KINECTv2 扫描了一个房间，并用它制作了一个 3D 模型。目标是使实时添加不同种类家具的 3d 模型成为可能。为了这个目标，我正在尝试不同的平面拟合算法，以便找到最快的算法。有人有什么建议吗？到目前为止，我只研究了 PCL.
中包含的基本 RANSAC 算法的用法两种常见的平面拟合方法是 RANSAC 和 Hough。这是一项性能比较：
与计算几何和图像处理中的许多问题一样，与其考虑什么是 "fastest,"，不如考虑在性能、开发工作量和成本方面对您的应用程序来说什么是最佳的。寻找尽可能快的算法可能会让您走上一条成本和复杂性都非常惊人的道路，而您可以实施一个相对简单的算法的数据处理链，运行 的速度刚好足以为用户。
长话短说，我建议从霍夫平面拟合开始。霍夫变换算法相对容易编写（一旦掌握了基础知识），调整参数也很直观。
https://en.wikipedia.org/wiki/Hough_transform
编写自己的算法的原因之一是，一旦（不是如果）您发现点云数据噪声更大且表现不佳，您将能够更好地了解需要进行哪些更改一个想要。
实现良好的速度将取决于许多因素，包括：
- 点云预处理。寻找将点云分解成可以更快处理的块的方法。
- 参数化。预处理数据后，您可以为平面拟合算法定义更窄的搜索范围。例如，仅尝试平面适合几度的垂直度。您还需要选择参数以在速度和拟合质量之间找到平衡点。
- 3D 数据的质量。这本身就是一个很大的话题，越早看清数据中的问题越好。
- "real time" 是什么意思。即使对于涉及用户交互的 3D 图形应用程序，实现严格基于规范的实时性（在 N frames/second 更新）可能不如呈现流畅和简单的界面重要。
- 多线程和并行。
- 3D显示。又是一个大话题。
预处理。 您不需要将任意大小的平面拟合到任意点云：相反，您需要拟合墙壁、地板和天花板。对于 Hough 算法，这意味着您可以限制测试参数的范围，从而加快处理速度。
与其尝试找到适合完整原始点云的所有平面，不如找到将点云分解为子云簇的方法，这样可以更有效地进行平面拟合测试 运行。
PCL 可以为您计算表面法线。如果您可以识别指向大致相同方向的表面法线簇，然后尝试对各个簇进行平面拟合，您应该能够大大加快速度。
此外，对于您的第一遍，您可能希望对数据进行下采样并尝试在相对较少的点上进行拟合。这类似于为 2D 处理创建 "image pyramid"。
Octrees 是很好的、简单的分割方法 space 用于查询、碰撞测试等。八叉树将一个 space 分成八个节点或 "octants." 这可以想象成将一个立方体切割成八个更小的立方体。然后每个八分圆进一步分为八个八分圆，依此类推。如果一个八分圆（一个节点）不包含点，则不需要进一步划分它。
https://en.wikipedia.org/wiki/Octree
参数化。 上面的描述应该清楚地表明，如果您可以通过简化 and/or 分解原始原始点云来预处理数据，那么您将能够测试更窄定义的搜索，这些搜索将 运行 更多很快。
就此而言，您可能不需要平面拟合的高精度。您可以生成相当好的配合，然后调整这些配合以生成彼此成直角的天花板、墙壁和地板。
3D 数据质量。 Kinect v2 是一种飞行时间设备，存在一些固有的测量精度问题。例如，如果您拍摄一张平坦墙壁的图像，然后检查深度值，您会注意到图像的角落有一些非平面的愚蠢之处。如果您查看多个图像上每个 (x,y) 像素的深度值范围（或标准差），您还会注意到中心像素和边缘像素之间的噪声差异。
执行平面拟合后，生成拟合质量的度量。这需要返回数据以计算用于计算的点的点到平面距离。 （为了加快速度，只使用每第 N 个点或对这些点进行随机采样。）当您修改参数时，您会看到速度和拟合质量方面的效果。
实时与明显平滑。 如果您只需要用户实时移动家具，那么花更长的时间来生成初始平面拟合应该没问题。
Multithreading/Parallelism 要处理数据输入、平面拟合和用户界面，您几乎可以肯定必须认真考虑多线程。要测试算法，您确实在 UI 线程上工作只是为了开始，但这是有限制的。
像这样的应用程序需要 CUDA 或 OpenCL。对于 3D 显示，无论如何您都将使用显卡。虽然您不需要立即跳入 GPU 编程，但记住如何并行化算法会很有帮助。
3D显示。 您打算使用 Direct3D 或 OpenGL 进行 3D 显示和交互吗？实施允许用户 "add 3d models of different kinds of furniture in real time" 的软件表明您将不得不依赖显卡。
如果您可以在 3D 视图中显示点云，也许您甚至不需要平面拟合。你甚至可以逃避碰撞检测：如果椅子的 3D 模型撞到一组点（即一堵墙），那么你可能只是检测碰撞而不是尝试拟合平面来定义边界。八分圆和其他 space 划分技术将有助于加速碰撞测试。
Matterport (http://matterport.com/) 公司开发了一些与您描述的非常相似的东西。如果不出意外，您可以尝试一下他们的软件，并考虑一下 improved/adapted 可能满足您的需求。
感谢 Rethunk 的详细评论并提供局部霍夫变换的变体。但首先，让我指出有一堆关于平面检测或相交平面检测的 Whosebug / stackexchange 帖子。其中一些是：
- Fit a plane to a 3D point cloud in C++
- Fit a plane to 3D point cloud using RANSAC
- Fast plane fitting to many points
- https://math.stackexchange.com/questions/1657030/fit-plane-to-3d-data-using-least-squares
- Best fit plane for 3D data
我建议的方法在 publication at 3DV 2015:
中有详细说明Local Hough Transform for 3D Primitive Detection, Bertram Drost, Slobodan Ilic, IEEE 3D Vision 2015
这个想法是基于选择两个有方向的点对。比较这些点的方向以确定这些点是否共同位于一个平面上。所有这些点对的贡献在局部投票 space 中组合，其中平面在 0 维投票 space 中参数化（定向点完全决定平面）。该技术可扩展到不同的基元。
RANSAC 通常不如 Hough 变换，但所提出的方法可以看作是全局投票方案和 RANSAC 之间的混合体。虽然 RANSAC 选择多个随机点，足以适合目标基元，但所提出的方法仅选择一个点，即参考点。
我还有 another stackexchange post 解释了如何为正交平面开发类似的方法。