3

我需要将两组 3D 点叠加在一起；即找到旋转和平移矩阵以最小化它们坐标之间的RMSD（均方根偏差）。

我目前使用Kabsch 算法，这对于我需要处理的许多情况都不是很有用。Kabsch 要求两个数据集中的点数相等，此外，它需要事先知道哪个点将与哪个点对齐。就我而言，点的数量会有所不同，我不在乎哪个点对应于最终对齐中的哪个点，只要 RMSD 最小化即可。

因此，该算法将（可能）找到两个点集的子集之间的 1-1 映射，以便在旋转和平移之后，RMSD 最小化。

我知道一些处理不同数量点的算法，但是它们都是基于蛋白质的，也就是说，它们试图将主干对齐在一起（一些连续段与另一个连续段对齐等），这对于点浮动没有用在太空中，没有任何联系。（好吧，要清楚，有些点是连接的；但是有些点没有任何连接，我不想在叠加过程中忽略这些点。）

我发现的唯一算法是DIP-OVL，在 STRAP 软件模块（开源）中找到。我尝试了代码，但行为似乎不稳定；有时它会找到很好的对齐方式，有时它无法在简单的 X 平移后将一组点与自身对齐。

有人知道处理这种限制的算法吗？如果性能有问题，我最多会得到 ~10^2 到 ~10^3 分。

老实说，要使用的目标函数不是很清楚。RMSD定义为对应点之间距离的RMS 。如果我有两组分别为 50 和 100 点，并且算法匹配组内的 1 个或几个点，那么这几个点之间的 RMSD 将为零，而整体叠加可能不会那么大。所有点对之间的 RMSD并不是更好的解决方案（我认为）。

我能想到的唯一一件事就是为集合 Y 中的每个点找到集合 X 中的最近点（因此将有准确的 min(|X|,|Y|) 匹配，例如在这种情况下为 50）并从中计算 RMSD火柴。但是距离计算和二分匹配部分似乎计算复杂，无法以批处理方式调用。该领域的任何帮助也会有所帮助。

谢谢！

4

3 回答 3

2

如果您知道哪些点对彼此对应，则可以使用线性最小二乘法(LLS) 恢复变换矩阵。

在考虑 LLS 时，您通常希望找到xin的近似值A*x = b。使用转置，您可以求解A而不是x.

  1. 用“1”扩展每个源和目标向量，所以它们看起来像 < x , y z , 1>
  2. 方程：A · x i = b i
  3. 扩展到多个向量：A · X = B
  4. 转置： ( A · X ) T = B T
  5. 化简：X T · A T = B T
  6. 替换P = X T，Q = A T和R = B T。结果是：P · Q = R
  7. 应用 LLS 的公式：Q ≈ ( P T · P ) -1 · P T · R。
  8. 代入：A T ≈ ( X · X T ) -1 · X · B T
  9. 求解A并简化：A ≈ B · X T · ( X · X T ) -1

( B · X T ) 和 ( X · X T ) 可以通过对各个向量对的外积求和来迭代计算。

  • B · X T = ∑ b i · x i T
  • X · X T = ∑ x i · x i T
  • A ≈ (∑ b i · x i T ) · (∑ x i · x i T ) -1

没有矩阵会大于 4×4，因此该算法不会使用任何过多的内存。

结果不一定是仿射的，但可能很接近。通过一些进一步的处理，您可以使其仿射。

于 2012-06-25T16:56:12.880 回答
2

您所说的看起来像是“云到云注册”任务。例如，查看http://en.wikipedia.org/wiki/Iterative_closest_point和http://www.willowgarage.com/blog/2011/04/10/modular-components-point-cloud-registration。您可以在开源点云库中使用您的数据，看看它是否适合您。

于 2012-06-25T13:03:25.033 回答
0

通过叠加发现对齐的最佳算法是 Procrustes Analysis 或 Horn 方法。请按照这个 Stackoverflow 链接。

于 2015-04-16T11:58:39.477 回答