地下管廊特征保持的三维点云数据精简研究

刘致远 侯至群 朱大明

摘  要： 本文提出了一种基于RANSAC平面分割和PCA特征提取的移动背包Lidar点云地下管廊特征保持的数据精简方法。首先基于移动背包获得地下管廊原始点云数据;然后利用RANSAC算法对目标点云分割并识别出含有管廊整体轮廓信息的面状点云;最后对所识别出的面状点云基于PCA算法和通过设定投影向量角度阈值提取出管廊特征轮廓数据。试验结果表明，该方法能够有效快速地提取出地下管廊点云数据中的特征轮廓目标，提取的特征轮廓与原始点云能准确符合。在保留轮廓特征的同时精简了数据，为三维点云数据的高效利用奠定了基础。

关键词： 移动背包;点云;RANSAC;轮廓特征提取;PCA;数据精简

中图分类号： P237; TP391; TN249    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2020.08.031

本文著录格式：刘致远，侯至群，朱大明，等. 地下管廊特征保持的三维点云数据精简研究[J]. 软件，2020，41（08）：110-115

【Abstract】： This paper presents a data reduction method based on RANSAC plane segmentation and PCA feature extraction for moving backpack Lidar point cloud in underground pipe gallery feature reserving. First， the original point cloud data of underground pipe gallery is obtained by mobile backpack; then the RANSAC algorithm is used to segment the target point cloud and identify the surface point cloud with the whole outline information of the pipe gallery; finally， based on the PCA algorithm and by setting the projection vector angle threshold， the pipe gallery feature contour data are extracted.The experimental results show that this method can effectively and quickly extract the feature contour targets in the point cloud data of underground pipe gallery， and the extracted feature contour can accurately match with the original point cloud. Reducing data while preserving contour features， laid the foundation for efficient utilization of 3d point cloud data.

【Key words】： Mobile backpack; Point cloud; RANSAC; Contour feature extraction; PCA; Data reduction

0  引言

大规模精细三维模型获取技术的不断发展，三维激光扫描技术凭借其数据获取速度快、精度高、覆盖广的特点，成为高精度三维模型数据获取的主流方式之一。但获取的点云数据量呈几何级数增长，可以轻易从模型表面获取数百万甚至更多的测量数据，使得人工处理数据效率低。由于海量三维点云数据在应用过程中并不都能产生作用，特别是对于地下建构筑物点云而言，其大体模型的建立只需要确定边界区域上的点云即可。因此，面对如此庞大的数据量，如何对海量散乱点云数据精简，从而加快处理速度，达到能提取出轮廓特征等有应用价值数据的目的，成为目前亟待解决的问题。

国内外众多学者对点云数据基于曲率或法矢向量的特征提取进行了深入研究。M J Milroy[1]提出依据近邻点求出该点曲率，剔除明显大于和小于点以达到提取边界特征点目的。当边界点属于较光滑、平坦区域时该方法能有效识别，但对曲率变化较大区域的特征提取效果不佳。王永波[2]等提出利用平均曲率和曲率极值法来实现对特征点的初始提取和精提取，该算法的缺点是受点云采样密度及领域大小的影响，无法应用大范围点云特征提取中。

