点云配准是计算机视觉和机器人技术中的一项基本任务，被广泛应用于三维建模、室内测绘、自动驾驶和同时定位与制图(simultaneous localization and mapping，SLAM)^[1-2]。迭代最近点(iterative closest point，ICP)是应用最为广泛的点云配准方法^[3]，但该方法对初始变换参数较为敏感^[4]。因此，相关学者提出了基于特征的点云配准方法，如文献[5—6]利用模式识别方法建立对应点统一点云坐标系。

为实现稳健配准，文献[7—8]设计了健壮的点云特征描述符。具有强描述性的描述符增强了非对应点间的识别能力，同时保证了正确对应点具有较大的相似性。点云特征描述符可分为基于人为设计和基于深度学习二类。基于人为设计的方法有旋转图像(spinImage)^[9]、快速点特征直方图(FPFH)^[6]和方向直方图描述(SHOT)^[10]，该类描述符由点云局部几何形状决定，对噪声较为敏感^[11]。受深度学习启发，基于深度神经网络的特征描述符被提出，如FCGF^[7]和PPFNet^[8]。

获取特征描述符后，利用特征匹配方法建立对应点。匹配策略可分为一元匹配策略和高阶匹配策略，基于一元的匹配方法有比率检验^[12]、距离度量^[13]和互反检验^[14]。一元匹配策略将每个特征描述符视为独立单元，易受噪声和对称结构干扰。高阶匹配策略保证了几何结构对齐，快速全局配准(fast global registration，FGR)^[15]和deep hough voting^[16]方法通过构造三联体验证对应点稳健性，但三联体仅适用于验证三点间的结构相似性，泛化性较差。在图像领域，基于图模型的对应点估计方法也得到了充分的发展，如谱匹配^[17]、重加权随机游走匹配(reweight random walks matching，RRWM)^[18]和最大池化匹配(max-pooling matching，MPM)^[19]等，虽然上述图匹配方法能较好地完成图像特征匹配，但在点云特征匹配中的性能并不理想。

点云特征匹配面临噪声、部分重叠和重复结构等诸多问题，匹配结果中不可避免地包含了大量错误匹配^[20]。随机抽样一致(random sample consensus，RANSAC)方法被广泛用于剔除点云配准中的错误匹配^[21]，但在离群值比率较高情况下，RANSAC方法配准结果不理想。3DRegNet^[22]、PointDSC^[23]和DGR^[24]方法利用稀疏卷积和多层感知机构建误匹配剔除方法实现点云配准。上述配准方法强调了离群值滤波的重要性，配准精度受初始匹配结果限制。

图模型不受点云位移和旋转的影响，较好地描述了三维点间的几何结构。针对传统特征匹配策略易受噪声和对称结构等不利因素影响的问题，本文利用图模型的几何信息作为对应点提取的约束条件，优化同平台点云初始匹配结果。图匹配可作为特征匹配方法，适用于多种基于特征的同平台点云配准技术。为充分利用点云几何信息优化配准精度，本文提出一种基于空间一致性的同平台点云配准方法(spatial consistency-based registration, SCR)。基于图模型构建具有高阶相似度的特征匹配模型，提出附加冲突行走预防的重加权随机游走匹配算法获取匹配结果，并利用假设检验方法估计点云位姿参数。与FGR和deep hough voting的三元组检验相比，SCR可推广到n元组检验，具有更为广泛的应用价值。

1 基于空间一致性的点云配准方法构建

SCR主要包括候选匹配选取、图匹配求解、离群值剔除和变换参数估计4个步骤，如图 1所示。

1.1 候选匹配选取

基于特征的点云配准方法通常将特征空间邻近点作为初始对应点^[15]，但点云受噪声和重复结构影响，正确对应点在特征空间中的距离可能并非最小值。因此，SCR扩大了关键点候选匹配数量，并利用空间一致性约束估计最优对应点。

