【点云配准-4PCS（2008）】4-Points Congruent Sets for Robust Pairwise Surface Registration

浅浅的花香味﹌ 2022-11-25 13:29 114阅读 0赞

### 文章目录 ###

*  1 背景
 *   *  1.1 问题描述
     *  1.2 相似性测度（Similarity Measure）
     *  1.3 随机采样一致性（Random Sample Consensus，RANSAC）
     *  1.4 Randomized Alignment
     *  1.5 4PCS算法概述
 *  2 4点一致性
 *   *  2.1 概述
     *  2.2 4点集的仿射不变性
     *  2.3 在3D空间中提取一致的4点
 *  3 4PCS算法
 *   *  3.1 算法描述
     *  3.2 实验结果
 *  参考

--------------------

# 1 背景 #

## 1.1 问题描述 ##

给定任意初始位置的两个点集 P P P和 Q Q Q，找到一个最佳变换（通常是刚性变换），使得 P P P、 Q Q Q中距离小于 δ \\delta δ的点数最多。

## 1.2 相似性测度（Similarity Measure） ##

在点云配准问题中，我们通常会用**相似性测度**来衡量两组点云之间的匹配程度，常见的相似性测度有**均方误差（Root Mean Square Error（RMSE）**、**最大公共点集（Largest Common Pointset，LCP）** 等。

4PCS算法中所使用的相似性测度即为LCP测度。由LCP测度的原理我们可以看出，4PCS算法最终并不一定能够得到一个非常精确的变换矩阵，因此它常被用作点云配准问题中粗配准（Coarse Registration）步骤中的方法，配合ICP等精配准（Fine Registration）算法共同实现精确的点云匹配。

## 1.3 随机采样一致性（Random Sample Consensus，RANSAC） ##

RANSAC是一种被广泛使用的通用性算法，用于对因噪声和异常值破坏的数据进行模型的鲁棒拟合。

基于RANSAC的点云匹配过程可以归纳为：

*  从点集 P P P和 Q Q Q中分别随机选取3个不同的点（方便起见，下文中我们把这3个不同的点称作“基底/base”）对作为基础的匹配点对；
 *  计算所选取3组对应点对的变换矩阵 T i T\_i Ti；
 *  计算点集 P P P和 Q Q Q的LCP测度 k i k\_i ki，即点集 P P P中的点与点集 Q Q Q中的点距离在 δ \\delta δ范围内点的个数；
 *  如果 k i k\_i ki足够大，则直接接受 T i T\_i Ti作为最佳的变换矩阵，否则重复以上步骤；
 *  这个过程将被重复 L L L次，并选择 k i k\_i ki最大时的变换矩阵 T i T\_i Ti作为最终的结果。

## 1.4 Randomized Alignment ##

Randomized Alignment是Irani和Raghavan在1996年提出的RANSAC算法的一种变体，用于在相似性变换下解决2D对齐问题。其基本步骤为：

*  从点集 P P P中随机选取一组基底；
 *  计算该基底与 Q Q Q中所有可能的基底得到的变换矩阵；
 *  验证得到的变换矩阵，这也是随机的：首先，仅随机抽取 P P P中固定数量的点进行验证，只有当该子集中大部分的点匹配上（即在点集 Q Q Q中存在与其距离在 δ \\delta δ内的点）时，才测试其余点；
 *  与RANSAC中一样，为了达到一定的成功率，以上过程将被重复 L L L次。

与基本的RANSAC不同的是，4PCS算法从 P P P中随机选择基底，然后使用某种配准算法在 Q Q Q中寻找对应的基底，下面将详细介绍4PCS算法。

## 1.5 4PCS算法概述 ##

我们知道，3个不共线的点对即可计算空间变换矩阵，而作者认为，寻找特殊的4点作为基底会使问题变得更加容易。4PCS算法就是使用一组来自 P P P的4个共面点作为基底 B B B，并从 Q Q Q中快速找到与 B B B大致一致的所有4点基底的子集，即允许刚性变换将两个4点集对齐且距离在 δ \\delta δ范围内。

# 2 4点一致性 #

## 2.1 概述 ##

仿射变换遵循以下规则：给定3个共线的点 \{ a , b , c \} \\\{a,b,c\\\} \{ a,b,c\}，它们之间的比例关系 r = a − b a − c r=\\frac\{a-b\}\{a-c\} r=a−ca−b是不变的。给定一组共面的4点集，在给定的点云数据中查找与其在距离约束（ δ \\delta δ）下具有仿射变换关系的4点集的集合。

## 2.2 4点集的仿射不变性 ##

![在这里插入图片描述][20200809222747384.png_pic_center]

定义非共线的共面4点 X ≡ \{ a , b , c , d \} X\\equiv\\\{a,b,c,d\\\} X≡\{ a,b,c,d\}， a b ab ab和 c d cd cd相交于点 e e e，则以下2个比率在仿射变换下是不变的：

r 1 = ∣ ∣ a − e ∣ ∣ ∣ ∣ a − b ∣ ∣ r 2 = ∣ ∣ c − e ∣ ∣ ∣ ∣ c − d ∣ ∣ r\_1=\\frac\{||a-e||\}\{||a-b||\} \\\\ r\_2=\\frac\{||c-e||\}\{||c-d||\} r1=∣∣a−b∣∣∣∣a−e∣∣r2=∣∣c−d∣∣∣∣c−e∣∣

给定含有 n n n个点的点集 Q Q Q，以及两个由点集 P P P得到的仿射不变性比率 r 1 r\_1 r1和 r 2 r\_2 r2，对于 Q Q Q中的每对点 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 2 = q 1 + r 2 ( q 2 − q 1 ) e\_1 = q\_1 + r\_1 (q\_2-q\_1) \\\\ e\_2 = q\_1 + r\_2 (q\_2-q\_1) \\\\ e1=q1\+r1(q2−q1)e2=q1\+r2(q2−q1)

