这总是需要大量的计算，特别是如果你想处理多达 2000 个点。我确信已经有针对这种模式匹配的高度优化的解决方案，但是您必须弄清楚它的名称才能找到它们。

由于您谈论的是点云（稀疏数据）而不是图像，因此我的互相关方法并不真正适用（并且在计算上会更糟）。像 RANSAC 这样的东西可能会很快找到匹配项，但我对此了解不多。

我的解决方案尝试：

假设：

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

所以你应该能够通过取消资格和减少计算时间来走很多捷径。简而言之：

1. 从源头挑三点
2. 搜索目标点，找到具有相同形状的 3 个点的集合
3. 当找到 3 个点的匹配时，检查他们定义的平面中的所有其他点，看看它们是否是紧密匹配
4. 如果找到所有点的多个匹配项，则选择 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 并将“距离”视为平方和。

如果没有找到 2 点匹配，则最短计算时间。 如果目标中有 2000 个点，这将是 2000 * 2000 距离计算，尽管许多会因减法而被取消资格，并且可以存储先前计算的结果，因此您只需要做$2000 \choose 2$= 1,999,000。

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

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

我会在 RANSAC 旁边的替代解决方案上添加 @mirror2image 描述，您可以考虑 ICP 算法（迭代最近点），可以在此处找到描述！

我认为使用这个 ICP 的下一个挑战是定义你自己的成本函数，以及目标平面相对于 3d 云点数据的起始位姿。一些实用的方法是在迭代期间在数据中引入一些随机噪声，以避免收敛到错误的最小值。这是我想你需要设计的启发式部分。

更新：

简化形式的步骤是：

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

重复步骤 1-4。

您可以在这里考虑可用的图书馆！（我还没试过），注册部分有一节（包括其他方法）。