一种改进的选权迭代算法在点云数据拟合中的应用 Application of an Improved Selecting Weight Iterative Algorithm in Point Cloud Data Fitting

doi:10.12677/GST.2018.64036

Geomatics Science and Technology
Vol. 06 No. 04 ( 2018 ), Article ID: 27265 , 6 pages
10.12677/GST.2018.64036

Application of an Improved Selecting Weight Iterative Algorithm in Point Cloud Data Fitting

Nianwu Deng¹, Meng Li^1,2, Weiling Hu³

●How to Cite this Article

¹School of Water Resources and Hydropower Engineering, Wuhan University, Wuhan Hubei

²Guizhou Water Conservancy and Hydropower Survey and Design Institute, Guiyang Guizhou

³Wuhan Metro, Wuhan Hubei

Received: Oct. 2^nd, 2018; accepted: Oct. 18^th, 2018; published: Oct. 25^th, 2018

ABSTRACT

To fit the point cloud data with massive outliers, an improved selecting weight iterative algorithm is proposed: the robust initial value is obtained by using the least trimmed squares algorithm, and the number of iterations is judged by the mixed total least squares algorithm; the parameters of the plane fitting and spherical surface fitting are calculated by the method. The result shows: the better parameters are achieved even if the percentage of outliers is high.

Keywords:Point Cloud Data Fitting, Selecting Weight Iteration Algorithm, Outliers, Least Trimmed Squares Algorithm, Mixed Total Least Squares Algorithm

一种改进的选权迭代算法在点云数据拟合中的应用

邓念武¹，李萌^1,2，胡魏玲³

¹武汉大学水利水电学院，湖北武汉

²贵州省水利水电勘测设计研究院，贵州贵阳

³武汉地铁集团有限公司，湖北武汉

收稿日期：2018年10月2日；录用日期：2018年10月18日；发布日期：2018年10月25日

摘要

针对粗差含量较高的点云数据拟合，提出了改进的选权迭代算法：通过最小截断二乘获取稳健的初值，在迭代过程中利用混合总体最小二乘估计控制迭代次数。将该改进算法运用在点云数据平面和球面拟合中的结果表明：该方法在粗差含量较高时仍具有很好的拟合结果。

关键词 :点云数据拟合，选权迭代算法，粗差，最小截断二乘算法，混合总体最小二乘

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

为了进行目标的三维重建，一般利用三维激光扫描仪或全站扫描仪对目标进行扫描 [1] ，快速获取目标的点云数据，然后对点云数据进行特征面拟合，得到目标的几何模型。特征面拟合方法一般有最小二乘估计、总体最小二乘估计、混合总体最小二乘估计等，对于含有粗差的点云拟合，常用的方法有稳健特征值法 [2] 、随机一致性抽样法 [3] 和选权迭代法 [4] 等。

选权迭代法采用一个增长慢的函数 $ρ (v_{i})$ 代替残差平方和 $v_{i}^{2}$ 进行最小二乘平差，通过迭代的方式来减小粗差点的权值从而平滑粗差对平差结果的影响 [5] 。但当粗差含量达到一定限度时，选权迭代法得到的几何基元将偏离基准值。鉴于此，有必要对选权迭代法进行改进：一方面，在选权迭代拟合算法中引入最小截断二乘估值作为选权迭代的初值，以有效提高算法的稳健性；另一方面，在迭代评判标准上，利用混合总体最小二乘估计代替最小二乘估计，其中混合总体最小二乘同时考虑了拟合模型中系数矩阵和观测向量存在误差。通过上述改进，拟合精度将得到提高。

2. 改进的选权迭代拟合算法

2.1. 基于最小截断二乘的参数初值估计

最小截断二乘(Least Trimmed Squares, LTS)是一种稳健估计方法，与最小二乘估计中使目标函数中所有观测值的残差平方和达到最小不同，LTS估计主要思想是将观测值的残差平方和升序排列，并取排在前一半的残差平方和最小时对应的估值作为最优估计值。由于LTS估计对局外点的影响不敏感，可以达到50%的崩溃点，因此它具有很强的稳健性 [6] 。

利用最小截断二乘法进行稳健初值估计时需要考虑全部观测值中任意截断个数的所有组合，由于点云数据量大，故可采用随机抽样法对LTS估值做近似计算，具体实现操作如下：