为降低特征匹配计算复杂度，首先利用内部形态描述子(intrinsic shape signatures，ISS)^[25]提取点云关键点，并利用FPFH方法获取关键点的特征描述符，文献[26]已证明了ISS和FPFH方法的有效性。SCR保留了关键点的多个假设候选匹配，若两点在特征空间中的距离小于设定的距离阈值，则将其作为一对候选匹配。设y_k=C(x_i)表示y_k和x_i为对应点，如图 2所示，y_a=C(x₁)，y_c≠C(x₁)。

1.2 空间一致性匹配模型

为从多个假设候选匹配中估计关键点的最优匹配，本文提出了基于图模型的空间一致性匹配方法。给定待配准点云关键点X={x_i|x_i∈R³}_i=1^N和目标点云关键点Y={y_k|y_k∈R³}_k=1^M，令Ω为X和Y的对应点集合，Ω={(x_j, y_j)}_j=1^K，两组点云由相同平台采集。若Ω中对应点均满足(x_i, x_j)两点间的欧氏距离等于(y_i, y_j)两点间的欧氏距离，则称Ω具有空间一致性；若长度不相等，Ω至少存在一对错误匹配，如图 3所示。

设C为邻接矩阵，若x_i和y_k为一组对应点，C_{i, k}等于1，否则为0，由定义可知C中元素为0或1。令a_{i, j}为x_i和x_j间的欧氏距离，a_{k, l}为y_k和y_l间的欧氏距离，空间一致性匹配方法目标方程f(C)由长度相似性s_e(a_{i, j}, a_{k, l})和点相似性s_p(x_i, y_k)组成，求解空间一致性匹配结果可表示为最大化f(C)

式中，。

为求解式(1)，将其转化为X和Y的图匹配问题。利用X和Y构建无向图G¹=(V¹, E¹, A¹)和G²=(V², E², A²)，其中，V为图中节点，即三维离散点，E为节点连接边，A为图元素属性。a_i¹∈A¹为节点x_i的特征描述符，a_{i, j}¹∈A¹表示节点x_i和x_j间欧氏距离。图匹配方法通过构建G¹和G²的联合图G^s=(V^s, E^s, A^s)，将G¹和G²匹配问题转化为G^s的节点排序问题。令W为G^s的亲和矩阵，节点v_1a∈V^s由节点x₁和y_a构成。亲和矩阵元素W_{ik: jl}定义为

式中，s_p(a_i¹, a_k²)=1/||a_i¹-a_k²||；se(a_ij¹, a_kl²)=max(D-|a_ij¹, a_kl²|, 0)；a_{i, j}¹=||x_i-x_j||₂；a_{k, l}²=||y_k-y_l||₂。令c∈{0, 1}^NM为C的列矢量化向量，将式(1)问题转化为基于重加权随机游走匹配的优化方法求解

1.3 图匹配

由于RRWM保留了该匹配问题中不兼容图节点间的连接，导致匹配结果不理想，因此本文提出了基于附加冲突行走预防的重加权随机游走匹配算法，简称为随机游走匹配。随机游走匹配通过保留G^s重要连接关系，剔除不兼容节点的连接边，构建更为紧凑的图模型，连接简化结果如图 4所示。连接简化模型被验证可有效优化图模型，提高方法精度和稳健性^[27]。

设y_a=C(x_i)，y_b≠C(x_j)，随机游走匹配算法保留了v_ia节点的连接，剔除了v_jb节点的连接关系。通过将亲和矩阵W冲突元素的值设为0，实现G^s的连接简化。令为连接简化亲和矩阵，为矩阵无限范数。随机游走匹配幂迭代过程为

式中，为MN×MN的双随机矩阵，1表示元素全为1的列向量，c_abs为吸收节点，对c进行标准化

为避免随机游走匹配结果出现局部性，游走模型以α的概率移动到下一个节点，或以1-α的概率跳跃到图中任一节点，随机游走匹配最终可表示为

