激光扫描匹配方法研究综述

宗文鹏，李广云，李明磊，王 力，李帅鑫

(信息工程大学，河南 郑州 450001)

1 引 言

定位是移动机器人领域研究最多也是最核心的问题之一，是机器人实现真正自主的先决条件，没有准确高效的定位，机器人就难以执行复杂的任务。通常，移动机器人可通过轮式里程计、惯性导航装置(Inertial Measurement Unit,IMU)等本体传感器进行定位。然而由于车轮打滑和漂移导致误差累积问题，故单独依靠本体传感器并不能提供准确可靠的定位结果。因此，移动机器人一般还需要加装外部感受传感器，如声呐、超声传感器、视觉传感器、激光雷达(Light Detection and Ranging,LiDAR)等。在进行定位的同时，利用这些传感器采集信息，能够建立环境的抽象表示即地图，地图反过来又辅助机器人进行定位，这是移动机器人实现避障、路径规划、目标识别与跟踪等任务的必要基础。于是，同步定位与地图构建(Simultaneous Localization and Mapping,SLAM)[1]技术应运而生。目前，最热门的SLAM实现方案主要依赖两类传感器，即激光雷达和视觉传感器，它们分别被称为激光SLAM和视觉SLAM[2]。相对于视觉传感器，LiDAR能够提供更加鲁棒、准确和噪声水平稳定的测量信息，且对光照条件变化不敏感，因而激光SLAM是目前最稳定可靠的SLAM解决方案。

根据求解方法不同，可将激光SLAM分为基于滤波的和基于图优化的两种[3]。其中，当前较为流行的基于图优化的激光SLAM系统框架主要分为前端和后端两个部分，前端完成数据关联和闭环检测，后端进行图优化。激光扫描匹配是实现激光SLAM数据关联最常用的方法。大多数文献中对激光扫描匹配的定义为，寻求一组平移和旋转参数，使得对齐后的两帧扫描点云达到最大重叠[4-6]。本文尝试给出一个更一般的定义，即通过求解坐标转换关系，将连续扫描的两帧或多帧激光点云统一到同一坐标系中(scan-to-scan)，或者将当前扫描点云与已建立的地图进行配准(scan-to-map)，从而最终恢复出载体位置和姿态的变化。

“扫描匹配”这一概念主要出现在机器人学相关文献中，本质上它与测绘等领域中的“点云拼接(或配准)”[7]解决的是同一个问题，但目的不同：前者通过将激光扫描点云配准到同一坐标系下而得到相对位姿变化，后者是为得到坐标系统一的点云。此外，由于应用场合和针对的目标不同，扫描匹配和点云拼接各有其特点。激光扫描匹配处理的是移动载体运动时LiDAR的扫描数据，点云较稀疏，且误差和噪声均较大，大多要求实时处理，力求在精度和效率之间寻求平衡；而点云拼接处理的多是LiDAR静态扫描数据，点云较密集，且误差和噪声较小，一般不要求实时处理而更注重拼接的精度。

近年来，激光SLAM技术发展迅猛，其应用从结构化场景拓展到非结构化场景，从室内环境发展到室外环境，从地面移动平台扩展到空中以及水下。相应地，激光扫描匹配技术经历了2D到3D、低动态到高动态、简单场景到复杂环境的发展变化，除用于激光SLAM外，也越来越多地被应用于导航定位[6,8]、移动测量[9]等领域。根据所处理的LiDAR数据的维度，扫描匹配可分为2D和3D扫描匹配。根据是否利用特征，扫描匹配可分为基于特征的和基于扫描的两种[10]。根据匹配时的参考对象，又可分为局部和全局扫描匹配[11]。一般来说，局部扫描匹配处理对象为连续获取的两帧扫描数据，通常需要利用里程计或IMU的输出或前一次扫描匹配结果作为初值，主要用于位姿跟踪，实现相对定位；而全局扫描匹配[12]将当前帧扫描数据与全局地图或过往全部扫描数据帧进行匹配，无需初值，用于实现全局定位。本文沿用文献[13]和[14]的分类方法，将激光扫描匹配分为三类：(1)基于点的扫描匹配；(2)基于特征的扫描匹配；(3)基于数学特性的扫描匹配。

需要指出的是，本文主要侧重于连续扫描帧间匹配(scan-to-scan)问题，对激光扫描匹配相关方法按照上述三种类型进行总结和讨论，旨在帮助读者快速了解该方向现有研究方法和存在的问题，以便在此基础上开展相应的研究。

2 基于点的方法

