论文引用格式：Wu Y， Yuan Y Z， Xiang B H， Sheng J L， Lei J Y， Hu C Y， Gong M G， Ma W P and Miao Q G. 2023. Overview of the computational intelligence method in 3D point cloud registration. Journal of Image and Graphics， 28（09）：2763-2787（引用格式:武越， 苑咏哲， 向本华， 绳金龙， 雷佳熠， 胡聪颖， 公茂果， 马文萍， 苗启广. 2023. 三维点云配准中的计算智能方法综述. 中国图象图形学报， 28（09）：2763-2787）［0　引 言三维数据是表达物理世界的一种方式，可以通过深度相机、激光雷达等设备获取，并且它有多种表示方式，例如深度图像、体素图像、三维点云和多边形网格等。随着三维扫描设备的成熟和普及，越来越多的点云数据产生并得到广泛应用，点云配准是点云数据处理的一个重要研究方向。本文主要研究刚性变化运动下的点云配准问题，给出定义如下：给定两个点云，旨在找到一个刚性变换运动参数以使源点云对齐参考点云，其中点云可能存在遮挡、噪声或两个点云重叠程度低等情况，因此要求算法需在保证运行效率的前提下，具备一定的鲁棒性和较高的准确性。点云配准问题研究历史颇久，Besl和Mckay（1992）提出具有开创性的迭代最近点算法（iterative closet point，ICP），通过迭代寻找对应点关系和计算运动参数两个过程，将解收敛至极小值，但是需要一个较好的初始位姿以免陷入局部最优解。随后，许多传统点云配准方法及其变体相继提出，例如正态分布变换（normal distributions transform，NDT）算法和4PCS（4-points congruent sets）算法，但是大多数传统点云配准算法容易陷入局部最优解或对异常值较为敏感。点云配准是一种十分复杂的问题，单靠传统的ICP算法计算是一项非常艰巨的任务，且依赖点云重叠度，并受噪声的影响过大。因此点云的配准迫使研究者使用计算智能来处理这一具有挑战性的任务。相较于传统的计算方法，计算智能具有对复杂问题的自适应性，可以更有效地解决不同复杂场景下的点云配准问题，并且准确性更高，还具有高鲁棒性。计算智能包含深度学习、进化计算和模糊学习等，各个方法已经成功用于点云配准。随着硬件的发展，深度学习受到普遍关注。基于体素（Maturan和Scherer，2015）和基于多视图的方法（Su等，2015）是将深度学习应用于点云配准的先驱，并且取得了良好的效果。Qi等人（2017a，b）提出PointNet和PointNet++，首次以直接的方式将深度学习运用于点云，直接读取点云数据而不进行体素化等操作，解决了体素化后数据量庞大且丢失精度的问题，并且使用对称函数保证了点云的置换一致性，解决点云数据中存在的无序排序的问题。随后，在基于深度学习的研究中，人们提出了许多具有较强鲁棒性的方法。本文将基于深度学习的点云配准研究根据有无对应关系分类为无对应关系点云配准和基于对应关系的点云配准方法。在无对应关系点云配准中，PointNetLK和PCRNet为最经典的两种网络，使用PointNet提取出点云特征后，前者通过一套逆向合成算法计算出最佳运动参数，而后者则通过数据驱动的方式，将两个点云特征连接后，连接全连接层以预测最佳运动参数。但它们都忽略了部分重叠点云配准中非重叠点给配准结果带来的负面影响。对此，Xu等人（2021）提出了OMNet，OMNet是一个基于全局特征的部分重叠点云配准迭代网络，可以处理部分重叠点云配准问题并展现出较强的鲁棒性。同年，Xu等人（2022）提出了FINet，FINet主要解决了在特征提取时忽略了多个输入之间的数据的联系，导致未能提取出一部分数据关联的特征这一问题，并提出双分支结构对旋转和平移运动参数分别进行处理。在有对应关系点云配准中，找到对应关系是取得好的配准效果的关键。受传统非学习的点云配准方法启发，大多数基于对应关系的深度点云配准方法都是基于特征的，由此可以将方法总体拆分成特征提取、特征匹配、离群值去除和运动参数估计4个模块。在特征提取上，许多方法受到PointNet的启发，将PointNet架构应用到自己的网络中以提取特征。提取特征后需要进行特征匹配以确定点与点之间的对应关系，由于环境遮蔽以及在某些低重叠场景下，直接获取对应关系比较困难，Lu等人（2019）以及Wang和Solomon（2019）通过对置信度进行加权，计算出对应点的位置；Huang等人（2021）通过双流编码—解码网络，采用交叉注意力机制结合上下文的信息，以此得出正确的匹配，解决了低重叠场景下的配准问题。在实际应用场景下，噪声和离群点不可避免，Pais等人（2020）将离群值去除考虑为二分类问题；Bai等人（2021）提出的PointDSC将空间一致性引入点云配准，用以处理离群点较多的情况。点云配准的最后一步是基于得到的对应关系估计运动参数，常用的方法是回归和奇异值分解（singular value decomposition，SVD）。与深度学习不同，进化计算（Yang和He，2015）是受大自然启发，通过模拟生物进化过程和群居生物行为过程来解决问题的一系列全局优化算法，它是计算智能的子领域之一。进化计算具有智能性（Iqbal等，2020）、并行性（Chen，2019）和健壮性（Back等，1997）的特征。智能性包括自组织性、自适应性和自学习性，且算法不依赖于问题本身，具有良好的通用性；基于进化计算的算法基本是以种群为单位、多个个体相互协作的方式来同时进行解空间的搜索，非常适合大规模并行处理；它们也具有良好的容错性，对初始条件极其不敏感，能够在不同条件下搜索到最优解。基于进化计算的算法是高效的全局搜索方法，与传统优化算法相比，进化计算具有以下优点：1）在处理优化问题时，不需要对求解问题的数学公式进行严格推导（De Jong，2016），只需将待求解问题描述为适应度函数，通过利用个体的适应度值就能迭代搜索最优解，而不需要用目标函数的导数信息以及其他特殊相关信息。所以，能够不受问题的约束，有效地求解传统优化算法难以解决的非凸、不连续和不可导的复杂优化问题（Fogel，1997）。2）进化算法通常具有一定的自适应搜索能力，随着迭代求解过程的推进，能够根据优化结果自适应地调整参数信息，以平衡全局勘探和局部开发的能力，同时保持种群多样性（Yang和He，2015），能够有效避免陷入局部最优和收敛缓慢的问题。3）传统优化算法以一个初始值来迭代搜索最优解，而进化算法是以种群的方式同时对解空间的多个区域进行探索，并且能在个体之间交流有效信息。这种方式使得进化算法能够以较快的速度搜寻更广泛的区域。4）进化算法中许多基本操作都是随机的，包括交叉、变异和选择算子（Eiben和Schoenauer，2002）。这些较高的随机因素使其处理不确定性问题具有一定优势，具有较好的鲁棒性。深度学习与进化计算旨在找到点云配准过程中的变换参数，而模糊逻辑可以应用于辅助工作。随着硬件的发展，三维数字化过程中会生成大量的点云数据，这在之后对其处理时成为一个严重的实际问题。结合这一点，许多研究者致力于研究减少点云数据的方法。三维数字化的数据简化任务是在较短时间内取得高质量模型的关键。而基于模糊逻辑的决策方法可以在复杂情况下大幅提升简化效果，并且可以使用户获得关于特定参数的效果，对用户更加友好。除此之外，三维点云配准的一个重要方向是在不了解真值的情况下对配准质量进行评估，而用以往的算法并不能自动实现这个目的。基于模糊聚类的点云配准方法相较于传统的算法提供了广泛的收敛范围和精确的配准，并且具有更高的鲁棒性。计算智能方法在处理点云配准问题上表现出较强的优势，其不依赖于问题的特性，自身容错性高，可以很好地解决初始位姿差、存在遮挡和噪音以及点云重叠程度低等问题，从而准确地寻找出问题的最优解。在点云配准方向的综述中，已有部分相关研究工作。有许多学者致力于提出鲁棒的点云配准方法（Yang等，2013；Ma等，2013；Ma等，2014a；Koide等，2021）。李建微和占家旺（2022）将点云配准方法分为非学习方法和基于学习方法对该方向的研究进行总结。秦红星等人（2022）和Zhang等人（2020）总结了深度学习刚性点云配准领域方面的相关研究。也有一些综述（Zhang等，2020）从关键点选择、对应点的匹配（Ma等，2013；2014b）、对应关系的权重、离群点去除、损失函数和运动参数估计的角度对传统点云配准方法进行分类。以上研究皆未涉及进化计算和模糊算法的点云配准方法，缺少全面性。为了全面系统地介绍三维点云配准中的计算智能方法，本文从基于深度学习、基于进化计算和基于模糊逻辑3个方面分别展开对点云配准方法的论述，同时对传统点云配准方法进行简要介绍，旨在以更全面、清晰的方式总结点云配准方向上的相关研究。本文主要贡献如下：1）对点云配准方向相关研究工作进行全面总结。对基于深度学习、进化计算和模糊逻辑的点云配准方法这3个方面给出比以往综述性工作更全面的总结。2）对近年来提出的针对重叠性低的点云配准方法进行全面调查。3）将基于深度学习的点云配准方法根据有无对应关系分为无对应关系点云配准方法和基于对应关系的点云配准方法，以更清晰的思路介绍相关研究。4）从基于进化算法和基于群智能算法的角度分类总结它们在点云配准中的应用。5）研究了模糊逻辑在点云配准中的应用。1　传统点云配准方法为了体现计算智能方法的优越性，也出于介绍完整性的目的，本节对传统点云配准方法做简要介绍。在传统点云配准中有3种经典的方法，分别为ICP（Besl和McKay，1992）、NDT（Magnusson等，2007）、4PCS（Aiger等，2008），随后许多配准算法均基于这3种经典配准算法演变而来。1.1　ICP算法ICP算法即迭代最近点算法，由Besl和Mckay（1992）提出，是点云配准中的经典方法，该方法首先找到两个点云的对应关系，然后计算运动参数以使得对应点距离最短，反复迭代上述两个步骤，当两次迭代间的对应点距离之差小于所设阈值时，终止迭代并得出变换参数。ICP这种方法容易陷入局部最优解，通常需要一个较好的初始位姿，对异常值敏感，鲁棒性不强，在计算上时间成本较大，因此在资源有限的移动平台上的实时程序中应用比较困难。后续许多基于ICP的研究主要都是从提高算法鲁棒性（Chen和Medioni，1992；Segal等，2009）、增强算法收敛性（Gold等，1998）和提高算法运行效率（Simon等，1995；Pavlov等，2018） 3方面展开的。1.2　NDT算法NDT算法是点云配准中的另一经典算法，由Magnusson等人（2007）提出。给定两个点云P = ｛pi｝，Q = ｛qi｝和长度l，首先将点云Q划分为若干个l×l×l的体素，分别计算出每个体素的均值μ⃗和协方差矩阵∑（体素内点的数量超过5才计算，若体素内点的数量小于3，则协方差矩阵必定是奇异的），使用正态分布和均匀分布的加权和表示一个体素的局部概率密度函数（local probability d-ensity functions，PDFs），计算每个体素内的PDFs的过程仅需要计算一次即可，不需要每次迭代时重复计算。最佳的变换矩阵是使得源点云各点经过刚性变换后在其对应的体素概率密度函数中的极大似然函数最大的变换矩阵。然后通过求导更新配准向量，该算法一直迭代上述过程直至收敛。NDT算法虽然能获得较好的配准效果，但是仍需要较好的初始位姿，否则将容易收敛至局部最优解。后续关于NDT的相关研究（Das和Waslander，2012，2014；Lu等，2015；Zaganidis等，2017）主要也是以提高方法的收敛性、准确性和运行效率为目的。1.3　4PCS算法4PCS算法是一种基于随机采样一致性（random sample consensus，RANSAC）算法理念设计的粗配准算法，由Aiger等人（2008）提出。给定点云P = ｛pi｝，Q = ｛qi｝和距离阈值δ，首先在点云P中找到共面的四点集B = ｛a， b， c， d｝，设两条线段相交于点e，计算出线段的比率r1与r2，再分别求出两条线段的长度d1和d2，然后在点云Q内找到若干4个共面点集组成集合U = ｛ui｝，其中，每个共面点集ui需要满足两条线段被交点e分割的比率分别与r1，r2大致相等（使用距离阈值δ控制可容忍的误差范围），且两条线段长度也分别与d1、d2大致相等（使用距离阈值δ控制可容忍的误差范围）。最后通过计算每个ui对应的最佳变换矩阵Ti，将点云P分别根据各个Ti进行变换，分别统计出变换后点云的点与点云Q中点距离小于阈值δ的数量，数量最大所对应的变换矩阵Ti即为最终结果。4PCS算法为粗配准算法，因此配准精度较低且算法速度较慢。后续关于4PCS算法的相关研究（Mellado等，2014；Huang等，2017；Mohamad等，2014；Fotsing等，2020）主要是提升该算法的运行效率。1.4　小结在传统点云配准算法中，ICP算法虽然精度较高，但是一般情况下需要一个较好的初始位姿，并且算法运行效率较低；NDT算法运行效率较高，但是也需要一个较好的初始位姿；4PCS算法不需要初始位姿，但是算法精度和运行效率较低。总而言之，传统点云配准的方法大多存在算法运行效率低、鲁棒性不强、精度不高、需要初始位姿等问题，而这些问题在计算智能应用于点云配准问题后得到了较好解决，计算智能的方法相比传统的配准算法更具有优越性。2　点云配准中的深度学习方法由于传统点云配准方法受异常值影响较大、计算成本较高，越来越多的研究将计算智能方法运用于点云配准。本节介绍计算智能方法中的深度学习在点云配准中的应用，根据有无对应关系，可以将基于学习的点云配准方法分为基于对应的点云配准方法和无对应点云配准方法，前者的大多研究都是基于ICP传统框架进行的，即将网络框架分为特征提取、特征匹配、离群值剔除和运动参数估计这4个部分；后者则是通过搜索两个点云全局特征的差异估计运动参数。基于深度学习的点云配准方法的发展如图1所示。10.11834/jig.220727.F001图1基于深度学习的点云配准方法发展Fig.1Point cloud registration based on deep learning development2.1　无对应点云配准方法无对应关系配准方法是通过搜索两个点云全局特征的差异，通过这个差异回归得到运动参数。其中有两个关键步骤：1）提取出对点云的姿势敏感的全局特征；2）利用两个点云全局特征的差异计算出运动参数。Aoki等人（2019）受Baker和Matthews（2004）提出的光流算法（Lucas-Kanade，LK）的启发，提出了PointNetLK，使用PointNet（Qi等，2017a）提取两个点云的全局特征ϕ(P)和ϕ(Q)，然后使用逆向合成算法求解运动参数，该网络以(Gest)-1Ggt-I4作为损失函数，其中，Gest为该网络求出的最佳运动参数，Ggt是实际运动参数，I4为一个4阶单位阵，以此度量实际运动参数与预估运动参数的误差。在该网络中，雅可比矩阵只需计算一次，不需要每次都重复计算，因此计算效率较高。Sarode等人（2019）提出PCRNet，它提取特征的方式与PointNetLK类似，同样是使用PointNet提取全局特征，然后将两个点云的特征连接成2 048维的合成特征，再利用连续的全连接层输出最终预估的运动参数，这是一种数据驱动点云的配准方法，该网络架构图如图2所示。Groβ等人（2019）提出另一种数据驱动点云配准的网络AlignNet-3D，该研究更注重真实的场景，着重专注于3D轨道的参数估计。10.11834/jig.220727.F002图2PCRNet网络架构图Fig.2PCRNet network architecture diagramHuang等人（2020）提出Feature metric regist-ration，该网络注重特征提取部分，使用了自编码器的机制，对于两个点云旋转后形成的副本，编码器提取出对位姿敏感的全局特征，解码器可以将不同的全局特征恢复成相对应的旋转后副本。Xu等人（2021）针对前人研究忽略了部分重叠点云配准中非重叠点给配准结果带来负面影响这一问题，提出OMNet。OMNet是一个基于全局特征的部分重叠点云配准迭代网络，可以处理部分重叠点云配准问题并展现出较强的鲁棒性。在同一年，Xu等人（2021）提出了FINet，FINet主要解决了特征提取时忽略多个输入之间的数据的联系，导致未能提取出一部分数据关联的特征这一问题。FINet将特征分成两部分，一部分用于旋转，另一部分则用于平移，通过一个双分支结构分别进行处理，另外，在特征提取部分插入了几个交互模块对数据进行关联。表1总结了无对应点云配准方法。10.11834/jig.220727.T001表1无对应点云配准方法Table 1Correspondences-free methods of point cloud registration模型方法改进优点PointNetLK（Aoki等，2019）使用PointNet提取出点云全局特征，使用逆向合成算法求解运动参数首个提出无对应配准的算法，并且雅可比矩阵只需计算一次，计算效率较高PCRNet（Sarode等，2019）使用PointNet提取点云全局特征，通过全连接层预测运动参数相比前人的工作，对点云的初始位姿和离群点的干扰更具鲁棒性AlignNet-3D（Groβ等，2019）提出另一种数据驱动点云配准的网络AlignNet-3D，该研究更注重真实的场景对存在遮挡的数据更具有鲁棒性FMR（Huang等，2020）使用自编码器的机制，对于两个点云旋转后形成的副本，编码器生成不同的全局特征，解码器可以将不同的全局特征恢复成相对应的旋转后副本使用自编码器监督点云的全局特征OMNet（Xu等，2021）提出了一种预测mask的方法，可以处理部分重叠点云配准问题在处理部分重叠点云配准问题上展现出较强的鲁棒性FINet（Xu等，2021）使用双分支结构分别进行预测旋转和平移，另外，在特征提取部分插入交互模块对数据进行关联解决了在特征提取时忽略多个输入之间的数据的联系2.2　基于对应关系的点云配准方法在通过深度学习进行点云配准的方法中，基于对应关系的配准方法占有很大比例。在传统的点云配准方法如ICP中，通过最邻近算法建立两个点云点与点之间的对应关系，以此来估计变换矩阵。但是这个方法对点云的初始位姿敏感且容易陷入局部最小值。为了解决这个问题，研究者提出了全局配准的方法，通过一种全局的特征描述符来描述点云中的特征点，同时该特征描述符会包含特征点邻域内的信息，以此来求解两个点云中的对应关系，并通过对应关系求解变换。随着深度学习的发展，基于学习的方法开始应用到点云配准中，它们沿袭了传统的非学习方法的思路，并获得了更好的性能以及更高的鲁棒性。基于对应关系的点云配准方法主要由特征提取、特征匹配、离群点去除和运动参数估计4个模块组成。由于许多方法并不是端到端的方法，为方便对比，本文对4个模块分别进行介绍。2.2.1　特征提取特征提取是点云配准中的首要任务和关键任务，特征的好坏直接影响到整个模型的性能（武越等，2022）。在基于对应关系的点云配准中，需要提取两个点云中每个点的全局特征，以此生成映射，求解变换矩阵。在数据的输入上，根据数据的类型可以分为基于体素的特征提取和基于原始数据的特征提取。Maturana和Scherer（2015）提出了VoxNet网络，该网络将体积占用网格表示与受监督的三维卷积神经网络（3D CNN）相结合，将点云中的每个点映射成离散的体素，使用3D CNN直接对体素数据提取特征，最后通过全连接层完成对象识别工作。Khoury等人（2017）提出了一种3D局部特征描述符（compact geometric features，CGF）。这种特征描述符是通过建立点周围球型范围内的分布直方图并通过局部参考框架（local reference frame，LRF）保证其旋转不变性，以此作为输入来训练一个神经网络得到的。这个方法将高维的特征映射到低维的紧凑的欧几里得空间，相较于未经过学习得到的特征描述符来说获得了更高的精确度。Zeng等人（2017）提出了3DMatch网络，将每个兴趣点及其邻域体素化，转换为截断距离函数 （truncated distance function，TDF）值的30 × 30 × 30体素网格，将其作为3D卷积神经网络的输入，训练网络得到一个512维的特征描述符。然而，直接将点云数据转换成体素数据可能会丢失精度，容易受到密度及分辨率的影响，同时可能会导致数据量变得十分庞大。为解决这个问题，Qi等人（2017a）提出了PointNet网络，首次直接使用点云的原始数据而不进行体素化。点云中的每个点表示为（x， y， z）坐标，并且加上额外的特征通道如颜色、法线等向量，以此作为网络输入，通过多层感知机（multilayer perceptron，MLP）提取特征，其中使用T-Net（transformation network）预测一个仿射变换矩阵来保证旋转不变性。PointNet最关键的一点是最后使用了一个对称函数（最大池化）来保证置换不变性，并生成点的全局特征。PointNet存在的一个缺点是没有办法提取到局部特征，这使得它难于应对复杂场景的分析。Qi等人（2017b）在PointNet的基础上进一步提出了Poi-ntNet++来解决这个问题。PointNet++首先通过一个采样层和分组层，使用最远距离采样算法（fart-hest point sampling， FPS）将点划分到一些局部的区域中，对每一个小区域使用PointNet得到局部特征，然后扩大范围，重复以上工作以得到更高维度的特征。这个思想与卷积神经网络的思想相似，都是将特征由低级发展到高级。面对非均匀点云时，使用多尺度分组（multi-scale grouping，MSG）和多分辨率分组（multi-resolution grouping，MRG）两个方法划分小区域，避免因为点云的稀疏性影响到特征提取。受PointNet的启发，Deng等人（2018a）提出了 PPFNet。首先将点的几何特征如坐标、法线等与点对特征（point pair feature，PPF）拼接在一起作为整个网络的输入，通过PointNet提取到局部特征，然后通过最大池化将局部特征聚合为全局特征，将全局特征与局部特征拼接后，通过多层感知机进行特征融合得到最终的3D特征描述符。在损失函数上，提出了N元组损失（N-tuple loss），改进了传统的二元组损失（contrastive loss）和三元组损失（triplet loss），使得在原始空间中相似的点在特征空间中也相似，充分利用了对应关系，提高了特征空间中不同点集的辨识度。PPFNet没有实现完全的旋转不变性并且仍然需要监督，为了解决这个问题，Deng等人（2018b）结合PointNet、FoldingNet（Yang等，2018）和PPFNet，提出了PPF-FoldNet，仅使用PPF特征并且进行无监督学习，将提取的PPF特征输入到一个由多层感知机和最大池化层构成的编码器，获得一个压缩的码字，这个码字作为全局特征输入到解码器进行解码，重建完整的PPF特征。这使得编码得到的码字保留最关键的和最具有鉴别力的特征信息。Choy等人（2020）提出全卷积几何特征（fully convolutional geometric features，FCGF），采用一种稀疏的张量表示3D点云数据，通过1 × 1 × 1的卷积核和一个带有跳连接和残差模块的UNet架构提取几何特征。Horache等人（2021）在 FCGF 的基础上提出了多尺度稀疏体素卷积（mul-tiscale sparse voxel convolution，MS-SVConv），这是一种基于多尺度UNet的方法，利用带数据生成的无监督迁移学习（unsupervised transfer learning with data generation，UDGE）对未知场景进行归纳。MS-SVConv保留了与FCGF一样基于U-Net的方法的简单性、速度快、效率高和模块化的特点，同时UDGE可以使网络在一些合成数据集上进行预训练，然后应用到下游任务中取得更好的效果。2.2.2　特征匹配通常来说，采集自同一目标的不同点云之间会存在着重叠区域，通过特征匹配找到重叠区域中的对应点就可以由此估算变换矩阵，这对点云配准来说至关重要。在传统方法中，会通过定义一个几何特征如欧氏距离、协方差矩阵等来表示两个点之间的相似度，以此找到最相似的点作为对应点。但是，由于不同点云之间的采集视角或环境遮蔽等一些原因，通过低级的几何特征可能难以找到对应点。为解决这个问题，Lu等人（2019）提出了DeepVCP网络用于生成对应点。首先，通过PointNet++提取源点云和参考点云的特征。其次，通过一个权重层（weighting layer）赋予每个点一个权重，选择权重较大的点，将其邻域内的一些点作为候选点参与后续匹配。接着，通过一个基于mini-PointNet的深层特征嵌入层（deep feature embedding layer）继续提取特征。然后，通过一个对应点生成层（corresponding point generation layer）并通过3D CNN和softmax得到源点和候选点间的权重矩阵。最后，通过加权求和计算得到最终的对应点，得到匹配关系。Wang和Solomon（2019）在ICP的基础上提出了基于深度学习的深度最近点（deep closest point，DCP）算法。在DCP中，首先通过DGCNN（dynamic graph convolutional neural network）（Wang和Solomon，2019）提取特征，使用一个基于自注意力机制的Transformer（Vaswani等，2017）网络对源点云和参考点云的特征进行编码，然后对于每个源点云中的点，通过与参考点云中的所有点做点积的方式衡量二者的相似度，使用softmax将相似度转换为概率。这个概率衡量了两个点云中的点互为对应点的可能性。最后将这个概率作用于参考点云计算出对应点，通过SVD求解变换矩阵。在低重叠场景下，源点云和参考点云的对应点会减少，这导致配准难度上升。Huang等人（2021）提出了PREDATOR，用于解决低重叠场景下的点云配准问题。PREDATOR使用了一个双流编码解码器网络，先对点云进行下采样，使其具有合理均匀的点密度，然后将其通过编码器得到超点（super point）集合，通过交叉注意力模块对两个点云的几何特征和上下文进行编码，并给每个超点分配两个重叠分数用以衡量超点位于重叠区域的可能性。最后通过解码器对上个模块得到的输出点进行解码，输出每个点的特征、重叠得分以及匹配得分。这个匹配得分类似于显著性，量化了一个点被正确匹配的可能性大小。2.2.3　离群点去除离群点去除同样是点云配准中的一个关键任务。点云是一种离散的、非结构化的数据，在实际应用中，通过设备提取到的点云数据可能会有许多噪声和离群点，这些对点云配准的性能有较大影响，研究者对于如何合理地去除这些离群点做了许多工作。Pais等人（2020）提出了3DRegNet网络。这个网络由分类模块和配准模块组成。分类模块由卷积层和多个ResNet 构成，最后得到每一个对应关系的权重，通过最大池化选择具有较大权重的对应点来进行配准，以此去除离群点。在配准模块中，通过深度神经网络（deep neural network，DNN）或奇异值分解（SVD）进行变换参数的预测。Bai等人（2021）提出了PointDSC（point deep spatial consistency）网络。PointDSC改进和拓展了基于长度一致性构建对应关系的SM（spectral match）算法，将空间一致性引入点云配准，在离群点去除上取得了更好的效果。PointDSC主要由3个模块构成：1）特征提取模块SCNonlocal，它将匹配后的点对作为输入，利用空间一致性提取特征。2）种子选择模块，将特征提取模块产生的特征通过多层感知机（MLP）产生每个匹配对的置信度，然后通过非最大值抑制选择具有较高置信度的点对作为种子。3）神经谱匹配模块（neural spectral matching，NSM）， 先对每个种子进行K近邻搜索，得到若干个满足空间一致性的子集，在子集上使用NSM求解刚性变换。Fu等人（2021）提出了基于深度图匹配的鲁棒点云配准框架（robust point cloud registration framework based on deep graph matching，RGM），首次提出利用深度图匹配来解决点云配准问题。RGM由局部特征提取器、边生成器、图形特征提取器、AIS（affinity layer， instance normalization and Sinkhorn）模块以及LAP（linear assignment problem）-SVD模块组成。在边生成器中，使用Transformer对特征进行编码，使其包含上下文信息，对两个点云的特征编码进行内积后，应用softmax函数生成软邻接矩阵。生成图像后，首先进行图内卷积提取结构特征，然后引入AIS模块对图进行特征匹配，得到点之间可靠的对应关系，最后通过SVD求解变换矩阵。图匹配不是仅利用每个点的特征，而是利用其他节点的特征和图的结构信息建立对应关系，从而更好地解决离群点的问题。2.2.4　运动参数估计运动参数估计是点云配准的最后一个任务。在基于对应关系的点云配准中，需要根据经过特征匹配得到的对应点来求解运动参数，如旋转矩阵R和平移向量t，以估计两个点云之间的刚性变换。最常用的方法是回归和奇异值分解（SVD）。Deng等人（2019）将PPF-FoldNet中PPF的部分用3D点本身代替变成PC-FoldNet，将其与PPF-FoldNet一起分别提取到两个点云中的旋转不变和旋转可变的特征，对于每个点云，利用这两个特征的差异生成了几乎完全专注于位姿信息的特征。将这个特征送入RelativeNet中通过回归的方式估计出两个点云之间的变换矩阵。在3DRegNet（Pais等，2020）中，最后使用深度神经网络（DNN）从经过多层感知机和多个ResNet提取到的特征中估计出运动参数。这些通过回归的方式估计运动参数的整体框架就是提取出源点云和参考点云的对应点，将其特征通过一个回归网络进行参数估计。在传统SVD的基础上，研究者又引入加权SVD的方法用以估计运动参数。传统SVD的效果依赖于每个对应关系发挥同等的作用，但是在实际情况中，获得的对应关系可能并不全部有效，通过加权SVD的方式可以将注意力放在权值较大的点上。在RPM-Net（Yew和Lee，2020）、IDAM（iterative distance-aware similarity matrix convolution network）（Li等，2020）、DGR（deep global registration）（Choy等，2020）中，最后都是使用加权SVD求解出刚性变换，并取得了很好的效果。2.3　小结本节讨论了点云配准中的深度学习方法，将基于深度学习的点云配准分为无对应点云配准方法和基于对应关系的点云配准方法。无对应关系配准方法是通过搜索源点云和参考点云全局特征的差异，通过这个差异回归得到运动参数。其中，有两个关键步骤：1）提取出对点云的姿势敏感的全局特征；2）利用两个点云全局特征的差异计算出运动参数。在基于对应关系的点云配准方法中，将其细分成了特征提取、特征匹配、离群点去除和运动参数估计4个任务，并对每个任务中使用的部分方法做了介绍，分析了一些算法的细节和特点。现有方法基本上都是通过完成这4个任务进行点云配准，首先要通过特征提取和特征匹配获取点云间的对应关系，然后进行离群点去除。最后的参数估计中，最常用的两种方法是回归和奇异值分解。前者通过网络学习出变换参数，后者计算出解析解，并且一些研究者在传统SVD的基础上引入了加权SVD的方法，取得了更好的效果。在计算智能的其他方法中，进化算法同样能够克服传统点云配准中所存在的不足。表2总结了一些在深度学习中基于对应关系的点云配准方法。10.11834/jig.220727.T002表2基于对应关系的点云配准方法Table 2Correspondence-based methods of point cloud registration模型方法改进优点VoxNet（Maturana和Scherer，2015）将点云中的每个点映射成体素，通过3D卷积神经网络提取特征将体素和3D卷积神经网络相结合，可以有效处理大量点云数据CGF（Khoury等，2017）建立点周围球型范围内的分布直方图作为网络输入，并训练网络得到CGF特征描述符保证了旋转不变性，精确度更高3DMatch（Zeng等，2017）将点云数据转换为体素网格，训练一个 3D卷积神经网络，生成一个512维的特征描述符适用于不同任务以及多种空间尺度PointNet（Qi等，2017a）首次将点云数据直接作为网络输入而不经过体素化，通过网络提取点云的全局特征直接使用点云原始数据，速度更快，通过使用对称函数保证了置换不变性PointNet++（Qi等，2017b）使用采样层、分组层和PointNet提取不同尺度的局部特征能够在不同尺度提取局部特征，解决点云密度不均匀问题PPFNet（Deng等，2018a）将点的几何特征和点对特征拼接作为网络输入，使用PointNet和最大池化聚合特征，最后通过多层感知机得到最终的特征描述符充分利用对应关系，提高了特征空间中不同点集的辨识度，鲁棒性强，保证了旋转不变性PPF-FoldingNet（Deng等，2018b）结合PointNet，FoldingNet和PPFNet，仅使用PPF特征进行无监督学习结合3个网络的优点，无监督，相较于PPFNet更能保证旋转不变性DeepVCP（Lu等，2019）使用PointNet++提取特征，通过加权求和的方式计算得到最终两个点云中的对应点第1个基于端到端学习的点云配准框架，配准准确性高DCP（Wang和Solomon，2019）使用DGCNN提取特征，通过Transformer对特征进行编码，使用概率的方式计算得到两个点云之间的对应点解决了将传统ICP算法拓展到深度学习领域的一系列问题PointDSC（Bai等，2021）改进和拓展基于长度一致性构建对应关系的Spectral Match算法将空间一致性引入点云配准，在离群点去除上取得了更好的效果PREDATOR（Huang等，2021）使用双流编码解码器网络，通过分配重叠分数用以衡量点位于重叠区域的可能性解决了低重叠场景下的点云配准问题RGM（Fu等，2021）首次提出利用深度图匹配来解决点云配准问题利用其他节点的特征和图的结构信息建立对应关系，从而更好地解决离群点的问题3　点云配准中的进化计算方法进化计算是一类具有元启发式和随机性特点的优化求解器（Yang和He，2015）。它受达尔文生物进化理论中优胜劣汰的自然选择机制和群体生活方式的启发，通过程序模拟这一迭代求解的过程，把待解决的问题描述为优化问题，将问题参数表示为候选解空间，利用种群的进化和繁殖，对全局解空间进行搜索寻优，最终能够找到全局最优解或可接受的近似解。进化计算通常包括种群初始化、个体适应度值评估、种群的繁殖和产生新种群的选择机制等基本操作。由于进化计算具有鲁棒、并行和自适应等优点，在以往的研究中，广泛用于解决各种复杂优化问题。Slowik和Kwasnicka（2020）概括了将进化计算用于处理各个领域中的连续参数优化、离散参数优化、离散连续混合优化和组合优化问题，展现了它在解决复杂优化问题上的强大优势。在自然图像配准（De Falco等，2008；Santamaría等，2011，2012；Albukhanajer等，2015；Cocianu和Stan，2019）、遥感图像配准（De Falco等，2009；Ma等，2014b；Wu等，2018，2019，2021；Yavari等，2018）、遥感图像分类（Wu等，2020）和医学图像配准（Wachowiak和Elmaghraby，2001；Wachowiak等，2004；Ingole等，2009；Damas等，2011；Abdel-Basset等，2017；Panda等，2017）领域，研究者提出了许多基于进化计算的方法。这些基于进化计算的图像配准方法，展现出进化算法对于处理配准问题的优势，同时也为点云配准提供了新的思路。随着点云数据的丰富，越来越多的研究者将基于进化计算的方法用于解决点云配准的问题，这些方法已经证明它们能够在点云配准中得到更好的性能。本文主要从以下两个方面进行总结：基于进化算法的点云配准方法和基于群体智能的点云配准方法。3.1　基于进化算法的点云配准方法进化算法是基于自然选择和自然遗传等生物进化理论的全局搜索算法。进化算法包括遗传算法（Holland，1975）、遗传规划（Nguyen等，2017）、进化规划（Porto，2020）和进化策略（Liu和Zhang，2020）。由于遗传算法在点云配准中的应用更为广泛，本文主要总结基于遗传算法的方法。除此之外，差分进化算法是一种通过利用个体之间差异信息来进化种群的新兴全局搜索算法，其结构简单，控制参数较少，且收敛性较好，已广泛应用于解决各个领域的优化问题（Das等，2016）。在点云配准领域，已经有大量的学者提出了许多基于差分进化的方法。遗传算法（genetic algorithm，GA）是由John Holland提出的一种自适应的元启发式优化技术（Holland，1975）。遗传算法具有并行、灵活、可扩展性和易实现等优点，能够自适应地调节参数和搜索状态，以达到在搜索空间中进行寻优的目的。如今，遗传算法已被广泛用于解决点云配准问题，并证明了其有效性以及在点云配准中强大的优势。许多研究者在将遗传算法应用于点云配准的问题上做了许多工作。Galantucci等人（2004）提出了一种基于人工神经网络和遗传算法的方法，来解决自由曲面的点云配准问题。先利用几个球体将点云细分为区域进行分析，通过人工神经网络识别出可行的区域进行粗匹配，再使用遗传算法执行精配准。该方法的主要特点在于遗传算法将种群分为6个子种群，分别对旋转平移中的某一个参数进行优化，最终得到了良好的配准结果。为了解决包含噪声、离群值并且部分重叠的点云配准问题，Lomonosov等人（2006）提出了一种用于点云预配准的鲁棒遗传算法。该方法将包含平移、旋转和重叠率的7个参数范围直接组成搜索空间，而没有进行二进制编码，这样有利于提高计算速度，再采用单点交叉和两种变异（转移变异和替换变异）来进化种群，通过迭代优化截断均方误差，得到预配准结果，再利用TrICP（trimmed iterative closest point algorithm）进行精配准。该算法是在之前的TrICP算法（Chetverikov等，2005）上的进一步完善，将遗传算法的通用性与TrICP的精确和鲁棒性进行结合，得到了一个鲁棒且精确的系统。Schenk和Hanke（Schenk和Hanke，2009；Hanke和Schenk，2014）提出了一种用于处理具有大量噪声、不完美几何特征和部分遮挡的配准技术。该方法分成3个阶段：首先利用不完美和细分特征进行粗配准；然后再通过运用两次遗传算法来进行细化形成近似解，其中，第1次使用特征匹配，第2次使用自由形式匹配，连续使用两次遗传算法是为了提高鲁棒性；最后使用ICP算法对近似解进行精配准。该方法可以看做是对已知的点云配准中的遗传算法进行扩展，通过在经典的粗配准和精配准之间实现遗传算法，能够加快配准速度，同时也进一步提高了系统的鲁棒性。Mansour等人（2010）提出了一个用于自动点云配准的混合遗传算法，该方法将遗传算法和拟牛顿算法结合起来，并引入了约束处理方法。结果证明，该方法不需要任何初始对齐，就能得到准确的配准结果。将遗传算法与其他算法相结合的方法有利于减少遗传算法中的迭代次数，使计算时间更短。为了解决在ICP算法中需要一个较好的初始值来保证收敛性的问题，Ji等人（2017）提出了一个基于遗传算法和ICP算法的完整配准系统。该方法首先需要实现两个点集的中心对齐，这样可以忽略3个平移参数，只对3个旋转参数进行二进制编码，再利用遗传算法的全局搜索能力进行初始配准，为ICP算法提供一个精确且良好的迭代初始值。该方法具有较强的通用性，在点云配准和2维曲线配准都能取得较好的配准效果。受ICP算法的启发，并结合进化算法的特点，Zhang等人（2020）提出了两种算法来处理点云配准问题，一种是基于遗传算法；另一种是基于分布估计算法。这两种方法与其他方法不同之处在于，它们没有对旋转和平移参数进行编码，而是从源点云和参考点云中进行随机抽样来初始化种群，并设计独特的交叉和变异操作。该方法能获得比ICP算法更好的配准结果，并证明了遗传算法在点云配准中的有效性。由于该算法评估个体适应度值十分耗时，所以算法效率需要进一步提升。Yacout和Shoukry（2021）针对逆向工程中的点云配准，提出了一种新的混合配准技术。将点云配准描述为优化问题，先利用遗传算法进行粗配准，得到两个点云之间的近似转换，再将其结果用内点法执行精配准。实验结果证明，采用遗传算法与内点法相结合的混合方法具有较高的精度和可靠性。差分进化（differential evolution，DE）算法是由Storn和Price（1995）提出的一种启发式全局搜索算法。与其他进化算法最大的区别是任何一个个体的改进都能立即影响其他个体的产生，而不需要等待整个种群全部完成更新（Kachitvichyanukul，2012）。由于它具有易实现、收敛迅速、控制参数少等优点，已成功应用于点云配准。Tao等人（2016）将基于光线投射的对应点搜索与改进自适应差分进化（improved self-adaptive differential evolution，ISADE）算法相结合，提出了一种新的全局混合配准算法。该算法设计了新的自适应变异策略选择，从3个变异策略中随机选择一个进行变异操作，这样使得ISADE算法在提高收敛性的同时保证一定的种群多样性，避免陷入局部最小值，然后也对比例因子和交叉控制参数进行自适应调节，来提高差分进化算法的全局搜索能力。该方法能够在不使用精配准的情况下寻找到全局最优解，不仅具有较强的准确性，也加快了配准速度。Prieto等人（2017）将正态分布变换与差分进化算法进行结合，提出了一种新的点云配准算法。该算法首先根据NDT算法建立了一个基于概率分布的目标函数，然后通过使用差分进化算法对其进行变换参数估计，最后得到全局最优变换参数，使源点云与参考点云对齐。该算法避免了梯度和Hessian计算，所以比传统的基于牛顿优化算法的NDT算法更快，同时也能取得可靠配准效果。Zhang等人（2018）针对TrICP在解决部分重叠点云配准时严重依赖初始值的问题，提出了一种基于差分进化算法的部分重叠点云配准方法。该方法将旋转、平移和截断参数进行编码，利用TrICP中的损失函数作为适应度函数，设计了一个根据迭代次数和适应度值自适应调节相应参数的进化操作，能够使种群分布更加广泛，提高搜寻全局最优解的可能性。该方法能够在更小的迭代次数内收敛到更好的结果，并且对于部分重叠的点云配准具有较强的鲁棒性和高效性。Li和Dian（2018）针对ICP算法容易陷入局部最优解的问题，结合差分进化算法强大的全局搜索能力，提出了一种基于动态差分进化（dynamic differential evolution，DDE）算法的点云配准方法。该算法对旋转和平移参数进行编码，将均方根误差定义为目标函数，采用最优排序变异操作，能够产生更好目标函数值的变异个体，也可以提高算法的收敛速度。该方法能够有效处理初始位置不好的点云，且配准精度能够达到与ICP算法相同，是一种高效的粗配准算法。Liu等人（2021）提出了一种基于改进差分进化算法的粗配准和基于点到面ICP算法的精配准相结合的混合配准方法，利用差分进化算法的全局寻优能力进行初始对齐，为精配准提供了一个良好的迭代初始值。该算法为了进一步提高动态差分进化算法（Li和Dian，2018）的全局搜索能力和收敛速度，设计一种改进的变异算子，该自适应变异策略能够有效平衡全局勘探和局部开发，并且也确立了一个更鲁棒的适应度函数。该方法具有高效、精确、鲁棒性强等优点。Tao等人（2022）在改进自适应差分进化算法（Tao等，2016）的基础上，通过结合基于点的方法和ISADE算法，提出了PADE-ICP（point-based adap-tive differential evolution）来解决三维点云配准的问题。该方法首先利用基于点的方法，将搜索维度从传统的基于变换参数的六维减小到二维，然后通过ISADE算法对搜索空间进行寻优，获得初始配准结果后，再执行ICP算法获得最终配准结果。该方法在收敛速度和准确性方面取得了更好的效果。利用进化算法的全局搜索能力能够有效解决点云配准中的一些问题。在使用进化算法解决点云配准问题时，需要着重关注个体的编码形式、适应度函数的建立、交叉和变异算子的设计以及算法参数的设定。其中，最重要的是适应度函数的选择，因为这是将点云配准建模为优化问题的关键，一个合理的适应度函数才能保证良好的点云配准效果，它是推动种群质量改进的动力。目前已经提出的基于进化算法的点云配准方法对未来的研究有着重要的参考价值。虽然已经取得了良好效果，但如何提高方法的速度、准确性和鲁棒性仍然是目前面临的重要问题。表3总结了进化算法在点云配准中具有代表性的方法。10.11834/jig.220727.T003表3基于进化算法的点云配准方法Table 3Point cloud registration methods based on evolutionary algorithm模型方法改进优点HGA-PCR（Mansour等，2010）将遗传算法、拟牛顿算法和约束处理方法结合，提出一种用于点云配准的混合方法配准能力和时间不受点云初始位置的影响，且精确度更高GAReg-ISF（Hanke等，2014）将遗传算法作为经典粗配准和精配准之间的细化步骤来实现能够处理具有大量噪声、不完美几何特征和部分遮挡的点云配准问题ISADE（Tao等，2016）通过结合基于光线投射的对应点搜索和改进自适应差分进化算法，提出一种新的无需良好初始位姿的全局配准方法能够在不使用精配准的情况下收敛到全局极小值，并且具有良好的准确性和鲁棒性，同时也加快了配准速度DENDT（Prieto等，2017）根据NDT算法建立一个目标函数，利用差分进化算法进行变换参数估计能够取得比传统3D-NDT更可靠、更快的配准效果POPCR-DE（Zhang等，2018）提出一种基于DE算法的TrICP全局优化方法，其中设计了一个能够自适应调节的进化操作能够解决部分重叠的问题，且具有更强的鲁棒性和高效性PCR-GA（Zhang等，2020）使用遗传算法来处理点云配准问题，通过从源点云和参考点云中随机抽样来初始化种群，并设计了独特的交叉、变异操作能够获得比ICP更好的配准结果GA-IPM（Yacout和Shoukry，2021）采用遗传算法和内点法相结合的混合配准方法具有较高的配准精度和可靠性IAPCR-IDE（Liu等，2021）利用改进差分进化算法的全局搜索能力来实现点云配准的初始对齐时间消耗少、鲁棒性强和配准精度高PADE-ICP（Tao等，2022）结合基于点的方法和ISADE算法来解决三维点云配准问题与传统的六维搜索相比，该方法在收敛速度和鲁棒性方面都有所提高3.2　基于群体智能的点云配准方法群智能算法（Parpinelli和Lopes，2011）是受鸟类、蜜蜂等生物的群体生活行为启发而提出的一类优化算法。它通过模拟种群位置的移动来搜索可行解，利用个体之间相互协作的行为表现来传递有用的信息，能够达到快速收敛的效果。由于群智能算法具有结构简单且易实现、灵活和足够高效的优点，在点云配准中有着广泛的应用。通过总结前人研究工作，粒子群优化算法和蚁群优化算法已经在点云配准应用中起着重要作用。粒子群优化算法（particle swarm optimization，PSO）是一种通过模拟鸟类觅食行为来解决复杂优化问题的随机搜索算法（Kennedy和Eberhart，1995）。PSO算法稳定、高效、易实现且可调参数较少，已广泛应用于点云配准中。Yu和Wang（2014）为了解决ICP算法中由于点云初始位置差而导致陷入局部最优的问题，提出了PSO-ICP算法来实现自动点云配准。该算法结合了粒子群优化算法的全局搜索能力和ICP算法的快速收敛能力。其中，粒子群优化算法用于为ICP算法提供各种初始位置，然后利用ICP算法计算每个候选解的均方误差值，并将其作为PSO算法的适应度值来指导粒子的更新，最终得到准确的配准效果。该算法可以实现更精确的配准，但由于需要对每一代的每个粒子都执行ICP算法，所以该算法存在计算量较大的问题。Ge等人（2016）为了进一步提高PSO-ICP算法（Yu和Wang，2014）的高效性和准确性，并且为了克服离群点和错误匹配的局限性，提出了一种改进的PSO-ICP算法。该算法先通过分类对点云进行离群值检测和过滤，然后在基于PSO算法的粗配准中设计了一个同时受点对之间距离和法向量方向约束的适应度函数，最后由ICP算法对PSO提供的初始位置进行精配准。改进的PSO-ICP算法具有更强的鲁棒性和更快的速度。Zhan等人（2018）提出了一种基于信息熵和粒子群算法（entropy and particle swarm algorithm，EPSA）的点云配准方法。该方法首先通过建立K-D树找到K近邻的点，使用均值滤波去除噪声，然后计算两个点云的重心来求得平移矩阵，最后利用PSO算法对旋转矩阵进行编码，选择信息熵作为适应度函数来搜寻最佳旋转矩阵。该算法能够有效消除噪声，并且提高了配准精度。Zhan等人（2020）为了解决EPSA算法中随机性的问题，提出了一种基于法向量和粒子群算法的点云配准方法。该方法首先计算法向量和当前点到8个相邻点的重心之间的距离作为点云的两个特征，然后利用粒子群算法最小化两个特征的相似性来搜寻两个点云中的对应点，再通过RANSAC过滤错误的对应点对，最后通过四元数法求得变换矩阵。该算法处理点云配准是十分有效的，并且在点云数据丢失的情况下，也能得到较好的配准效果，但是存在效率低的问题。Wongkhuenkaew等人（2021a）为了同时解决旋转、平移、缩放和剪切变换问题，提出一种基于粒子群算法的三维仿射变换点云配准方法。其中，粒子群算法对旋转、平移、缩放和剪切的15个未知参数进行编码，通过最小化均方误差函数来对参数空间进行寻优，最终能达到较好的配准效果。此外，Wongkhuenkaew等人（2021b）提出了一种基于统计随机化粒子群算法（statistical randomization-based particle swarm optimization，SR-PSO）与ICP算法相结合的混合配准方法。SR-PSO算法是基于粒子群优化（Wongkhuenkaew等，2021a）的进一步改进，避免过早收敛的问题，并且能更好地平衡全局勘探和局部开发能力。该算法先利用SR-PSO算法找到合适的仿射变换参数来进行粗配准，其中，引入了额外的中间粒子，通过在每个维度上使用高斯分布随机化粒子的位置，以提高种群的多样性，最后使用ICP算法来进行精配准。通过以上研究可以看出，粒子群优化算法在处理点云配准的问题上展现出了强大的优势。但同时也存在着一些问题，它利用最优个体来引导粒子位置的改变，通常会出现过早收敛的问题，从而导致陷入局部最优。所以，在利用粒子群算法处理点云配准的问题时，需要设计合理的策略来增强粒子的多样性，以平衡全局勘探和局部开发的能力。同时，随着搜索过程的进行，搜索性能会越来越差，需要提出有效的自适应策略来提高算法的性能。因此，基于粒子群算法的点云配准方法还存在许多值得深入研究的问题。蚁群优化算法（ant colony optimization，ACO）是Dorigo等人（1996）提出来的一种启发式搜索算法，其灵感来自于某些蚂蚁的信息素轨迹铺设和跟踪行为（Dorigo等，1996）。ACO算法可以高效处理复杂优化问题，并且能够避免陷入局部最优。已经用于处理自然图像配准（Peng等，2006；Rezaei等，2009）和遥感图像配准（Wu等，2019），但在点云配准中的应用目前仍处于探索阶段。Khanna和Rajpal（2015）提出了一种基于蚁群算法的适用于带噪声的密集点云构造曲线的方法。该算法的主要思想是，先将点云减少到几个点，跟踪通过所有点的路径，以使移动距离最小，然后使用蚁群算法构建TSP（travelling salesman problem）路径，生成目标曲线。该算法适用于各种类型的曲线，包括简单曲线、闭合曲线、自相交曲线和曲线的多个分量。与其他的启发式算法相比，蚁群算法具有独特的正反馈机制，它在性能求解上有较高的鲁棒性，简单修改基础的蚁群算法模型就可以使用到各种组合优化问题中。除此之外，蚁群算法的全局搜索能力也较高，并且蚁群算法与其他启发式优化算法的结合十分容易，可以改善算法的性能。因此，将蚁群算法与别的启发式算法共同应用到点云配准任务中是一个值得深入的研究方向。除了以上提到的遗传算法、差分进化算法、粒子群算法和蚁群算法在点云配准中的应用以外，近些年人们还提出了一些其他的基于进化计算的点云配准方法。模拟退火算法（van Laarhoven和Aarts，1987）是一种基于概率的算法，受到固体退火原理的启发。固体从高温开始，以温度参数随机进行升温或降温，逐渐温度下降，直到达到热力学平衡为止。在多次迭代情况下，可以收敛到最优解。Liu等人（2019）提出了一种基于模拟退火的改进ICP方法，可以在点云精配准中避免陷入局部收敛，即使在恶劣的条件下，也能找到模型之间最优的变换参数。人工蜂群算法（Karaboga等，2014）是受蜜蜂采蜜行为启发提出的一种优化算法。蜂群中包含3种类型的蜜蜂，即引领蜂、侦查蜂和跟随蜂，它们根据自己不同的身份会进行不同的活动，并且通过蜂群中个体之间分享相关信息来找到更好的食物源。该算法有着较快的收敛速度。在点云配准应用中，Bhuvaneshwari和Rajeswari（2018）为了能在较短的时间内提高配准精度，提出了一种基于人工蜂群的ICP算法。该算法提高了ICP算法的稳定性和准确性，并且与几种ICP变体算法相比，在精度和计算速度上都有着出色的表现。灰狼优化器算法（Mirjalili等，2014）是群智能算法之一，它通过模拟灰狼的狩猎行为，包括追踪、包围和攻击猎物来获取食物。该算法由于具有更好的收敛性和全局搜索能力，已应用于处理点云配准问题。Feng等人（2020）提出一种基于灰狼优化器的点云配准算法（point cloud registration algorithm based on the grey wolf optimizer，PCR-GW），以解决点云配准中算法速度慢和配准精度低的问题。除此之外，人们提出了许多新颖的优化算法。例如，人工免疫系统算法（Delibasis等，2011）、人工鱼群算法（赵海峰 等，2011）、萤火虫算法（Du等，2013）和菌群算法（Bermejo等，2015）等，它们已用于处理图像配准问题，证明了其具有的优势，但在点云配准中还未发现有相关应用。或许可以从中借鉴一些想法，为解决点云配准问题提供新的思路，这也是值得探索的研究方向。表4总结了一些群智能算法在点云配准中具有代表性的方法。10.11834/jig.220727.T004表4基于群体智能的点云配准方法Table 4Point cloud registration methods based on swarm intelligence模型方法改进优点PSO-ICP（Yu和Wang，2014）将PSO算法用于为ICP算法提供各种初始位置避免由于点云初始位置不好而导致的局部最优，同时具有更强的鲁棒性和自适应性EPSO-ICP（Ge等，2016）使用增强粒子群算法进行粗配准。其中，提出一种受点对距离和法向量方向约束的适应度函数能够有效避免局部最优解，与PSO-ICP相比，该方法可以实现更高效、更准确的配准结果EPSA（Zhang等，2018）选择信息熵作为适应度函数，利用PSO算法搜索最佳旋转参数能够有效地消除噪声和提高刚性配准的精度NVP（Zhang等，2020）利用粒子群算法最小化两个特征的相似性来搜索两个点云中的对应点即使在点云数据丢失的情况下，也具有较高的配准精度TDPCR-PSO（Wongkhuenkaew等，2021b）利用PSO算法来处理点云配准中的三维仿射变换问题能够同时解决旋转、平移、缩放和剪切变换问题SR-PSO（Wongkhuenkaew等，2021a）为避免过早收敛，设计了基于统计随机化的粒子群算法来寻找最佳仿射变换参数提高了种群的多样性，并且能够取得比TDPCR-PSO算法更好的配准结果3.3　小结通过以上分析，基于进化计算的方法已经证明了它们在处理点云配准问题上的独特优势。通常利用进化算法和群智能算法与其他算法相结合来进行点云配准，并且为了得到高效的变换参数搜索算法，需要设计有效策略来平衡全局勘探和局部开发。同时，也还要考虑配准的速度、精度和鲁棒性等问题。总之，需要根据点云配准的特殊性，对基于进化计算的方法进行改进，提出更适用于点云配准任务的算法。另外，将计算智能中的模糊逻辑方法应用于点云配准问题上时也有着较为突出的效果。4　点云配准中的模糊逻辑方法4.1　模糊逻辑概述模糊逻辑（Zadeh，2008）可以容忍不够精确的数据，对任意复杂度的非线性函数建模，便捷地将输入空间映射到输出空间。模糊逻辑主要包含模糊化、模糊规则、模糊推理和去模糊化4个部分。模糊逻辑的中心思想就是精确化，即将一个对象x转换为一个对象p*的操作。除此之外，模糊逻辑的一个关键概念是广义约束，主要的约束条件是可能性、概率性和真实性。模糊逻辑可以用来模糊逻辑泛化，即将任何基于二阶逻辑的理论通过添加从模糊逻辑中提取的概念和技术而得到模糊逻辑的推广。例如模糊控制、模糊线性规划、模糊概率论和模糊拓扑等。通过整理大量的相关文献，发现目前模糊逻辑已经很好地应用于图像配准。例如，Hata等人（1999）以及Berks等人（2001）使用模糊集来确定变换。Lelieveldt等人（1999）使用模糊集来选择和预处理要配准的特征。Tarel和Boujemaa（1999）提出了一种利用模糊聚类解决三维配准问题的方法。Ramirez等人（2006）将图像配准过程分为两个阶段。第1阶段用于获得旋转的精确估计和平移的粗略估计。第2阶段用于提高平移估计的精度。在每个阶段，使用模糊逻辑控制器调整配准参数，以获得准确的变换估计。除了应用到图像配准中，模糊逻辑的特性也十分适合应用到点云配准及其预处理过程中。表5总结了一些基于模糊逻辑的点云配准方法。10.11834/jig.220727.T005表5基于模糊逻辑的点云配准方法Table 5Point cloud registration methods based on fuzzy logic模型方法改进优点RFCR（Tarel等，1999）使用模糊聚类算法对点云数据进行粗配准具有良好鲁棒性，可以同时配准多个数据FFS（Lelieveldt等，1999)提出一种基于模糊集的半自动方法。使用模糊集求解刚性变换的变换矩阵提高了局部配准过程的配准质量ITNFL（Zadeh等，2008）总结了模糊逻辑在模糊逻辑泛化、模糊规则、精确化以及文字计算方面的应用总结了模糊逻辑的使用方向FLBDM（Budak等，2011）提出了一种将模糊逻辑应用提高点云数据缩减时质量的方法提高了最大偏差的缩减率，平均偏差得到改善，结果质量更高FLACO（Kavita等，2015）提出了一种使用模糊聚类将点云数据生成曲线的方法。用模糊c均值法求出隶属度矩阵和聚类中心矩阵。再用聚类中心数据生成曲线可处理含噪声无组织的密集点云，且性能良好FMBMP（Liao等，2021）设计了一种通过最小化模糊聚类中心之间距离的模糊加权和的点云配准方法对噪声具有鲁棒性，解决异常值问题，且在没有地面真值的情况下给出配准质量评估的方法FCBMEGO（Farhood等，2020）提出了一种使用模糊逻辑和特征匹配对深度图通过比较相邻像素强度进行多模态边缘检测的算法对噪声有很好的抑制效果，可将真实图像转换为精度更高的三维点云数据4.2　缩减点云数量方法在点云配准过程中，由于大量的点云数据会导致工作量大、算法效率不高的问题，许多研究者在减少点云数据的方法上做了许多工作。Budak等人（2011）提出了一种基于模糊逻辑的决策方法，可以在点云数据缩减时大幅提高质量。该算法首先将输入空间划分为多个模糊集，利用模糊变量和所属的模糊子集及其隶属函数，定义了模糊控制的9条规则，并用规则将模糊集分配到输出空间中。与不使用模糊方法相比，该算法在复杂的情况下简化效果十分明显，使平均简化误差显著降低，为通过采样以减少点云数据开发了一个新的方法，并且提供了更加用户友好和直观的应用。Farhood等人（2020）提出了一种利用模糊逻辑和特征匹配对深度图进行多模态边缘检测的算法，主要通过模糊逻辑比较相邻像素的强度来检测边缘，首先将深度图的梯度作为输入，定义一个高斯隶属函数以建立模糊系统，最终输出输入数据是否为边缘的隶属度。该算法的主要优点是更可靠地抑制噪声，将真实图像转换为精度更高的三维点云数据。与其他算法相比，模糊逻辑在输入集变换上有更高的精准度，可以提高点云配准初始数据的质量。除此之外，模糊逻辑方便与其他算法相结合，以提高算法的性能。因此，将模糊逻辑与其他算法相结合应用于提高缩减点云数量后数据的质量是一个非常好的思路。4.3　基于模糊聚类的点云配准模糊聚类是一种模糊集理论与聚类分析相结合的方法。模糊聚类包含3个步骤：1）将输入数据标准化，转换为模糊矩阵；2）建立模糊相似矩阵；3）依靠模糊矩阵对所研究对象分类。相较于传统聚类方法，模糊聚类可以将一个数据根据其隶属度分配给所有的聚类，提高了聚类的分类效果。Liao等人（2021）提出一种使用模糊聚类对齐三维扫描点云的配准方法，并且在刚性点云配准中，给出了没有真值情况下的配准质量评估方法。该算法中每一个扫描由模糊聚类表示，通过最小化模糊聚类中心之间距离的模糊加权和进行点云配准。同时，在给定旋转矩阵和平移向量的情况下，为求得基于模糊聚类的度量的上界和下界，提出一种从粗到细高效执行的基于分支定界的优化方案，可以在不考虑初始化情况下全局最小化度量。首先使用模糊聚类来描述给定的扫描，然后将基于分支定界算法和基于梯度算法结合起来进行全局搜索，实现两次粗略对准。在全局搜索过程中，使用配准质量评估作为停止标准，然后将扫描中较多的点作为模糊聚类中心，利用基于梯度的局部收敛方法将粗配准转换为细配准。与已存在的算法相比，该优化方案通过基于模糊聚类的度量和配准质量评估，在鲁棒性和效率方面有了很大提高。Khanna和Rajpal（2015）使用了模糊逻辑、模糊聚类与蚁群算法，提出了一种含噪声的无组织密集点云中重建曲线的方法。该算法可以处理自相交并识别曲线中的多个分量以及处理丢失的输入数据，并且可以在多项式时间内运行。与以前的算法相比，该算法的优点主要是可以处理密集的点云数据，在重建曲线与原始曲线相似的情况下，具有良好的性能。4.4　小结目前，模糊逻辑由于其优异的鲁棒性应用于点云配准任务，主要是结合神经网络与遗传算法共同使用。相较于传统的计算，使用模糊逻辑的软计算可以适应现实的不精确性，利用不精确性以实现可处理性、鲁棒性和较低的解决方案成本。在未来，模糊逻辑会在点云配准中与其他算法结合并扮演越来越重要的角色。5　数据集和评价指标5.1　常用数据集在研究工作中，使用优秀的数据集可以更好地评价方法的优劣。本节介绍三维点云配准领域中的常用数据集。从总体上说，这些数据集可以分为合成数据集和真实场景数据集两大类。合成数据集主要是由人工建立的各种事物的三维模型，而真实场景数据集则由专业的设备，如用激光雷达、结构光传感器和立体相机等采集而来。点云配准领域中的常用数据集如下：1）ModelNet数据集。是普林斯顿视觉与机器人实验室2015年发布的合成数据集，包含662 个分类，127 915 个CAD（computer aided design） 模型以及10类标记过方向的数据。相关工作人员从数据中选择常见的40类和10类组成子集，分别表示为ModelNet40和ModelNet10两个数据集。数据集获取地址为http：//modelnet.cs.princeton.edu。2）3Dmatch数据集。是真实场景数据集，收集了来自于62个场景的数据，其中54个场景的数据用于训练，8个场景的数据用于评估，包含7-Scenes（Shotton等，2013）和SUN3D（Xiao等，2013）等子集。数据集获取地址为http：//3dmatch.cs. princeton.edu。3）Stanford 3D Scanning Repository数据集。由美国斯坦福大学发布，包含由Cyberware三维扫描仪采集得到的多个兔子、龙和马等各类雕像的斯坦福模型（Stanford model）。所有模型都经过改进后的ICP算法对齐，平移和旋转的参数保存在数据集中。数据集的获取地址为http：//graphics.stanford.edu/ data/3Dscanrep/。5.2　评价指标在研究工作中，提出的方法性能好坏需要用合适的评价指标进行衡量。本节介绍在点云配准问题上的一些常用指标。均方根误差（root mean squard error，RMSE）、平均绝对误差（mean absolute error，MAE）和均方误差（mean squared error，MSE）度量源点云经过估计的运动参数变换后与真实点对应关系的误差。具体计算为RMSE=1Mi,j∑p,q∈Mi,jRp+t-q2 （1）MAE=1Mi,j∑p,q∈Mi,jRp+t-q （2）MSE=1Mi,j∑p,q∈Mi,jRp+t-q2 （3）式中，源点云的点p对应目标点云的点q，Mi,j表示所有对应关系的集合，R表示估计的旋转参数，t表示估计的平移参数。配准召回率（registration recall，RR）度量在实验数据集中配准误差小于误差阈值的点云对数量占数据集所有点云对数量的比例。具体计算为ERR=1N∑i=1N1RMSEτ1 （4）式中，N为实验数据集点云对集合，τ1表示RMSE误差阈值。1［ ］表示Iverson括号，当括号内的值为真时取1，否则取0。平均相对平移误差（mean relative translation error，MRTE）和平均相对角度误差（mean relative angular error，MRAE）度量运动参数估计值与真值的差值。具体计算为MRTE=meantpre-tgt2 （5）MRAE=meancos-1trRpre-1Rgt-12 （6）式中，Rpre为预测的旋转参数，Rgt为旋转参数真值，tpre为预测的平移参数，tgt为平移参数真值。内点比例（inlier ratio，IR）度量一个点云对的有效对应关系比例，特征匹配召回率（feature match recall，FMR）度量实验数据集中成功配准点云对的比例。具体计算为EIR=1Mi,j∑p,q∈Mi,j1Rgtp+tgt-qτ2 （7）EFMR=1N∑i=1N1EIRiτ3 （8）式中，τ2为距离阈值，EIRi表示第i个点云对的内点比例，τ3为内点比例阈值。6　结语点云配准在计算机视觉应用中具有重大意义，一个较好的配准结果是许多相关应用的基础要求，并会对后续技术造成较大的影响。点云配准技术已经经过了几十年的发展，在某些方面有了重大的进展，但是点云配准作为一个开放的问题，仍然有许多问题和内容值得进一步解决和研究。通过总结分析当前的研究，人们提出了许多基于进化计算和一些新的网络模型改进方法，并且取得了巨大成就，证明了它们在处理点云配准任务中有着强大的优势。与传统点云配准方法相比，它们能够得到更加高效和精确的配准结果。在今后的研究中，需要根据点云配准的特殊性，从网络模型的结构上进一步提升，也可以利用进化计算的全局搜索能力，构造鲁棒的目标函数，设计出合理有效的信息交流策略和自适应策略，来求解最佳变换参数。除此之外，也能够将深度学习和进化计算方法进行混合，同时利用它们的优势，提出更加精确的配准方法。模糊逻辑具有适应不确定性的特点，并且它能够通过与深度学习和进化算法相结合，更高效地处理点云配准问题。结合目前的研究进展，以下将重点讨论点云配准仍然面临的困难和未来的研究方向。6.1　挑战和展望深度学习、进化计算和模糊逻辑都具有一些独特的优点，以往研究表明，它们可以很好地与点云配准任务相结合，并且取得了较好的配准效果。但是如何更好地发挥深度学习、进化计算以及模糊逻辑的优势，提高点云配准的速度与精度仍是重点问题。以下几个方向可能将是有用的探索：1）实际点云数据的获取通常会受环境的影响，得到的点云数据会包含大量的噪声和离群值。也会由于视角的限制而得到低重叠的点云数据。目前，虽然已经有研究者针对这两个问题分别提出了相应方法，但是为了提高算法的普遍适用性，通常需要同时考虑噪声、离群值和低重叠的影响，合理设计有效策略来解决此类问题。2）在许多实际应用场景中，通常会包含海量的点云数据。研究者通常为了减小计算开销而采用降采样来对点云进行预处理，但是降采样可能会造成局部几何信息的丢失，从而对局部几何特征的提取造成一定的影响。利用关键点检测技术能够在不丢失局部几何特征的情况下有效处理此类问题。因此，如何基于深度学习、进化计算以及模糊逻辑的思想来设计高效、准确的关键点检测方法仍然是需要进一步解决的问题。3）由于点云数据的获取方式多样，存在需要将来自不同类型点云进行配准的情况，称为多源点云配准。由于它们之间的点云分布和点云数量都存在巨大差异，所以直接使用传统的点云配准方法来解决多源点云配准问题，会使配准精度低，甚至会导致配准失败。目前，对于解决多源配准问题仍处于探索阶段。因此，如何利用基于进化计算的方法解决多源点云配准的问题仍然是一个待解决的难题。4）在利用基于进化计算的点云配准方法中，由于需要通过迭代搜索来寻找最优变换参数，通常都会存在计算时间较长的问题，从而造成算法缺乏实时性，所以需要对算法进行合理改进，以达到在较短迭代次数内能够寻找到全局最优，也可以将其与并行计算技术进行结合，利用并行计算强大的计算能力来帮助提高算法的速度，实现点云实时配准。5）点云配准分为刚性点云配准和非刚性点云配准。刚性配准只包括旋转、平移，而非刚性配准还包括缩放、仿射等一系列比较复杂的变换，刚性配准比非刚性配准包含的变换参数更少。因此，目前的大量的研究工作都只是关注刚性配准问题，而忽略了非刚性配准问题的研究。但在实际应用中，非刚性配准普遍存在并且非常重要，是一个亟需解决的难题。如何利用深度学习和进化计算的优势，提出合理高效的方法来处理非刚性点云配准的问题是值得研究的方向。6.2　总结点云配准在各种点云处理应用中发挥了重要作用，吸引了大量关注，以往的研究在该领域取得了重大成就。本文对现有点云配准算法进行全面的讨论，综述了深度学习、进化计算以及模糊逻辑在点云配准中的应用， 并根据不同的算法进行详尽地分类总结， 结合不同的算法流程和点云配准的基本流程分别对深度学习、进化计算以及模糊逻辑在配准任务中所起到的作用和创新性进行阐述。最后，本文进一步介绍了点云配准现存方法所面临的挑战以及未来的研究方向， 包括存在大量噪声离群值和低重叠率的点云配准以及大型场景点云配准、多源点云配准、点云实时配准以及非刚性配准等热门研究方向。随着未来深度学习、进化计算以及模糊逻辑的发展， 一定会提出速度更快、精度更高且鲁棒性更强的点云配准方法， 能够为点云配准技术贡献更多新的想法。