闫利：融合遗传算法和ICP的地面与车载激光点云配准

融合遗传算法和ICP的地面与车载激光点云配准

闫利 , 谭骏祥 , 刘华 , 陈长军     

武汉大学测绘学院, 湖北 武汉 430079

基金项目：国家重点研发计划（2016YFC0802500）

之一作者简介：闫利(1966-), 男, 教授, 博士生导师, 研究方向为摄影测量、遥感和三维激光扫描技术。E-mail:lyan@sgg.whu.edu.cn

微信号：MeetyXiao
添加微信好友, 获取更多信息
复制微信号

通信作者：谭骏祥, E-mail: lyan@sgg.whu.edu.cn

摘要：车载激光扫描可快速获取大场景点云，由于存在视场限制和遮挡，需地面激光点云作补充。车载与地面点云分别位于大地坐标和局部坐标系统，本文提出结合遗传算法（genetic algorithm，GA）和（iterative closed point，ICP）的自动点云配准 *** 以统一基准。ICP采用局部优化，效率较高，但依赖初始解；GA为全局优化 *** ，但效率低。融合策略为当GA配准趋于局部搜索时，采用ICP完成配准。GA配准以地面激光扫描仪内置GPS测量粗略位置限定优化搜索空间。为提高GA配准精度，提出了更大化归一化匹配分数之和（normalized sum of matching scores，N *** S）配准模型。实测数据试验验证了N *** S模型的有效性，GA配准均方根误差（root mean square error，RMSE）为1~5 cm；融合配准比GA配准效率高约50%。

关键词：车载激光扫描    地面激光扫描    点云配准    遗传算法    ICP    

Registration of TLS and MLS Point Cloud Combining Genetic Algorithm with ICP

YAN Li , TAN Junxiang , LIU Hua , CHEN Changjun     

Abstract: Large scene point cloud can be quickly acquired by mobile laser scanning (MLS) technology, which needs to be supplemented by terrestrial laser scanning (TLS) point cloud because of limited field of view and occlusion.MLS and TLS point cloud are located in geodetic coordinate system and local coordinate system respectively.This paper proposes an automatic registration method combined genetic algorithm (GA) and iterative closed point ICP to achieve a uniform coordinate reference frame.The local optimizer is utilized in ICP.The efficiency of ICP is higher than that of GA registration, but it depends on a initial solution.GA is a global optimizer, but it's inefficient.The combining strategy is that ICP is enabled to complete the registration when the GA tends to local search.The rough position measured by a built-in GPS of a terrestrial laser scanner is used in the GA registration to limit its optimizing search space.To improve the GA registration accuracy, a maximum registration model called normalized sum of matching scores (N *** S) is presented.The results for measured data show that the N *** S model is effective, the root mean square error (RMSE) of GA registration is 1~5 cm and the registration efficiency can be improved by about 50% combining GA with ICP.

Key words: mobile laser scanning     terrestrial laser scanning     point cloud registration     genetic algorithm     ICP    

车载激光扫描(mobile laser scanning，MLS)能快速获大场景点云数据，在道路交通领域有应用价值和潜力^[1-2]，如道路信息调查^[3]和智能驾驶高精度三维地图制作^[4]。MLS硬件系统发展很快，形成了多种类型的商业化产品，该系统必要组件包括激光扫描仪、高精度POS系统和高精度时间同步控制系统^[5]。由于MLS测量存在视场限制和遮挡，需要将地面激光扫描(terrestrial laser scanning，TLS)点云数据作为补充。MLS点云位于大地坐标系，TLS点云位于局部坐标系，需要进行坐标转换。本文采用TLS与MLS点云配准以完成基准统一。

点云自动配准一般按“初始配准”和“精配准”两步进行^[6]。点云精配准最著名的算法是ICP算法^[7-9]。最小二乘3D(least-squares 3D，LS3D)表面配准^[10]近些年也被采用。ICP和LS3D均使用局部优化算法，局部优化收敛性依赖于初始转换参数。初始配准为精配准提供初始值，研究最多的是特征匹配。特征匹配通过在重叠区自动提取特征建立对应关系，所采用的特征需要具有旋转和平移不变性，如曲率和点标签^[11]、旋转图像(spin image)^[12]、快速点特征直方图(FPFH)^[13]。文献[14—15]对已有特征描述子进行了总结，并比较了它们的性能，结果表明特征提取 *** 需谨慎选择。点云特征匹配面临分布不均匀、噪声、部分重叠、数据量大、重复结构等诸多问题，加上无法准确度量同名对应关系的几何质量，特征匹配的优化往往耗时且容易失败^[16]。

