从点云中检测一组平面
Detecting set of planes from point cloud
我有一套点云，想测试一下3D房间里有没有角落。所以我想讨论我的方法，以及在速度方面是否有更好的方法，因为我想在手机上测试它。
我会尝试使用 hough 变换来检测线，然后我会尝试查看是否有三条线相交并且它们也构成了一个相交的两个平面。
正常的方法是ransac
- 随机选择3个点。
- 造飞机。
- 检查彼此的点是否在平面上。
- 如果平面上有足够多的点 - 从所有这些点重新计算最佳平面并将它们从集合中移除
- 如果不行再来3分
- 当你有足够的平面或剩下的点太少时停止。
另一种方法，如果你知道平面接近垂直或接近水平。
- 选择一个较小的垂直范围
- 得到这个范围内的所有点数
- 尝试拟合二维线
- 重复其他 Z 范围
- 如果您在每个 Z 切片中得到一组平行线，那么它们可能有一个平面 - 重新计算点的最佳拟合平面。
如果点云数据来自深度传感器，那么您的墙壁采样相对密集。我发现与深度传感器（例如 Kinect 或 DepthSense）配合使用效果很好的一件事是@MartinBeckett 建议的 RANSAC 程序的强大版本。
不是随机选取 3 个点，而是随机选取一个点，并在云中获取相邻点。有两种方法可以做到这一点：
- 正确的方法：使用 3D 最近邻查询数据结构，如 KD 树，获取距查询点一小段距离内的所有点。
- 草率但更快的方法：使用随机选择的像素的像素网格邻域。这可能包括在 3D 中远离它的点，因为它们在不同的 plane/object 上，但没关系，因为该像素不会从数据中获得太多支持。
下一步是根据该组 3D 点生成平面方程。您可以在它们的 3D 坐标上使用 PCA 来获得定义平面的两个最重要的特征向量（最后一个特征向量应该是法线）。
从那里开始，RANSAC 算法照常进行：检查数据中有多少其他点接近该平面，并找到具有最大支持的平面。我发现最好找到最大的支撑平面，移除支撑 3D 点，然后 运行 算法再次找到其他 'smaller' 平面。这样你或许可以搞定你房间的所有墙壁。
编辑：
为了澄清以上内容：假设平面的支持是与该平面的距离至多为某个阈值（例如10 cm，应取决于深度传感器的测量误差模型）的所有3D点的集合。
在 RANSAC 算法的每个 运行 之后，选择具有最大支持的平面。通过对支持集执行 PCA/linear 回归，可以使用支持该平面的所有点来改进平面方程（这比仅使用相邻点更稳健）。
为了继续寻找其他平面，应该从 3D 点集中移除先前迭代的支持，以便剩余的点位于其他平面上。只要有足够的点并且最佳平面拟合误差不太大，就可以重复此操作。
在你的情况下（寻找一个角落），你需要至少 3 个垂直平面。如果你发现两个大致平行的大支撑平面，那么它们可能是地板和一些柜台，或者两个平行的墙。要么房间没有可见的角落，要么你需要继续寻找支撑较小的垂直平面。
首先要指出
尽管这是一个旧的post，但我想提出一种类似于霍夫投票的补充方法，以共同找到由平面交点组成的所有角点位置：
- 统一采样space。确保点之间至少有一个距离 $d$（例如，您甚至可以通过 'space' 子采样的 CloudCompare 做到这一点）
- 计算这些点的点云法线。
- 从这个降采样云中随机选取 3 个点。
- 每个定向点（点+平面）定义一个假想平面。因此，每选取 3 个点定义 3 个平面。这些平面，如果不平行且不相交于一条直线，则总是相交于一个点。
- 创建一个投票space 来描述拐角：3 个平面（点）的交点可能是一个有效的参数化。所以我们的参数space有3个自由参数。
- 每得 3 分就在累加器中投一票 space 到角点。
- 转到（2）并重复直到所有采样点都用完，或者完成足够的迭代。这样我们就可以为所有可能的角落位置投票。
- 取累加器的局部最大值space。根据投票情况，我们将选择从最大平面的交点（因为它们将获得更多选票）到小平面的交点的角。最大的 4 个可能是房间的角落。如果不是，还可以考虑其他局部最大值。
请注意，投票 space 是量化的 3D space，角点位置将是对实际角点的粗略估计。如果需要，可以将平面交点存储在那个位置并对其进行细化（使用类似于 ICP 等的迭代优化）以获得非常好的角位置。
如果您可以优化位置，这种方法会非常快并且可能非常准确。我相信这是迄今为止最好的算法。当然，这是假设我们可以计算点云的法线（我们总是可以借助协方差矩阵的特征向量在样本位置进行计算）。
也请看这里，我在 Whosebug 上列出了与飞机装配相关的问题列表：
我有一套点云，想测试一下3D房间里有没有角落。所以我想讨论我的方法，以及在速度方面是否有更好的方法，因为我想在手机上测试它。
我会尝试使用 hough 变换来检测线，然后我会尝试查看是否有三条线相交并且它们也构成了一个相交的两个平面。
正常的方法是ransac
- 随机选择3个点。
- 造飞机。
- 检查彼此的点是否在平面上。
- 如果平面上有足够多的点 - 从所有这些点重新计算最佳平面并将它们从集合中移除
- 如果不行再来3分
- 当你有足够的平面或剩下的点太少时停止。
另一种方法，如果你知道平面接近垂直或接近水平。
- 选择一个较小的垂直范围
- 得到这个范围内的所有点数
- 尝试拟合二维线
- 重复其他 Z 范围
- 如果您在每个 Z 切片中得到一组平行线，那么它们可能有一个平面 - 重新计算点的最佳拟合平面。
如果点云数据来自深度传感器，那么您的墙壁采样相对密集。我发现与深度传感器（例如 Kinect 或 DepthSense）配合使用效果很好的一件事是@MartinBeckett 建议的 RANSAC 程序的强大版本。 不是随机选取 3 个点，而是随机选取一个点，并在云中获取相邻点。有两种方法可以做到这一点：
- 正确的方法：使用 3D 最近邻查询数据结构，如 KD 树，获取距查询点一小段距离内的所有点。
- 草率但更快的方法：使用随机选择的像素的像素网格邻域。这可能包括在 3D 中远离它的点，因为它们在不同的 plane/object 上，但没关系，因为该像素不会从数据中获得太多支持。
下一步是根据该组 3D 点生成平面方程。您可以在它们的 3D 坐标上使用 PCA 来获得定义平面的两个最重要的特征向量（最后一个特征向量应该是法线）。
从那里开始，RANSAC 算法照常进行：检查数据中有多少其他点接近该平面，并找到具有最大支持的平面。我发现最好找到最大的支撑平面，移除支撑 3D 点，然后 运行 算法再次找到其他 'smaller' 平面。这样你或许可以搞定你房间的所有墙壁。
编辑：
为了澄清以上内容：假设平面的支持是与该平面的距离至多为某个阈值（例如10 cm，应取决于深度传感器的测量误差模型）的所有3D点的集合。 在 RANSAC 算法的每个 运行 之后，选择具有最大支持的平面。通过对支持集执行 PCA/linear 回归，可以使用支持该平面的所有点来改进平面方程（这比仅使用相邻点更稳健）。
为了继续寻找其他平面，应该从 3D 点集中移除先前迭代的支持，以便剩余的点位于其他平面上。只要有足够的点并且最佳平面拟合误差不太大，就可以重复此操作。 在你的情况下（寻找一个角落），你需要至少 3 个垂直平面。如果你发现两个大致平行的大支撑平面，那么它们可能是地板和一些柜台，或者两个平行的墙。要么房间没有可见的角落，要么你需要继续寻找支撑较小的垂直平面。
首先要指出
尽管这是一个旧的post，但我想提出一种类似于霍夫投票的补充方法，以共同找到由平面交点组成的所有角点位置：
- 统一采样space。确保点之间至少有一个距离 $d$（例如，您甚至可以通过 'space' 子采样的 CloudCompare 做到这一点）
- 计算这些点的点云法线。
- 从这个降采样云中随机选取 3 个点。
- 每个定向点（点+平面）定义一个假想平面。因此，每选取 3 个点定义 3 个平面。这些平面，如果不平行且不相交于一条直线，则总是相交于一个点。
- 创建一个投票space 来描述拐角：3 个平面（点）的交点可能是一个有效的参数化。所以我们的参数space有3个自由参数。
- 每得 3 分就在累加器中投一票 space 到角点。
- 转到（2）并重复直到所有采样点都用完，或者完成足够的迭代。这样我们就可以为所有可能的角落位置投票。
- 取累加器的局部最大值space。根据投票情况，我们将选择从最大平面的交点（因为它们将获得更多选票）到小平面的交点的角。最大的 4 个可能是房间的角落。如果不是，还可以考虑其他局部最大值。
请注意，投票 space 是量化的 3D space，角点位置将是对实际角点的粗略估计。如果需要，可以将平面交点存储在那个位置并对其进行细化（使用类似于 ICP 等的迭代优化）以获得非常好的角位置。
如果您可以优化位置，这种方法会非常快并且可能非常准确。我相信这是迄今为止最好的算法。当然，这是假设我们可以计算点云的法线（我们总是可以借助协方差矩阵的特征向量在样本位置进行计算）。
也请看这里，我在 Whosebug 上列出了与飞机装配相关的问题列表：