EN中文

地球信息科学学报 >

2018 , Vol. 20 >Issue 4: 430 - 439

DOI: https://doi.org/10.12082/dqxxkx.2018.170493

全国激光雷达大会特约稿件

基于虚拟特征点的三维激光点云粗配准算法

  • 李鹏 , 1, 2, * ,
  • 邢帅 1, 2 ,
  • 李瑾 3 ,
  • 何华 1 ,
  • 王丹菂 1, 2 ,
  • 李鹏程 1, 2
展开
  • 1. 信息工程大学地理空间信息学院,郑州 450001
  • 2. 地理信息工程国家重点实验室,西安 710054
  • 3. 兰州交通大学博文学院,兰州 730010

作者简介：李 鹏(1988-),男,硕士,主要从事摄影测量与遥感应用研究。E-mail:

收稿日期: 2017-10-30

  要求修回日期: 2018-01-27

  网络出版日期: 2018-04-20

基金资助

国家自然科学基金项目(41371436)

基于LDA模型的机载LiDAR多特征地物提取(SKLGIE2016-M-3-1)

信息工程大学优秀青年基金项目（2016610902）

收起

A Three-dimensional Laser Point Cloud Rough Registration Algorithm Based on Virtual Feature Points

  • LI Peng , 1, 2, * ,
  • XIN Shuai 1, 2 ,
  • LI Jin 3 ,
  • HE Hua 1 ,
  • WANG Dandi 1, 2 ,
  • LI Pengcheng 1, 2
Expand
  • 1. Institute of Surveying and Mapping, Information Engineering University, Zhengzhou 450001, China
  • 2. State Key Laboratory of Geo-information Engineering, Xi′an 710054, China;
  • 3. Lanzhou jiaotong University Bowen College, Lanzhou 730010, China
*Corresponding author: LI Peng, E-mail:

Received date: 2017-10-30

  Request revised date: 2018-01-27

  Online published: 2018-04-20

Supported by

National Natural Science Foundation of China, No.41371436

Multi-feature Extraction of Airborne LiDAR Based on LDA Model, No.SKLGIE2006-M-3-1

Information Engineering University Outstanding Youth Fund Project, No.2016610902.

Copyright

《地球信息科学学报》编辑部 所有
Fold

摘要

在地面三维激光点云特征提取的过程中,由于三维点云数据采集仪器、采集方法及后期处理等因素影响,依靠传统的基于曲率、法线等几何特征及统计学算法提取出的点云特征数量较多且存在较大误差,若使用其直接作为特征点数据进行点云粗配准,很难提高点云粗配准的精度及速度。因此,本文在对点云数据实际空间分布结构分析的基础上,结合特征点提取算法、法向一致化算法、PCA（Principal Component Analysis）方法及特征点聚类等方法,提出了一种三维激光点云数据虚拟特征点拟合算法。该算法生成的虚拟特征点是由点云实际的特征点拟合得到,或是由位于被测物特征线上的特征点拟合生成的特征线计算得到,该虚拟特征点并不是扫描对象上实际存在的激光反射脚点。通过实验验证,虚拟特征点拟合算法可以较准确地拟合出由于设备及操作方法等原因而未被采集到的建筑物边角点数据,得到的虚拟特征点数据较实际特征点数据具有更少的数据量及更高的精度,使用拟合得到的虚拟特征点可以减少粗配准算法的计算量,提高粗配准算法的计算效率并能获得更精确及可靠的初始配准变换参数。

关键词： 虚拟特征点; 粗配准; 最小二乘; 点云配准; 激光点云

本文引用格式

李鹏 , 邢帅 , 李瑾 , 何华 , 王丹菂 , 李鹏程 . 基于虚拟特征点的三维激光点云粗配准算法[J]. 地球信息科学学报, 2018 , 20(4) : 430 -439 . DOI: 10.12082/dqxxkx.2018.170493

Abstract

Due to the influence of the 3D point cloud data collection instrument, acquisition method and post-processing, the number of point cloud features extracted from statistical algorithm base on geometric features such as the curvature and normal is quite large and with large errors. Using these features for rough cloud point registration, it is difficult to improve the precision and speed of rough cloud point registration. Since the accurate registration algorithm of point cloud data, such as ICP (Iteration Closest Point), 3D-NDT (3-Dimensional-Normal Distributions Transform) and GMM (Gaussian mixture model), works in a narrow registration range, the proper initial transform parameters are requested to essentially improve the speed and accuracy of the algorithm, otherwise it will cause the exact registration algorithm to fall into local optimum or result in registration failure. By analyzing actual spatial distribution of point cloud data, we find that it is difficult to collect accurate point, line feature and plane features information of point cloud or the accuracy of the collected key features is very low due to collection instruments, acquisition methods and post-processing and other factors. Therefore, combined with the method of feature point extraction, principal component analysis (PCA) and feature point clustering, this paper presents a virtual feature point fitting algorithm. Based on the commonly used feature point extraction algorithm, this algorithm uses segment endpoints of an average of more than 3 lines that are not parallel and the endpoints in the range domain ε1 or adopt the distance weighted calculation to complete the virtual feature points fitting. Another way is to use the feature points to fit lines by the least squares method, and then according to the principle of the smallest two norms, 3 or more non-parallel lines whose distance each other is less than ε2 is used to fit the virtual feature points whose distance to those lines is shortest. The virtual point feature generated by the algorithm is calculated from the actual feature points of the point cloud and the feature lines generated by fitting the feature points. It is not the actual laser reflection foot point on the scanned object. Through experimental verification, the virtual feature point algorithm can be more accurate to fit the corner point data of building which cannot be collected due to equipment and operating methods and other reasons. The virtual point feature data obtained by the algorithm is 64.71% less than the actual feature point data amount, the computing speed increased by 41.90%, and accuracy was improved by an order of magnitude. Using the fitted virtual feature points can reduce the amount of data involved in the coarse registration algorithm, improve the computational efficiency of the coarse registration algorithm and obtain more accurate and reliable initial transformation parameters.

