我需要评估两组3D点是否相同(忽略平移和旋转),通过查找和比较适当的几何哈希值。我研究了一些几何哈希技术的论文,并发现了一些算法,但它们往往会受到“视觉要求”的复杂性的影响(例如2D到3D,遮挡,阴影等)。
此外,如果两个几何形状稍有不同,我希望哈希值也不会有太大的差异。
有没有人知道符合我的需求的算法,并可以提供一些进一步研究的链接?
谢谢
此外,如果两个几何形状稍有不同,我希望哈希值也不会有太大的差异。
有没有人知道符合我的需求的算法,并可以提供一些进一步研究的链接?
谢谢
对我而言,这似乎是一个数值优化问题。您希望找到将一组点转换为尽可能接近另一组点的变换参数。定义某种残差或“能量”,在点重合时最小化它,并将其传递给最小二乘优化器或类似工具。如果它成功将分数优化为零(或根据浮点误差可以期望的那样接近于零),那么这些点就是相同的。
搜索引擎
least squares rotation translation
发现有很多论文基于这种技术(例如"两点模式之间的最小二乘估计变换参数")。
以下是根据下面的评论更新:如果不知道点之间的一对一对应关系(如上述论文所假设的那样),则只需要确保被最小化的得分独立于点的顺序。例如,如果将这些点视为小质点(使用有限半径球体来避免零距离问题),并通过优化平移和旋转参数来使系统的总引力能最小化,那么就可以使用该方法。
有许多SIGGRAPH出版物可能对您有所帮助。
例如,Brown和Rusinkiewicz的“三维扫描的全局非刚性对齐”:
http://portal.acm.org/citation.cfm?id=1276404
一个可以帮助你入门的通用搜索:http://scholar.google.com/scholar?q=siggraph+point+cloud+registration
这是我会做的方法:
要比较两个集合,除非您需要提前存储哈希结果,否则只需将第3步的点集应用您喜欢的比较算法即可。例如,可以计算两个集合之间的距离。
我不确定是否可以为第4步推荐算法,因为似乎您的要求是相互矛盾的。任何称为哈希的东西通常具有这样的特性:输入的微小变化会导致非常不同的输出。无论如何,现在我已经将问题简化为数字数组,所以您应该能够解决问题。
[*] 如果您的两个或三个轴重合,请通过其他方式选择坐标,例如作为最长距离。但是对于随机点来说,这种情况极为罕见。