基于点的扫描匹配直接对扫描获取的原始数据点进行操作，其中ICP (Iterative Closest/Corresponding Point)算法是应用最广、研究最多也是目前最为成熟的一种算法。ICP分别由Chen[15]和Besl[16]独立提出。不同之处在于前者利用点到面的距离作为误差度量，而后者采用点到点的距离误差度量，故可分别记为P2Pl(Point-to-Plane)-ICP和P2P(Point-to-Point)-ICP。

2.1 标准ICP算法

其中，R∈SO(3)为旋转矩阵，t为平移向量，eij为误差度量，C={(i,j)m}表示对应点对集合，点pi对应点qj。

2.2 ICP的改进算法

Besl[16]证明了ICP算法总能单调收敛到一个局部最小值，但这基于一个假设，即对应点对数量及对应关系在迭代过程中保持不变，而这显然是不现实的。此外，ICP算法还假定两个点云中的点完全相同，而事实上，当传感器视点改变后，尤其是当采样分辨率较低时，前后两次扫描找到同一物理点的对应点对的可能性极小。为此，Chen[15]提出P2Pl-ICP算法，采用更鲁棒的点到面的距离作为误差度量替代点到点距离误差度量，即：

eij=(Tpi-qj)·nj, (2)

其中，nj为点qj处的法向。

标准ICP算法所采用的欧式距离，不能很好的解释传感器的旋转变化，当目标函数接近局部极值时收敛很慢。文献[17]提出计算两组对应关系，一组采用欧氏距离，另一组利用极坐标距离和角度，联合两种对应关系准则，提出了IDC(Iterative Dual Correspondence) 算法。该算法改善了ICP算法对于传感器旋转角度的表达，加快了收敛速度，但同时采用两种对应关系建立准则分别求解平移和旋转，可能出现多组极值组合，从而影响算法的鲁棒性和精度。文献[18]提出一种组合扫描匹配方法CSM(Combined Scan Matcher)，联合了一种点-线扫描匹配方法[19]和一种点-点扫描匹配方法[17]；当扫描数据中存在足够多的直线用于匹配时执行点-线扫描匹配算法，否则执行点-点扫描匹配算法。

文献[20]提出的MbICP(Metric-based ICP)算法，定义了一种传感器位形空间中新的距离度量，同时考虑平移和旋转，使得平移和旋转在所有步骤中同时得到补偿，改善了算法的鲁棒性、精度、收敛性，并降低了计算代价。MbICP能够处理较大的旋转，但该方法不能利用KD树等技术来加速最近邻域搜索，需要在极坐标空间进行较慢的搜索，难以扩展到完全3D的扫描匹配[21]。

针对此问题，文献[11]引入了一种除几何关系外的新的度量，即点云强度信息，提出了“Intensity-ICP”方法。该方法将强度误差度量纳入到目标函数中，并赋以通过实验确定的权重。该方法为相对位姿的求解增加了一个新的约束，为解决具有相同几何形状而不同反射特性的场景下的扫描匹配提供了可能。但该方法基于前后两次扫描间距离变化足够小而不影响强度的假设，而实际上强度值受测量距离和入射角的影响均较大，应用前需先对传感器的强度测量进行标定；存在的另外一个问题是难以准确度量强度误差对位姿变化的贡献，即难以确定一个合适的权重值。

文献[22]和[23]提出ICL(Iterative Closest Line)算法，即利用点-线距离度量来实现ICP，以提高精度和收敛速度。但是对于较大的位移稳定性较差。文献[24]采用3D栅格，将点云分割成体素(Voxel)[25]，以体素对应关系代替了传统ICP中的点间对应关系，且考虑了点云局部结构即体素的形状参数，实现了3D扫描匹配，能够用于室内外结构与非结构化场景中，得到局部一致的测图结果。

文献[26]提出GICP(Generalized-ICP)算法，在单个概率框架中结合了P2P-ICP算法与P2Pl-ICP算法，误差度量中既包含当前扫描也包含了参考扫描的表面信息，所采用的误差度量可视为面到面距离，从而GICP是一种Pl2Pl(Plane-to-Plane)-ICP算法。GICP核心思想是考虑点周围的表面形状，并近似为平面片，利用了点云表面局部连续这一性质，考虑进了传感器的噪声模型，利用法向来给目标函数中的每个对应匹配赋权，能有效降低误匹配的影响，已成为众多ICP改进算法中最为有效和鲁棒的算法之一。但需要指出的是，在室外及非结构化场景中GICP并不比标准ICP表现出色[35]。文献[27]和[28]拓展了GICP中提出的面-面误差度量，在求解最优变换时，最小化的误差度量为各对应点对的马氏距离及它们的法向。该算法的主要特点为：对每个点，考虑其周围表面特性，计算法向和曲率；在寻找对应关系和最优变换求解中都利用了场景结构，采用了测量的扩展表示，即每个点的欧式坐标用表面法向增广，误差度量是6D向量而不再是3D点。

