比较三维结构

Question

比较三维结构

algorithmmathhash3dgeometry

5

我需要评估两组3D点是否相同（忽略平移和旋转），通过查找和比较适当的几何哈希值。我研究了一些几何哈希技术的论文，并发现了一些算法，但它们往往会受到“视觉要求”的复杂性的影响（例如2D到3D，遮挡，阴影等）。

此外，如果两个几何形状稍有不同，我希望哈希值也不会有太大的差异。

有没有人知道符合我的需求的算法，并可以提供一些进一步研究的链接？

谢谢

- Stefano Borini

我知道一些暴力方法来做这件事，想看看是否还有更简单的方法。 - stevedbrown

2

有趣的问题。如果我只是检查相同集合，我解决这个问题的方法是找到两个最远的点并将其作为x轴，然后找到距离该轴最远的点并将从x轴到该点的法线作为y轴。但是，这种方法很容易失败于“相似”的集合。 - Nosredna

@Nosredna：这种规范化方法与我在一篇关于机器人视觉的论文中发现的相同。唯一的区别是，它会针对每对点进行评估，因为可能存在遮挡情况。一旦您完成规范化并获得所有配对数据，就可以使用“投票计数”技术进行量化和相似性评估，以确定是否匹配正确。 - Stefano Borini

1

知道你考虑的是什么类型的数据会很有帮助？它们是表面的密集样本吗？这些集合有多大？ - balint.miklos

小型的三维点集（最多不超过100-200个点）。 - Stefano Borini

7个回答

1

对我而言，这似乎是一个数值优化问题。您希望找到将一组点转换为尽可能接近另一组点的变换参数。定义某种残差或“能量”，在点重合时最小化它，并将其传递给最小二乘优化器或类似工具。如果它成功将分数优化为零（或根据浮点误差可以期望的那样接近于零），那么这些点就是相同的。

搜索引擎

least squares rotation translation

发现有很多论文基于这种技术（例如"两点模式之间的最小二乘估计变换参数"）。

以下是根据下面的评论更新：如果不知道点之间的一对一对应关系（如上述论文所假设的那样），则只需要确保被最小化的得分独立于点的顺序。例如，如果将这些点视为小质点（使用有限半径球体来避免零距离问题），并通过优化平移和旋转参数来使系统的总引力能最小化，那么就可以使用该方法。

- timday

1

这解决了错误的问题。它从每个顶点与其他对象对应顶点的已知匹配开始。然后找到对象之间的变换。在提交者的情况下，您没有任何关于成对匹配顶点的知识...如果有的话，问题就变得简单了。 - SPWorley

好的，抱歉引用的那篇论文是个糟糕的例子，因为它假设了点的顺序对应。但是，仍然可以定义一个与点顺序无关的“接近度”分数，并进行数值优化（请参见上面的更新）。 - timday

是的，这是一个解决不同问题的好方法。不，我认为你不能轻易从你的更新中得到任何东西。试着将你提出的问题形式化，你会看到问题所在（也许你能解决它，但如果你能，请发布解决方案！） - ilya n.

1

有许多SIGGRAPH出版物可能对您有所帮助。

例如，Brown和Rusinkiewicz的“三维扫描的全局非刚性对齐”：

http://portal.acm.org/citation.cfm?id=1276404

一个可以帮助你入门的通用搜索：

http://scholar.google.com/scholar?q=siggraph+point+cloud+registration

- nsanders

1

旋转图像是其中一种方法。

- Autoplectic

1

如果你想要估算两个相似点云之间的刚性变换，可以使用成熟的迭代最近点（Iterative Closest Point）方法来实现。该方法从粗略的变换估计开始，然后通过计算最近邻居和最小化相关成本函数来迭代地优化变换。它可以高效地实现（甚至实时），并且有适用于Matlab、C ++等多种编程语言的实现可用。此方法已经得到扩展，并有多个变体，包括估计非刚性变形，如果您对此感兴趣，应该查看解决扫描配准问题的计算机图形学文章，其中您的问题是一个重要的步骤。初学者可以参考维基百科上的“迭代最近点”页面，里面有好几个外部链接。下面是一张简短的介绍图片，来自于一个匹配点云的matlab实现:

