基于LSSVM-NSGA-II的桥梁钢构件三维激光扫描方案优化

吴贤国，邓婷婷，黄金龙，王洪涛，王堃宇，陈虹宇，李铁军

(1. 华中科技大学 土木与水利工程学院， 湖北 武汉 430074； 2. 中建三局集团有限公司， 湖北 武汉 430000；3. 南洋理工大学 土木工程与环境学院， 新加坡 639798； 4. 中国交通建设集团有限公司， 北京 100088)

由于三维激光扫描系统的精度高，在工程项目中得到了越来越多的使用，其中在获取构件空间点云数据的应用尤为广泛。而在三维激光扫描过程中，三维激光扫描参数的设置会直接对扫描精度带来很大的影响，因此，通过调节三维激光扫描参数降低扫描误差的研究是十分有价值的。

近些年来，为了获得较优的参数值，国内外学者进行了大量的研究，于志亮等[3]提出粗瞄与精瞄结合的螺旋-正弦复合方法，并基于线性优化对参数进行设置；杨书哲[4]等利用三维激光扫描技术通过对三维点云数据的获取及处理，以快速且精准度超高的线性方式直接获取物体表面的空间三维坐标；贾冰等[5]提出基于激光脉冲扫描测量体制下的高速点目标捕获、跟踪测量方法，基于时间序列法的捕获方法，优化最佳捕获次数。蔡军等[6]设计了由高精度旋转云台和小型二维激光测距传感器组成的三维激光扫描系统，并根据非线性最小二乘法对三维激光扫描系统的参数进行优化计算；宗文鹏等[7]提出了以优化点云数据中平面的平面度和平面面积为目标的内参数标定方法，并通过提出的单纯形和人工蜂群混合优化算法(Nelder-Mead Simplex and Artificial Bee Colony，NMS-ABC)进行参数解算，实现内参数标定；韩光瞬等[8]介绍了三维激光扫描系统的测量原理、测树过程和测树因子的获取方法，在甘肃省小陇山林业局党川林场，利用样木三维模型理论及方法；韩啸等[9]提出了非线性摄像机成像模型，在对标定图像进行预处理之后，给出了一种快速、准确的角点提取算法；Pathak等[10]采用偏好选择指数和元启发式方法来确定扫描过程参数的最佳值，并使用PSI(Purchase Sales Inventory)方法探索的多标准决策(Multi-Criteria Decision-Making，MCDM)技术；Li等[11]为了估计三维激光扫描仪的测量模型参数，提出了结合入侵杂草优化(Invasive Weed Optimization，IWO)和LM(Levenberg-Marquardt)算法的空间球面标定方法，建立了三维激光扫描仪标定的目标函数。

以往的研究均对三维激光扫描参数优化有一定程度的帮助，但是没有更加精准地表示出相对误差和三维激光扫描参数之间的复杂关系，所以在优化上可能存在较大误差。针对此问题，本文将提出基于三维激光扫描参数的LSSVM-NSGA-II(Least Squares Support Vector Machines and Non-dominated Sorting Genetic Algorithm)优化模型，利用最小二乘支持向量机对相对误差和扫描时间进行预测，以预测非线性函数作为适应度函数，利用遗传算法进行优化，在实现相对误差的基础上获得各个三维激光扫描参数的取值，从而实现精准、有效快速的钢构件拼装。

1 理论基础

1.1 最小二乘支持向量机基本原理

支持向量机(Support Vector Machines，SVM)作为一种智能算法，可以很好地克服非线性问题，具有全局性且适用于小样本[12]。利用最小二乘支持向量机预测耐久性，即利用核函数学习输入指标与输出指标之间的规律进而做出决策的过程。

(1)

式中：α，α*为Lagrange乘数；K(xi，x)为核函数；b为对xi赋予权重乘积后所发生的偏置数。为了降低支持向量机的计算量，提出最小二乘法的支持向量机模型，LSSVM最大的优势就是采用平方和误差代替原本的损失函数，损失函数φ(w)如下：

(2)

同时损失函数应该满足的约束条件为：

yi=wTφ(xi)+b+ei

(3)

式中：γ为LSSVM的惩罚参数；ei为LSSVM的误差变量；φ(xi)为从x到内积特征空间的映射；w为xi的权重系数向量。引入拉格朗日乘子，则表达形式转化为：

(4)