文献[29]提出一种ICP预处理技术ICN(Iterative Closest Normal)，其目的是估计连续扫描帧间大的旋转，当处理了大的旋转后再采用标准的ICP或点-线ICP来估计剩余变换。为避免ICP算法局部最优问题，文献[30]提出Go-ICP方法，将ICP算法与分支定界方法相结合，以保证求解的全局最优，但计算代价较大；文献[31]将基于八叉树的ICP算法与分层搜索策略相结合，利用一种早期预警机制来监测局部极小问题，并采用一种启发式逃离方法来避免局部极值从而获得全局最优解。

传统的ICP改进算法通常假设获取一帧扫描数据的时间足够短，从而近似认为所有扫描点是同时测得的，但实际上扫描数据是依次测量得到的，而在这一过程中，传感器的位姿始终在变化，获得的点云存在变形，因而当传感器运动速度较快时，传统的ICP改进算法会给出错误的位姿估计。文献[32]指出在确定对应点前需要对扫描数据进行畸变改正，提出一种利用速度更新增强ICP算法的新方法VICP(Velocity updating ICP)，在ICP的迭代求解过程中估计传感器速度，利用该速度估计来补偿由于运动造成的点云畸变；并且，在速度更新的迭代过程中，能够有效排除异常点，从而得到更加鲁棒和准确的位姿估计。文献[33]中Continuous-ICP(CICP)将ICP算法进一步扩展，提出一种用于特定类型3D LiDAR(由2D LiDAR+旋转驱动装置组成)-SLAM的连续时间轨迹估计方法，利用估计的连续位姿进行畸变改正。

2.3 模块化的ICP算法

随着ICP及其改进算法的不断发展和完善， ICP类算法可归纳为以下6个步骤[34]：

(1)选择点集；

(2)确定点集间对应关系；

(3)给对应点对适当加权；

(4)排除特定的对应点对；

(5)设定误差度量；

(6)最小化误差度量。

Pomerleau[35]通过分析概括已有ICP改进算法并结合自身开发经验，提出了模块化的ICP算法，既方便进一步开发和调试新算法，同时又便于对不同改进算法进行对比。如图1所示，首先，可先对输入扫描点云进行滤波处理，去除冗余点、离群点，或计算表面特征如曲率和法向；然后，将匹配函数用于关联输入点云和参考点云的元素，通常这一关联过程在欧式空间进行并利用KD树加速搜索；建立好元素对应关系后，可利用不同的统计方法来排除错误或异常的元素对应，如可设置距离阈值，超过该阈值的对应点对被认为是无效对应而被剔除；最终，剩余的有效对应元素对被用于最小化误差度量，求解新的变换关系直到满足收敛条件。

图1 模块化ICP算法流程图 Fig.1 Pipeline of modular ICP

2.4 其他基于点的方法

除了ICP及其改进算法外，还存在其他一些基于点的扫描匹配方法。文献[37]提出一种概率的扫描匹配方法pIC(probabilistic Iterative Correspondence)。其将扫描点及位姿视为随机变量，利用马氏距离寻找所有可能的统计相容点(即对应点)，概率模型纳入了传感器测量噪声及初始位姿的不确定度，利用迭代的方式进行求解，收敛速度、鲁棒性和精度优于标准ICP和IDC算法。Diosi提出极坐标扫描匹配方法PSM(Polar Scan Matching)[38]，使得对应点匹配更加准确可靠，从而提高了扫描匹配效果。后来他又提出改进的扫描匹配方法[39]，利用LiDAR测量为极坐标的本质，直接利用极坐标量即距离和角度测量值，结合匹配关联规则和加权距离残差最小化来实现扫描匹配，提高了处理速度并扩大了收敛域，但该方法难以扩展到3D扫描匹配。文献[40]提出一种改进的PSM方法，利用遗传算法来进行匹配，避免了ICP类算法中容易出错的数据关联步骤。文献[41]又提出一种基于周界的PSM算法，称为PB-PSM，获得了更好的效果。