除两步配准外，遗传算法(genetic algorithm，GA)可一步完成配准^[17]。GA是一种全局优化算法，采用在整个解空间全局自适应地搜索更优解^[18]。GA很早被应用于3D医学点云配准^[19]。文献[20]分析了GA应用在点云配准中的细节，提出了基于均方误差(mean square errors，MSE)的配准模型。文献[21—23]均采用基于MSE的配准模型进行GA配准。MSE度量准则源自局部优化算法，需要转化为更大化的适应度值用于评价转换参数的好坏程度。与基于特征的配准相比，GA配准不需要特征提取和描述；与ICP相比，GA配准不依赖于初始转换参数，但效率更低。论文提出一种结合GA与ICP的高效率自动配准 *** 。

1 GA简述

GA是一种采用随机搜索机制的全局优化 *** ，模拟生物进化过程，即保持一个候选解组成的种群，用3个遗传操作完成进化：选择、交叉和变异^[18, 24-26]。不同的优化问题，进化操作的解表达形式不同。解转化为其表达形式的过程称为编码，即将搜索空间的解表示为由多个基因组成的可遗传操作的染色体，形式上为一个向量。解码是编码的逆操作。数值优化问题采用数值编码和解码 *** ，常用 *** 为二进制和浮点编码^[26]。前者是将实数解转为二进制数构成染色体，相应解码为二进制数染色体转成实数解；后者直接将实数解作为染色体，无须解码。实数编码没有转化精度损失，效率更高，也易与经典优化估计 *** 结合使用^[18]。

标准GA包括3个主要步骤：种群初始化、适应度计算和遗传操作。在确定编码方式后，进行种群初始化生成候选解集。种群是由个体组成的 *** {Pop| Ch₁，Ch₂，…，Ch_M}。M为个体数目，其经验值取几十至几百。种群初始化 *** 一般为均匀随机生成搜索空间内样本 *** 。搜索空间是优化问题的解域，定义为[-U，U]，U为搜索空间上限。GA优化获得更优解的过程是种群进化的过程，适应度用于评价解的好坏，是选择操作的依据。适应度函数是非负更大的，一般由目标函数转化而来。由于搜索空间、适应度函数定义与实际问题相关，点云配准的相关定义在GA配准一章阐述。

遗传操作是模拟生物基因产生下一代的操作，包括选择、交叉和变异。选择操作是从父代总群中选择M个染色体作为子代进行进化。某一个体被选中的机会应当与适应度值成比例，适应度越高，被选中的概率越大。期望值选择^[26]是一种较好的算法，可以确保适应度值较大的个体以较高的概率被选择。首先，直接复制∑Num_i个个体到下一代

 (1)

式中，F_i为第i个个体的适应度值。复制后剩余适应度值为

 (2)

所有个体的剩余适应度值用于按适应度比例随机选择余下的M－∑Num_i个个体。

交叉操作通过双亲染色体的基因值依交叉概率P_c作运算产生两个新的个体，变异操作依变异概率P_m改变染色体一个或多个基因值产生新个体。交叉与变异操作与编码方式有关。算术交叉和非均匀变异 *** 适用于浮点编码 *** ^[18]，在本文提出的 *** 中被采用。依经验，P_c取0.6~1的值，P_m不大于0.1。为了让某一代的更优解不被交叉和变异操作破坏，适应度值更高的个体直接复制到下一代群体中。

适应度值计算和遗传操作迭代进行，构成了GA进化过程。GA进化的终止条件为以下两个条件满足任意一个时：

(1) 更大代数max_gen：进化代数达到max_gen时终止；

(2) 更大适应度保持不变代数max_best：更大适应度值已max_best代(相邻两代更大适应度值相等)保持不变则终止。为了获得全局更优解，max_gen和max_best不能过小。

2 配准 *** 2.1 问题描述