通过对式(4)进行等式求导后可以得到以下方程组：

(5)

求解上述方程组可以得到LSSVM参数(αi，ei，w，b)。最后可得LSSVM的非线性回归模型为：

(6)

式中：核函数K(x,xi)用来代替高维空间上的内积运算；xi为核函数的中心；x为训练样本的输入值；yi为样本的输出;N为样本数量。

1.2 遗传算法基本原理

遗传算法是一种基于达尔文进化理论的智能优化算法[13]，2002年，Deb等在原遗传算法的基础上提出带精英策略的非支配排序遗传算法(NSGA-II)。改进后的遗传算法最大特点是快速非支配排序和拥挤距离。

传统的遗传算法的非支配排序是O(MN3)(M为目标数，N为种群大小)，经过改进之后，NSGA-II算法的的非支配排序是O(MN2)，提升了种群的排列速度，所以称为快速非支配排序。

在进行拥挤距离计算时，对种群升序排序，将第一个、最后一个拥挤距离设置为无穷大，用拥挤距离法就可以计算每个解的距离，其中第i个解的拥挤距离计算如下：

(7)

1.3 基于LSSVM-NSGA-II的目标优化算法构建

本文为了全局地考虑所有方案且提高参数优化的准确度，可以先利用数据挖掘中最小二乘支持向量机算法探究不同参数与优化目标之间的关系，以达到拟合目标函数的目的，继而利用遗传算法进行参数优化，主要步骤分为：(1)利用最小二乘支持向量机回归拟合标定参数之间的函数关系；(2)利用遗传算法对各个标定参数进行优化。LSSVM-NSGA-II流程图如下：

图1 基于LSSVM-NSGA-II三维激光扫描多目标优化流程

1.3.1 基于LSSVM三维激光扫描相对误差预测

Step 1：数据获取及预处理

本研究可以选取项目上一个某扫描构件作为实验对象，所涉及的三维激光扫描参数为：水平入射角度、倾斜角度、点云密度、测量距离、分辨率以及能见度，利用试验数据进行三维激光扫描，并计算相对误差和确定扫描时间，从而得到足够数量的样本数据。

数据预处理主要是对数据进行归一化，避免样本出现数据过大或过小的情况，导致数据被淹没或不收敛[14]。本文将利用式(8)将输入变量和输出统一到[-1,1]区间，实现数据归一化，使得每个特征在预测过程中起到效果。

(8)

式中：y为归一化之后的标准值；ymax，ymin分别默认为1和-1；x为样本值；xmax，xmin分别为样本值的最大值和最小值。

Step 2：核函数参数优化

核函数对最小二乘支持向量机预测精度有很大的影响。在不同预测模型中，应根据研究特点选择合适的核函数[15]。由于高斯核函数既有径向基核函数的优势，还有良好的抗干扰能力，本文将采用高斯核函数当作预测模型的核函数进行研究，其表达式为：

(9)

式中：xi为输入变量；x为输出变量。

在确定核函数后，为了确保LSSVM的泛化水平，本文将采用K折交叉验证，进行网格搜索对核函数宽度参数g和惩罚系数c进行优化。其中，网格搜索法是一种全局搜索法，在避免局部最优的同时节约时间[16]；K折交叉验证常用于LSSVM模型性能的验证，可以保证LSSVM模型良好的学习状态。

Step 3：预测结果分析

为了验证LSSVM模型的预测精度，通过两个模型性能的指标均方根误差RMSE和拟合优度R2来进行检验。均方根误差RMSE表示预测值与真实值之间的离散程度，拟合优度R2表示预测值与真实值之间的拟合效果，两个指标分别由式(10)(11)得出：

(10)

(11)

1.3.2 NSGA-Ⅱ多目标优化

Step 1：建立目标函数

引入LSSVM三维激光扫描相对误差和扫描时间回归预测算法替代传统数学函数作为多目标遗传算法中的适应度函数，从而表示输入变量与输出目标之间存在复杂非线性关系，三维激光扫描相对误差和扫描时间回归函数ming1和ming2表示为：

ming1(lssvm(x1,x2,…,xn))

(12)

ming2(lssvm(x1,x2,…,xn))

(13)

Step 2：建立目标约束条件

为了使得生成的方案更加合理可行，需要对方案生成时的各个因素设定限制范围，形成变量的约束条件，约束条件的一般形式如下：

