-
车载LiDAR(light detection and ranging)系统作为一种快速的空间数据获取手段, 广泛运用于数字城市、基础测绘、城市规划、道路改建等领域[1]。但车载LiDAR系统获取的数据具有海量特性, 数据调度耗时,无法快速定位并实时渲染作业区域的点云数据,大大降低了车载点云数据内业处理的效率。因此,针对车载海量点云数据的高效管理与可视化技术研究具有重要意义。
机载LiDAR数据一般采用分幅管理,通过构建四叉树索引结构完成数据动态调度[2-5]。随着地面三维激光扫描技术的发展,国内外学者对地面海量点云数据管理也进行了大量研究[6-9]。地面海量点云数据的处理大多根据测区进行管理,测区内数据采用基于八叉树的索引结构进行数据调度。目前对于车载点云数据管理的研究较少,实际应用中通常采用机载或者地面扫描数据的处理流程。但车载LiDAR数据分布不均匀,测区范围广,无论采用分幅式管理还是测区式管理效率都不高。且车载LiDAR数据包含丰富的侧面信息,浏览方向并不固定,采用四叉树索引结构不能满足这一需求,而基于地面扫描数据设计的八叉树存储结构也存在数据预处理时间长,数据更新困难等问题。
针对这些问题,为了更高效可靠地支持车载点云数据快速处理,本文提出一种适用于海量车载点云数据的管理调度和快速可视化的方法。
-
车载扫描系统获得的最终数据成果是记录点云数据文件(.las, .asc等格式),点云文件数据量大,数据导出耗时,难以从原始点云数据文件快速导出到目标区域并可视化。本文针对车载LiDAR数据的特点,提出了轨迹导航的管理方式,将原始点云数据分段后生成轨迹,并将分段数据的属性信息写入轨迹文件,便于数据快速导航。车载扫描系统在单位时间内获取的点云数据量基本相同。为了消除车辆在停车、慢速状态下的影响,保证清除冗余数据后每段点云数据量大致相等,本文以车辆行驶里程作为分段依据,每行驶1 km扫描获取的点云数据分为一段,并根据每段点云起始点和最终点的扫描时间在pos文件中插值生成该段点云的行驶轨迹,写入到shape file格式的矢量文件中,并且记录当前点云文件名、相邻点云文件名等拓扑关系,以满足快速导航的需求,生成的shp文件属性信息如图 1所示。最后,将生成点云轨迹和对应区域的正射影像(或地形图)叠加显示,通过正射影像快速定位目标区域,并选择目标区域的轨迹,即可根据轨迹属性信息快速调度出对应点云数据,如图 2所示。
-
尽管对点云数据文件进行了分段处理,但由于分段点云文件没有建立空间索引结构,在进行可视化浏览时仍然存在数据导入耗时长,渲染帧率低等问题。要解决点云数据快速查找的问题,必须建立与点云数据相适应的空间索引结构,并通过高效的索引查找方法实现点云数据的实时快速调度[10-13]。和地面激光扫描数据相比,车载扫描数据量更大,数据更新频繁,空间索引存储结构必须满足以下几个特点。
1) 预处理时间短。目前许多点云调度方法在生成点云索引结构的过程中耗时较长,车载点云数据量庞大,要提高数据处理效率,必须缩短预处理时间。
2) 支持数据快速更新。车载激光扫描在作业过程中经常会扫描到重复区域,数据更新频繁,目前大多点云索引结构生成之后往往不支持数据更新或者更新效率低。
3) 支持数据的并行访问和C/S架构模式。车载点云数据处理一般是多人协同作业,传统方法将数据拷贝到本机既耗时又浪费存储空间。因此,索引结构应满足C/S架构模式,数据都存放在服务器上,多台客户机能够同时访问操作。
为了满足上述几个条件,本文以八叉树索引结构为基础,借鉴了瓦片地图的思想,提出了一种基于文件夹的瓦片式多分辨率存储结构。
-
目前八叉树索引存储结构的主要问题是预处理时间长、更新困难、不支持并行访问等[14-18]。针对这些问题,本文提出了一种基于文件夹系统的瓦片式多分辨率存储结构。该方法以计算机中的文件夹系统来表示八叉树结构的节点,以文件夹目录的层级来表示八叉树结构的深度,并在节点文件夹中存放该节点包含的点云数据文件和节点属性文件。索引结构如图 3所示,文件名为0~7的文件夹表示该八叉树节点的子节点,.node格式文件记录了该节点的属性信息(如外包盒大小、当前深度、点云数目等),.pointcloud格式文件存储了属于该节点内的点云数据。采用这种方式进行数据存储,在数据预处理时只需将原始数据读取一遍,计算节点位置后写入到对应节点文件夹中即可,且各个节点中的数据存储相互独立,任意节点的数据更新都不会影响其他节点的数据。同时,这种瓦片式的结构也适用于C/S模式的软件架构,支持并行访问,很好地满足了高效管理调度车载点云数据的需求。
-
在设计好点云的存储结构后,需要对原始点云数据进行预处理,转换成具有空间索引信息的多分辨率存储结构。由于点云数据分段后每段文件大小固定,可以预先设定八叉树深度,能够显著提高预处理效率。具体步骤如下。
1) 原始点云数据预处理。与机载激光扫描不同,车载激光扫描数据中存在大量的重复扫描数据,这是由于扫描车载行驶过程中红灯、堵车、行驶轨迹重复等客观原因造成的。这类冗余数据对数据处理没有任何帮助,且占用了大量的存储空间。为了保证点云数据在空间上分布均匀,本文采用了曲率约束下的格网抽稀方法。该方法先求出点云数据的外包盒,将外包盒均匀划分为小立方体,小立方体的边长由车载扫描系统在最快行驶速度下的水平间隔和最远扫描距离处的竖直间隔确定,并计算每个点的近似曲率,曲率大于阈值的点为特征点,每个立方体中只保留一个非特征点和所有特征点,原始数据经过抽稀后既去除了大量冗余数据,又完整保留了点云的特征信息。
2) 计算存储分辨率。八叉树深度即为点云的存储分辨率,不同的八叉树层级存储了不同分辨率的点云数据。为了确保相同分辨率下节点大小基本相等,在计算外包盒最大边长后开始划分子节点,当子节点的外包盒边长在5~10 m之间时结束划分,此时的八叉树深度即为存储分辨率。
3) 计算节点位置。遍历去噪处理后的点云文件,逐点读入,根据点的坐标信息自上而下计算节点位置,计算公式见式(1)、式(2)。式中,(x, y, z)为点的三维坐标;(Xm, Ym, Zm)为节点中心坐标;(bx, by, bz)表示点在子节点中的位置;以节点中心为坐标原点,0表示负半轴,1表示正半轴,n为子节点编号。例如,八叉树深度为6,计算得到节点路径为0-1-5-3-4-6;则在计算机中寻找路径root\\0\\1\\5\\3\\4\\6,若该路径不存在,则新建节点路径,并创建点云文件,写入该点,并更新节点属性文件;若该节点路径已经存在,则直接将该点写入到点云文件中,并更新节点属性文件。
$$ \left\{ \begin{array}{l} {b_x} = \left\{ \begin{array}{l} 0,x < {X_m}\\ 1,{\rm{ }}x > {X_m} \end{array} \right.\\ {b_y} = \left\{ \begin{array}{l} 0,{\rm{ }}y < {Y_m}\\ 1,{\rm{ }}y > {Y_m} \end{array} \right.\\ {b_z} = \left\{ \begin{array}{l} 0,z < {Z_m}\\ 1,z > {Z_m} \end{array} \right. \end{array} \right. $$ (1) $$ n = {2^2} \times {b_z} + {2^1} \times {b_y} + {2^0} \times {b_x} $$ (2) 4) 更新子节点数据。通过步骤2),所有点云数据都分配到叶节点中后,以叶节点数据为基础,自下而上更新中间节点的数据(上层节点数据由下层节点数据抽稀获取),生成多分辨率的点云存储结构。
本文设计的瓦片式多分辨率存储结构不仅能有效满足点云数据的快速索引需求,这种节点数据独立存储的模式还支持点云数据的快速更新,同样也适用于B/S、C/S架构的数据调度模式。另外,本文对点云存储文件进行了无损压缩,由于切片后的点云文件小,解压速度快,能大大减少数据存储空间。
-
基于八叉树结构的点云多分辨率存储结构构建完成后,即可实现点云数据的快速渲染。在保证点云数据渲染流畅的前提下,为了最大程度地保证点云数据的渲染质量,本文在点云数据渲染过程中应用了视锥体裁剪技术(view frustum culling)和多线程动态调度技术。对于渲染过程中的每一帧,首先采用深度优先的递归遍历方法对八叉树节点进行遍历,判断节点是否在视锥体内。如果在视锥体内则计算投影面积,并将节点信息加入到优先队列中(根据节点在屏幕上的投影面积大小排序),同时数据读取线程从节点优先队列获取节点数据路径,读取节点点云数据并加入到渲染队列中,完成渲染。具体渲染流程如图 4所示。本文将所有视锥体内的节点根据投影面积进行排序并加入到优先队列中,优先读取和渲染投影面积较大的节点,通过这种方式可以有效地保证点云数据的渲染质量。
-
本文基于Visual Studio平台采用C++语言开发了车载点云数据综合管理平台Real Viewer,实现了车载点云数据的高效管理和快速可视化算法,算法运行平台为Windows 7 64位系统,主要硬件配置为Intel Core i7及4 GB内存。本文使用的实验点云数据由自主研发的车载激光扫描系统获取,采用Rigel VZ400的二维扫描模式,每秒扫描速度远远大于一般的线性扫描仪,一天的扫描数据量在几十GB左右(1 GB约4 000万点云)。本文取车载扫描系统一天的扫描数据作为实验数据,总数据量31.8 GB。
将点云数据处理生成轨迹文件并分段构建生成多分辨率存储结构后,导入车载点云数据综合管理平台。如图 5所示,下方为数据导航窗口,将车载轨迹和正射影像叠加显示后可以实现所有车载点云数据的快速导航,红色轨迹为所有车载扫描轨迹,黄色线段为当前浏览点云,点云数据在上方的点云渲染窗口中显示。
本文的多分辨率存储结构渲染过程如图 6所示,根据当前的视点位置和视场范围实时调度合适层级的节点数据。图 6显示了八叉树结构深度为3~6级的渲染效果。由图 6可知,本文算法在数据动态调度的过程中,帧率稳定在60帧/s,操作流畅,且能够拥有较高的数据渲染质量。
本文的多分辨率存储结构中的数据存储文件除了存储点云的坐标信息外,还支持点云其他属性的扩展(颜色、强度、法向量等),并能够根据不同需求改变渲染方式,除默认的高程伪彩色渲染外,还包括真彩色渲染和法向量伪彩色渲染,如图 7所示。
本文对车载点云数据处理前后的各项性能指标进行了统计分析,原始数据大小为31.8 GB,通过本文算法生成多分辨率存储结构后大小为5.6 GB,压缩率高达17%,大大减少了硬盘存储空间,预处理耗时35 min。每段数据(1 GB)的读取时间提高了8倍,每帧耗时为8 ms,渲染帧率为60帧/s,显著提高了作业过程中的流畅性。另外,也和开源海量点云处理软件XGRT以及免费点云浏览软件Quick Terrain Reader(QT)进行了性能对比,各项性能统计对比见表 1,本文算法在数据存储大小、每段数据读取时间、内存占用量等方面优势明显。
表 1 本文算法性能统计
Table 1. Performance of Localization Algorithms
数据大小/GB 读取时间/s 预处理时间/s 内存占用 选点耗时/s 原始数据 31.8 16.8 0 1.1 GB 0.2 QT 31.8 16.8 0 1.1 GB 0.01 XGRT 48 1.5 18 000 300 MB 0.8 本文算法 5.6 1.0 2 100 < 300 MB 0.01 本文提出的点云多分辨率存储结构是基于文件夹系统的切片式存储结构,不仅能够满足本地点云数据的快速调度与可视化,同样也适用于基于B/S、C/S架构的软件模式,支持多用户同时访问同一段数据。图 8为本文的点云数据组织方法在街景平台和3DGIS平台中的应用。
-
为了满足车载海量点云数据的快速调度与处理需求,本文提出了一种新的适用于车载海量点云的数据组织方法,并在该组织方法的基础上实现了高效的点云数据渲染。实验证明,本文的数据组织方法不仅能够实现点云数据的快速导航,且支持数据的快速更新和并行访问,并在数据预处理时间、占用存储空间、数据读取时间、渲染帧率等方面做出了大量优化,大大降低了数据调度时间,提高了数据可视化速度,实现了车载点云数据的高效管理和快速可视化,从而提高了车载点云数据内业处理的生产效率。
-
摘要: 为了支持车载移动激光扫描点云数据的高效管理与快速可视化,提出了一种适用于车载海量点云的数据组织方法。该方法将原始点云数据分段后生成轨迹信息用于快速索引,分别对每段数据建立基于八叉树结构的LOD(levels of detail)索引,并采用多线程动态调度技术实现基于视点的海量点云渲染与漫游,显著提高了车载点云数据的调度效率。实验结果证明该点云数据组织方法是一种适合车载点云数据的高效管理方法。Abstract: This paper proposed an organization method of laser point cloud data for the efficient management and rapid visualization of the massive point cloud data of vehicle-mounted laser scanner. In this paper, both the original point cloud data and its trajectory are sectioned for the fast indexing firstly, then the LOD(levels of details) index of each section is build based on octree structure. With a tile type and multiresolution storage mode based on folder system, the depth of octree structure is represented by the level of folder directory, and in every node folder, the corresponding point cloud data file and its node properties file are both include. The storage method of this paper decreases the preprocessing time greatly and can support concurrent access owing to mutually independence of each node. Moreover, with the application of view frustum culling technology and multi-thread dynamic dispatch technology, the rendering and roaming of massive point cloud can realize real time updating according to viewpoint change, which significantly improves the dispatch efficiency of vehicle-mounted laser point cloud data. In the experiment, our method was compared with several popular software of point cloud data processing (e.g. XGRT, Quick Terrain Reader) on the data dispatch. The results show our method has obvious advantage on storage capacity, data access time, memory footprint, rendering frame rate and so on, it indicates our method is effective for the management of vehicle-mounted laser point cloud data and can improve the production efficiency for indoor-work of vehicle-mounted laser point cloud data processing.
-
Key words:
- mobile laser scanning /
- octree /
- point cloud data management /
- visualization /
- mobile mapping system
-
表 1 本文算法性能统计
Table 1. Performance of Localization Algorithms
数据大小/GB 读取时间/s 预处理时间/s 内存占用 选点耗时/s 原始数据 31.8 16.8 0 1.1 GB 0.2 QT 31.8 16.8 0 1.1 GB 0.01 XGRT 48 1.5 18 000 300 MB 0.8 本文算法 5.6 1.0 2 100 < 300 MB 0.01 -
[1] 魏征. 车载LiDAR点云中建筑物的自动识别与立面几何重建[D]. 武汉: 武汉大学, 2012 http://cdmd.cnki.com.cn/Article/CDMD-10486-1013151916.htm Wei Zheng. Automated Extraction of Buildings and Facades Reconstructon from Mobile LiDAR Point Clouds[D].Wuhan:Wuhan University, 2012 http://cdmd.cnki.com.cn/Article/CDMD-10486-1013151916.htm [2] Ma Hongchao, Wang Zongyue. Distributed Data Organization and Parallel Data Retrieval Methods for Huge Laser Scanner Point Clouds[J]. Computers & Geosciences, 2011, 37(2):193-201 http://www.sciencedirect.com/science/article/pii/S0098300410002694 [3] 支晓栋, 林宗坚, 苏国中, 等.基于改进四叉树的LiDAR点云数据组织研究[J].计算机工程与应用, 2010, 46(9):71-74 http://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201009021.htm Zhi Xiaodong, Lin Zongjian, Su Guozhong, et al.Data Organization Based on Modified Quad Tree for LiDAR Point Cloud[J].Computer Engineering and Application, 2010, 46(9):71-74 http://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201009021.htm [4] 黄先锋, 陶闯, 江万寿, 等.机载激光雷达点云数据的实时渲染[J].武汉大学学报·信息科学版, 2005, 30(11):975-978 http://ch.whu.edu.cn/CN/abstract/abstract2317.shtml Huang Xianfeng, Tao Chuang, Jiang Wanshou, et al.Real Time Display for Airborne LiDAR Point Cloud Data[J]. Geomatics and Information Science of Wuhan University, 2005, 30(11):975-978 http://ch.whu.edu.cn/CN/abstract/abstract2317.shtml [5] 杨建思.一种四叉树与KD树结合的海量机载LiDAR数据组织管理方法[J].武汉大学学报·信息科学版, 2014, 39(8):918-922 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201408007.htm Yang Jiansi.A Method Combing the Model of the Global Quadtree Index with Local KD-Tree for Massive Airborne LiDAR Point Cloud Data Organization[J]. Geomatics and Information Science of Wuhan University, 2014, 39(8):918-922 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201408007.htm [6] 谢洪, 吴博义, 赵展.一种新的海量点云数据管理方法研究[J].遥感信息, 2013, 28(6):26-32 http://www.cnki.com.cn/Article/CJFDTOTAL-YGXX201306005.htm Xie Hong, Wu Boyi, Zhao Zhan.A Novel Organization Method of Massive Point Cloud[J].Remote Sensing Information, 2013, 28(6):26-32 http://www.cnki.com.cn/Article/CJFDTOTAL-YGXX201306005.htm [7] Palarola R.Stream-Processing Points[C].The Conference on Visualization'05, Minneapolis, USA, 2005 [8] Wand M, Berner A, Bokeloh M, et a1.Processing and Interactive Editing of Huge Point Clouds from 3D Scanners[J].Computers&Graphics, 2008, 32(2):204-220 http://www.sciencedirect.com/science/article/pii/S0097849308000253 [9] Elseberg J, Borrmann D, Nüchter A.One Billion Points in the Cloud-An Octree for Efficient Processing of 3D Laser Scans[J].ISPRS Journal of Photogrammetry and Remote Sensing, 2013, 76:76-88 doi: 10.1016/j.isprsjprs.2012.10.004 [10] 路明月, 何永健.三维海量点云数据的组织与索引方法[J].地球信息科学, 2008, 10(2):190-194 http://www.cnki.com.cn/Article/CJFDTOTAL-DQXX200802013.htm Lu Mingyue, He Yongjian.Organization and Index Method for 3D Point Cloud Data[J].Earth Informatation Journal, 2008, 10(2):190-194 http://www.cnki.com.cn/Article/CJFDTOTAL-DQXX200802013.htm [11] Wand M.Point Based Multi-resolution Rendering[D].Germany:University of Tubingen, 2004 http://www.dissertation.com/abstracts/1105157 [12] 廖丽琼, 白俊松, 罗德安.基于八叉树及KD树的混合型点云数据存储结构[J].计算机系统应用, 2012, 21(3):87-90 http://www.cnki.com.cn/Article/CJFDTOTAL-XTYY201203020.htm Liao Liqiong, Bai Junsong, Luo De'an. Integrated Point Cloud Storage Structure Based on Octree and KDTree[J]. Computer Systems & Applications, 2012, 21(3):87-90 http://www.cnki.com.cn/Article/CJFDTOTAL-XTYY201203020.htm [13] Gobbetti E, Marton F, Iglesias G, et a1. A Single-pass GPU Ray Casting Framework for Interactive Out-of-Core Rendering of Massive Volumetric Datasets[J]. Visual Computing, 2008, 24:797-806 doi: 10.1007/s00371-008-0261-9 [14] Mehra R, Tripathi P, Sheffer A, et al.Visibility of Noisy Point Cloud Data[J].Computers & Graphics, 2010, 34(3):219-230 http://graphics.stanford.edu/~niloy/research/robustPointVisibility/robustPointVisibility_smi_10.html [15] Gong Jun, Ke Shengnan, Zhu Qing, et al.An Efficient Point Cloud Management Method Based on a 3D R-Tree[J].Photogrammetric Emgineering & Remote Sensing, 2012, 78(4):393-381 [16] Ravada S, Horhammer M, Baris M K.Point Cloud:Storage, Loading, and Visualization[C].National Science Foundation Tera Grid Workshop on Cyber-GIS, Washington DC, USA, 2010 [17] Boubekeur T, Schlick C.Interactive Out of Core Texturing with Point-sampled Textures[C].The 3rd Eurographics/IEEE VGTC Conference on Point-Based Graphics, Switzerland, 2006 [18] Luebke D, Watson B, Cohen J.et al.Level of Detail for 3D Graphics[M].USA:Elsevier, 2003 -