_{（来源：mathworks.com）} 在对齐后，您可以使用最终误差度量来比较两个点云的相似性，但这只是一种特定情况下的解决方案，可能还有更好的方法。使用形状描述符，可以计算出在平移/旋转下通常保持不变的形状指纹。在大多数情况下，它们是针对网格而不是点云定义的，但有许多形状描述符可用，因此根据输入和要求，您可能会发现某些有用的内容。为此，您需要查阅形状分析领域，并且可能会参考这个2004年的SIGGRAPH课程演示，以了解人们如何计算形状描述符。

- balint.miklos

根据维基百科上的描述，通过其他方式获得良好的第一近似仍然要好得多。例如，我会使用惯性张量（见下文）。 - ilya n.

是的，你说得完全正确，要开始优化就需要一个合理的估计。你的解决方案步骤1和2是一个不错的方法。仅供参考，原则上这是主成分分析的一种特殊情况，它是一种寻找点集的主导轴的技术。请参阅http://en.wikipedia.org/wiki/Principal_components_analysis。 - balint.miklos

0

也许你还应该了解一下RANSAC算法。它通常用于拼接全景图像，这似乎与你的问题有些相似，只是在二维空间中。只需在谷歌上搜索RANSAC、全景和/或拼接，就能找到一个起点。

- Niki

0

这是我会做的方法：

将集合放置在质心处
计算惯性张量。这给出了三个坐标轴。旋转到它们。[*]
按照给定顺序（例如，从上到下，从左到右）写下点列表，并使用所需的精度。
应用任何您喜欢的算法以获得结果数组。

要比较两个集合，除非您需要提前存储哈希结果，否则只需将第3步的点集应用您喜欢的比较算法即可。例如，可以计算两个集合之间的距离。

我不确定是否可以为第4步推荐算法，因为似乎您的要求是相互矛盾的。任何称为哈希的东西通常具有这样的特性：输入的微小变化会导致非常不同的输出。无论如何，现在我已经将问题简化为数字数组，所以您应该能够解决问题。

[*] 如果您的两个或三个轴重合，请通过其他方式选择坐标，例如作为最长距离。但是对于随机点来说，这种情况极为罕见。

- ilya n.

这是我现在正在使用的算法。主要缺点是“几乎相同”的设置会产生非常不同的哈希值，有点令人烦恼。 - Stefano Borini

你可以对数组应用不同的“哈希”函数。 - ilya n.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SPWorley · Accepted Answer

您的第一个想法可能是寻找将一个对象映射到另一个对象的旋转，但这是一个非常复杂的话题...实际上并不必要！您不是在询问如何最好地匹配两者，而是仅在询问它们是否相同。

通过所有点间距离的列表来描述您的模型。按该距离对列表进行排序。现在比较每个对象的列表。它们应该是相同的，因为点间距离不受平移或旋转的影响。

三个问题：

1）如果点数很大，那么就有一大堆成对出现的（N *（N-1）/ 2）点。在这种情况下，您可以选择仅保留最长的点，或者更好的是为每个顶点保留1或2个最长的点，以便模型的每个部分都有一些贡献。然而，删除这样的信息会使问题变得概率化而不是确定性的。

2）这只使用顶点来定义形状，而不是边缘。这可能是可以接受的（在实践中也将是如此），但如果您希望具有相同顶点但连接边缘不同的图形，则需要测试顶点相似性。如果通过了这个测试，那么通过使用排序后的距离为每个顶点分配唯一的标签。最长的边缘有两个顶点。对于这些顶点中的每一个，找到具有最长（剩余）边缘的顶点。将第一个顶点标记为0，下一个顶点标记为1。按顺序重复其他顶点，您将分配与移位和旋转无关的标签。现在，您可以精确比较边缘拓扑结构（检查对象1中每个连接两个顶点之间的边缘是否存在相应的连接相同两个顶点的边缘2）。注意：如果有多个相同的点间距离，因此需要进行抢占比较以使分配稳定且唯一，则开始变得非常复杂。

3）有可能两个图形具有相同的边缘长度分布，但它们并不相同...这是当一个对象是另一个对象的镜像时成立的。这很难检测！一种方法是使用四个非共面点（也许是从上一步标记为0到3的点），并比较它们定义的坐标系的“左右性”。如果左右性不匹配，则对象是镜像图像。

请注意，距离列表使您能够轻松拒绝非相同的对象。它还允许您通过允许一定量的排序错误来添加“模糊”接受度。也许将两个列表之间的均方根差作为“相似性度量”会很好。

编辑：看起来您的问题是一个没有边缘的点云。然后，令人讨厌的边缘对应问题（＃2）甚至不适用，可以忽略！但是，您仍然必须小心镜像图像问题＃3。