文献[42]提出CRSM(Critical Rays Scan Matching)的思想，不需使用所有数据点参与匹配，而是在每帧扫描数据中根据扫描密度寻找关键射线对应的测量点，提出了一种基于射线筛选的扫描匹配方法，有效降低了计算复杂度，减少匹配所需时间。文中提出和对比了3种不同的射线筛选方法，均匀筛选方法、基于扫描密度的方法以及将扫描数据分段并利用局部密度的方法。利用随机重启爬山法代替遗传算法进行求解，比ICP算法更准确比遗传算法更快。其实验结果得到一个有益的启示，即利用全部可用信息进行扫描匹配并不总会改善结果。

2.5 存在的主要问题和发展趋势

ICP类算法存在3个主要误差来源[43]：

(1)错误的收敛，ICP算法总是收敛到局部极值的本质导致最终结果可能偏离真值，该误差难以建模；

(2)欠约束导致的误差，一些环境下没有足够的信息来估计完整的位姿信息，如长直走廊环境或圆形场景，但可通过Fisher信息矩阵来检查是否是该情况；

(3)传感器噪声引起的误差，即使ICP算法到达真值的收敛域，传感器噪声的存在仍将导致其最终结果不同。当ICP用于定位时，克拉美-罗下界[44]给出了协方差的良好近似，但是对于扫描匹配来说过于乐观。

此外，由于数据关联开始是未知的，迭代的方法不一定能建立正确的对应关系。由最小二乘导出的不确定度估计不能准确反映数据关联中的不确定度，不确定度估计往往过于乐观[45]。另外两个与ICP算法相关的问题为：

(1)计算效率问题：为加速收敛，Besl[16]基于最近两到三次迭代过程中变换变量的值，利用线搜索方法启发式地确定变换变量；虽然这在一定程度上改善了局部极值处的收敛速度，但对于较大的旋转仍然不能得到较好的结果。寻找对应点的过程计算复杂度相当高，加速搜索过程需利用KD树[46]或最近点高速缓存[47]等技术。

(2)鲁棒性问题：异常点对扫描匹配影响较大，文献[20,39]等提出采用预处理技术减少异常点。尽管如此，很难将LiDAR数据中所有异常点或噪声彻底剔除。

ICP类算法已从最初的迭代最近点发展到迭代对应点再到迭代对应元素，在鲁棒性、计算效率和收敛域方面得到了提高。未来，将有更多的可用信息被利用，从而进一步改进ICP算法，如强度信息、语义信息；对应元素可进一步拓展到体素及超体素[48]，将有更多的非线性优化算法能够用于参数求解。

3 基于特征的方法

图2 基于特征的扫描匹配方法流程图 Fig.2 Pipeline of the feature-based scan matching method

与其利用可能包含异常点和噪声的所有LiDAR数据，激光扫描匹配的另外一种思路是只利用数据中的部分关键元素进行匹配，这种元素可以是点、线、面等几何基元或者它们的组合。于是催生了另一个系列的激光扫描匹配方法，即基于特征的扫描匹配，其流程如图2所示。基于特征的扫描匹配方法，类似于图像匹配问题，需要先从扫描点云中提取有效特征，如点、线、弧、面或其组合特征，以及法向、曲率等柔性特征，还包括自定义的各种特征描述子。基于检测到的特征，可实现快速对应匹配，无需提供初值，即可求解位姿变化。

3.1 直接从LiDAR点云中提取特征

(1)点特征

点特征广泛存在于各种场景中，基于点特征的扫描匹配方法应用较广，适用性较强。文献[49]直接从点云中提取拐角和边角点，用于全局扫描匹配。受计算机视觉中SIFT特征描述子的启发，文献[50]提出一种用于2D扫描匹配的局部不变特征CIF(Congruence Transformation Invariant Feature)，当应用全等变换时保持不变；利用从LiDAR数据中提取的CIF特征点，可实现杂乱环境下的全局扫描匹配。文献[51]又对CIF方法进行了改进，解决当利用较大地图作为参考扫描进行扫描匹配时容易失败的问题。文献[52]提出ICE扫描匹配方法，利用多种特征点，包括交叉点(Intersection)、角点(Corner)和墙的端点(End Of Wall)。

文献[53]提出一种自动化、实时的基于角点的扫描匹配算法，以提取的线之间的交叉点作为角点；为说明角点的不确定度，利用提取线的方差来估计角点的协方差；该算法既可单独使用，也可用于辅助迭代方法。文献[54]提出一种叫做FLIRT的方法，研究了3种类型的激光点云特征检测子(基于距离、法向和曲率)和两种特征描述子(线性局部形状上下文描述子和β-栅格描述子)。基于综合分析，进行最佳组合形成FLIRT，但是计算其描述子非常慢，难以用于实时SLAM。事实上，3D激光点云的点特征检测方法和特征描述子[55-56]还有很多，但大多由于提取精度、计算效率、适用条件等问题难以用于激光扫描匹配。

