代码之家 › 专栏 › 技术社区 › loneboat

算法:从已知点的星座中寻找二维方向?

geometry algorithm

loneboat · 技术社区 · 14 年前

问题

一、假设我在墙上拍摄一组已知的二维点的“照片”。我想知道拍照时相机相对于“垂直居中”的位置。一些点可能在图片中看不到(它们可能被遮挡)。(在这个类比中,假设相机是正交的,并且总是直接指向墙的平面,所以不需要考虑扭曲或透视)

提议的方法:

不知道怎么做;乐于接受建议。可能取B中所有点周围的凸包区域,并将其缩放到a周围的凸包区域。这很棘手,因为B中可能缺少点。

步骤2:将“B”中的任意点与其“A”中的孪生子匹配

选择集合B中的某个随机点。将此点称为K。以某种方式获取K相对于B中所有其他点的“指纹”(仅使用距离)。通过对A中的所有点进行指纹分析,并取与K最相似的点,在A中找到匹配点。

多个解决方案是可能的,所以继续旋转360度寻找解决方案。

那只是从臀部开枪,我可能离基地很远。有人有什么想法吗?

3 回复 | 直到 14 年前

Drew Hall 14 年前

假设您实际上不知道两个云中的点之间的对应关系,可以尝试使用统计方法。

首先,计算平均值 x0 计算原始云的平均值 x1 子集云的。平均向量的差异, x1-x0

现在,从每组中减去相关的平均向量,得到两个以原点为中心的云。计算每个云的协方差矩阵,找出其特征值和特征向量。所需的旋转可以从特征向量中找到,而缩放对应于特征值。

组合所有这些,您应该对所需的转换有一个良好的统计估计。显然,它的质量将取决于子集跨越原始集合的程度。

Lajos Arpad 14 年前

“给我一个站立的地方,我就可以移动地球”阿基米德

Arpi算法: 我们必须用坐标(0,0)选择集合a的一个点(X1)。(这将是站立的地方)

集合A中所有其他点的坐标将基于X1(0,0)和X2(一些_坐标,0)的坐标计算。

现在,从集合B(Y1)中选择一个点,它将是集合B的中心。从集合B(Y2)中选择另一个点,并将其放到集合B中的OX。现在,我们有一个标量和一个旋转角度。如果这是一个解决方案,那么B集中的Y1表示a集中的X1,B集中的Y2表示a集中的X2。如果我们可以在此基础上找到B集和a集之间的映射,使用B集的所有点和Yi<gt;Yj如果i<gt;j,其中i和j是我们表示中的点的索引,那么我们就有了一个潜在的解决方案,并存储了它。 Arpi算法结束

foreach point in A as X1 do
    foreach point in A as X2 do
        arpi's algoritm(X1, X2)

当然,您可以优化它,但是为了简单起见,我描述了它而没有优化(复杂),您的工作就是优化它,而且只有在您需要的时候。

Zack Bloom 14 年前

我会尽量减少目标点和发现点之间的偏差。这意味着我将每个目标点与一个找到的点配对,并对所有目标点应用任何变换(旋转、缩放或倾斜),从而减少偏差之和。我将对所有的势对重复这个过程,最终将匹配作为对的集合,并用最小的总偏差进行必要的变换。

真正的问题是如何优化它,使性能优于O(n^2)。我假设是某种启发式匹配,可能是缓存中间结果,或者是在过程的早期找到一种消除一些对的方法。