目录
- 写在前面
- Abstract摘要
- 1 Introduction引言
- 2 Background研究背景
- 3 Approximate Congruent 4-Points近似共面四点
- 4 The 4PCS Algorithm 4PCS算法
- 5 Results结果
- 总结
- 参考及感谢
- 完
写在前面
论文4-Points Congruent Sets for Robust Pairwise Surface Registration阅读笔记
下载地址：share_noel/papers/reg-4-Points Congruent Sets for Robust Pairwise Surface Registration.pdf提取码：0ooc
该论文是比较出名的4pcs点云配准算法原文，本篇博客为论文阅读笔记，对关键内容进行提取、翻译、解释，并包含个人理解，如有错漏敬请指正。
Abstract摘要
本文提出4PCS(4-Points Congruent Sets)算法进行点云配准。允许原始噪声，离群值，无需滤波去噪，无需初始配准。我们的方法基于一种新的技术，即从一个三维点集中提取所有共面4点集，这些点集在刚性变换下与给定的共面4点集近似全等。这个过程时间大致消耗
O
(
n
2
+
k
)
O(n^2+k)
O(n2+k)，其中n是候选点的数目，k是得到的4点集的数目。实际上，当噪声低和重叠度足够高时，使用局部描述子可以将时间复杂度减至
O
(
n
+
k
)
O(n+k)
O(n+k).
知道icp算法的同学都知道，icp算法精度高，但是对数据的要求也相对较高，噪声离群值都会对算法产生影响，并且需要点云进行粗配准（或初始配准）防止算法陷入局部最优。
1 Introduction引言
刚体变换可以由3对已知的点对恢复。我们把这样的点集成为基集（base）。刚体变换下不变的局部描述子经常用来提取 可以产生良好候选点对的 点集。
给定在任意初始姿态下的两个个点集P和Q，匹配的基集（一个来自P，另一个来自Q）生成一组可以将P和Q进行配准的候选变换。可以使用一种称为几何哈希的技术从这样的候选集中选择一个好的变换[Wolfson and Rigoutsos 1997]。随机算法，如RANSAC（随机抽样一致性）[Fischler and Bolles 1981]，对一些基本候选重复投票过程足够多次，以确保它以高概率找到一个好的解决方案。Chen[1999]提出了对这种基本方法的改进，并在速度和对噪声的鲁棒性之间进行了权衡。
目标质心和PCA(e object centroids and Principal Component Analysis (PCA))常用来粗配准。在部分重叠的情况下，PCA等粗配准方法不太好（原文是breakdown）。
局部特征描述是很好的工具。虽然在噪声下也可能鲁棒地计算出这些局部特征描述子,但是在噪声和离群点很严重的时候，定义可信的描述子仍然是挑战。
在这种情况下，一个有效的替代方法是依赖大数原理（principle of large numbers），而不是使用局部描述符。该方法需要求解最大公共点集（LCP）问题：给定两个点集P和Q，在δ 一致(δ-congruence，此处不知怎样翻译最好)下的LCP来求解P的一个子集P’（P’有最大的基数），使得在适当的距离测度下T（P’）和Q之间的距离小于δ，其中T是一个刚性变换。
当P和Q分别是m和n点时，最原始的方法的时间复杂度是
O
(
m
3
n
3
)
O(m^3n^3)
O(m3n3)（因为3个点对就能求解刚体变化，从P中选3个点需要
m
3
m^3
m3，从Q中选3个点需要
n
3
n^3
n3）。该算法的随机版本从P开始尝试适当数量的随机基，从而将复杂度降低到
O
(
m
n
3
l
o
g
n
)
O(mn^3logn)
O(mn3logn)[Irani和Raghavan 1996]。通过随机验证，这种复杂度可以进一步降低到
O
(
n
3
l
o
g
n
)
O(n^3logn)
O(n3logn)。然而，对于较大的点集，这样仍然是狠耗时的。
本文算法的关键是选取一个宽基集（wide-base），如图2。（就是选取的点的距离相对大些，算法才更稳定，明显上面的配准效果比下面的好，因为上面的点隔得远，但是最远距离要受重叠度的限制）
宽基集（wide-base）和LCP让我们的配准算法能适应噪声和离群点，因此算法能对原始数据进行直接配准。即使在低重叠度和没有初始配准的情况下，算法也能成功配准点云，如图1。
2 Background研究背景
问题定义：
给定任意初始位置的两个点集P和Q，从一个指定的变换族中找到最佳变换，通常是刚性变换，它能最好地配准P和Q。对最佳变换，我们指的是这个变换，能将P配准至Q，P’是P的子集，此时P’中的点数量最大且P’中的点（可认为是重叠部分的点） 与 Q的距离 均小于
δ
\delta
δ。在刚性变换的情况下，三个点对足以唯一地确定一个空间变换。
RANSAC
RANSAC大量用于拟合被噪声和离群值污染的模型。
基于RANSAC的配准如下：
随机从P、Q中各选择3个点（P中3个，Q中3个），组成3个点对，计算变换矩阵
T
i
T_i
Ti;
将P使用
T
i
T_i
Ti变换后，计算P中与Q的距离小于
δ
\delta
δ的点数，记为
k
i
k_i
ki；
如果
k
i
k_i
ki足够大，将
T
i
T_i
Ti视为一个好的结果，否则重新选择3个点对进行计算；
上述过程将会执行L次，最终选择
k
i
k_i
ki最高的结果作为最佳结果。从P和Q中随机选取基点的过程重复L次，选出最佳解，即ki值最高的解。
RANSAC原文：
share_noel/papers/RANSAC原文-Random sample consensus–a paradigm for model fitting with applications to image analysis and automated cartography.pdf提取码：0ooc
关于RANSAC算法的理解和其他应用可参考以下博客：
RANSAC算法详解
RANSAC
RANSAC算法理解
深度解析RANSAC算法
Randomized Alignment
Randomized Alignment是RANSAC的一种变体算法。
设
p
g
p_g
pg是从P中随机选择的一个点也存在于Q中的概率（即，在重叠区域中），基(base)的大小为N，
p
f
p_f
pf是在L尝试找到存在的良好拟合后算法退出的概率。由于我们随机从P中选择点，我们得到：
p
f
=
（
1
−
p
g
N
）
L
p_f=（1-p^N_g）^L
pf=（1−pgN）L。
因此，
p
s
p_s
ps为大于成功的概率，则有迭代次数L:
L
>
l
o
g
(
1
−
p
s
)
/
l
o
g
(
1
−
p
g
N
)
(1)
L>log(1-p_s)/log(1-p^N_g)\tag{1}
L>log(1−ps)/log(1−pgN)(1)
对于刚体变换，N=3已经足够。
对于这个公式，下面给出我的理解：
失败的概率
p
f
p_f
pf等于1减去成功的概率
p
s
p_s
ps：
p
f
=
1
−
p
s
p_f=1-p_s
pf=1−ps
则：
p
f
=
（
1
−
p
g
N
）
L
=
1
−
p
s
p_f=（1-p^N_g）^L=1-p_s
pf=（1−pgN）L=1−ps
取对数，并把L放前面：
l
o
g
(
1
−
p
g
N
)
L
=
l
o
g
(
1
−
p
s
)
log(1-p^N_g)^L=log(1-p_s)
log(1−pgN)L=log(1−ps)
L
=
l
o
g
(
1
−
p
s
)
/
l
o
g
(
1
−
p
g
N
)
L=log(1-ps)/log(1-p^N_g )
L=log(1−ps)/log(1−pgN)
这是成功实现的情况下的L，那么实际使用时，L肯定只能大于上述结果，所以：
L
>
l
o
g
(
1
−
p
s
)
/
l
o
g
(
1
−
p
g
N
)
L>log(1-ps)/log(1-p^N_g )
L>log(1−ps)/log(1−pgN)
文章的算法基于 randomized alignment。但是，我们并没有测试Q中的所有可能基集合，我们使用共面点集来选取一个小的基集合来和P的基集匹配。
3 Approximate Congruent 4-Points近似共面四点
与上面的只选取3点不同，我们的方法是从P中选择一个共面4点集，记为B，然后在Q中快速查找与B近似全等（approximately congruent to B）的所有子集。后面将阐述如何高效地从P中提取一个B子集。两点集近似全等（approximate congruence），意味着两个四点集可以使用刚体变换进行配准。下文将阐述如何在 O ( n 2 + k ) O(n^2+k) O(n2+k)时间内在Q中提取所有这样的全等子集。
3.1overview 概述
放射变换具有如下属性：
给定三个共线点
{
a
,
b
,
c
}
\{a,b,c\}
{a,b,c}，比值
∥
a
−
b
∥
/
∥
a
−
c
∥
\parallel{a-b}\parallel/\parallel{a-c}\parallel
∥a−b∥/∥a−c∥不变。
对于给定的一个共面的4点基集，我们在另一个给定点云中寻找（近似）与其仿射等价的4点集。
3.2 Affine Invariants of 4-Points Sets四点集的仿射不变
如图4，共面点集
X
≡
{
a
,
b
,
c
,
d
}
X\equiv\{a,b,c,d\}
X≡{a,b,c,d}，并不全部共线，
e
e
e是
a
b
ab
ab和
c
d
cd
cd的交点，定义两个独立的比值
r
1
,
r
2
r_1, r_2
r1,r2：
r
1
=
∥
a
−
e
∥
/
∥
a
−
b
∥
r_1=\parallel{a-e}\parallel/\parallel{a-b}\parallel
r1=∥a−e∥/∥a−b∥
r
2
=
∥
c
−
e
∥
/
∥
c
−
d
∥
(2)
r_2=\parallel{c-e}\parallel/\parallel{c-d}\parallel\tag{2}
r2=∥c−e∥/∥c−d∥(2)
r
1
,
r
2
r_1, r_2
r1,r2在仿射变换下具有不变性，并且在唯一地定义了仿射变换的4个点。现在给定一个
n
n
n个点的集合Q，以及两个仿射不变比
r
1
,
r
2
r_1, r_2
r1,r2，我们可以在
O
(
n
2
+
k
)
O(n^2+k)
O(n2+k)时间内有效地提取由这两个不变量定义的所有4点集，其中
k
k
k是所提取的4点集的个数。对于每个点对
q
1
,
q
2
∈
Q
q_1, q_2\in{Q}
q1,q2∈Q，计算两个中间点：
e
1
=
q
1
+
r
1
(
q
2
−
q
1
)
e_1=q_1+r_1(q_2-q_1)
e1=q1+r1(q2−q1)
e
2
=
q
1
+
r
2
(
q
2
−
q
1
)
(3)
e_2=q_1+r_2(q_2-q_1)\tag{3}
e2=q1+r2(q2−q1)(3)
任何两对中间点（一个来自
r
1
r_1
r1，另一个来自
r
2
r_2
r2）重合，可能对应于一个仿射变换4点集（见图5）。由于点
e
1
−
s
e_1-s
e1−s和
e
2
−
s
e_2-s
e2−s都在同一个坐标系中，因此可以使用邻域搜索结构快速搜索重合点。
在实际中，由于噪声的影响，中间点不是完全重合的，最终成为附近的点。为了允许对邻近点进行快速范围查询，我们在
R
3
\mathbb{R}^3
R3中使用标准数据结构。
我们使用近似范围树，它可以在
O
（
n
l
o
g
n
）
O（n logn）
O（nlogn）内由大小为
n
n
n的点集构建，并支持在
O
（
l
o
g
n
+
k
）
O（logn+k）
O（logn+k）时间内查询任何矩形内的所有点，
k
k
k是要报告的点数。一旦所有的中间点都插入到范围树中，我们将查询与
r
1
r_1
r1相关联的所有点，这些点位于与
r
2
r_2
r2相关的点的
δ
−
\delta-
δ−邻域(
δ
−
\delta-
δ−neighborhood)中。
计算所有中间点需要
O
（
n
2
）
O（n^2）
O（n2）时间，构建和查询相邻点需要
O
（
n
2
l
o
g
n
+
k
）
O（n^2 logn+k）
O（n2logn+k），其中k是报告的总点数。稍后我们将进一步改善这种复杂性。
3.3 Extracting Congruent 4-points in 3D三维中提取全等4点集
给定一个（近似）共面4点集B（B从P中选择），和另一个点集
Q
∈
R
3
Q\in\mathbb{R}^3
Q∈R3，我们的目标是从Q中提取与B近似全等的所有4点的集合，直到近似水平
δ
\delta
δ。首先给定B，我们计算它在这个平面上的两个仿射不变量比率，如前所述。然后从点Q中，使用3.2节中描述的方法，通过仿射变换提取与B相关的所有点集。
为了去除非全等基（non-congruent bases），我们观察它们在
R
3
\mathbb{R}^3
R3中的原始位置，并验证相应的集合是否在某个阈值内与基集B一致。然后利用基集B和Q中的每个潜在可能的基集，利用Horn[1987]提出的闭式解计算最小二乘意义下的最佳刚体变换。对于宽基，由于基点之间的距离接近Q的直径，因此子集的典型数目为
O
(
n
)
O(n)
O(n)加上一个小常数（这里的
O
(
n
)
O(n)
O(n)表示空间复杂度而不是时间复杂度）。在这种情况下，我们可以从大小为n的点集中提取所有的全等4点集。
上述过程需要计算和存储
O
(
n
2
)
O(n^2)
O(n2)中间点，这对于大点集是不允许的。然而，当寻找刚性变换时，一个保守的
O
(
n
)
O(n)
O(n)子集就足够了，因为以下原因：刚性变换保持点间欧几里德距离。给定基
B
≡
{
a
,
b
,
c
,
d
}
B\equiv\{a,b,c,d\}
B≡{a,b,c,d}，我们首先计算距离
d
1
=
∥
a
−
b
∥
d_1=\parallel{a-b}\parallel
d1=∥a−b∥和
d
2
=
∥
c
−
d
∥
d_2=\parallel{c-d}\parallel
d2=∥c−d∥。现在我们只考虑Q中相距
d
1
d_1
d1或
d
2
d_2
d2的点对，误差为
δ
\delta
δ。对于具有大致均匀采样的点集，我们只需要在距离数据结构中插入
O
(
n
)
O(n)
O(n)对。因此，整个算法在$O(n^2)时间内运行，包括距离树构造的时间。只考虑线性数量的此类对，而不是它们的二次数，会导致显著的加速和可管理的空间，即使对于大型点集，也可以实现刚体变换配准。
4 The 4PCS Algorithm 4PCS算法
我们给出了两个点集P和Q，点的位置精度的一些不确定度(
δ
>
0
\delta>0
δ>0)，以及对P中部分点
f
f
f的估计，
f
f
f里面的点能与Q匹配。我们的目标是找到一个刚性变换，使P中最大数量的点到Q的距离小于阈值
δ
\delta
δ。我们提出了一个算法（见algorithm 1），其运行取决于给定点集之间的最大匹配点的数量，并被随机化，以很高的概率找到正确的解。
首先我们选择一个共面4点组成的基集：
B
⊆
P
B\subseteq P
B⊆P。实际上，先随机选3个点，再选第四个点，与前三个点近似在同一平面。点各自相隔较远能让结果更稳定，但是太远的话可能点又不在重叠区域内了，因此得不到满意的结果。我们使用重叠度
f
f
f来估计这个距离。如果
f
f
f没有给定，那么在算法上使用从1递减的
f
f
f如
f
=
1
,
0.5
,
0.25
,
.
.
.
f=1,0.5,0.25,...
f=1,0.5,0.25,...直到得到满意的结果。在重叠度
f
f
f已知情况下，我们可以选择一个在重叠部分的3点集，再按上面的方法选择第4个点。
在基集B的获取阶段，我们定义仿射不变比。对于近似平面的基集，我们使用 连接点对的线之间 最近的点 来定义不变比率。现在，我们应用第3.3节中的方法，从Q中提取所有4点子集的集合
U
≡
{
U
1
，
U
2
，
…
，
U
s
}
U\equiv\{U_1，U_2，…，U_s\}
U≡{U1，U2，…，Us}，这些子集与B近似全等。对于每个
U
i
U_i
Ui，利用B和
U
i
U_i
Ui之间的对应信息，我们计算最佳刚体变换
T
i
T_i
Ti，使B在最小二乘意义上接近
U
i
U_i
Ui[Horn 1987]。为了验证
T
i
T_i
Ti，我们计算
T
i
(
P
)
T_i(P)
Ti(P)并找出
T
i
(
P
)
T_i(P)
Ti(P)中有多少点与Q的距离小于
δ
\delta
δ。这种验证是以随机方式进行的。为了提高效率，我们在
R
3
\mathbb{R}^3
R3中使用ANN（近似最近邻）[Arya等人，1998]进行邻域搜索。我们首先从P中选择恒定数量的部分点集S，使用
T
i
T_i
Ti对这些点进行空间变换，然后对于S里面的每个点查找其在Q中的近邻点。如果匹配到足够多的点（S中有足够多的点与Q的距离小于
δ
\delta
δ），我们再对P中剩余的点进行相同测试，并为
T
i
T_i
Ti分配一个分数（参见[Irani and Raghavan 1996]）。设
T
T
T表示具有最佳得分的变换。
给定一个基
B
i
B_i
Bi，我们描述了如何计算与其对应的最佳变换
T
i
T_i
Ti。每个变换
T
i
T_i
Ti基于阈值
δ
\delta
δ有一个分数。使用此程序，我们现在执行randomized alignment（见第2节），并根据重叠度
f
f
f的估计值，测试L个不同的基（
B
i
B_i
Bi）（见公式1）。最后我们得到得分最高的转换
T
o
p
t
T_{opt}
Topt。
further enhancement进一步提高
局部描述子，刚体变换下具有不变性，经常用来减少配准时的搜索空间。同样，当局部描述子能被可靠地计算时，本算法也能通过局部描述子得到提升。在下文中，我们展示了即使使用简单的非不变描述符（如曲面法线），也可以实现显著的加速，同时仍然可以使用宽基保持计算变换的精度。给定一个由4个共面点组成的基
B
B
B和一个
Q
∈
R
3
Q\in \mathbb{R}^3
Q∈R3的集合，我们要在一个近似水平
δ
\delta
δ内找到Q的所有4个点子集，这些子集与
B
B
B是近似全等的。设
B
≡
{
a
,
b
,
c
,
d
}
B\equiv\{a,b,c,d\}
B≡{a,b,c,d}为P中的四个共面点（如第4节所选），
O
≡
{
N
a
,
N
b
,
N
c
,
N
d
}
O\equiv \{N_a,N_b,N_c,N_d\}
O≡{Na,Nb,Nc,Nd}为它们的相关法线，
d
1
=
∥
a
−
b
∥
d_1=\parallel{a-b}\parallel
d1=∥a−b∥，
d
2
=
∥
c
−
d
∥
d_2=\parallel{c-d}\parallel
d2=∥c−d∥。设
N
(
x
,
y
)
N(x,y)
N(x,y)分别表示点x和y处两条局部法线之间的二面角。请注意，我们不要求法线方向的全局一致性。
在近似法线的条件下，所有满足
∥
q
1
−
q
2
∥
≈
d
1
\parallel{q_1-q_2}\parallel\approx d_1
∥q1−q2∥≈d1或
∥
q
1
−
q
2
∥
≈
d
2
\parallel{q_1-q_2}\parallel\approx d_2
∥q1−q2∥≈d2的点对
{
q
1
,
q
2
}
∈
Q
\{q_1,q_2\}\in Q
{q1,q2}∈Q进行进一步修剪：选择任意一点
q
∈
Q
q\in Q
q∈Q，计算其近似法向
N
q
N_q
Nq，然后提取所有点
q
i
∈
Q
q_i\in Q
qi∈Q，使得
N
(
Q
,
q
i
)
≈
N
(
a
,
b
)
N(Q,q_i)\approx N(a,b)
N(Q,qi)≈N(a,b)，或
N
(
Q
,
q
i
)
≈
N
(
c
,
d
)
N(Q,q_i)\approx N(c,d)
N(Q,qi)≈N(c,d)。在近似法线（用高斯球上的点表示）上使用邻域数据结构，可以有效地完成上述计算。因此，在实际中，这种基于法线和距离的约束没有存储所有
n
2
n^2
n2对点，而是输入点的线性关系。即使使用在刚性变换下变化的无向近似曲面法线，我们也观察到了两倍的加速。当可靠的刚性不变描述子可用时，可以进一步加速。
5 Results结果
我们在各种输入数据上测试了4PCS算法，这些数据具有不同的噪声量、离群值和重叠程度。我们将展示算法准确性和和鲁棒性。为了进行比较，使用了基于局部描述符的RANSAC算法，并在相同的输入上执行。
图7显示了在没有使用ICP精配准的情况下，在零均值不同方差
σ
\sigma
σ的高斯噪声下配准过程的鲁棒性。
在图9中，我们显示了在存在不同数量的离群值时的配准结果，且没有使用icp进行精配准。
在一个相关的实验中，我们改变重叠量来评估性能（图6）。可看到改变异常值的数量或重叠度对4PCS的运行时间有相似的影响，因为这两种方法都会导致两个对象之间的全等基集更少。
在图8中，我们列出了算法的各种性能特征。为了进行比较，我们使用结合了最先进的（state-of-the-art）局部描述子的RANSAC算法。我们使用多尺度自旋图像[Li and Guskov 2005]和鲁棒积分不变量[Pottmann等人，2007]的组合作为局部描述子。随着噪声和离群值的增加，基于RANSAC的方法会随着局部描述子的可靠性降低而变慢，最终退化为暴力搜索。在局部特征空间中，我们手动选择最小搜索半径，使得估计误差值与我们提出的算法相当。在极端条件下，基于局部描述子的结果无法进一步使用icp来收敛到正确的解，而4PCS的表现仍然令人满意。总而言之，在存在大量异常值、低重叠或高噪声的情况下，我们的算法总是优于LD-RANSAC（local descriptor RANSAC）。在局部描述符可以可靠计算的情况下，4PCS的工作速度甚至更快。
在表1中，我们展示了4PCS在各种测试数据集上的性能。如与局部描述符方法（图8）的比较所示，噪声和小的重叠度让配准时间不是线性变换。我们使用了一个高阈值的法线，其估计对含噪声的数据是不可靠的，从而实现了只有两个加速因子。法线估计的预计算时间也包括在其中。
如图10所示，很容易将我们的算法扩展到恢复较小的剪切(shear)变换。然而，对于这样的仿射变换（指剪切变换），不能用P中的单个4点基唯一确定，我们必须构造一对具有两个共同点的4点基：其余算法保持不变。虽然这个过程可以处理较小的剪切，但对于一般的仿射变换，该算法可能会存储输入点数为二次方的中间点，这使得该过程不切实际。(原文：Although this procedure can handle small shears, for general affine transforms the algorithm may store intermediate points quadratic in number of input points, making the procedure impractical.
the algorithm may store intermediate points quadratic in number of input points这句话没懂，所以给出的翻译也是直接机器翻译的)
局限性
在图13中，如果被扫描的底层对象是可滑动的，4PCS的性能如何——结果可能在滑动方向上是次优的（参见[Gelfand and Guibas 2004]）。由于我们是在点层次上操作的，这个问题是不可避免的。然而，消除这些歧义可能需要更多关于对象的语义信息，而不仅仅是现在使用的点位置。
在极低重叠扫描的极端情况下，选择宽的4点基集不太可能（choosing a 4-points wide base might not be possible）。在这种情况下，我们不得不通过选择较窄的基集来牺牲配准的稳定性。然而，任何配准技术在输入上都面临类似的问题。
总结
算法：
从待配准点云
P
P
P中选择
L
L
L个共面4点集构成基集
B
i
≡
{
a
,
b
,
c
,
d
}
(
i
=
1
,
2
,
,
,
L
)
B_i\equiv\{a,b,c,d\}(i=1,2,,,L)
Bi≡{a,b,c,d}(i=1,2,,,L)，实际应用中，这4点并不是严格共面，而是近似共面。选择方式是先随机选3个点，然后再选一个与前3个点近似共面的点作为第4个点。我们希望这4个点越远越好，算法越稳定，但是，必须在点云的重叠部分。利用4个点的对角线交点（ab交cd于e），记录对于仿射变换不变的比例关系
r
1
=
∥
a
−
e
∥
/
∥
a
−
b
∥
r_1=\parallel{a-e}\parallel/\parallel{a-b}\parallel
r1=∥a−e∥/∥a−b∥，
r
2
=
∥
c
−
e
∥
/
∥
c
−
d
∥
r_2=\parallel{c-e}\parallel/\parallel{c-d}\parallel
r2=∥c−e∥/∥c−d∥，以及点间距离
d
1
=
∥
a
−
b
∥
d_1=\parallel{a-b}\parallel
d1=∥a−b∥，
d
2
=
∥
c
−
d
∥
d_2=\parallel{c-d}\parallel
d2=∥c−d∥。
在参考点云Q中寻找所有与
B
i
B_i
Bi近似全等的4点集
U
≡
{
U
1
，
U
2
，
…
，
U
s
}
U\equiv\{U_1，U_2，…，U_s\}
U≡{U1，U2，…，Us}，条件是
U
s
U_s
Us的4点满足
B
i
B_i
Bi 的4点生成的比例关系和距离关系。计算由
U
s
U_s
Us和
B
i
B_i
Bi确定的空间变换
T
i
s
T_{is}
Tis（4个点对求解空间变换矩阵，这里是一个
B
i
B_i
Bi对应s个U）。使用
T
i
s
T_{is}
Tis对
P
P
P进行变换后，统计此时
T
i
s
(
P
)
T_{is}(P)
Tis(P)中与Q的距离小于阈值
δ
\delta
δ的点数
k
i
s
k_{is}
kis，留下
k
i
s
k_{is}
kis最大时的变换作为最优的
T
i
T_i
Ti。
对
L
L
L个
B
i
B_i
Bi均执行上述过程，在保留的
T
i
T_i
Ti中，再次选择最优的一个作为最后的结果
T
o
p
t
T_{opt}
Topt。
问题/疑惑：
文中给出用重叠度
f
f
f来选择在重叠部分的3点集，再选择第4个点，但是没有具体说怎么选择根据
f
f
f选择3点集。
在未知重叠度
f
f
f时，从1往下递减，每次递减的量多少合适，太小比如每次减0.01这种会太耗时，太大像0.25这种，又得不到准确的重叠度，用2分法去试那不就增加了手动的成分？
希望懂的朋友能指教！
参考及感谢
papers:
Aiger D , Mitra N J , Cohen-Or D . 4-points congruent sets for robust pairwise surface registration[J]. Acm Transactions on Graphics, 2008, 27(3):1-10.
FISCHLER, M. A., AND BOLLES, R. C. 1981. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24, 6, 381–395.
blog:
文中已列出
完
边学边用，如有错漏，敬请指正
--------------------------------------------------------------------------------------------诺有缸的高飞鸟202012