(2)线特征

在室内及结构化场景中，存在较多的线特征，特别是对于2D扫描匹配方法，线特征的提取(即分割)较为简单和高效，因而基于线特征的扫描匹配方法主要存在于2D应用中。分割-合并(Split-and-Merge)方法[57]是2D扫描匹配中广泛采用的一种线段分割方法，此外，文献[58]给出了针对2D扫描数据的3种线段分割方法，即连续边缘跟随(Successive Edge Following,SEF),线跟踪(Line Tracking,LT), 迭代端点拟合(Iterative End Point Fit,IEPF)。霍夫变换也是提取线特征的一种有效方法[59]，文献[60]提出HSM(Hough Scan Matching)方法，利用霍夫变换提取线段，并在霍夫域进行匹配，但当环境中包含大量较短线段或曲线时，这种方法不再适用。

文献[61]提出基于完整线段(Complete Line Segment, CLS)的扫描匹配方法，根据线段长度、中心点的相对位置、相对旋转进行线的对比。文献[62]利用互兼容约束来实现线段关联，从而实现扫描匹配。文献[63]利用曲率方法，通过自适应曲率函数将扫描点云分为曲线段和直线段。文献[64]提出的2D扫描匹配方法，首先利用模糊聚类算法分割点云，然后对每段进行加权最小二乘拟合，选择两帧扫描数据中满足线性分布的线段进行匹配，从而计算旋转参数，然后再利用点匹配准则对点建立对应关系，从而求解平移参数。文献[65]提出一种基于点和线特征的2D扫描匹配方法，基于扩展的1D SIFT检测显著特征点，利用改进的分割-合并算法提取线特征，利用距离直方图来描述点和线特征，采用直方图聚类技术滤除异常对应，从而提供准确的刚体变换的初始值；相对位姿估计采用lq范数度量，而不是经典优化方法中代价函数所采用的l2范数。

(3)面特征

室内及城市环境中，存在大量的平面或曲面特征，合理利用这些特征同样能够实现激光扫描匹配。文献[66]从扫描数据中提取欧式不变特征，利用几何哈希法匹配两帧扫描数据，需要场景中包含曲面形状物体。文献[67]利用体素滤波器对原始数据进行均匀下采样，通过区域生长提取平面宏特征，如墙面和大平面，只利用平面上的点进行扫描匹配，剔除了人及其他不相关特征即杂乱点。文献[68]提出了一种从稀疏点云中高效提取线和面特征的方法。文献[69]提出的Loam(Lidar odometry and mapping)算法中，使用位于锐利边缘线和平面上的特征点，并且分别匹配特征点到边缘线段和平面片上，通过扫描匹配实现LiDAR里程计，对不同类型的3D LiDAR，在多种场景中均取得了出色的效果。

(4)其他特征

其他基于特征的扫描匹配方法使用点特征直方图PFH(Point Feature Histograms)[70]及其更快的变种FPFH(Fast Point Feature Histograms)[71]、角度不变特征[72]、曲率函数[73]等。此外，文献[74]利用城市环境中存在大量垂直表面，如建筑物墙面、甚至垂直树干等，实现扫描匹配。文献[75]提出一种分类特征扫描匹配方法CFSM (Classified Feature-based Scan Matcher)：根据几何观测，将特征分为平移特征和旋转特征两类，分别用于解释传感器的平移和旋转变化，并利用解析式计算位姿估计。文献[76]提出一种利用条件随机场(Conditional Random Fields,CRF)的基于特征的方法：采用一帧扫描中的所有观测进行联合估计，考虑形状信息进行误匹配剔除；该模型能够组合多种特征，如形状特征和外貌特征；但计算复杂度较高，且对于部分重叠的帧间扫描匹配不可靠。文献[77]提出利用方向分布表征扫描点云的几何趋势，从而通过巴氏距离度量两帧扫描数据间的相似度。该方法能够给出两帧扫描数据间旋转变化的初始估计，因而能够处理大的旋转变化。

3.2 转换为图像并提取特征

相较于直接处理散乱的无序点云数据，将扫描数据转化为图像并利用相对成熟的图像处理方法来实现激光扫描匹配是另一种切实可行的思路。文献[78]将点云投影为图像，然后提取SIFT特征；文献[79]通过点云生成深度图像然后提取NARF(Normal Aligned Radial Feature)特征用于匹配。文献[80]考虑扫描匹配效率和数据存储问题，提出利用多分辨率影像金字塔来处理一对多，多对多2D扫描匹配问题。文献[81]提出一种基于关键点的2D扫描匹配方法，该方法首先将LiDAR数据转化为占据栅格地图，然后再转换到图像，利用Harris角点检测方法来提取关键点，最终利用RANSAC(Random Sample Consensus)算法实现匹配。文献[82]利用从360°点云中提取的面片进行扫描匹配，为加快点云处理，将点云投影到3个2D图像来提取面片。

