点云配准论文阅读笔记—Globally consistent registration of terrestrial laser scans via graph Optimization

   三维点云拼接技术在不同场合亦被称为重定位、配准或拼合技术, 其实质是把不同的坐标系下测得的数据点云进行坐标变换, 问题的关键是坐标变换参数R( 旋转矩阵) 和t ( 平移矢量) 的求取。  

 点云配准有手动配准、依赖仪器的配准和自动配准。通常我们所说的点云配准技术即是指最后一种。目前采用的自动配准技术一般分为初始配准和精确配准两步, 初始配准是为了缩小点云之间的旋转和平移错位以提高精确配准的效率和趋向, 精确配准则是为了使两个点云之间的配准误差达到最小。一般初始配准很难满足精度要求,需在初始配准的基础上使用迭代算法进行精确配准, 使点云之间的配准误差达到最小。

Globally consistent registration of terrestrial laser scans via graph Optimization

这篇文章来自2015年的ISPRS，作者：Pascal Willy Theiler ⇑, Jan Dirk Wegner, Konrad Schindler。文章提出了一种多地面激光扫描自动配准的框架。该方法可以处理从任意位置获得的多次扫描数据，且不需要事先知道它们的相对方向。这篇文章并没有使用matching descriptors，而是用明确的利用了几何关键点之间的对应关系，建立图模型进行候选筛选。

在许多TLS项目中，来自附加传感器的一部分方向是先验已知的，特别是扫描仪经常是水平的，使得围绕x轴和y轴的旋转很小。在这种情况下，使得两两配对方法变得更加的简单。然而，现实中这样的情况几乎是不可能的，为了配准方法尽可能通用，文章不假设扫描仪是水平的。

配准流程分为两大步骤，粗配准和精配准，粗配准采用K-4pcs方法进行两两配对（pairwise matching），初步形成全局一致网络，为精配准提供初始值。

1、粗配准

（1）Pairwise coarse registration with K-4PCS

K-4PCS方法（Theiler, P.W., Wegner, J.D., Schindler, K., 2014a. Keypoint-based 4-points congruent sets – automated marker-less registration of laser scans. ISPRS J. Photogramm. Rem. Sen. 96 (0), 149–163.）主要分为两个步骤：1）利用VoxelGrid滤波器对点云进行下采样，然后使用标准方法（3D harris或者3D DoG.）进行3D关键点检测。2）通过4PCS算法（Aiger, D., Mitra, N.J., Cohen-Or, D., 2008. 4-Points congruent sets for robust pairwise surface registration. ACM Trans. Graph. 27 (3), 1–10.）找到两个关键点云之间的候选变换关系。4PCS算法将必须的3组对应点扩展到4组对应点，利用平面四边形的仿射不变性，来寻找对应点，使得复杂度大大减少。

（2）Global graph-based coarse registration（全局粗配准）

这个部分也主要分为两个步骤：1）对每一组假定的对应点对开始，我们试图选择一对候选点对，分别对应为扫描图（scan graph）中的每条边，使得整体差异最小化。不可避免的是，有时会发生一对或多对的对应假设都是错误的，因此，对于离散(强制选择)优化，我们为每一对引入了额外的虚拟解决方案。只有当所有可用的候选方案与整个网络不一致时，才会选择虚拟解决方案，且这样的点对在scan graph中被删除，后续的处理中将不再使用。

2）建立图模型（graphical model GRX（X,L）），可以将图模型理解为扫描图的双重表示。构建如下能量函数：

其中，变量表示扫描对（scan pairs），每一组扫描对的l个候选变换关系为,即：

表示一致性约束条件，当闭环误差增大时，φk也增大。权重ω平衡了一元项和高级项的重要性。