Key words： virtual feature points; rough registration; least squares; point cloud registration; laser point cloud

1 引言

在地面三维激光扫描中,由于扫描仪器硬件设备的局限、探测目标的限制及测量精度的更高要求,需要操作人员对探测对象进行多次扫描。为了得到被测地物表面统一且完整的点云数据,需要对未统一到同一坐标系下的激光点云数据进行配准。现阶段三维激光点云配准工作大致分为配准前准备、初始配准、精确配准及精度检验4步,其中配准前准备需要提取出供初始配准使用的点云对应特征,并对点云数据进行滤波等操作。现阶段的点云数据配准主要包括基于点特征、线特征、面特征、曲率及法向量的配准算法,其中基于点特征的配准算法使用最广泛。传统的点特征均局限于被测物表面实际测量得到的激光脚点数据,而角点数据由于测量设备的测量误差、被测目标的空间视角及测量人员的操作水平等因素影响难以达到严格意义上的对应,有时甚至出现较大误差。
现行的三维点云对应特征点提取算法：① 基于曲率值、法向量等几何特征的方法[1,2]。该方法以曲率或法向突变的点作为特征点[3],以被测物的实际测量点云为分析目标,通过分析点云数据各点的k邻域,提取出点曲率大于某一阈值ε的点数据作为该站点云数据的特征点,供初始配准阶段的粗配准方法使用。经过实验分析,如果经实验室精确测量得到的点云数据,如空间分布分布良好、点位置均匀、曲率变化明显,则该方法能够高精度地提取出被测物在各测站的对应特征点,通过比较简单的配准方法便可以达到配准目标,且配准速度快精度高[4]。而在实际地面三维激光扫描过程中,由于三维激光扫描仪自身测量精度限制、被测物空间视角变换影响及操作人员布设站点不合理等因素的影响,从各测站获得的点云数据,尤其是其边角点云数据难以达到上述特征点提取算法使用的实际需求,所提取出的对应特征点存在飞点、噪点及错误点等情况,致使整个点云配准算法在初始配准阶段难以得到较为理想的初始变换参数,直接导致粗配准速度慢精度低,更会影响精确配准的效率和精度,使整个配准过程及结果满足不了实际需求。② 影像特征辅助点云特征点提取[5]。利用在不同测站获得的被测物影像,结合影像角点检测算法,获得对应特征点。利用配准参数将影像特征映射到三维点云数据当中,得到对应点云数据的特征点数据[6],但该类方法由于在不同测站获取的影像光照强度、空间视角、及被测物表面纹理样式等因素影响,以及结合影像与点云数据投影视差与配准误差等的影响,从而使得从不同测站获得的对应特征点误差较大,而致使点云配准失败[7]。
针对以上问题,本文在分析现有特征点提取过程、提取目标及提取方法的基础上,考虑实际点云数据空间结构分布,提出了一种基于三维激光点云数据的虚拟特征点拟合算法,使用实测数据分析该算法的可行性,并结合三维点云数据初始配准阶段的粗配准算法验证了该虚拟特征点的粗配准精度。

2 三维激光点云数据虚拟特征点拟合算法

三维激光点云数据虚拟特征点拟合算法首先利用点云数据的曲率特征提取出点云初始特征点,其次计算并调整被测建筑物表面点云法向,然后精确计算初始特征点法向并据此提取精确特征点,接着通过特征聚类方法将位于同一特征线上的点聚类,最后使用端点拟合法和直线拟合法虚拟特征点。端点拟合法使用不平行且线段端点位于ε1范围内的3条以上线段端点计算均值或按距离加权完成虚拟特征点拟合,得到虚拟特征点;直线拟合法使用不平行且空间距3条及以上直线的垂线段距离小于ε2的直线进行拟合,并按照二范数最小的原则使用最小二乘方法求取该点位置,得到虚拟特征点。最后,使用拟合出的虚拟特征点进行粗配准检验,验证算法的可行性、有效性及精确性。整个算法流程如图1所示。
Fig. 1 Algorithm flow chart