Pauly[3]基于移动最小二乘（Moving Least Squares）提出了一个完整的采样点几何自由曲面造型框架，并且可以在采样点对象上生成和保留尖锐的特征。Abdalla Alrashdan[4]提出计算每个点的法矢方向，依据相邻法矢方向的突变情况，判断提取边界点。当边界点处法矢方向变化较小时会出现漏提现象。T. Rabbani[5]等依据扫描点法向量的聚类分析和区域增长点云分割算法，对固定激光扫描仪获取的工业设备点云进行表面分割和提取。Tarsha[6]针对相同的LiDAR数据源，分别采用3D Hough和RANSAC算法进行平面提取试验，试验结果表明RANSAC算法具有较高的计算效率和精度。邓博文[7]等提出利用随机抽样一致算法的形态学梯度来实现对目标物边界的提取，然而该算法受法向量计算准确性的影响，同时也受构造面判断准确性的影响。孙殿柱[8]提出一种新的提取算法，以R*-tree作为散乱点云的空间存取模型来组织数据点之间的拓扑关系，根据k近邻搜索算法与最小二乘法将待判断点与其k个点集拟合切平面。再通过点集在为切面上的投影计算出相邻向量夹角，根据设定阈值夹角判断条件进行取舍，最终达到提取边界点目的。裴书玉[9]首先采用移动最小二乘法进行法矢估计，然后将k邻域法矢夹角的均值作为点的显著性指标进行特征点判别，最后对特征点进行下采样得到清晰完整的特征线。石波和卢秀山[10]提出基于kd-tree在不知道点云之间的拓扑关系时快速确定某一点及其周围邻域，并计算该点法向量，利用建筑物的平面特征对先验知识即共向性条件和共面性条件改进，根据法向量相似性实现了散乱点云的平面分割。杨必胜等人[11-13]引入自适应邻域法避免了点云密度变化带来的影响，提出除了法向量和主方向的几何特征外增加了维数特征以精确计算每个扫描点的几何特征，兼顾了几何特征和强度信息的最优，综合建筑物立面语义知识，提高了对复杂区域内不同地物提取的完整性和精確度。

众多研究表明，基于点云的边界提取成为人们研究的重点，因其不需提前构建三角格网步骤，只需直接针对点云进行边界点提取。基于对海量点云的特征轮廓提取，考虑到研究区扫描对象种类丰富且形状不一以及算法的时间效率。因此，在分析上述算法的基础上，本论文的总体研究目标是：以移动背包三维激光扫描系统一个行走轨迹的原始点云为单位，从采用随机抽样一致性算法（RANSAC）的整体分割到基于主成分分析法（PCA）的局部提取的思想，探讨一套适合城市常见地下建、构筑物特征保持的海量三维点云数据精简方法。

1  算法概述

本文基于海量三维点云数据，并考虑到后期应用于三维建模的点云数据需具有针对性和高效性，提出基于地下管廊特征保持的三维点云数据精简方法，该方法在剔除大量数据的前提下保持了原有特征轮廓。流程图如图1所示，主要步骤如下：

（1）原始点云数据的生成，明显噪声的剔除;

（2）基于RANSAC算法，通过阈值t和最小N的确定对原始点云分割，得到如顶、墙、地面等包含了特征轮廓的整个面状点云数据;

（3）对分割后的面状点云数据构建kd-tree空间索引，利用最邻近点搜索算法，对k个邻近点进行搜索，利用主成分分析法（PCA）实现数据的降维，将邻近点投影到投影面上，通过判断相邻向量夹角最大角度差与设定角度阈值的大小关系从而确定数据的特征轮廓。

1.1  基于RANSAC的点云分割

1.1.1  RANSAC算法基本思想

随机抽样一致算法（RANdom SAmple Consensus，RANSAC），它可以通过迭代方式从一组包含正确数据和离群数据（噪声）的观测数据集中鲁棒的估计数学模型参数，从而区分出“inliers”（局内点）和“outliers”（局外点）。该算法最早由Fischler和Bolles于1981年提出。是数据处理的一种经典算法，其作用是在大量噪声情况下，提取物体中特定的成分。RANSAC算法的核心思想是其非确定性，在某种意义上说，它会产生一个在一定概率下合理的结果，其允许通过提高迭代次数来提高概率从而得出一个合理的结果。RANSAC算法也有不足之处，其迭代次数没有上限，因此参数计算结果的好坏会受到迭代次数设置的影响，并且它要求设置跟问题相关的阈值。

1.1.2  平面拟合步骤及参数确定

利用RANSAC算法对点云进行平面拟合，其详细步骤为：

（1）在原始点云数据中随机选取3个不共线的点（两两斜率相同即共线）;

1.2  基于PCA的特征提取