点云配准分解为两个子问题：如何建立同名对应关系(correspondences，CORRS)；如何利用CORRS构造优化目标函数估计坐标转换参数。传统基于特征的配准是先提取关键点(特征明显且感兴趣的点)，对关键点进行描述，再利用相似关系建立CORRS；采用RANSAC算法剔除错误CORRS，并估计更优转换参数。ICP配准利用距离最近点构造CORRS，再利用距离阈值和法向量夹角阈值剔除错误CORRS，进而估计更优转换参数。基于特征的配准和ICP配准归纳为4步^[27]：点云选择、CORRS建立、错误CORRS剔除、转换参数估计。点云选择是选择部分的点用于配准，目的是提高配准效率。基于特征的配准关键点提取的过程即为点云选择。ICP配准则采用下采样完成点云选择，应用较多的 *** 为法线空间采样，它在法向量空间内均匀随机抽样，结果表现为地物特征变化大的地方剩余点较多，变化小的地方剩余点稀少，可有效保持地物特征^[9]。

给定待配准点云S的匹配点S_i，基准点云T的点T_i，点云配准首先建立S和T的对应关系(S_i，T_j)，再根据对应关系建立目标函数并估计更优转换参数。这里，S为TLS点云，T为MLS点云。点云配准采用的变换模型如下^[27]

 (3)

式中，S是待配准点云，S_i=[S_xi S_yi S_zi]^T为第i个配准点；基准点云T，T_j=[T_xj T_yj T_zj]^T为对应点；t=[t_x t_y t_z]^T为平移向量；R表示旋转矩阵，是x、y、z轴三个旋转角α、β、γ的函数。

传统配准 *** 的优化目标为CORRS距离平方和最小，即MSE度量

 (4)

式中，N为CORRS数目。

2.2 GA配准

GA本身是一种全局的启发式的优化 *** ，它在整个转换参数空间自适应搜索更优解。这里将GA配准概括为4个步骤(如图 1所示)：总群初始化和点云选择，待配准点云转换，适应度计算，遗传操作。后3个步骤迭代计算，构成GA进化过程。总群初始化和GA进化已作了描述。在预处理后，点云数据量仍然较大，很多点位于地面，需用点云选择提高配准效率。GA配准点云选择 *** 与ICP配准相同，即为法线空间采样法。

图 1 遗传算法配准流程Fig. 1 The flow chart of the proposed GA registration
虚线框内为遗传进化过程

GA配准建立CORRS的 *** 为先对待配准点云进行转换，然后用邻近点搜索距离最近点建立CORRS。点云转换和邻近点搜索需要对总群每一个体分别进行，为计算最耗时的阶段。点云转换和适应度计算对个体的计算是独立的，可以采用多核并行运算，本文采用OpenMP编程^[28]作加速。

传统配准采用最小化形式的目标函数E估计更优参数，GA配准依更大化形式的适应度F进行优化。F由E转换而来，常用 *** 为负指数函数作转化函数

 (5)

由于S和T部分重叠，文献[17, 20]提出在GA配准中使用距离截断MSE模型对式(4)作修正。距离截断函数为

 (6)

式中，d_th为距离阈值，它是重叠区域CORRS的更大距离。Silva模型将CORRS分为两类：重叠区域内为内点和非重叠区域内为外点。该模型意味着通过最小化MSE同时更大化内点数目得到更优转换参数。

2.3 搜索空间

GA是在整个搜索空间进化搜索更优解的过程。点云配准的搜索空间由转换参数的上界U确定，即[-U，U]。在任意情况下，α、β、γ的上界为180°，t_x、t_y、t_z是无界的。如果搜索空间过大，GA收敛慢，或早熟(收敛至局部更优)，或退化为随机搜索。搜索空间越小，GA收敛速度越快，配准效率越高。因此，确定一个有限且尽可能小的搜索空间是必要的。

本文将TLS扫描仪设站粗略位置作为先验信息限定搜索空间。扫描仪设站的粗略位置可由内置GPS获取。关于内置GPS的信息量少，可了解的是它采用单点定位方式，定位精度达分米级或米级^[29]。t_x、t_y、t_z的取值在位置误差范围内，本文将其设定为10 m。α、β与扫描平台的水平程度有关，它们的值通常很小，一般在5°以内；γ与北向对准有关，在任意设站时的范围是[-180°，180°)。因此，转换参数的搜索空间为(α，β，γ，t_x，t_y，t_z |α，β∈ [-5°，5°]，γ∈ [-180°，180°]，t_x，t_y，t_z∈ [-10 m，10 m])，即U等于[5°, 5°, 180°, 10 m, 10 m, 10 m]。