3.3 存在的主要问题和发展趋势

在结构化场景中，基于特征的扫描匹配方法能够处理具有部分重叠和较大偏移的连续扫描，但也存在一些问题：

(1)对于稀疏的扫描点云或非结构化场景，难以提取稳定可靠的特征，而对于特征丰富场景，匹配时存在歧义或模糊问题；

(2)提取鲁棒的特征需要较高的计算代价，计算特征描述子需花费大量时间；

(3)缺乏适当的策略来移除误匹配特征，而一旦存在误匹配的特征，将会导致重大错误而不仅是误差的增大；

(4)相比于ICP类算法，通常精度较差，因而对于通过增量式的连续扫描匹配来估计位姿，往往会存在更为严重的漂移。

鉴于上述问题，采用由粗到精的混合扫描匹配方法逐渐成为一种趋势，先用基于特征的方法求得初始位姿估计，再运行ICP类算法进一步修正位姿，从而最终得到准确的位姿。如文献[14]和[83]所用扫描匹配方法默认工作在基于特征的扫描匹配模式，当没有足够线特征可匹配时，激活ICP扫描匹配模式。此外，文献[84]提出了一种新颖的3D特征，能够从存在运动畸变的点云中鲁棒地提取出来并匹配，为实现不进行畸变改正直接对变形的连续扫描点云进行扫描匹配提供了可能。

4 基于数学特性的方法

除了基于点的扫描匹配和基于特征的扫描匹配，还有一大类利用各种数学性质来刻画扫描数据及帧间位姿变化的扫描匹配方法，其中最著名的当属基于正态分布变换(Normal Distributions Transform,NDT)的方法。

4.1 NDT及其改进算法

点云是激光扫描数据最简单直观的表达形式，对于可视化来说非常有用，但是点坐标的表示形式不能明确表达被测目标的表面特性，如表面朝向、平滑度、孔洞等。因此，Biber[85]提出一种基于NDT的2D扫描匹配新方法，成功用于相对位姿跟踪和激光SLAM。该方法将单次扫描中的离散2D点变换为定义在2D平面上的分段连续且可微的概率密度，概率密度由一组容易计算的正态分布构成，另一帧扫描与NDT的匹配就定义为最大化其扫描点配准后在此密度上的得分，并利用牛顿法进行优化求解。该方法的显著优点是，不需要建立点间或特征间的明确对应关系，而对应关系确立过程往往存在错误关联，因而更鲁棒；正态分布给出了扫描数据的分段光滑表示，具有连续的一二阶导数，有了该表示，使得将标准的数值优化方法应用于扫描匹配成为可能，导数可解析计算，从而求解更快速和准确。

文献[86]将2D的NDT方法推广到3D，提出一种P2D(Point-to-Distribution)-NDT扫描匹配方法。该算法首先将参考帧扫描数据划分为小立方体(体素)组成的网格，对于每个体素利用其内部包含的点qk=1,…,m计算一个概率密度函数(Probability Density Function,PDF)，每个体素内的PDF可以视为表面点x的生成过程，即点x是根据PDF表示的分布采样得到的。假设服从D维正态分布，则在测得点x的似然为:

其中，μ和Σ表示体素内点的均值向量和协方差矩阵，即:

应用NDT进行扫描匹配的目标是寻求位姿变换T，使得变换后当前帧扫描中的点位于参考帧扫描表面的似然最大，即

这里的PDF不必限定为正态分布，可以选用任意能够恰当表示表面结构且对异常点鲁棒的分布。由于单纯的正态分布对异常点不鲁棒[87]，NDT算法中采用的PDF是正态分布和均匀分布的混合，即

Σ-1(x-μ)]+c2ξ0, (7)

图3 P2D-NDT扫描匹配方法流程图 Fig.3 Pipeline of the P2D-NDT based scan matching method

文献[89]将P2D-NDT进一步扩展，对待匹配的两帧扫描数据均用正态分布表示，提出D2D(Distribution-to-Distribution)-NDT方法，并且讨论了迭代优化算法初始点的选取以及协方差的估计。由于D2D-NDT方法只在NDT模型上进行操作，其运行速度比P2D-NDT要快得多，但代价是鲁棒性稍差[90]。此外，NDT还存在多种改进算法，这里不再一一列举。

