如何实现带旋转平移的2D观测点集与真值点集的匹配？

问题明确 #

已知点集A={P1,P2,P3,P4,P5}（坐标系o1，2D点）的完整距离矩阵，观测得到点集B=[B1,B2,B3]（坐标系o2，2D点），B的点均来自A但存在观测误差，o1与o2间有未知旋转(R)和平移(T)。需确定B中点与A中点的一一匹配关系。

基于图匹配的实现步骤 #

把点看作图的节点，两点间的距离作为边的权重（旋转平移不改变相对距离，这是核心依据），通过对比子图的边权重匹配度来确定对应关系：

• 构建B的距离子矩阵
  计算B中所有两点间的距离，生成3×3的距离矩阵D_B：

  0   d_B1B2  d_B1B3
  d_B2B1  0   d_B2B3
  d_B3B1  d_B3B2  0
  

• 枚举A中所有三元组组合
  从A的5个点中枚举所有可能的3点组合，共C(5,3)=10种（例如(P1,P2,P3)、(P2,P3,P5)等）。

• 遍历三元组的所有排列并计算匹配误差
  对每个A的三元组，生成其所有6种点顺序排列（因为B的点顺序不一定与A的三元组顺序一致），针对每种排列：

  • 从A的完整距离矩阵中提取对应顺序的3×3子矩阵D_A_sub
  • 计算D_B与D_A_sub的匹配误差，推荐用对应元素的平方差之和：

    误差 = Σ(D_B[i][j] - D_A_sub[i][j])² （i,j取0-2）
    

• 确定最优匹配
  遍历所有三元组的所有排列，选择误差最小的组合，该组合对应的A中点顺序即为B中点的匹配对象。

优化技巧 #

• 预排序快速筛选：将B的三个非零距离排序，同时对每个A的三元组的三个非零距离排序，先对比排序后的距离序列，快速排除差异较大的三元组，减少后续计算量。
• 阈值过滤：设定误差阈值，若某个组合的误差超过阈值，直接跳过，不用计算后续排列。

内容的提问来源于stack exchange，提问作者HC S