ail

(14)

式中：xi为第i个设计参数；ail，aiu分别为第i个设计参数值的下限和上限。

Step 3：NSGA-Ⅱ多目标优化

当目标函数和约束条件都确定下来之后，便可基于NSGA-II算法实现多个目标优化，可以找到基于扫描参数的三维激光扫描相对误差的Pareto最优解集。NSGA-II算法与传统遗传算法相比，关键不同步骤主要有两个：

(1)在设置初始种群后，NSGA-II算法将通过快速非支配排序后，利用三个遗传机制：选择、交叉、变异后获得首批子代种群。

(2)在第二代种群进化后进行父、子代合并，通过快速非支配排序之后计算个体之间拥挤度，根据非支配关系和个体间拥挤距离确定新种群，通过三个遗传机制产生新的子代种群。

2 实例分析

2.1 项目背景

我国北方某段高速公路建设项目某一标段主线全长约206 km，在进行项目桥梁钢构件加工和拼装过程中，采用三维激光扫描技术获取构件点云数据，所选择的三维激光扫描仪器是Leica Scan Station P30/40扫描仪，这种型号的扫描仪测角精度8″，测距精度1.2 mm±10 ppm，扫描速度可达1000000点/s，标靶获取精度2 mm@50 m。其中三维激光扫描现场如图2所示，现场钢构件测量标记如图3所示。

图2 三维激光扫描现场

图3 现场钢构件测量标记

2.2 最小二乘支持向量机预测2.2.1 数据获取及归一化

在三维激光扫描过程中，为了探究扫描参数与相对误差以及扫描时间的关系，选取相对误差和扫描时间作为LSSVM预测模型的输出指标。水平入射角度、倾斜角度、点云密度、测量距离、分辨率以及能见度六个对测量误差有较大影响的三维激光扫描参数作为输入指标。通过现场实验，收集一共100组样本数据如表1所示，其中点云模型实验图如图4所示，随机抽取80组样本构成训练集，剩下的20组样本作为测试集。通过式(8)对输入和输出特征指标进行归一化处理。

图4 点云实验图像

表1 输入和输出指标样本数据

2.2.2 核函数参数优化

根据1.3节的分析，选择5折交叉验证法和网格搜索法对LSSVM模型的核函数宽度参数g和惩罚系数c进行选优，分别得到相对误差和扫描时间核函数最优参数，图5，6分别为相对误差、扫描时间预测参数优化结果3D视图。

图5 相对误差参数优化3D视图

图6 扫描时间参数优化3D视图

2.2.3 预测结果分析

从图5中可知，惩罚系数bestc=1，核函数参数bestg=3.0314，此时均方根误差CVmse=0.0018012。表示c=1，g=3.0314，在5-CV验证后的均方误差值最小。

同样，从图6中可知，惩罚系数bestc=48.5029，核函数参数bestg=0.57435，此时均方根误差CVmse=0.00029359。表示c=48.5029，g=0.57435，在5-CV验证后的均方误差值最小。

基于LSSVM核函数参数优化的结果，利用训练集进行学习，分别建立LSSVM相对误差预测模型和扫描时间预测模型，再利用测试集检验训练集的预测模型。根据上述步骤，相对误差训练集预测结果如图7a，测试集预测结果如图7b；同理扫描时间训练集预测结果如图8a，测试集预测结果如图8b。

图7 相对误差预测结果

图8 扫描时间预测结果

从图7能够发现，LSSVM模型能够很好地预测相对误差的变化。图7a为相对误差训练集预测模型，均方根误差为0.00277，拟合优度为0.9777，可以看出该模型拟合结果很好，其预测值与实际值之间误差非常小。图7b为SVM模型对训练集预测回归函数的检验，其中均方根误差为0.000234，拟合优度为0.996，相对误差的支持向量机预测模型对测试集样本的预测值与试验值十分接近。以上数据说明该模型对相对误差预测具有良好的精度且具有出色的泛化能力。

同样从图8中可以看出LSSVM预测模型对扫描时间预测也具有良好的精度。

为了进一步验证利用LSSVM对三维激光扫描的高精度性，将LSSVM模型的预测效果与SVM、BP人工神经网络以及小波神经网络三个预测模型的预测精度及误差进行对比分析，对比结果如表2，3所示。

根据预测精度及误差分析对比表可得：