1) 从点云数据集(总个数为p)中随机抽取n + 1个点(n为确定拟合模型参数所需的最少点个数)，利用最小二乘法估计参数；

2) 计算点云中所有点在到每次抽样估计模型中的残差，对残差平方进行升序排序，计算前h(h = int(p + n + 1)/2)个残差的平方和作为抽样拟合质量的评价指标。

3) 确定抽样次数N，重复N次上述计算，选取残差平方和最小所对应的模型参数作为选权迭代估计的初值。

2.2. 权函数的选取

选权迭代法中常用的权函数主要有Huber权函数、Hampel权函数、丹麦权函数和IGG系列权函数等。考虑到Huber权函数和丹麦权函数没有淘汰段，抗差能力与其他函数相比较弱，而Hampel权函数表达形式更为复杂，模型选择IGG III方案作为算法的权函数 [7] 。

${\bar{p}}_{i} = {\begin{array}{l} p_{i} & | v_{i} / m_{v} | \leq k_{0} \\ \frac{k_{0}}{| v_{i} / m_{v} |} (\frac{k_{1} - | v_{i} / m_{v} |}{k_{1} - k_{0}}) p_{i} & k_{0} < | v_{i} / m_{v} | \leq k_{1} \\ 0 & k_{1} < | v_{i} / m_{v} | \end{array}$ (1)

式中 ${\bar{p}}_{i}$ 为等价权对角元素； $p_{i}$ 为前一次迭代计算所得权值，对于几何基元点云数据拟合，认为观测数据为等精度测量，故设定初始权矩阵为单位阵； $v_{i}$ 为残差，迭代开始前的残差以最小二乘估计计算求得； $m_{v}$ 为中误差； $k_{0}$ 、 $k_{1}$ 为常数，一般取 $k_{0} = 1.5$ ， $k_{1} = 2.5$ 。

2.3. 选权迭代终止条件

利用混合总体最小二乘进行参数估计。当本次估计参数与前次估计参数的差值小于设定值时迭代终止。

混合总体最小二乘法是将最小二乘法和总体最小二乘法结合起来，不仅解决了观测向量和系数矩阵存在随机误差时的参数估计，还顾及到系数矩阵中存在常数项的问题 [8] 。

总体最小二乘的观测方程为 $(A + Δ_{A}) X = L + Δ_{L}$ ，当系数矩阵 $A$ 中存在常数项时，可以对系数矩阵进行分块，即 $A = [A_{1} A_{2}]$ ，其中 $A_{1}$ 为系数矩阵的常数列， $A_{2}$ 为除去常数列后的系数矩阵。相对应的未知数 $X$ 分块为 $X = {[X_{1} X_{2}]}^{T}$ ，其中 $X_{1}$ 为 $A_{1}$ 相对应的未知参数构成的矩阵， $X_{2}$ 为 $A_{2}$ 相对应的未知参数构成的矩阵。混合总体最小二乘的观测方程为： $A_{1} X_{1} + (A_{2} + Δ_{A_{2}}) X_{2} = L + Δ_{L}$ 。

2.4. 执行迭代

以最小截断二乘的参数估计为初始参数，以单位权作为初始权函数，进行选权迭代计算，利用混合总体最小二乘进行迭代参数估值，当前后两次迭代参数估值的差小于某一较小数时，迭代停止，此时将后一次得到的参数估值输出作为模型参数的最优解。

根据上述步骤，改进的选权迭代算法可以由图1所示。

3. 点云数据空间平面数据拟合算例分析

为验证改进的选权迭代拟合算法在点云数据平面拟合中的有效性，自选平面方程z = −1.70998x − 1.73205y + 14.14214，利用MATLAB编程进行拟合仿真实验。

随机从自选平面中随机抽取5000个点组成平面点云数据，将模拟点三维坐标(x,y,z)方向上均加入随机误差v~N(0,0.002)形成非粗差点，点云数据如图2所示。分别用于选权迭代法和改进的选权迭代法进行参数拟合，结果见表1和表2中粗差含量为0%的拟合结果。

设定粗差比例从5%逐次增加到30%共模拟6组数据，分别利用选权迭代法和改进的选权迭代拟合算法对平面进行拟合，结果见表1和表2。

实验发现，当不含粗差或粗差较小时，这两种方法均能较好地进行平面拟合，且精度较高，当粗差含量增大时，利用选权迭代法拟合平面精度逐渐降低，而改进的选权迭代拟合算法结果仍能保持很高的精度。

Figure 1. Flowchart of improved selecting weight iterative algorithm

图1. 改进的选权迭代拟合算法流程图

Figure 2. Simulated plane point cloud data

图2. 模拟平面点云数据

Figure 3. Simulated sphere point cloud data

图3. 模拟球面点云数据

Table 1. Plane fitting results of different gross errors under selecting weight iterative algorithm

表1. 各粗差含量下选权迭代法平面拟合结果

Table 2. Plane fitting results of different gross errors under improved selecting weight iterative algorithm

表2. 各粗差含量下改进的选权迭代拟合算法平面拟合结果

Table 3. Sphere fitting results of different gross errors under selecting weight iterative algorithm

表3. 各粗差含量下选权迭代法球面拟合结果

Table 4. Sphere fitting results of different gross errors under improved selecting weight iterative algorithm

表4. 各粗差含量下改进的选权迭代拟合算法球面拟合结果

4. 点云数据球面数据拟合算例分析

与空间平面拟合类似，为验证改进的选权迭代拟合算法用于球面点云数据拟合的有效性，自选球面方程 ${(x - 10)}^{2} + {(y - 10)}^{2} + {(z - 1)}^{2} = 200$ ，利用MATLAB编程进行拟合仿真实验。

从自选平面中随机抽取5000个点组成球面点云数据，同样在所有模拟点三维坐标(x, y, z)方向上均加入随机误差v~N(0,0.002)形成非粗差点，点云数据如图3所示。

设定粗差比例从5%逐次增加到30%共模拟6组数据，分别利用选权迭代法和改进的选权迭代拟合算法对球面进行拟合，结果见表3和表4。实验结果发现，当粗差含量增多时，利用选权迭代法拟合球面精度逐渐降低，而改进的选权迭代拟合算法结果仍能保持很高的精度。

5. 结束语

改进的选权迭代法首先通过最小截断二乘获取稳健的初值，其次在迭代过程中利用混合总体最小二乘估计控制迭代次数，综合考虑了系数矩阵和观测向量的误差。经过这两次改进，在粗差含量较高时也能获得很好的拟合结果。试验结果表明：当粗差含量不高时，采用选权迭代法和改进的选权迭代法均能获得较好的平面和球面拟合模型。当粗差含量逐步增加时，选权迭代模型随粗差含量的增加而导致拟合效果下降，而改进的选权迭代法仍然得到理想的拟合结果。

文章引用

邓念武,李萌,胡魏玲. 一种改进的选权迭代算法在点云数据拟合中的应用
Application of an Improved Selecting Weight Iterative Algorithm in Point Cloud Data Fitting[J]. 测绘科学技术, 2018, 06(04): 309-314. https://doi.org/10.12677/GST.2018.64036

参考文献

1. 邓念武, 李萌. 实物逆向工程中全站扫描仪精度分析[J]. 测绘通报, 2016(3): 146-147.

2. 官云兰, 程效军, 施贵刚. 一种稳健的点云数据平面拟合方法[J]. 同济大学学报(自然科学版), 2008, 36(7): 981-984.

3. 游俊甫. 基于RANSAC的点云数据特征提取[D]: [硕士学位论文]. 抚州: 东华理工大学, 2015.

4. 李明磊, 李广云, 王力. 点云平面拟合新方法[C]//全国工程测量2012技术研讨交流会论文集. 2012.

5. 周江文. 抗差最小二乘法[M]. 武汉: 华中理工大学出版社, 1997.

6. 杨飚, 张曾科, 孙政顺. 基于LTS稳健初值的选权迭代法[J]. 科学技术与工程, 2005(22): 30-33, 37.

7. 程效军, 李杰. 具有最小截断二乘稳健初值的点云平面拟合算法[J]. 同济大学学报(自然科学版), 2015, 43(9): 1419-1424.

8. 龚循强, 李志林. 一种利用IGG II方案的稳健混合总体最小二乘方法[J]. 武汉大学学报(信息科学版), 2014, 39(4): 462-466.

期刊菜单