7

我正在尝试自动检测 3d 点云上的旋转轴。

换句话说，如果我取一个小的 3d 点云，选择一个单一的旋转轴，并以不同的旋转角度制作多个点的副本，那么我会得到一个更大的点云。

我的算法的输入是较大的点云，所需的输出是单对称轴。最终我将计算相互旋转的点之间的对应关系。

较大点云的大小约为 100K 点，旋转副本的数量未知。

在我的例子中，旋转角度有恒定的增量，但不一定跨越 360 度。例如，我可能有 0、20、40、60。或者我可能有 0、90、180、270。但我不会有 0、13、78、212（或者如果我有，我不在乎来检测它）。

这似乎是一个计算机视觉问题，但我无法弄清楚如何精确找到轴。输入通常非常干净，接近浮点精度。

我没有旋转/复制以制作更大点云的原始较小点云。我知道数据是合成的，噪音很小（通常是另一个程序的输出）。

我们不能轻易地计算较小云中可能的点数，因为不幸的是，这些点不会沿着轴重复。如果我们知道哪些点在轴上，那么我们可以想出可能的因素，但是我们已经解决了这个问题。

--

谢谢大家的建议。看起来我的最终算法将尝试使用 k-nn 度量提出匹配点的派系。每个派系都会给出一个轴。然后，我可以使用 RANSAC 将轴拟合到所有派系的结果。

4

9 回答 9

2

好吧，以下方法可能有用，但这取决于您的数据的具体情况。它基于相邻位置之间的间隙足够大（20 度可能很好）并且小点云接近表面（可以克服最后一个）的假设。我建议使用局部特征匹配（计算机视觉中的流行技术）。

首先，对于大云的每个点，您应该计算本地描述符（如图像的 SIFT 或 SURF）。最流行的点云是旋转图像：

Johnson, A. 和 Hebert, M. (1999)。在杂乱的 3 d 场景中使用旋转图像进行有效的对象识别。IEEE 模式分析和机器智能汇刊，21（5），433-449。引用者。取自http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8816&rep=rep1&type=pdf。

这里使用高级修改：

Endres, F.、Plagemann, C.、Stachniss, C. 和 Burgard, W. (2009)。使用潜在狄利克雷分配从范围数据中无监督地发现对象类别。在机器人：科学和系统。美国西雅图。

如果计算起来很困难，请问我如何在不损失很多判别力的情况下降低维数，我做过一次。

然后你应该匹配描述符，即在它们的高维空间中为它们中的每一个找到最近的邻居。如果小云已经旋转了 3 次，应该有 3 个好的最近邻。然而，由于云自相交，匹配可能会包含噪声。您仍然必须找到适合大量匹配的轴（尽管不是全部匹配）。在这里，您可以使用一些稳健的拟合，例如 RANSAC（您应该做一些数学运算来定义找到匹配项的轴位置的可能性）。请注意，它与其他人建议的方法不同。根据描述符，而不是原始点，您应该只拟合一条线而不是平面族（RANSAC 可能无法拟合具有 4-5 个正确点和 100K 异常值的平面）。

另请注意：

如果你有一个不近似表面的小扫描，你应该想出一个不同的旋转不变描述符，而不是旋转图像。

为了计算法线并进行检索，您可以查看以下库： http: //graphics.cs.msu.ru/en/science/research/3dpoint/lidark（即将发布主要版本）。

于 2010-04-16T11:19:40.367 回答
2

以下假设有 3 个或更多副本。考虑大点云的凸包。找到它的两个平行的面。旋转轴将垂直于这些。如果您发现不止一对，只需测试每个方向。

显然，如果根据轴的最极端点正好在轴上，则这不起作用，但是在一般情况下，这种情况非常罕见。

于 2010-04-17T06:43:04.567 回答
1

选择任意一点，然后找到与之等距的另外两个点。这应该是 O(n^2) 最坏的情况，但启发式可以大大减少这种情况。这三个点唯一地确定了一个圆。如果在与第一个或第三个点相同的距离处有第四个点，那将大大增加您对圆的信心。