图1 算法流程图

（1）计算点云数据初始特征点并法向一致化
设pi为点云数据中任一点,用点pi的k邻域构建协方差矩阵C。设协方差矩阵C的特征值为λi,且λ0≤λ1≤λ2,则根据文献[8]提出的方法,该点成为特征点的可能性（特征置信度）σp=λ0/λ0+λ1+λ2反映了该点处的特征信息[9],通过设定合适阈值筛选得到初始特征点集Pc。根据文献[10],最小特征值λ0对应的特征向量作为该点的法向量的近似估计,然后使用最小生成树方法进行法向一致化[11]。
（2）精确计算特征点法向
由于第一步提取出的初始特征点存在角点等尖锐特征点,对于点云数据中存在的尖锐特征,通常远离局部多项式曲面[12],而在该点处,用来拟合平面的k邻域将位于多个平面上,需要将这些特征点的法向进行整理,文献[13]在文献[14]基础上提出了对当前点的邻域赋予高斯权重,使距离当前点越近的邻域点对拟合平面的作用越大,距离越远作用越小,则使用选取点k邻域拟合的最小二乘平面表示为：
Pl ( n , d ) = argmin ∑ i = 1 k ω d ( x i ) n x i - d 2 （1）
式中： ω d x i = exp - x - x i / σ d 2 为pi点到邻域点的高斯权重;σd为距离带宽;n是平面的法向量;d为邻域点到拟合平面的距离。在式（1）基础上增加了残差因子[15],改进为：
Pl ( n , d ) = argmin ∑ ρ ( d + ( x - x i ) T n ) ω d ( x i ) （2）
式中： ρ x = σ r 2 2 1 - exp ( - x - x i / σ r 2 为Welsch函数,σd及σr为距离及残差带宽,用于控制邻域对当前选定点作用的大小。在此基础上考虑法向偏差的高斯权重ωn(n),由于当前点pi的法向与邻域点的偏差越大,该邻域点对当前点拟合的平面作用越小[16],将最小二乘平面表示为：
Pl ( n t , d t ) = argmin ∑ r i t ω d ( x i ) ω r ( r i t - 1 ) ω n ( n i t - 1 ) （3）
式中： r i t = d t + ( x i - x ) T n T 表示第t次迭代点xi的残差; ω r r i = exp - r i / σ n 2 为高斯权重函数; ω n n = exp - n - n i / σ n 2 为法向偏差的高斯权重,σn为法向偏差带宽;σd,σr,σn等带宽影响法向估计的准确性,可根据被测物表面点云情况自行设定。通过邻域点迭代加权来逐步改变不在同一曲面的邻域点对拟合平面的作用,进而精确计算初始特征点法向[17]。
（3）精确提取特征点
精确提取特征点是通过对初始特征点数据 P c = p i = x i , y i , z i ∈ R 3 i = 1,2 , ⋯ , N 搜索其k邻域 N p i = x j , y j , z j ∈ R 3 j = 1,2 , ⋯ , k ,对 N p i 按照精确计算后的法向进行聚类,对聚类结果中的每一类利用最小二乘拟合一个平面。并计算选定点到所有平面的距离dj,若dj小于设定阈值ε3,则该选定点pi在平面上;若dj大于设定阈值ε3,则不在平面上。则若pi同时位于2个或者2个以上平面上,则该点为精确特征点[18]。
（4）精确特征点聚类
在精确提取的特征点集Pa中任意选定一点pi,搜索半径为re的球形邻域,提取邻域中与该点不属于同一类的点qi,若pi点与qi点的主法线方向的夹角余弦值小于某一阈值cosθc（式（4））,则将qi点与pi点归为一类,并将qi点作为新的生长点,若阈值均大于cosθc,将该点设置为该聚类线特征的端点,则从初始pi点出发使用上述方法反向生长,找到线段的另一个端点,则停止生长,直到找出所有与pi点在同一条直线上的点集[19],并将所有该线段上的点归为一类,则完成精确特征点聚类,将各聚类结果分别存储。
c os ( e 3 ( p i ) , e 3 ( q ) ≤ cos θ c （4）
（5）虚拟特征点拟合
第1种方式是使用聚类分割确定的同类点数据,将聚类结果数据进行整理,如图2（a）-（d）所示。提取出每一聚类生成的线段的端点数据Pd,任选不在同一类中的3个端点Pdi、Pdj、Pdk,判断3个点的空间位置关系,计算空间分布距离在ε1范围内的3个点,确定位置关系后,计算3个点坐标的平均值,即 x ̅ = ( x di + x dj + x dk ) 3 、 y ̅ = ( y di + y dj + y dk ) 3 、 z ̅ = ( z di + z dj + z dk ) 3 ,使用得到的均值坐标 x ̅ 、 y ̅ 、 z ̅ 作为虚拟特征点Pvi的坐标,如图2（b）及图3所示。将2个站点云数据的虚拟特征点Pvi一一对应,完成虚拟特征点对应提取,尔后将罗德里格坐标变换算法用于2组对应的虚拟点云数据,计算得到旋转变换参数R、平移变换参数T及缩放系数k,最后使用由虚拟特征点计算得到的粗配准变换参数R、T、k完成2组点云数据的初始配准。
Fig. 2 Virtual feature points by endpoints matching algorithm

图2 端点拟合虚拟特征点示意图
注：图2（a）、（b）为模拟图,（c）、（d）为实际点云图

Fig. 3 Virtual feature points by endpoints matching algorithm

图3 实测点云端点拟合虚拟特征点示意图

第2种方式是使用聚类得到的线特征数据,运用整体最小二乘方法拟合出空间直线[20]。具体假设一条空间直线通过点 P 0 ( x 0 , y 0 , z 0 ) ,其中 x 0 = 1 n ∑ i = 1 n x i , y 0 = 1 n ∑ i = 1 n y i , z 0 = 1 n ∑ i = 1 n z i [21],xi、yi及zi均为聚类生成的同一线段坐标,方向向量为（F, G, H）则直线的对称式方程为：
x - 1 n ∑ i = 1 n x i F = y - 1 n ∑ i = 1 n y i G = z - 1 n ∑ i = 1 n z i H （5）
使用空间直线的参数形式可以将式（5）改写成：
x = F H z + 1 n ∑ i = 1 n x i - F nH ∑ i = 1 n z i y = G H z + 1 n ∑ i = 1 n y i - G nH ∑ i = 1 n z i （6）
设 a = F H , b = 1 n ∑ i = 1 n x i - F nH ∑ i = 1 n z i , c = G H , d = 1 n ∑ i = 1 n y i - G nH ∑ i = 1 n z i ,将式（6）改写成矩阵形式（式（7））。
x y = z 1 0 0 0 0 z 1 a b c d T （7）
写成误差形式：
V = z 1 0 0 0 0 z 1 a b c d T - x y （8）
令,,将（8）式简化为 V = B X ^ - L 的形式,由于系数矩阵B中含有坐标z（即误差方程中观测值含有误差）,则在求解过程中不能使用最小二乘方法（Least Squares,LS）进行求解,需要使用整体最小二乘方法（Total Least Squares,TLS）进行参数求解,故可将式（8）简化为：
B L + Δ B Δ L X ^ - 1 = 0 （9）
求解式（9）的TLS方法可以表示为约束最优化问题（式（10））。
Δ B Δ L F = min （10）
使用精确特征聚类生成的点数据 P c ( x i , y i , z i ) 则：
L = x i y i ⋯ x n y n T （11）
B = z 1 1 0 0 0 0 z 1 1 ⋯ ⋯ z n 1 0 0 0 0 z n 1 （12）
求解出参数向量 X ^ ,则可以确定空间直线方程。任意取3条直线,求解距该3条直线距离之和最小的点Pi作为虚拟点Pvi,具体步骤如下：
① 从图4（a）所示的3条直线中任选2条直线l1和l2,设 P di x di y di z di 点位于直线l1上, P dj x dj y dj z dj 位于直线l2上,求解线段 P di P dj ,使得 P di P dj 线段最短,如图4（b）所示。
Fig. 4 Virtual feature points by straight line matching algorithm（Simulated points）

图4 线段拟合虚拟特征点示意图（模拟点云图）

② 如图4（c）所示,过线段 P di P dj 的中点 P mi 确定一个以 P di P dj 方向为法线方向的平面α,表达 式如式（13）所示。
x dj - x di x + y dj - y di y + z dj - z di z + d = 0 （13）
式中： d = - x dj - x di 2 2 + y dj - y di 2 2 + z dj - z di 2 2 ， 即该平面过中点Pmi。
③ 判断第3条直线l3与平面α的位置关系,即使用平面法向量与直线向量的向量积。若向量积不为0则直线平面α与相交,求解其与平面α的交点 P dk x dk y dk z dk ,连接点 P dk 与点 P mi ,则距该3条直线距离最短的点Pi点位于该连接线上,使用点Pi位于该线段上、点Pi位于平面α上及Pi到该3条直线距离最短,确定Pi坐标,如图4（d）所示。其中点到空间直线的距离公式如下[22]：
式中： Δ x i , Δ y i , Δ z i 为该点与 P di x di y di z di , P dj x dj y dj z dj , P dk x dk y dk z dk 的距离差值, F ^ , G ^ , H ^ 为该3条直线的方向向量计算值;若向量积为0,则直线l3在平面内或直线l3平行于平面,若在平面内,使用二维平面内点到直线距离公式计算Pmi到l3并求解垂足,过Pmi与垂足作直线,则距离 3条直线最近的点Pi位于Pmi与垂足之间与直线l3确定的平面上,依据上步求解方法求解点Pi;若在平面外,则作直线l3在平面α的投影,使用l3在平面上的Pi求解方法求解Pi（由于被测物为规则建筑,本文在实验过程中只使用平面法向量与直线向量的向量积近似为1的直线进行求解）。
④ 求解Pi到l1,l2和l3距离 ∑ d i ,保留 ∑ d i < ε 2 的Pi点作为虚拟特征点Pvi,如图5所示。
对2个站点云分别求取其虚拟特征点Pvi并一一对应,使用罗德里格坐标变换算法计算粗配准变换参数R、T、k,并使用该变换参数对两组点云数据进行计算,完成初始配准。
Fig. 5 Virtual feature points by straight line matching algorithm（Actual measurement points）

图5 线段拟合虚拟特征点示意图（实际点云图）

3 实验结果与分析

本文使用实测数据进行实验,分别采用了靶标球特征点、基于曲率的特征点提取算法提取到的特征点、端点拟合算法拟合出的特征点及线段拟合算法拟合出的特征点,进行初始配准实验,并对实验结果进行了对比分析。
本次试验选择了某学校内一建筑为扫描对象,使用Faro focus 3D 130扫描仪进行扫描,共布设 9个测站,布设标准半径为70 mm靶标球10个,保证每两个测站可以同时扫描得到至少6个公共靶标球,并设置Faro测量用标准平面靶标26张,使用莱卡TM50全站仪对测区内球靶标及平面靶标进行测量。9个测站共扫描得到7812万个数据点。本文实验选择8、9号测站测得的数据,实验场景如图6所示。
Fig. 6 Test scene

图6 实验场实际影像图

分别使用8、9号测站实测三维激光点云数据进行边角点提取,初次提取出对应边角点pi共计1296对,使用这1296对边角点进行初始配准,并使用扫描仪自带软件Faro SCENE 6.2.0自动识别得到靶标球点位置数据进行检验,所得配准参数及各坐标均方根误差如表1所示。
Tab. 1 Initial registration parameters and error by conventional algorithm

表1 初次提取的边角点进行初始配准参数及误差

配准参数 均方根误差
缩放系数k 旋转矩阵R 平移向量T X/m Y/m Z/m
0.97045 0.99967 0.02546 0.97045 -5.43740 0.55077 1.15995 0.23857
-0.02546 0.99967 0.99968 19.08851
-0.00178 0.00065 0.00065 -0.80831
在初次提取出的1296对边角点pi的基础上,各站共拟合出了17条线段,其中端点距离小于设定值ε1=0.05 m的3条以上线段共有6组,使用端点拟合特征点算法拟合出对应特征点Pvi,将其中距离小于设定值ε1的端点所提取的特征点Pvi提取出来,如表2所示。
Tab. 2 Virtual feature points by endpoint fitting algorithm

表2 端点拟合得到的虚拟特征点

虚拟点编号 8号测站端点拟合的虚拟点坐标 9号测站端点拟合的虚拟点坐标
Pvx Pvy Pvz Pvx Pvy Pvz
1 1.96220 5.04140 -9.46110 7.74903 -13.7184 -8.94537
2 -1.39840 4.59223 -9.46020 4.40403 -14.2609 -8.94420
3 -2.11530 4.52080 -10.46730 3.67897 -14.2120 -9.93900
4 -1.26770 4.64480 -10.45770 4.55350 -14.2055 -9.94297
5 -0.36603 4.76697 -10.46770 5.46060 -14.0643 -9.94593
6 2.50203 4.65843 -9.43187 8.31707 -14.0908 -8.89783
使用端点拟合生成的虚拟特征点及使用罗德里格坐标转换算法进行初始配准,并用靶标球点进行检验,所得配准参数及各坐标系均方根误差如表3所示。
Tab. 3 Initial registration parameters and error by endpoints fitting algorithm

表3 端点拟合特征点初始配准参数及误差

配准参数 均方根误差
缩放系数k 旋转矩阵R 平移向量T X/m Y/m X/m
0.99585 0.99990 0.01381 0.99999 -5.60008 0.23450 0.21212 0.16693
-0.01382 0.99985 0.00977 18.98459
-0.00124 0.00979 0.99995 -0.69463
使用直线拟合虚拟特征点算法将这17条线段进行拟合,对空间距离小于ε2=0.05 m直线段依据上节算法拟合,共拟合出6组对应虚拟特征点Pvi,如表4所示。
Tab. 4 Virtual feature points by line fitting algorithm

表4 直线拟合得到的虚拟特征点

虚拟点编号 8号测站端点拟合的虚拟点坐标 9号测站端点拟合的虚拟点坐标
Pvx Pvy Pvz Pvx Pvy Pvz
1 1.92401 5.03767 -9.23144 7.65660 -13.6367 -8.58715
2 -2.90627 4.30942 -9.11996 2.46531 -14.3348 -8.57708
3 -1.68841 4.34429 -9.51169 3.74963 -13.8842 -9.24356
4 -0.88299 4.55450 -9.85436 3.96854 -13.3019 -8.55429
5 0.156401 4.55181 -9.78249 4.98653 -13.4157 -8.53616
6 2.38413 4.38090 -9.16290 7.73109 -13.0720 -8.59846
使用直线拟合的虚拟特征点及使用罗德里格坐标转换算法进行初始配准,并用靶标球点进行检验,所得配准参数及各坐标系均方根误差如表5所示：
Tab. 5 Initial registration parameters and error by straight line matching algorithm

表5 直线拟合特征点初始配准参数及误差

配准参数 均方根误差
缩放系数k 旋转矩阵R 平移向量T X/m Y/m Z/m
1.00513 0.99975 0.02124 0.00633 -5.45971 0.09822 0.16531 0.22227
-0.02113 0.99963 -0.01670 18.74874
-0.00668 0.01656 0.99984 -0.19724
在初始配准的过程中对3种方法消耗时间进行了统计,统计结果如表6所示。
Tab. 6 Time statistics for three algorithms

表6 3种特征点提取算法初始配准时间统计

边角点提取/s 虚拟特征点拟合/s 初始配准/s 合计时间/s
基于曲率特征点提取算法提取
出的角点及边界点		 10.232 19.3060 29.5380
线段拟合虚拟特征点 10.232 6.871 0.0687 17.1717
直线拟合虚拟特征点 10.232 9.236 0.0653 19.5333
由上述实验过程可以看出,在使用初次提取出的边角点特征数据直接进行初始配准计算时,初始配准的均方根误差较大,使用初次提取出的边角点拟合出的虚拟特征点进行初始配准计算时,误差明显减小。从算法原理上看,使用端点拟合或直线拟合所得的虚拟特征点虽然不是扫描得到的被测物实际激光脚点数据,但该算法生成的虚拟点具有被测物表面实际特征点的位置精度,而且精度更高,该算法加权了端点或直线上所有点的位置精度,使得虚拟特征点的位置精度的可靠度更高,而且由于虚拟特征点数目较初次提取出的边角点数目有大量减少,可以加快初始配准的速度。需要说明的是,端点拟合出的虚拟特征点与直线拟合出的虚拟特征点是有区别的,端点拟合的虚拟特征点,它的位置精度只受在设定值 ε 1 范围内的端点位置影响,它的精度由参与运算的端点决定,而直线拟合的虚拟特征点,它的位置精度要受到包含端点在内的并在设定值范围内的3条以上线段所有点的影响,位置精度更可靠。
由实验结果可以看出,使用端点拟合算法与线段拟合算法提取出的虚拟特征点,经罗德里格算法获得的初始变换参数优于基于曲率特征提取算法提取得到的特征点计算的变换参数。本文提出的拟合算法得到的特征点数据是经过整体最小二乘拟合的虚拟特征点,它抛弃了原始算法提取被测物实际特征点的思想束缚,从点云数据空间结构出发,精确了特征点位置,提高了特征点精度,并减少了特征点误差,对该虚拟特征点赋予相应的权重,使其具有更高的精度。由于特征点数量大量减少,且精度更高,所以进一步提高了初始配准算法的计算速度及计算效率。

4 结论

针对基于几何特征的特征提取算法提取出的特征点受三维激光扫描仪仪器本身精度、被测物空间视角及操作人员设站方案等影响而出现提取结果不准确、不精确等问题,本文在分析现有特征点提取过程、提取目标及提取方法的基础上,考虑实际点云数据空间结构分布,提出了一种基于端点拟合、直线拟合虚拟特征点的特征点拟合算法。该算法在虚拟特征点提取的过程中充分考虑了原始特征点误差、权重的影响,通过实测数据的实验结果表明,在同一配准算法进行初始变换参数求解的情况下,本文算法使用的特征点数据量减少了64.71%,速度较常规基于几何特征的算法提高了41.90%,求解的虚拟特征点精度提高了一个数量级。因此,利用本文算法提取特征点可为点云数据的初始配准提供精度更高、稳定性更好地变换参数,并能提高初始配准算法的精度及速度,进一步为加快精确配准算法的速度奠定基础。经过试验测定,本文算法能很好的适用于具有规则几何外形的被测物,但对不规则形状、或缺乏明显特征的被测物还不能很好的适用,下一步将扩展本文算法的适用性,使其能较好的适用于缺少边角点特征及特征模糊的点云数据,并在算法计算效率方面进行改进。

The authors have declared that no competing interests exist.

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Zhang Z.Iterative point matching for registration of free-form curves and surfaces[J]. International Journal of Computer Vision, 1994,13(2):119-152.

DOI

[2]
郑德华,岳东杰,岳建平.基于几何特征约束的建筑物点云配准算法[J].测绘学报,2008,37(4):464-468.

[ Zheng D H,Yue D J, Yue J J.Geometric feature constraint based algorithm for building scanning point cloud registration[J]. Acta Geodaetica et Cartographica Sinica, 2008,37(4):464-468. ]

[3]
刘倩,耿国华,周明全,等.基于三维点云模型的特征线提取算法[J].计算机应用研究,2013,30(3):933-937.针对以往算法存在无法区分尖锐和非尖锐特征点、提取的特征点与视角有关、特征点未连线等问题，提出一种基于高斯映射和曲率值分析的三维点云模型尖锐特征线提取算法。该算法先进行点云数据点的离散高斯映射，并将映射点集聚类；然后使用自适应迭代过程得到两个或多个面的相交线上曲率值和法向量发生突变的尖锐特征点，这些点与视角无关；最后，用改进的特征折线生长算法，将特征点连接，得到光顺特征线。实验证明，该算法具有良好的自适应性、抗噪性和准确性，是一种有效的三维模型特征线提取算法。

DOI

[ Liu Q, Geng G H, Zhou M Q, et al.Alorithm for feature line extraction based on 3D point cloud models[J]. Application Research of Computers, 2013,30(3):933-937. ]

[4]
R Yang, P Allen.Registering, integrating, and building CAD models from range data[C]// IEEE International Conference on Robotics and Automation,1998. Proceeding IEEE, 1998,4:3115-3120.

[5]
彭晨,余柏蒗,吴宾,等.基于移动激光扫描点云特征图像和SVM的建筑物立面半自动提取方法[J].地球信息科学学报,2016,18(7):878-885.lt;p>建筑物立面是城市地物的重要组成部分,而移动激光扫描是获取城市地物三维信息的重要手段之一。本文提出了一种基于移动激光扫描点云的建筑物立面半自动提取算法。该方法首先构建研究区水平网格;然后计算局部点云几何特征,并且将特征投影到水平网格生成点云特征图像;接着基于支持向量机（Support Vector Machine,SVM）对建筑物立面网格进行粗提取;最后使用网格属性（形状系数、网格面积、最大高程）对粗提取结果进行过滤,并将结果反投影到三维空间中得到精确的建筑物立面。以卡内基梅隆大学的移动激光扫描点云进行试验后表明,本算法能够较好地提取出建筑物立面,提取精度为84%,召回率为90%,数据修正后精度为88%,召回率为91%。通过与现有算法对比,本文提出的算法具有较高精度。</p>

DOI

[ Peng C, Yu B L, Wu B, et al.A method for semiautomated segmentation of building facade from mobile laser scanning point cloud based on feature images and SVM[J]. Journal of Geo-information Science, 2016,18(7):878-885. ]

[6]
Li B F.Accelerator of the global automated image registration algorithm[J]. Journal of Computer-Aided Design & Computer Graphics, 2012,24(10):1363-1368.Due to the high computing and memory requirements of the global automated image registration algorithm,an accelerator called BWAGIR II is proposed.It adopts a dedicated two-rank-multi-bank memory to support accessing 16 pixels within a 4×4 interpolating window in one cycle.And some logics are designed to support hybrid operations between a fixed-point operand and a floating-point operand directly.Experimental results from a FPGA-based implementation show that a throughput of over 258×106 pixels/s is achieved with 5 BWAGIR II units.

[7]
张靖,江万寿.激光点云与光学影像配准:现状与趋势[J].地球信息科学学报,2017,19(4):528-539.

[ Zhang J, Jiang W S.Registration of laser point cloud and optical image: Status and trend[J]. Journal of Geo-information Science, 2017,19(4):528-539. ]

[8]
Auly M, Keiser R, Gross M.Multi-scale feature extraction on point-sampled surfaces[J]. Computer Graphics Forum, 2003,22(3):281-289.Abstract We present a new technique for extracting line-type features on point-sampled geometry. Given an unstructuredpoint cloud as input, our method first applies principal component analysis on local neighborhoods toclassify points according to the likelihood that they belong to a feature. Using hysteresis thresholding, we thencompute a minimum spanning graph as an initial approximation of the feature lines. To smooth out the featureswhile maintaining a close connection to the underlying surface, we use an adaptation of active contour models.Central to our method is a multi-scale classification operator that allows feature analysis at multiplescales, using the size of the local neighborhoods as a discrete scale parameter. This significantly improves thereliability of the detection phase and makes our method more robust in the presence of noise. To illustrate theusefulness of our method, we have implemented a non-photorealistic point renderer to visualize point-sampledsurfaces as line drawings of their extracted feature curves.

DOI

[9]
Linsen L.Point cloud representation[R]. Karlsruhe University of Karlsruhe. Faculty of Computer Science, 2001.

[10]
Liu Y J,Yuen M M F. Optimized triangle mesh reconstruction from unstructured points[J]. The Visual Computer, 2003,19(1):23-37.A02variety of approaches have been proposed for polygon mesh reconstruction from a02set of unstructured sample points. Suffering from severe aliases at sharp features and having a02large number of unnecessary faces, most resulting meshes need to be optimized using input sample points in a02postprocess. In this paper, we propose a02fast algorithm to reconstruct high-quality meshes from sample data. The core of our proposed algorithm is a02new mesh evaluation criterion which takes full advantage of the relation between the sample points and the reconstructed mesh. Based on our proposed evaluation criterion, we develop necessary operations to efficiently incorporate the functions of data preprocessing, isosurface polygonization, mesh optimization and mesh simplification into one simple algorithm, which can generate high-quality meshes from unstructured point clouds with time and space efficiency.

DOI

[11]
苏志勋,栗志扬,王小超.基于法向修正及中值滤波的点云平滑[J].计算机辅助设计与图形学学报,2010,22(11):1892-1898.

[ Su Z X, Li Z Y, Wang X C.Point cloud smoothing based on normal correction and median filtering[J]. Journal of Computer Aided Design and Computer Graphics, 2010,22(11):1892-1898. ]

[12]
邹冬. 点云模型的尖锐特征提取与分片分析[D].南京:南京师范大学,2012.

[ Zou D.Fractive feature extraction and fragmentation analysis of point cloud model[D]. Nanjing: Nanjing Normal University, 2012. ]

[13]
袁小翠,吴禄慎,陈华伟.尖锐特征曲面散乱点云法向估计[J].光学精密工程,2016,34(10):2581-2588.针对现有算法对尖锐特征曲面点云法矢估计不准确,点云处理时容易丢失曲面细节特征等问题,提出一种尖锐特征曲面散乱点云法向估计法。该方法用主成分分析法粗估计点云法向;然后,根据各邻域点的空间欧氏距离和法向距离对各邻域法向加权,用加权邻域法向之和来更新当前点的法向;最后,测试估计法向与标准法向的误差,评价估计法矢的准确性,并且将估计的法向应用到点云数据处理中来比较特征保留效果。实验结果表明:本文方法能够准确地估计尖锐特征曲面的法向,最小误差接近0。另外,该方法对噪声有较好的鲁棒性,点云处理时能保留曲面的尖锐特征。相比于其他特征曲面法向估计法,所提出的方法估计的法向误差更小、速度更快、耗时更少。

DOI

[ Yuan X C, Wu L S, Chen H W.Normal estimation of scattered point cloud with sharp feature[J]. Optics and Precision Engineering, 2016,34(10):2581-2588. ]

[14]
Pauly M, Gross M, Kobbelt L P.Efficient simplification of point-sampled surfaces[C]// IEEE Visualization 2002, Washington DC: IEEE Computer Society Press, 2003:163-170.

[15]
Mederos B, Velho L, De Figueiredo L H. Robust smoothing of noisy point clouds[C]//Proc Siam Conference on Geometric Design & Computing. Seattle, USA, 2003:405-416.

[16]
Huber P J.Robust Statistics[M]. Wiley, 2011.

[17]
Hoppe H, DeRose T, Duchamp T, et al. Surface reconstruction from unorganized points[C]//Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH. New York: ACM Press, 1992:71-78.

[18]
陈朋,谭晔汶,李亮.地面三维激光扫描建筑物点云特征线提取[J].激光杂志,2016,37(3):9-11.

[ Chen P, Tan Y W, Li L.Extraction of building′s feature lines based on 3-D terrestrial laser scanning[J]. Laser Journal, 2016,37(3):9-11. ]

[19]
李国俊. 基于Delaunay细化的散乱点云曲面重建研究[D].郑州:解放军信息工程大学,2015.

[ Li G J.Research on surface reconstruction based on delaunay refinement from scattered point clouds[D]. Zhengzhou: PLA Information Engineering University, 2015. ]

[20]
姚宜斌,黄书华,孔建,等.空间直线拟合的整体最小二乘算法[J].武汉大学学报·信息科学版,2014,39(5):571-574.

[ Yao Y B, Huang S H, Kong J, et al.Total least squares algorithm for fitting spatial straight lines[J]. Geomatics and Information Science of Wuhan Universtity, 2014,39(5):571-574. ]

[21]
张小红. 机载激光雷达测量技术理论与方法[M].武汉:武汉大学出版社,2007.

[ Zhang X H.Airborne lidar measurement technology theory and methods[M]. Wuhan: Wuhan University Press, 2007. ]

[22]
胡川,陈义,朱卫东,等.整体最小二乘和最小二乘拟合空间直线的比较[J].大地测量与地球动力学,2015,35(4):689-692.lt;p>&nbsp;给出整体最小二乘法拟合空间直线的一种迭代算法。将空间直线垂直投影到坐标平面，分别采用整体最小二乘法和最小二乘法拟合直线。对坐标点等精度观测、非等精度观测和坐标分量非等精度观测3种场景进行模拟计算，比较两种方法估计的参数和验后单位权方差，并对三维激光扫描仪实测数据拟合结果进行分析。</p>

DOI

[ Hu C, Chen Y, Zhu W D, et al.Comparisons of total least squares and squares for fitting spatial lines[J]. Journal of Geodesy and Geodynamics, 2015,35(4):689-692. ]

Options
文章导航

/

〈 〉