如果所采用的扫描仪不带内置GPS，可采用其他的辅助测量方式获取设站位置，如外置GPS或GPS RTK。GPS RTK采用差分GPS定位，精度达厘米级，则t_x、t_y、t_z的搜索范围可限定在0.1 m以内，即t_x，t_y，t_z∈ [-0.1 m，0.1 m，0.1 m]。无论采用何种辅助测量方式，平移向量的搜索范围应根据定位精度进行设置。

2.4 N *** S配准模型

已有GA配准 *** 采用基于MSE的配准模型。MSE度量源自局部优化算法，应用于全局优化精度会受影响。对应点满足d_i≤d_th时为内点，增加K个内点，目标函数值为

 (7)

通过作差计算，如果d_i≤1，则E_K≤E；否则E_K>E。当d_th>1 m(文献[17]取值为5 m，本文取值2 m)且1 < d_i≤d_th时E_K>E，即增加内点目标函值增大，与内点增加目标函数减小的期望相反。

这里则提出了N *** S配准模型，该模型直接依距离映射函数计算F，并将法向量约束引入配准模型进行优化。N *** S配准模型的形式如下

 (8)

式中，n_i和n_j为对应点的归一化法向量；S_c为距离映射函数，其值称为匹配分数。S_c需要满足：0 < S_c≤1，单调递增。第1个条件使得F是归一化的，不会随CORRS数目增大而无限增大；第2个条件使距离越大，分数越小，即对F贡献越小。

同Silva模型一样，这里将整个匹配区域也分为重叠区域和非重叠区域。为了保证距离较近的CORRS获得高的分数，重叠区域又分为理想重叠区域和缓冲区域。重叠区域内两个区域分段处的距离阈值称为理想距离d_ideal。在d_ideal处，匹配点被赋予分数高置信度0.95；在d_th处，被赋予分数低置信度0.05。利用负指数函数定义连续的匹配分数函数(如图 2所示)。

 (9)

图 2 N *** S模型的匹配分数函数Fig. 2 The matching score function of the proposed N *** S model

N *** S模型带两个参数d_ideal和d_th。d_ideal一般较小，本文取0.05 m。如果d_th较小，则内点较少，总群的整体适应度值较小，不利于遗传进化，即很难搜索到更优解；其值较大，总群的整体适应度值较大，容易搜索到更优解，但分数函数变化较缓(图 2(b))，个体差异变小，所获解的精度较低。由于搜索空间已经限定，本文取适当值d_th=2 m。

2.5 GA与ICP融合策略

由于GA采用全局搜索策略，其收敛性不依赖于初始值，但计算效率低，局部收敛慢，因此进一步提出采用GA与ICP相结合的配准策略以提高配准效率。结合方式为：先采用GA配准，当进化到一定代数时，GA已经趋于局部搜索，其获得的解已接近于更优化解，此时改用ICP进行局部优化。由于局部范围内的GA适应度比较接近，为控制GA的终止精度，可将GA第2个终止条件中的“相邻两代更大适应度相等”改为“相邻两代更大适应度之差的绝对值小于e″。e是微小正数，一般取10^-3~10^-2。

3 试验与分析

为验证GA配准的有效性，N *** S配准模型的优越性以及GA与ICP融合配准策略的高效性，采用两组实测数据进行了试验。图 3(a)所示为数据1，待配准点云S约1.3千万点，基准点云T约1.1千万点；图 3(b)所示为数据2，待配准点云S约5.2千万点，基准点云T含1千万点。两组数据重叠度均约为50%；使用的地面激光扫描仪为Riegl VZ400，设站粗略位置均通过扫描仪内置GPS获得。