4.2 其他方法

基于相关或互相关的扫描匹配方法研究相对较多。文献[91]提出的CCF方法将2D扫描数据转换为统计表示形式，利用角度直方图以及x、y直方图间的归一化互相关来实现匹配。文献[92]提出一种新的鲁棒的互相关扫描匹配方法，对于大的平移和旋转也能较好处理，且对环境中的动态目标鲁棒。基于互相关的方法虽然效率高得多，但精度低于ICP算法，适用于载体计算能力有限的平台。

文献[4]提出利用广义霍夫变换(Generalized Hough Transform,GHT)得到的粒子分布来近似目标分布，称为GPM(GHT Particles Matching)，该方法能够应用于非结构化场景，对遮挡鲁棒，在欠约束条件下也能表现良好，执行效率很高。文献[5]和[8]基于计算机视觉中常用的谱技术[93]提出了谱扫描匹配(Spectral Scan Matching,SSM)方法。该方法包括两个步骤：首先，利用谱技术及扫描点间的成对几何关系来确定几何一致的对应；然后，基于RANSAC的最小二乘拟合用于位姿变化。该方法无需初始对准，甚至能够用于存在动态目标的场景或扫描点云部分损坏的情况下。

傅里叶梅林变换(Fourier-Mellin Transform,FMT)是广泛用于图像配准领域的一种技术，具有良好的抗噪性，不需要特征提取，但计算代价较高。文献[94]设计了3个1D匹配向量来描述旋转和平移状态，将3D问题转换为1D问题。1D傅里叶变换对于3个不同扫描片段执行3次，显著降低了计算代价，成功用于2D激光扫描匹配。文献[95]提出一种基于普鲁克分析的2D扫描匹配方法。文献[96]提出一种基于动态似然场(Dynamic Likelihood Field,DLF)的2D扫描匹配算法，作为非线性最小二乘问题，利用高斯牛顿法求解，避免了需要建立明确的数据对应问题。该方法在保证一定精度的同时在计算效率上具有明显的优势。文献[97]提出一种基于高斯场(类似于NDT中的正态分布)的3D配准准则，该方法的主要思想是采用高斯混合模型同时度量来自两帧扫描的点间的空间距离和点周围的局部表面相似性，在由空间维度和许多属性维度组成的多维空间中比较点。此外，遗传算法[98]、差分进化算法[99]等元启发式优化算法也被运用到扫描匹配中。

4.3 存在的主要问题和发展趋势

NDT类方法比ICP类算法有更高的效率和更广的收敛域，对于2D和3D应用已有较为成熟的解决方案，但在缺乏良好初值的情况下，也会陷入局部最优。其他基于数学特性的扫描匹配方法目前仍处于初步探索阶段，大多只适用于2D扫描匹配，而且难以在匹配过程中给出其结果的不确定度。但随着激光扫描匹配基础理论的不断发展，将有更多的理论方法引入到扫描匹配中，已有的基于数学性质的2D方法将进一步拓展到3D，对相应方法的可观测性、收敛性及不确定度的研究将进一步发展。

5 激光扫描匹配方法比较与评价

根据前述分析，我们可将典型激光扫描匹配方法的特点总结如表1所示。

表1 典型扫描匹配方法的特点

但激光扫描匹配方法的精度往往难以科学评定，因为难以获得准确的基准值，并且，扫描匹配受众多因素的影响：

(1)LiDAR有关的因素，如测量噪声、频率、测量范围及视场大小；

(2)与载体有关的因素，如运动速度(包括旋转和平移)、点云重叠度、是否存在其他传感器提供初始值以及初始值的质量；

(3)与环境有关的因素，包括场景类型如室内/室外、结构化/非结构化场景，环境中的动态目标以及遮挡程度。

关于扫描匹配方法评价的早期研究主要关注收敛速度和最终结果的精度[34]。对于精度的评价，平移分量较为简单，直接利用欧式距离即可；而对于旋转分量精度的评价有多种不同方法，文献[100]将3D扫描数据与2D的位姿真值融合，评价在2D空间中进行，通过方位偏差绝对值来评价旋转分量精度，统计量采用标准差和最大误差。文献[101]对6种用于SO(3)的距离进行了评价，结果表明欧拉角差的范数不是一种距离，而采用单位球上的测地距离更可取。

