比较三维结构

Question

我需要通过查找和比较适当的几何哈希来评估两组3d点是否相同（忽略平移和旋转）。我做了一些关于几何散列技术的论文研究，并且发现了一些算法，但是这些算法往往会因“视觉要求”（例如2d到3d，遮挡，阴影等）而变得复杂。此外，我会喜欢这个，如果两个几何图形略有不同，哈希值也没有什么不同。

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

谢谢

Answer 1

这是我会怎么做：

1. 位置质量
2. 计算inertia tensor中心集合。这给你三个坐标轴。旋转到他们。 [*]
3. 按照给定的顺序（例如，从上到下，从左到右）以您所需的精度记下点列表。
4. 将所需的任何算法应用于结果数组。

要比较两个组，除非你需要预先存储的哈希结果，只是用自己喜欢的比较算法的套步骤3点的这可能是，例如，计算两个集合之间的距离。

我不确定是否可以向您推荐步骤4的算法，因为它似乎是您的要求是矛盾的。任何被称为散列的函数通常具有输入的小改变导致非常不同的输出的性质。无论如何，现在我已经将问题简化为一系列数字，所以您应该能够弄清楚事情的真相。如果你的两个或三个坐标轴通过其他方法重合选择坐标，例如，作为最长的距离。但对于随机点来说这是非常罕见的。

Answer 2

似乎是一个数值优化问题给我。你想找到变换的参数，它将一组点转换为尽可能靠近另一点。定义某些剩余或“能量”，当点重合时将其最小化，并将其放在某个最小二乘优化器或类似物中。如果它设法将得分最优化为零（或者给定浮点错误可以预期的那么接近），那么点是相同的。

谷歌搜索

least squares rotation translation 

变成了这种技术（例如"Least-Squares Estimation of Transformation Parameters Between Two Point Patterns"）相当多的论文建设。

更新下面的评论如果点之间的一对一的对应关系是不知道的（如上文所述），那么你只需要确保被最小化的分数独立于点排序。例如，如果您将这些点视为小质量（有限半径球体以避免零距离放大），并着手通过优化旋转参数来使系统的总重力能量最小化，那么这应该起作用。

Answer 3

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

例如“3-d扫描全局的非刚性对齐” 布朗和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

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

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

三个问题：

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

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

3）有可能两个人物具有相同的边缘长度人群，但它们并不完全相同。当一个物体是另一个物体的镜像时，这是真实的。这是很烦人的检测！一种方法是使用四个非共面点（可能是上一步标记为0到3的点），并比较它们定义的坐标系的“惯性”。如果使用方向不匹配，则对象为镜像。

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

编辑：看起来像你的问题是没有边缘的点云。然后边缘对应（＃2）恼人的问题甚至不适用，可以忽略！尽管如此，你仍然必须小心镜像问题＃3。

Answer 6

1. 如果你想估计刚性 变换两者之间的相似点 云您可以使用 完善 迭代最近点方法。该方法开始于对变换的粗略估计，然后通过计算最近的 邻居并最小化相关联的成本函数，迭代地优化变换的 。它可以是 有效地实现（甚至 实时）和存在可用 实现可用于 MATLAB，C++ ...该方法一直 延伸并具有若干变型，包括 估计非刚性变形 ，如果有兴趣 您应该看看 计算机图形文件解决 扫描注册问题，其中 您的问题是一个关键的步骤。有关 的一个起点，请参阅Wikipedia page on Iterative Closest Point 其中有几个很好的外部链接。刚刚从matlab implementation这是设计了一个传情图像匹配点云： alt text http://www.mathworks.com/matlabcentral/fx_files/12627/1/icp.gif

   对准你可以在最后 错误措施，说 两个点云的相似程度后，但这是 非常即席解决方案，有 应该是更好的一个。

2. 使用形状描述符一个罐的形状，其 往往下 平移/旋转不变的 计算指纹。在大多数情况下，它们被定义为网格，而不是点云，但是有很多形状描述符，所以根据您的输入和要求，您可能会发现一些有用的东西。为此，您需要查看shape analysis的字段，并且可能this 2004 SIGGRAPH course presentation可以感知人们做什么来计算形状描述符。

Answer 7

也许你还应该阅读RANSAC算法。它通常用于将全景图像缝合在一起，这些图像看起来与您的问题有点相似，仅在二维中。只需谷歌RANSAC，全景和/或拼接起点。