logo标签列表

3D点云叠加算法

algorithm3dgeometrycomputational-geometry
4
我需要将两组3D点叠加在一起；即找到旋转和平移矩阵，以最小化它们坐标之间的RMSD（均方根偏差）。我目前使用Kabsch算法，但对于我需要处理的许多情况并不是很有用。Kabsch要求两个数据集中的点数相等，并且需要预先知道哪个点将与哪个点对齐。对于我的情况，点数将不同，并且我不关心哪个点对应于最终对齐中的哪个点，只要RMSD最小化即可。因此，该算法将（可能）找到两个点集子集之间的1-1映射，以使旋转和平移后RMSD最小化。我知道一些处理不同数量点的算法，但它们都是基于蛋白质的，也就是说，它们试图将主干对齐在一起（一些连续段与另一些连续段对齐等），这对于漂浮在空间中、没有任何连接的点是无用的（好吧，为了清楚起见，有些点是连接的；但在叠加过程中我不想忽略没有任何连接的点）。
我找到的唯一算法是DIP-OVL，它在STRAP软件模块（开源）中。我尝试了这段代码，但行为似乎不稳定；有时候它会找到良好的对齐，有时候它无法将几个点集与自身进行简单的X轴平移对齐。

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

说实话，使用的目标函数并不是很清晰。RMSD被定义为对应点之间距离的均方根。如果我有两组分别有50个和100个点的数据集，并且算法只匹配了其中的1个或几个点，在这些点之间得到的RMSD将为零，而整体的重叠可能并不好。在所有点对之间计算RMSD也不是更好的解决方案（我认为）。唯一能想到的是为集合X中的每个点找到最近的点（因此在那种情况下会有恰好min(|X|,|Y|)个匹配，例如50个），并从这些匹配中计算RMSD。但是距离计算和二分图匹配部分似乎过于复杂，无法批量调用。在这方面的任何帮助都将有所帮助。谢谢！
这是一个非常困难的问题。由于点数不同，完全有可能找到变换，使得点数较少的集合是另一个集合的子集。此外，根据您的数据，可能会有许多这样的变换，那么如何决定哪个是最好的呢？是否需要更精确的方法，例如叠加每个集合的质心，然后找到最小化RMS的最佳旋转？还是需要更高的准确性？ - mathematician1975
@mathematician1975：说实话，这个问题并不像听起来那么开放。点的数量通常是相似的，较大的集合可能最多有两倍的点数，我的目标是找到“一个”（不是最优的）叠加，以使其中30-50％的点重叠在一起。如果存在完美的旋转（小集合在变换后是子集），那就是我要寻找的完美情况。否则，它应该缩小大小，直到达到可接受的匹配。质心可能没问题，但想象一下：一个球和一个半球。它们的质心在完美对齐时是不同的。 - froost
1
没有明确的迁移路径。虽然这个问题在这里是合适的，但可能太学术化了，无法得到你需要的支持。你可以查看相关迁移路径的Metas。联系了[cstheory.se]的管理员，他认为那里不适合这个问题。可能在[gamedev.se]或[cs.se]会得到更多的支持，但我不确定。 - user1228
这些点集是任意的吗？还是它们是某种潜在几何结构的样本，可以被求解器利用？ - atb
这些点来自蛋白质结构，因此存在一种基础结构，但我认为这不是容易利用的东西。 - froost
3个回答
3
2
如果您知道哪些点对应于彼此，您可以使用线性最小二乘法（LLS）恢复变换矩阵。
在考虑LLS时，通常希望找到A*x = b的x的近似值。通过转置，您可以解决A而不是x。
1. 将每个源向量和目标向量扩展为“1”，使它们看起来像<x, y z, 1> 2. 方程式：A · xi = bi 3. 扩展到多个向量：A · X = B 4. 转置：(A · X)T = BT 5. 简化：XT · AT = BT 6. 替换 P = XT，Q = AT 和 R = BT。结果是：P · Q = R 7. 应用 LLS 公式：Q ≈ (PT · P)-1 · PT · R 8. 替换回去：AT ≈ (X · XT)-1 · X · BT 9. 解出 A，并简化：A ≈ B · XT · (X · XT)-1 (B · XT)和(X · XT)可以通过对各个向量对的外积求和来迭代计算。
  • B · XT = ∑bi·xiT
  • X · XT = ∑xi·xiT
  • A ≈ (∑bi·xiT) · (∑xi·xiT)-1

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

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

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接