主成分分析方法（Principal Component Analysis，PCA），是一种数据降维算法，其目的是对冗余的数据特征进行降维处理的同时保留数据最重要的一部分特征，使其主要的特征成分最大的保持整个数据信息完整性。PCA的主要思想是在原有的n维特征基础上将k维正交特征即主成分映射出来，通过计算数据集的协方差矩阵得到相应的特征值和特征向量，按特征值最大将k个维度的特征值对应的特征向量排序（最大特征值即最大方差，其反映了数据的最重要的信息），因此就将n维数据矩阵转换到了k维数据矩阵中，实现了数据特征的降维。算法步骤如下：

（5）如图所示，根据k个投影点所构成的相邻向量夹角 排序，将邻近向量夹角差值的最大值和角度阈值AngleThreshold对比，根据经验阈值，邻近向量夹角差值的阈值近似于90°，最终将阈值确定为90°。若最大值大于等于阈值，该点为边界点;若最大值小于阈值，该点为非边界点。投影面上的边界点判断如图2所示。

2  实验与分析

2.1  背包数据

本次试验采集数据设备为Leica Pega-sus：Backpack移动背包三维激光扫描系统，集成了GNSS技术、惯性导航技术和SLAM技术于一体，其中GNSS可接收GPS、GLONASS、Galileo及北斗卫星信号，能够实时确定室内室外场景的仪器所处位置及姿态，2个激光扫描仪和5个相机能够快速准确的获取室内外的三维点云数据以及全景照片的采集，并结合轨迹数据解算，实现三维点云数据的高精度自动拼接。该设备可由人员背负或者在车上搭载，在采集数据过程中可以根據环境条件和采集需要随时上下移动，对于人员能经过的地方都能进行数据采集，对工作环境要求低，适应性强，真正实现“走哪测哪、实景再现”。

研究区为某地下管廊，为了能获得更精确的数据，背包采用Fused SLAM模式，该模式通过1个或多个GNSS基准站的架设来进行数据后处理差分解算，以实现室外及室内外一体化的数据采集。室外环境下主要使用GNSS/INS组合的轨迹定位模式，从室外进入室内的过程中，系统将室外的时空基准传导到室内。在此基础上，室内环境下的数据采集主要使用Lidar/INS组合的轨迹定位模式。固背包获取POS数据后要进行轨迹以及SLAM的解算以得到原始点云数据，之后在ReCap里删除明显离群噪声点，最后共保留1526615个数据点。如图3所示。

2.2  基于RANSAC分割

本次试验平台为Win7 64位操作系统，主要硬件配置为Inter core i5 2.8GHz，12 GB内存。算法基于点云库PCL 1.8.0（Point Cloud Library）在Visual Studio2013中实现。根据需要设置分割阈值，如图4阈值设置不合理造成过分割现象。本试验采用阈值t=0.034，采样分辨率为0.068，至少有一个数据基本子集包含的数据全部是局内点数据的概率大于99%时，迭代次数M应为1000次[15]。地下管廊内部环境特征丰富，包括支撑架、通风口、投料口、防火门等，固设置保留最小面状点云数据个数为2000，判断参与拟合模型的点数是否大于2000，若大于，则认为得到正确的数学模型参数，停止迭代。经RANSAC分割后仅保留能反应管廊特征轮廓面上的点云数据，共保留9个面388363个数据点，如图5所示。

2.3  基于PCA的特征提取

（1）建立空间索引

三维激光扫描点云数据是一种散乱、无序的表面的海量点集合，并不具备传统实体网络数据的几何拓扑信息，这种大数据量且分布不均匀点云数据点云数据给后续处理带来一定难度。尤其是在对点云数据进行处理时往往需结合其近邻点而无法根据单个点坐标进行处理判断，这一过程涉及到点云近邻点查询。所以点云数据处理最核心的问题，就是建立离散点间的拓扑关系，以便将点云数据进行合理组织，从而实现基于邻域关系的快速查找。构建点云数据空间索引在点云数据处理中已有广泛应用，比较有代表性的包kd-tree和oc-tree。kd-tree在不知道点云数据之间的拓扑关系时能快速确定散乱点云中判断点的某一邻域，特别在点云数量増加到百万级别以上，快速获取近邻点时对算法的耗时要求就高，此时优先选择kd-tree效率更高[16]。故本文采用 kd-tree建立三维数据点之间的拓扑关系，进而找出各数据点的k近邻。

