点云中的配置文件匹配

#1 楼

这总是需要大量的计算，尤其是当您要处理多达2000点时。我敢肯定，已经有针对这种模式匹配的高度优化的解决方案，但是您必须弄清楚它的名称才能找到它们。

因为您是在谈论点云（稀疏数据）而不是图像，所以我的互相关方法并没有真正应用（在计算上甚至会更差）。像RANSAC这样的东西可能很快找到了匹配项，但是我对此并不了解。

我尝试解决的方法：

假设：


您想要找到最佳匹配，而不仅仅是宽松或“可能正确”的匹配
由于测量或计算中的噪声，匹配将具有少量误差
源点共面
所有源点都必须存在于目标中（=任何不匹配的点都与整个配置文件不匹配）

因此，您应该能够通过取消限制条件和减少计算时间来采取许多捷径。简而言之：


从源中选取3个点
搜索目标点，找到3个形状相同的点的集合
找到3个点的匹配，请检查它们定义的平面中的所有其他点，以查看它们是否接近。
如果找到所有点的多个匹配项，则选择3D距离误差之和最小的那个

更详细：

pick a point from the source for testing s1 = (x1, y1)
Find nearest point in source s2 = (x2, y2)
d12 = (x1-x2)^2 + (y1-y2)^2
Find second nearest point in source s3 = (x3, y3)
d13 = (x1-x3)^2 + (y1-y3)^2
d23 = (x2-x3)^2 + (y2-y3)^2

for all (x,y,z) test points t1 in target:
    # imagine s1 and t1 are coincident
    for all other points t2 in target:
        if distance from test point > d12:    
            break out of loop and try another t2 point
        if distance ≈ d12:
            # imagine source is now rotated so that s1 and s2 are collinear with t1 and t2
            for all other points t3 in target:
                if distance from t1 > d13 or from t2 > d23:
                    break and try another t3
                if distance from t1 ≈ d13 and from t2 ≈ d23:
                    # Now you've found matching triangles in source and target
                    # align source so that s1, s2, s3 are coplanar with t1, t2, t3
                    project all source points onto this target plane 
                    for all other points in source:
                        find nearest point in target
                        measure distance from source point to target point
                        if it's not within a threshold:
                            break and try a new t3
                        else:
                            sum errors of all matched points for this configuration (defined by t1, t2, t3)

以其他所有点的平方误差最小的配置为最佳匹配

由于我们正在处理3个最近的相邻测试点，因此可以通过检查匹配的目标点是否在某个半径内来简化匹配的目标点。例如，如果从（0，0）搜索半径1，我们可以基于x1- x2取消（2，0）的资格，而无需计算实际的欧几里得距离，从而将其加快一点。假定减法比乘法快。也有基于更多任意固定半径的优化搜索。

function is_closer_than(x1, y1, z1, x2, y2, z2, distance):
    if abs(x1 - x2) or abs(y1 - y2) or abs(z1 - z2) > distance:
        return False
    return (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 > distance^2 # sqrt is slow

3D欧式距离为$ d = \ sqrt {（x_1-x_2）^ 2 +（y_1 -y_2）^ 2 +（z_1-z_2）^ 2} $
，但是平方根很慢。由于我们只是在比较相对距离，因此我认为我们可以删除sqrt并将“距离”视为平方和。如果目标中有2000个点，则这将是2000 * 2000距离计算，尽管许多计算都会因减法而取消资格，并且可以存储以前的计算结果，因此您只需要执行$ 2000 \ choose 2 $ = 1,999,000。

实际上，由于无论如何都需要计算所有这些，无论是否找到匹配项，并且由于您只关心最近的邻居，所以如果有足够的记忆，最好预先存储-使用优化算法计算这些值。诸如Delaunay或Pitteway三角剖分之类的方法，其中目标中的每个点都与其最近的邻居相连。将它们存储在表中，然后在尝试将源三角形拟合到目标三角形之一时在每个点上查找它们。

涉及很多计算，但是它应该相对较快，因为仅涉及稀疏的数据，而不是像体积数据的互相关那样将大量无意义的零相乘。如果您首先找到点的中心并将其存储为一组坐标，则同样的想法适用于2D情况。

#2 楼

我会在RANSAC旁边的替代解决方案上添加@ mirror2image描述，您可以考虑ICP算法（迭代最近点），请参见此处的描述！定义自己的成本函数，以及相对于3d浊点数据的目标平面的起始姿势。一些实用的方法是在迭代过程中在数据中引入一些随机噪声，以避免收敛到错误的最小值。我想这是您需要设计的启发式部分。

更新：

简化形式的步骤是：


查找每个输入点的最接近点。
计算从输入到目标的变换，然后使用该变换移动输入点。
计算相似度函数（例如，每个输入点的距离wrt到其对应的配对目标点）。
检查停止条件。

重复步骤1-4。

这里有可用的库可供您考虑！ （我还没有尝试过），注册部分有一个部分（包括其他方法）。