4-Points Congruent Sets for Robust Pairwise Surface Registration

---

1. 背景

1.1. 问题描述

给定两个处于任意初始位置的点集P$P$和Q$Q$，找到两个点集之间的最佳刚性变换，使得P$P$，Q$Q$中两点间距离小于δ$\delta$的点数最多。

1.1.1. RANSAC

• 分别在点集P$P$和点集Q$Q$中任意选取三个点来组成一个基础关联对
• 计算这个关联对的旋转矩阵Ti$T_i$
• 计算点集P$P$中处在点集Q$Q$中的点δ$\delta$距离内的点的个数ki$k_i$
• 如果ki$k_i$足够大，则认为ki$k_i$是个好结果，否则重读以上步骤
• 这个过程将被重复L$L$次，选取最高的ki$k_i$作为最后的结果

1.1.2 Randomized Alignment

• 在点集P$P$中随机选取一个base
• 计算在点集Q$Q$中所有有可能的bases，得到旋转矩阵
• 验证配准
  
  • 先验证部分点集重合
  • 验证剩余点

如何有效的计算可能的bases，提出4点法，基于共面点（planar congruent sets）

1.2. 4点法概述

使用从点集P$P$中选取的共面四点作为base B$B$，然后采用一定的算法在点集Q$Q$中找到所有的与B$B$近似一致的共面4点对，近似一致指的是两个4点对可以经过刚性变换(rigid transformation)在允许范围(allowed tolerance)δ$\delta$内对齐

2. 4点法

2.1 Overview

仿射变换遵循以下法则，给定三个共线点a,b,c$a,b,c$，那么比例r=||a−ba−c||$r=||{\displaystyle \frac{a-b}{a-c}}||$是不变的。给定一个共面四点标准对(coplanar 4-points base sets)，我们在给定的数据点中寻找近似仿射相等的共面四点对，接着我们确认这些共面四点对与选定的共面四点标准对是否在一定的距离约束下相等。

2.2 4点对的仿射不变性

并非全共线的一个共面四点集X≡a,b,c,d$X\equiv a,b,c,d$,定义了两个独立的比率。令ab$ab$,cd$cd$相交于点e$e$，则两个独立的比率为：

在仿射变化中是不变的并且是唯一的。

现在给定一个具有n$n$个点的点集Q$Q$，以及两个由点P$P$得到的仿射不变的比率r1$r_1$,r2$r_2$,对每一对点q1,q2⊂Q$q_1,q_2\subset Q$，计算他们的中间点：

若任意两对这样的点，一对由r1$r_1$计算得到的中间点和另一对由r2$r_2$计算得到的中间点在允许范围内一致，那么可以认为这两对点可能是P$P$中基础点的仿射对应点。

2.3 如何在3D模型中找到合适的4点

给定一个在一定范围内共面的基础对B⊂P$B\subset P$，以及另一个点集Q⊂R3$Q\subset R^3$。我们的目标是从点集Q$Q$中找到所有在允许范围δ$\delta$与基础对B$B$一致的4点的集合。

• 计算给定基础对B$B$的放射不变比
• 使用2.2中提到的算法在点集Q$Q$中寻找所有能与基础对B$B$通过放射变换配对的4点集合
• 通过检测这些点集的原始位置，保留下只能通过刚性变化配对的点集
• 通过最小二乘法，对每一对点和B$B$计算其最佳变化

事实上，考虑到寻求刚性变换的解，对于一个基础对B≡{a,b,c,d}$B\equiv \{a,b,c,d\}$，首先计算两两点间的距离d1=||a−b||，d2=||c−d||$d_1=||a-b||，d_2=||c-d||$，然后仅仅考虑点集Q$Q$中两点距离在一定范围δ$\delta$内为d1$d_1$或d2$d_2$的点对。

3. 4点法（The 4PCS Algorithm）

给定两个点集P，Q$P，Q$，不确定度δ$\delta$，以及点集P$P$与点集Q$Q$芙蓉重叠度的预估f$f$。我们的目标是找到一个刚性变换使得点集P$P$中的点尽可能多的与点集Q$Q$中的某些点的距离小于δ$\delta$。

• 在点集P$P$中选择一些共面4点对。实际上，在选择的过程上是先随机选择3个点，再选择能够与这个三个点在一定范围内组成共面4点对的另一个点。若选择的这个点与其他点相距较远，可以提升配准的稳定度，也就是说更加精确。然而，如果选择的点过远，则会导致选择的点可能不全在两个点集重叠的部分，从而无法计算出理想的变化对。这里使用重复度（overlap）来预估这个最大距离。
• 对于给定的基础对B$B$，我们可以定义放射不变比集合。从点集Q$Q$中提取出所有在一定范围δ$\delta$内可能与B$B$相符合的4点集合。U≡{U1,U2,…,Us}$U\equiv \{U_1,U_2,\dots ,U_s\}$。对任一Ui$U_i$，通过B$B$和Ui$U_i$的关系可以计算出最佳刚性变换Ti$T_i$使得B$B$和Ti$T_i$足够接近。
• 为了确认唯一的Ti$T_i$，我们计算Ti(P)$T_i(P)$，并且统计有多少点与点集Q$Q$之间的距离小于δ$\delta$。采用ANN（Approximate Nearest Neighbor）来提高确认效率。具体来说就是首先从点集P$P$中选择一部分点使用Ti$T_i$进行变换，然后统计与点集Q$Q$足够接近的点，如果有足够的点被统计到，那么对余下的点也进行这样的测试，并且为Ti$T_i$评估一个分数。最后得到最佳刚性变换矩阵T$T$。
• 对于不同的基础对Bi$B_i$，我们都可以按照上述的办法找到最佳变化Ti$T_i$，根据overlap测试L$L$组不同的基础对，最终得到最佳变换矩阵Topt$T_{o}pt$。