图 3 试验点云Fig. 3 The test point clouds蓝色为待配准点云; 红色为基准点云

      点云数据量大、含噪声，且配准需要法向量，因此对点云进行了预处理。预处理过程为：剔除扫描距离较大的点，这里距离阈值根据扫描仪的有效距离设置为100 m；进行均匀间隔下采样，采样间隔为2.5 cm；根据邻域局部协方差矩阵估计法向量与曲率估计^[30]；树叶易随风飘动，树叶点对配准有影响，其呈散状分布，曲率大，通过曲率阈值0.05可予剔除，如图 4所示。预处理后，数据1中S的点约占原始的19%，T的点约占原始的58%，效果见图 3(c)；数据2中S的点约占原始的9.5%，T的点约占原始的45%，效果见图 3(d)。可见，预处理后点云数据量明显减小，但原有特征信息仍然保留。

图 4 散状点剔除Fig. 4 The removal of scattered points点云按高程值渲染

为定量评价GA配准精度，将待配准点云S与其参照点云S_ref的距离均方根误差RMSE作为衡量指标。S_ref是S的理论值。理论值是未知的，这里通过人工选择特征点进行粗配准(如图 5)，再采用ICP精配准获得S和T之间的转换参数，将S转换点云近似作为S_ref。为剔除错误的对应关系，ICP配准的对应点距离阈值设为0.2 m，法向量夹角阈值为10°。

图 5 人工选择特征点进行粗配准Fig. 5 Coarse registration by manually selected eigen points

因用于配准的点云是依法向量空间随机选择且GA采用随机搜索机制，各组配准试验均独立进行了50次，以统计结果进行评估。为剔除错误的对应关系，ICP算法的对应点距离阈值设为0.2 m，法向量夹角阈值为10°。试验运行环境为：Intel Core i7-4790 CPU @ 3.60 GHz，4核心处理器和8 G内存。详细的GA配准参数见表 1，计算机线程数目等于8。

表 1 GA配准试验参数Tab. 1 The experimental parameters of GA registration

      采用N *** S模型与Silva模型的GA配准对比试验结果如表 2所示。N *** S模型的精度和效率均优于Silva模型，平均优化时间高于Silva模型20%左右，RMSE在1至5 cm之间。采用N *** S模型的GA配准效果如图 6所示。在具有任意北偏角和较大平移值的情况下GA仍然能完成匹配，验证了 *** 有效。

表 2 GA配准结果统计Tab. 2 The statistical results of GA registration

图 6 GA配准后点云Fig. 6 The point cloud after GA registration
蓝色为待配准点云；红色为基准点云；绿线框内为局部地物放大

GA更大适应度变化曲线如图 7所示，在进化初期，适应度变化较快，GA表现全局搜索；当进化至一定阶段时，适应度变化缓慢并趋于成熟，GA表现局部搜索。GA配准50%以上迭代位于变化平缓区域，表明局部收敛速度慢。数据1和数据2的GA与ICP融合策略平均运行时间分别为98 s、217 s；平均进化代数为76、67。融合GA和ICP的配准策略效率比GA配准提高了50%左右。

图 7 GA配准更大适应度Fig. 7 The max fitness of GA registration1条折线表示1次试验

4 结论

为统一地面激光扫描与车载激光扫描点云坐标基准，提出了一种结合遗传算法GA与ICP的高效率自动配准 *** ：当GA配准趋于局部搜索时，改用ICP完成配准。本文重点研究了GA配准，其归结为4步：①总群初始化和点云选择；②匹配点云转换；③适应度计算；④遗传操作。GA配准以地面激光扫描仪内置GPS测量粗略位置作为先验信息限定优化搜索空间。笔者提出了更大化的归一化匹配分数之和(normalized sum of matching scores，N *** S)配准模型以提高全局配准精度。通过实测点云数据进行试验，结果表明：GA配准是有效的，基于N *** S模型的均方根误差(root mean square error，RMSE)为1~5 cm；N *** S模型的精度和效率均优于已有的基于均方误差(mean square errors，MSE)的Silva模型；融合配准策略可将效率提高50%左右。GA配准可以达到很高的配准精度，可一步完成点云配准；也可以作为初始配准，与精配准结合以提高效率。
 

【引文格式】闫利, 谭骏祥, 刘华, 等. 融合遗传算法和ICP的地面与车载激光点云配准[J]. 测绘学报，2018，47(4)：528-536. DOI: 10.11947/j.AGCS.2018.20170235