式中，重权函数f_c(·)包含了参数膨胀和双随机归一化^[18]。若c⁽ⁿ⁺¹⁾=c⁽ⁿ⁾=c，幂迭代过程停止。设∈{0, 1}^NM为c的离散化结果，c离散化可表示为

式中，，若顶点x_i和y_k为一组对应点，等于1，否则为0。匈牙利算法常用于离散化图匹配结果^{[18, 28]}，因此利用该算法求解式(7)获取匹配结果，且满足。

1.4 离群值剔除和变换参数估计

为统一点云坐标系，基于假设验证方法构建点云配准模型。首先，利用PointDSC离群值滤波模块剔除匹配结果中的错误匹配，并获取对应点的内点概率e。令R为旋转矩阵，t为平移矩阵，变换参数求解模型为

式中，x_i和y_i为点云三维坐标。通过奇异值分解方法获取式(8)闭环解^[29]，以此产生一组R，t用于假设验证。设定阈值τ，选择最佳变换参数

式中，符号内的结果满足判断要求便返回1，此外为0。值得注意的是，PointDSC和RANSAC等配准方法强调了误匹配剔除方法的重要性，而SCR在初始匹配阶段利用空间一致性方法优化匹配结果，强调特征匹配的重要性，因此两者可较好结合。SCR对应点提取结果如图 5所示，图中绿线表示正确对应点，红线为错误对应点。

2 试验结果与分析 2.1 测试数据

本文分别利用3DMatch^[30]数据集和WHU-TLS^[11]数据集进行配准试验，3DMatch数据集中包含了8个不同室内场景的点云数据，WHU-TLS数据集包含了由激光扫描仪获取的10个不同场景的点云数据，两个数据集都提供了变换参数真值。试验对点云进行降采样，精度验证只统计重叠度大于30%数据的配准结果。

2.2 评价指标

本文利用特征匹配召回率(feature matching recall, FMR)、配准误差(registration error, E_RMSE)、旋转误差(rotation error, RE)和平移误差(translation error, TE) 4个指标对配准结果进行质量评价。特征匹配召回率定义为

式中，Ω_s为对应点集合，|Ω_s|表示Ω_s中包含的元素数量；x和y为点云三维坐标；T^*为真实变换矩阵；τ₁和τ₂为设定阈值。式中符号内的结果满足判断要求便返回1，此外为0。特征匹配召回率越高，说明算法匹配结果越好。当获得变换参数后，旋转误差和平移误差定义为

式中，R^*和t^*分别为旋转矩阵和平移向量真值。配准误差定义为

式中，Ω^*为两点云对应点真值，|Ω^*|表示Ω^*中包含的对应点数量；x^*和y^*为正确对应点三维坐标。若两点云的RE和TE同时小于0.3，则视为配准成功，令召回率(Recall)为配准成功的数量在总数据量中的比重。

2.3 图匹配试验

为研究所提出的图匹配方法在同平台点云配准中的性能，本文利用RRWM、MPM图匹配方法进行对比试验。为消除特征描述和关键点探测算法对试验结果的影响，采用相同算法提取点云的关键点和特征描述符，并将离群滤波和变换参数估计作为通用步骤。试验结果显示，采用本文图匹配方法可将FMR提高至26.5，配准精度有明显提升，图匹配方法点云配准性能比较，见表 1。

比较未引入图匹配方法和RRWM、MPM方法结果发现，RRWM和MPM方法不会提高点云配准精度，并出现负面影响。与未引入图匹配的配准方法相比，引入本文图匹配方法的配准结果具有更高的特征匹配召回率、更优的配准精度。虽然MPM方法和本文图匹配方法的特征匹配召回率接近，但配准误差相差较大，且对比未引入图匹配方法和MPM方法可知，特征匹配召回率更高并不等同配准精度更高，本文图匹配方法获取的对应点更准确。