表2 相对误差预测模型精度及误差对比

表3 扫描时间预测模型精度及误差对比

无论是对三维激光扫描的相对误差还是对扫描时间进行预测，LSSVM预测模型与SVM模型、BP人工神经网络以及小波神经网络预测模型相比，模型的均方根误差都是最低的，同时模型的拟合优度是最高的。因此，利用LSSVM预测模型对三维激光扫描的相对误差以及扫描时间进行预测所得的结果是可靠精准的。

2.3 基于LSSVM-NSGA-II算法三维激光扫描多目标优化

2.3.1 建立目标函数

在实际三维激光扫描过程中，扫描精度是首要考虑的目标之一，除此之外，为了可以在保证精度的基础上提高测量效率，需要减少扫描时间。因此，本研究将以扫描相对误差以及扫描时间为考虑对象，同时进行多目标优化。

(1)基于LSSVM相对误差目标函数

根据上述式(12)(13),可得相对误差和扫描时间的目标函数：ming1(lssvm(x1,x2,…,x6))，ming2(lssvm(x1,x2,…,x6))。其中，x1,x2,x3,x4,x5,x6分别为水平入射角度、倾斜角度、点云密度、测量距离、分辨率以及能见度。

2.3.2 建立多目标约束范围

根据规范以及工程实际等要求确定合理的三维激光扫描参数取值范围，根据式(14)确定优化的约束条件：

2.3.3 基于NSGA-Ⅱ的多目标优化

在三维激光扫描相对误差和扫描时间的目标函数以及扫描参数约束范围后，基于NSGA-Ⅱ进行多目标优化。本文取NSGA-Ⅱ算法的交叉算子为0.8，变异算子为0.02，种群大小为40，最大进化代数和停止代数为60，利用NSGA-Ⅱ算法进行全局寻优，迭代60次后得到最优配比组合，如图9所示。

图9 最优Pareto前沿

由图9可知，随着相对误差的减少，三维激光扫描的扫描时间增长。由于项目对构件的要求比较高，因此要求三维激光扫描的相对误差不能大于3.5 mm。由最优Pareto前沿可得当三维激光扫描的相对误差不大于3.5 mm时，最短的扫描时间为335.944 s，此时相对误差为2.93 mm，水平入射角度、倾斜角度、点云密度、测量距离、分辨率以及能见度分别对应的参数解为89.79°，89.77°，3.29 mm，3 m，0.456，8.67 km。根据项目实际情况，将水平入射角度、倾斜角度和点云密度均取整数，则分别为90°，90°，3.2 mm。利用优化得出的三维激光扫描参数值对扫描仪进行调整，所得点云图像如图10所示，可以看出图像清晰度处于良好水平。

图10 优化后的点云图像

3 结 论

本文建立了一种基于LSSVM-NSGA-II的优化模型，首先以相对误差和扫描时间为研究对象，基于三维激光扫描参数进行试验获取100组样本数据集，然后进行LSSVM实现高精度预测，并将预测函数作为适应度函数，结合规范及工程项目的要求，利用NSGA-II算法进行目标优化，在满足相对误差最低的条件下，得到最优三维激光扫描参数。

(1)选取水平入射角度、倾斜角度、点云密度、测量距离、分辨率以及能见度等6个因素作为最优输入变量集构建基于LSSVM预测三维激光扫描精度模型，预测结果表明基于采用LSSVM算法对相对误差和扫描时间进行预测的精度很高。其中，在对相对误差进行预测时，均方根误差为0.000234，拟合优度为0.996；在对扫描时间进行预测时，均方根误差为0.0012，拟合优度为0.9971。说明了LSSVM模型在三维激光扫描误差分析预测中的可行性以及有效性。

(2)由于基于最小二乘支持向量机预测的效果良好，可将LSSVM回归预测函数作为目标适应度函数，对相对误差和扫描时间进行NSGA-II算法优化后，在满足相对误差达到2.93 mm的基础上，最短的扫描时间为335.944 s，此时相对误差为2.93 mm，水平入射角度、倾斜角度、点云密度、测量距离、分辨率以及能见度分别对应的参数解为90°，90°，3.2 mm，3 m，0.456，8.67 km。结果表明，这是一种智能、精确、高效的参数优化方法，在三维激光扫描中具有非常好的应用价值，达到了保证钢构件加工尺寸的准确性。