圆的中心是轴上的一个点，圆的法向量是轴的方向向量。

给定轴，您可以确定旋转之间的角度并用其他一些点检查您的猜测。如果错了，请选择另一个点并重新开始。

编辑：顺便说一句，这显然是不确定的，但是如果您的点数据像您说的那样干净并且使用了良好的启发式方法，那么它应该非常准确。

于 2010-04-14T18:47:27.660 回答
0

1）如果您找到较大点云的质心 C，则 ISTM 原始旋转轴必须通过该点。

没关系：我没有看到旋转不能跨越一个完整圆圈的要求。对于您的 20、40、60 示例，质心不会在旋转轴上。

也许以下参考文献会有所帮助？

“用部分采样重建旋转表面” http://portal.acm.org/citation.cfm?id=980064

于 2010-04-14T18:08:54.087 回答
0

几点：）

  1. 如果我们有 1 个从不旋转的初始点，那么轴的数量是无限的。
  2. 如果我们有 1 个初始点旋转 1 次，那么也有无限数量的轴。
  3. 如果我们有 1 个初始点并将其旋转 2 次，那么我们可以找出轴，因为 3 个点唯一确定了一个平面。垂直于通过与 3 个点中的每一个等距的点（1 个初始点 + 2 个旋转点）是轴。
  4. 请注意，旋转 360 度是没有意义的。
  1. 从云中选择任意一点（P）。
  2. 跟踪点 P 的轨迹（L）（当 P 围绕某个轴旋转时，L 应该是一个圆）
  3. 垂直于通过其中心的圆 (L) 的平面是云的旋转轴。

我的意思是刚体的旋转轴与任何单个粒子的旋转轴相同。我们不需要关心所有其他的点。

于 2010-04-14T18:17:36.453 回答
0

看看在立体视觉中用于计算两个图像之间的单应性的技术——您对点云集的问题似乎类似于在同一对象/场景的多个图像中匹配点。似乎您可以应用 RANSAC 算法来计算点云集之间的转换。

于 2010-04-14T19:02:58.423 回答
0

一个疯狂的想法...

如果同一点围绕同一轴旋转多次，所有点将位于同一平面内。根据您的数据集，可以使用 ransac 方法检测该平面。

旋转轴将垂直于该平面，一旦确定了轴的方向，就应该相对容易确定轴的位置。

于 2010-04-15T17:28:56.343 回答
0

您应该考虑两件事：

  1. 点云的角跨度。
  2. 旋转角度。

现在如果 (rotation > span) 解决方案更简单，因为您必须寻找一个子模式并根据它的出现，尝试匹配一个更大的模式。

如果 (rotation < span) ，您将不得不忽略边缘效应，因为在该区域内（第一次旋转之后，最后一次旋转之前）您仍然会有一个对称的点云，对称角 = 跨度角; 如上述情况。

如果您不知道自己属于哪个类别，则可以安全地假设第二个类别。

如前所述，RANSAC 是模式匹配的最佳方法，因为它花费的时间更少，并且结果不错。您留下的唯一问题是在初始化期间估计迷你点云的跨度角度。这种估计很难做出。因此，如果您有足够的计算能力/时间，我建议以 1 度的步长进行迭代。从适度的 5 度开始到 45 度。随着结果开始收敛，角度精度会增加。

于 2010-04-17T07:06:51.237 回答
0

由于原始点云很小，最简单的解决方案可能是 RANSAC：

  1. 随机选择三个点
  2. 计算这些点的旋转轴（垂直于圆并通过中心的线）
  3. 其他观点同意吗？
  4. 如果没有，迭代直到找到正确的轴

The probability for a correct estimation is 1/((n-1)(n-2)), where n is the number of points in the original cloud. Since each test can be done very quickly, this might be a useful approach.

于 2010-04-20T21:43:59.903 回答