为进一步证明本文图匹配方法的适用性，试验展示了图匹配方法结合RANSAC、FGR和3DRegNet方法的配准结果。RANSAC、FGR和3DRegNet方法均利用特征描述符获取点云的初始对应点，因此试验将本文图匹配方法作为RANSAC、FGR和3DRegNet方法的特征匹配模块进行配准试验，配准结果见表 2。

表 2前3行分别为RANSAC、FGR和3DRegNet原始方法的配准结果，后3行为图匹配结合3种方法的配准结果。虽然FGR原始方法与结合方法的平移误差相等，但由表 2可知，相较于原方法，结合图匹配的配准方法均具有更优的配准结果。综上所述，图匹配可作为特征匹配方法广泛地应用于基于特征的同平台点云配准，具有较好的适用性；图匹配方法通过利用几何结构约束对应点提取，提高同平台点云配准精度。

2.4 室内场景配准试验

为验证SCR方法的有效性，配准试验展示了3种经典配准方法(ICP、FGR和RANSAC)和3种深度学习配准方法(PointDSC、DGR和3DRegNet)的配准结果。经典配准方法由Open3D库^[31]提供，深度学习配准方法采用3DMatch数据集的训练权值进行配准，配准结果见表 3。

由表 3可知，SCR平移误差略高于PointDSC方法，但旋转误差和配准误差显著优于PointDSC方法，且不难看出，SCR配准精度较其余算法有较大提升。3DRegNet相较其原文性能有较大程度的下降，是因为FPFH描述符初始匹配中离群值比率较高，部分配准方法Recall指标如图 6所示。

为进一步验证SCR方法的有效性，表 4展示了RANSAC、PointDSC和SCR方法在不同重叠度下的配准结果。

由表 4可知，重叠度为40%和50%时，SCR评价指标均优于RANSAC和PointDSC方法。究其原因，RANSAC和PointDSC方法通常将特征空间邻近点作为初始对应点，导致配准精度较低。SCR通过空间一致性约束在多个假设匹配中选取了具有一致性的对应点，有效地提高了同平台点云配准的精度和稳健性。如图 7所示，SCR方法在所示两个场景中获得更好的配准结果。

1范数和2范数作为一元相似度匹配方法被广泛使用^[13]。分别在该数据集中8个场景中定量比较基于1范数度量、基于2范数度量和空间一致性匹配方法的特征匹配结果，结果见表 5。

由表 5可知，空间一致性匹配方法在多类型场景下具有较高的特征匹配召回率。且与三元组检验相比，该方法可检测n个点间结构的相似性，具有更为广泛的应用价值。

2.5 室外场景配准试验

利用WHU-TLS数据集验证本文方法在室外场景下的有效性，分别选取该数据集3个场景(park，campus和riverbank)中的一对点云进行配准试验，选取的3对点云重叠度分别为74.4%、69.7%和49.6%。SCR将对应点的内点概率e均设置为1，试验展示了RANSAC、FGR和SCR的配准精度，结果见表 6。

由表 6可知，在3个场景的配准试验中，SCR都显著优于RANSAC和FGR，其旋转误差和平移误差均低于RANSAC和FGR的旋转误差和平移误差，3个场景的配准结果如图 8所示。利用本文方法构建关键点图模型不受配准场景大小限制，可通过获取室外扫描数据的空间一致性对应点提高点云配准精度，因此，SCR适用于配准大规模地面激光扫描点云。

3 结论

为充分利用同平台点云几何信息提高配准精度，本文提出了基于空间一致性的同平台点云配准方法。通过优化现有图匹配方法，本文提出了附加冲突行走预防的重加权随机游走匹配算法；SCR利用图匹配方法在多个候选匹配中选取了具有一致性的对应点，并基于假设验证方法统一点云坐标系。利用3DMatch数据集和WHU-TLS数据集对本文方法进行验证，综合试验结果表明，本文方法对于配准同平台点云有较好的适用性，通过利用空间一致性约束优化了对应点提取结果，提高了点云配准精度。后续工作将提取点云中的高级语义信息构建点云图模型，进一步提高图匹配在点云配准中的稳健性和精度。