kd-tree（k-demension tree）是从BST（Binary Search Tree）发展而来，也是二叉树的一种分割k维数据空间的高维索引树形数据结构，对一个三维空间，kd-tree按照一定的划分规则将多个点划分为节点空间，划分规则通常是根据距离的平方作为划分权重，即根据距离权重的二分法形成的树结构，目的用于快速查找一个指定点的邻域的其他点的信息。如图6所示。

基于点云构造kd-tree的方法如下：在树的根部，所有子节点在第一个指定的维度上被分开，也就是说把制定维度的点放在根上，在指定的第一个维度中坐标小于根节点的点将被分在左边的子树中，大于根节点的点将分在右边的子树中。树的每一级都在下一个维度上分开，所有其它的维度用完之后就回到第一个维度。然后重复这个过程，直到准备分类的最后一个分类仅仅由一个点组成。随着树的深度增加，循环的选取坐标轴，如根节点选取x轴，根节点的子节点选取y轴，再下一个节点选取z轴划分，三个维度划分完继续循环下去，直到叶子节点出现，即kd-tree构建结束。如图7所示。

（3）基于点云库PCL采用PCA算法实现对分割后面片上的388363个点云（如图9所示）的特征轮廓提取。根据先验知识k值的选取在10-30之间为最佳[17]，取决于点云的密度，当数据密度大时可以取小些，数据比较稀疏时该值可以取大些。设定最优的k值是接下来特征轮廓提取的第一也是关键一步。k值的大小与邻近点的数量成正比，设置的越小，邻近点包含的信息就越少，达不到特征轮廓判断的要求，如图10所示，提取轮廓特征点数为25148个，程序运行时间为189.38秒;反之设置的越大，邻近点包含的信息越多，对特征轮廓造成错判断，并且对算法效率大大降低，如图11所示，提取轮廓特征点数为7490个，程序运行时间为653.42秒。

最佳提取结果如图12所示，当k为15时，提取轮廓特征点共12414个，程序运行时间为278.20秒。所提取点云数据在剔除了大量数据的前提下很好的保留了管廊的特征轮廓。把所提取的特征轮廓与原始点云套合比对如图13所示，发现所提取数据能很好地反应原始点云的特征轮廓。

3  結束语

移动背包三维激光扫描系统其采集对象距离更近，数据精度、数据量总量、数据密度等也都相应比较高，能弥补传统测量方式在作业时因室内环境的复杂度与空间局限性受到诸多限制，做到无死角测量，已成为一种快速的空间数据获取手段。本文基于城市地下管廊提出了一套特征轮廓提取的方法，其中RANSAC算法的优点在于它的抗噪性，能从包含大量噪声的点云中估计出高精度的数据。而利用PCA算法在进行局部提取并计算特征值的过程中能很好的降低算法的计算开销，为后期的三维模型建立提供了很好的数据基础。一方面对点云数据进行了精简，去除点云数据中大量冗余数据，使数据占用更少的存储空间，提高了利用率。另一方面提取的特征轮廓与原始点云能准确符合，在数据应用于三维重建时，可以快速准确重建扫描对象，提高整个重建过程的效率。

本文提出的特征轮廓提取方法适用于地下管廊及其相似的地下建构筑物等某一特定区域内的研究对象特征轮廓的提取，对于提取对象种类丰富，特别是一些精细对象的特征轮廓提取还需要人工的大量干预，因此在之后研究工作中，充分合理利用点云的几何特征、颜色信息、照片信息、强度信息、密度信息等，建立多源数据下的自动化特征轮廓提取算法，实现在地理场景采集的点云数据最终用少而有效的点描述扫描对象。

参考文献