文献[27]对比了ICP、GICP和NICP算法。文献[102]研究了匹配算法对于初始不对准的鲁棒性，在收敛域、鲁棒性和配准精度3个方面对比了ICP和3D-NDT方法。结果显示：3D-NDT方法处理更快，能够从偏离真值较大的初值达到收敛，但可能在初值偏差较小的情况下匹配失败，因而相对来说ICP表现更可预见。文献[103]研究了低重叠度对配准算法的敏感度，并用于预测扫描匹配的失败。文献[104]评价了一个局部方法NDT和一个全局扫描配准方法MUMC(Minimally Uncertain Maximum Consensus)。利用仿真进行扫描匹配方法对比也是一种行之有效的方法，如文献[34]利用仿真数据，针对不同的空间约束和传感器噪声对比了ICP的变种算法。文献[105]针对室内环境，仿真分析了何种LiDAR采用何种扫描匹配方法最优，对比了标准ICP、CSM、MbICP、PSM和2D-NDT 共5种算法，并给出了选择建议。

科学方法的一个关键部分是性能测试实验能够被其他研究人员重复实现以便比较不同的结果。通常，文献中进行扫描匹配算法验证时往往选择较为简单的适合相应算法的场景与某一到两种其他方法进行对比，未测试或只测试上述个别因素对扫描匹配的影响；并且，同一算法在不同文献中有不同的实现，这使得多种算法的严格对比难以实现。文献[35]在激光扫描匹配方法评价方面具有里程碑意义，提出了利用公开数据集系统评价ICP及其改进算法的首套规范，已成为许多学者评价激光扫描匹配方法的事实标准[90]。此外，该文还开源了一个模块化的ICP库，使得在同一框架下对比不同ICP改进算法成为可能。

目前，对激光扫描匹配的大规模深入研究仍然较少。文献[90]首次将文献[35]提出的规范用于评价非ICP方法，同时指出文献[35]提出的基准存在重大缺陷：首先，来自数据集的可用扫描数据对的选择较少，因而限制其应用于全局扫描匹配方法；其次，所提供的初始偏移往往是不切实际的，而扫描重叠度通常较低，虽然这使得数据集更具挑战性，但限制了其在更符合实际情况下的辨别力。相应地，文献[90]提出了对于扫描匹配评价测试规范[35]的修改建议：

(1)采用固定大小的位姿偏移(如文献[86])，而不是从正态分布中采样得到(即加方差一定的高斯噪声)；

(2)提供更多确定可用的扫描对，大量的初始位姿估计只对局部方法有意义，对于不需要初值的全局方法，提供更多的扫描数据对及其真值更为重要。

6 总结与展望

回顾激光扫描匹配方法的发展变化，从最初的基于点的扫描匹配，到基于特征的扫描匹配，再到基于正态分布变换等数学性质的扫描匹配，对扫描数据(即场景的采样)的表示形式越来越高级；新的方法松弛甚至完全脱离了传统方法的假设，使得模型越来越逼近真实情况，从而得到越来越精确、鲁棒的结果；采用由粗到精的“两步法”逐渐成为扫描匹配的标准方案，混合扫描匹配方法能够扬长避短，从而提升系统的可靠性；随着硬件计算能力的提升，一些求解更准确但计算复杂度较高的方法变得可实时运行，加速了场理论、谱技术、智能优化算法等移植到扫描匹配的进程。总的来说，激光扫描匹配已经得到了相当程度的发展，其中ICP类方法、基于特征的方法以及NDT类方法是目前发展较为成熟、应用相对广泛的代表性解决方案，但仍然存在一些亟待完善和解决的问题，同时也是激光扫描匹配研究的发展方向，可能包括但不限于：

(1)降低扫描匹配旋转分量误差，旋转参数误差往往与平移参数误差在同一量级，但在较远处造成的实际偏差往往很大，使测得的图不准，误差累积后漂移严重；

(2)应对扫描点云运动畸变问题，由于传感器随载体快速运动，扫描点云产生变形难以匹配，尤其是采用低速旋转3D LiDAR时[22]；

(3)有效处理动态场景中的动态目标，首先是识别和跟踪，然后是如何处理(如采用降权的方式，而不一定是直接剔除的方式)；

(4)长期运行而又不闭环情况下如何减小扫描匹配的累积误差，即漂移问题；

(5)寻求新的鲁棒高效的3D特征点，包括检测算法和特征描述子；

(6)混合扫描匹配算法，鲁棒于不同的环境条件，如重叠度变化、环境结构性条件变化以及高动态(如大旋转角)，可自适应调整参数[67]、切换或有效组合不同方法；

(7)故障监测，即有效预测和检测扫描匹配失败；

(8)运用深度学习等人工智能技术来解决扫描匹配问题[106]；

(9)结合语义信息进行扫描匹配(如利用语义信息辅助ICP算法中的对应点匹配[107])。