比较三维结构

Question

我需要通过查找和比较适当的几何散列来评估两组3d点是否相同（忽略平移和旋转）。我做了一些关于几何散列技术的论文研究，并且我发现了一些算法，然而这些算法往往因“视觉要求”（例如2d到3d，遮挡，阴影等）而变得复杂。

而且，我很乐意，如果两个几何形状略有不同，那么散列也没有太大差异。

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

谢谢

Answer 1

我就是这样做的：

1. 将组定位在质心处
2. 计算inertia tensor。这为您提供了三个坐标轴。转向他们。 [*]
3. 以您所需的精度记下给定顺序中的点列表（例如，从上到下，从左到右）。
4. 将您想要的任何算法应用于结果数组。

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

我不确定我是否可以推荐步骤4的算法，因为看起来你的要求是矛盾的。任何称为散列的东西通常都具有输入的微小变化导致输出非常不同的特性。无论如何，现在我已经将问题简化为一系列数字，所以你应该能够解决问题。

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

Answer 2

你的第一个想法可能是试图找到将一个对象映射到另一个对象的旋转，但这是一个非常复杂的主题......并且实际上并不是必需的！你不是问如何最好地匹配这两者，你只是问它们是否相同。

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

三个问题：

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

2）这仅使用顶点来定义形状，而不是边缘。这可能很好（实际上也是如此）但是如果你希望有相同顶点但连接边不同的数字。如果是这样，首先测试顶点相似性。如果通过，则使用该排序距离为每个顶点指定唯一标签。最长边有两个顶点。对于每个顶点，找到具有最长（剩余）边的顶点。标记第一个顶点0和下一个顶点1.按顺序重复其他顶点，您将分配与移位和旋转无关的标记。现在，您可以准确地比较边缘拓扑（检查两个顶点之间的对象1中的每个边缘，对象2中相同的两个顶点之间是否存在相应的边缘）注意：如果您有多个相同的点间距离，那么这开始变得非常复杂需要决胜局比较才能使作业稳定而独特。

3）两个数字有可能是相同的边长，但它们并不相同。当一个物体是另一个物体的镜像时，这是正确的。发现这很烦人！一种方法是使用四个非共面点（可能是上一步标记为0到3的点）并比较它们定义的坐标系的“手性”。如果手性不匹配，则对象是镜像。

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

编辑：看起来您的问题是没有边缘的点云。然后令人讨厌的边缘对应问题（＃2）甚至不适用，可以忽略！你仍然需要注意镜像问题＃3。

Answer 3

有一堆SIGGRAPH出版物可能对您有所帮助。

例如Brown和Rusinkiewicz撰写的“全球非刚性三维扫描”：

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

一般搜索可以帮助您入门：

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

Answer 4

spin images是一种解决它的方法。

Answer 5

对我来说似乎是一个数值优化问题。您希望找到转换的参数，这些参数将一组点转换为尽可能接近另一组。定义某种残差或“能量”，当点重合时将其最小化，并将其夹在某些最小二乘优化器或类似物上。如果它设法将得分优化为零（或者在给定浮点误差的情况下尽可能接近），那么这些点是相同的。

谷歌搜索

least squares rotation translation

在这种技术的基础上发表了不少论文（例如"Least-Squares Estimation of Transformation Parameters Between Two Point Patterns"）。

更新以下评论：如果点之间的一对一对应关系未知（如上文所述），那么您只需要确保最小化的分数与点排序无关。例如，如果将点视为小质量（有限半径球体以避免零距离爆破），并通过优化平移和旋转参数来设置最小化系统的总重力能量，则应该可行。

Answer 6

1. 如果要估计两个相似点云之间的刚性变换，可以使用完善的迭代最近点方法。该方法从对变换的粗略估计开始，然后通过计算最近邻居并最小化相关联的成本函数来迭代地优化变换。它可以有效地实现（甚至是实时），并且有可用于matlab，c ++的可用实现...这个方法已经扩展并有几个变体，包括估计非刚性变形，如果你对扩展感兴趣，你应该看看计算机图形文件解决扫描注册问题，你的问题是关键的一步。有一个起点，请参阅Wikipedia page on Iterative Closest Point，它有几个很好的外部链接。只是来自matlab implementation的预告图像，旨在匹配点云： （来源：mathworks.com） 在对齐之后，您可以使用最终的错误度量来说明两点云的相似程度，但这是一个非常特殊的解决方案，应该有更好的解决方案。
2. 使用形状描述符，可以计算在平移/旋转下通常不变的形状的指纹。在大多数情况下，它们是针对网格而不是点云定义的，但是有很多形状描述符，因此根据您的输入和要求，您可能会发现一些有用的东西。为此，您可能需要查看shape analysis的字段，并且可能this 2004 SIGGRAPH course presentation可以了解人们如何计算形状描述符。

Answer 7

也许您还应该阅读RANSAC算法。它通常用于将全景图像拼接在一起，这似乎与您的问题有点类似，仅在2个维度上。只需google for RANSAC，全景和/或拼接即可获得起点。