[1] M J Milroy， C Bradley， GW Vickers. Segmentation of a wrap- around model using an active contour[J] . Computer-Aided Design， 1997， 29（4）： 299-320.

[2] 王永波， 盛业华. 一种基于曲率极值法的LiDAR点云特征提取算法[J]. 中国矿业大学学报， 2011， 40（04）： 640-646.

[3] Pauly M， Keiser R， Kobbelt L P， et al. Shape modeling with point-sampled geometry[J]. ACM Trans Graph， 2003， 22（3）： 641-650.

[4] Abdalla Alrashdan， Saeid Motavalli， Behrooz Fallahi. Automatic segmentation of digitized data for reverse engineering applications[J]. IIE Transactions（2000）32： 59-69.

[5] Rabbani T， Van Den Heuvel F， Vosselmann G. Segmentation of point clouds using smoothness constraint[J]. International Archives of Photogrammetry， Remote Sensing and Spatial Information Sciences， 2006， 36（5）： 248-253.

[6] Tarsha Kurdi F， Landes T， Grussenmeyer P. Hough-Transform and extended ransac algorithms for automatic detection of 3D building roof planes from LiDAR data [J]. International Archives of Photogrammetry， Remote Sensing and Spatial Information Systems， 2007， 36： 407-412.

[7] 邓博文， 王召巴， 金永， 等. 基于形态学梯度的激光扫描点云特征提取方法[J]. 激光与光电子学进展， 2018， 55（05）： 239-245.

[8] 孙殿柱， 范志先， 李延瑞. 散乱数据点云边界特征自动提取算法[J]. 华中科技大学学报（自然科学版）， 2008（08）： 82-84.

[9] 裴书玉， 杜宁， 王莉， 等. 基于移动最小二乘法法矢估计的建筑物点云特征提取[J]. 测绘通报， 2018（04）： 73-77.

[10] 石波， 卢秀山， 陈允芳. 基于kd-tree的建筑物散乱点云平面分割[J]. 测绘科学， 2008（01）： 135-136+250.

[11] 杨必胜， 董震， 魏征， 等. 从车载激光扫描数据中提取复杂建筑物立面的方法[J]. 测绘学报， 2013， 42（3）： 411-417.

[12] Yang B， Xu W， Dong Z. Automated extraction of building outlines from airborne laser scanning point clouds[J]. IEEE Geoscience & Remote Sensing Letters， 2013， 10（6）： 1399-1403.

[13] Yang B， Wei Z， Li Q， et al. Semiautomated building facade footprint extraction from mobile LiDAR point clouds[J]. Geoscience & Remote Sensing Letters IEEE， 2013， 10（4）： 766-770.

[14] 張蕊， 李广云， 李明磊， 等. 利用PCA-BP算法进行激光点云分类方法研究[J]. 测绘通报， 2014（07）： 23-26.

[15] 李娜， 马一薇， 杨洋， 高晟丽. 利用RANSAC算法对建筑物立面进行点云分割[J]. 测绘科学， 2011， 36（05）： 144-145+138.

[16] 刘艳丰. 基于kd-tree的点云数据空间管理理论与方法[D]. 中南大学， 2009.

[17] 钱锦锋， 陈志杨， 张三元， 叶修梓. 点云数据压缩中的边界特征检测[J]. 中国图象图形学报， 2005（02）： 164-169.

[18] 朱海德. 点云库PCL学习教程[M]. 北京航空航天大学出版社， 2012， 10.

[19] 王磊， 郭清菊， 姜晗. 基于改进的八叉树索引与分层渲染的海量激光点云可视化技术[J]. 软件， 2016， 37（3）： 114-117.

[20] 杜宇楠， 叶平， 孙汉旭. 基于激光与立体视觉同步数据的场景三维重建[J]. 软件， 2012， 33（11）： 1-5.

[21] 黄昉菀， 戴礼豪， 陈国龙， 等. 基于激光数据特征提取的一般环境下实时定位方法[J]. 软件， 2012， 33（5）： 9-11.