任意两对中间点 e 1 e 2 e\_1 e\_2 e1e2在允许范围内重合的点，都可以被看作与 P P P中基础点对可能的仿射对应点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NmYW45Mjc_size_16_color_FFFFFF_t_70_pic_center]

## 2.3 在3D空间中提取一致的4点 ##

给定点集 P P P中不共面的4点作为基底 B B B，以及另外一个点集 Q ∈ R 3 Q \\in \\mathbb\{R\}^3 Q∈R3，我们的目标是从 Q Q Q中找到所有在允许范围（ δ \\delta δ）内与 B B B一致的4点的集合。基本步骤为：

*  计算给定 B B B的两个放射不变比率，即 r 1 r\_1 r1和 r 2 r\_2 r2；
 *  利用2.2中描述的方法，从 Q Q Q中查找所有通过放射变换能与 B B B相匹配的点集；
 *  通过距离约束（ δ \\delta δ），过滤掉不符合要求的匹配（主要针对仿射变换中存在尺度缩放的一部分点集）；
 *  利用最小二乘法，计算余下每对点与 B B B的最佳变换。

事实上，对于大的点集，上述过程的计算量是相当大的。考虑到我们寻求的是刚性变换的解，对于一个基底 B ≡ \{ a , b , c , d \} B\\equiv\\\{a,b,c,d\\\} B≡\{ a,b,c,d\}，首先计算两点间的距离 d 1 = ∣ ∣ a − b ∣ ∣ d\_1=||a−b|| d1=∣∣a−b∣∣， d 2 = ∣ ∣ c − d ∣ ∣ d\_2=||c−d|| d2=∣∣c−d∣∣，然后仅考虑点集 Q Q Q中两点距离与 d 1 d\_1 d1或 d 2 d\_2 d2相差在一定范围内（ δ \\delta δ）的点对。

# 3 4PCS算法 #

## 3.1 算法描述 ##

给定两个点集 P P P和 Q Q Q，不确定性度量（ δ > 0 \\delta > 0 δ>0），以及预估的两点集的重叠率 f f f，我们的目标是找到一个刚性变换，使 P P P中的点到 Q Q Q中的点距离小于 δ \\delta δ的个数最多。

*  首先选择由4个共面点组成的基底 B ⊆ P B\\subseteq P B⊆P。实际上我们不一定能到找到完全共面的4个点，因此先随机选择3个点，再查找第4个点组成近似共面的基底。理论上来说，点之间的距离越远得到的匹配结果越精确，然而若距离过远，可能导致所选择的点不在两个点集的重叠部分，也就无法计算得到理想的匹配对。因此使用重叠率 f f f来估计这个最大距离（ f f f的默认值为1）；
 *  得到基底 B B B后，我们可以定义仿射不变比。从 Q Q Q中查找所有与 B B B在距离约束（ δ \\delta δ）下的对应点对集合 U ≡ \{ U 1 , U 2 , . . . , U s \} U\\equiv\\\{ U\_1,U\_2,...,U\_s \\\} U≡\{ U1,U2,...,Us\}。利用最小二乘法计算 B B B与 U i U\_i Ui的最佳变换 T i T\_i Ti；
 *  验证所得到的 T i T\_i Ti的准确性，该过程以随机方式进行。计算 P P P经过 T i T\_i Ti变换后与 Q Q Q的相似性测度（在 δ \\delta δ约束下的最大公共点集）。为了提高效率，最近点的查找使用近似最近邻算法（Approximate Nearest Neighbor，ANN）。具体来说，首先从 P P P中选择固定数量的点，计算这些点经过 T i T\_i Ti变换后与 Q Q Q中的点距离在 δ \\delta δ内的点的个数，如果足够多的话则对余下的点也做这样的计算。匹配点数最多的变换将被作为本次匹配中最佳的变换矩阵 T T T；
 *  对于重复 L L L次不同的基底 B i B\_i Bi，均按照上述步骤找到最佳变换 T i T\_i Ti，并最终得到总体的最佳变换矩阵 T o p t T\_\{opt\} Topt作为最终结果。

## 3.2 实验结果 ##

几组作者论文中给出的实验结果，所有结果都是经过ICP微调后的效果。

**（1）不同重叠率**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NmYW45Mjc_size_16_color_FFFFFF_t_70_pic_center 1]  
**（2）不同噪声程度**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NmYW45Mjc_size_16_color_FFFFFF_t_70_pic_center 2]  
其余的大家直接看论文吧。

# 参考 #

\[1\] [https://sci-hub.tw/10.1145/1360612.1360684][https_sci-hub.tw_10.1145_1360612.1360684]  
\[2\] [http://graphics.stanford.edu/~niloy/research/fpcs/fpcs\_sig\_08.html][http_graphics.stanford.edu_niloy_research_fpcs_fpcs_sig_08.html]

[20200809222747384.png_pic_center]: /images/20221124/caf98a6ff4af4afe8ccddfd2d0478796.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NmYW45Mjc_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/9bc168d2703c466397f2936635226316.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NmYW45Mjc_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/c922ca22bc00463c8f9ed06a725379c4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NmYW45Mjc_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/2debee3e426f43f393359b772f85b526.png
[https_sci-hub.tw_10.1145_1360612.1360684]: https://sci-hub.tw/10.1145/1360612.1360684
[http_graphics.stanford.edu_niloy_research_fpcs_fpcs_sig_08.html]: http://graphics.stanford.edu/~niloy/research/fpcs/fpcs_sig_08.html