海量车载激光扫描点云数据的快速可视化方法

1、海量车载激光扫描点云数据的快速可视化方法激光扫描系统能够直接获取被测目标表面的三维空间坐标，具有采样密度高、点云分 布密集等特点，正逐渐成为三维空间信息快速获取的主要手段之一，被广泛应用于文物保 护、三维重建、数字地面模型生产、城市规划等领域 1 。现代车载激光扫描系统，通常 安装多个激光扫描头采集三维点云数据，如Optech 公司的 LYNX 系统,Riegl 公司的 VMX-450 系统。车载激光扫描系统沿着某一轨迹采集数据，多个高频采样激光头数据相互叠加， 产生海量三维点云数据，其数据量随着轨迹的延长而线性增加。例如，VMX-450 系统在约一个小时内，可获取 40 km 左右长度的点云

2、数据，数据量高达1 TB。对于车载激光扫描系统采集的海量三维点云数据，单在数据量方面即对后续数据处理 （ 如点云滤波、分割，目 标识别，三维重建和可视化等 ）带来巨大的挑战。为实现海量点云数据的空间分析及可视 化，需要实时、高效地完成点云数据的调度和查询工作。空间数据的调度，关键在于数据 的索引与检索，索引的性能优劣直接影响到系统的效率和分析能力。因此，如何建立合理 的空间索引机制，是解决海量空间数据组织和快速调度的关键问题。许多标志性索引方法 已被广泛应用于空间数据的检索、查询、存储以及管理，如四叉树2、R 树3,4、R*树5 和八叉树 6 等。在地理信息系统中，支持二维空间数据的索引方法已

3、非常成熟。但是，随着三维点云 数据的广泛应用，迫切需要在虚拟地理环境下可视化全部三维点云数据。在三维点云数据 可用性不断增强的驱动下，出现了一些具有可视化和三维点云数据管理功能的商业软件 7,8 。然而， QuickTerrain Reader 、 Point Tools 等商业点云处理软件对载入点云数据量有严格限制，不支持车载海量激光点云数据的实时三维可视化，从而引发了完善三维 激光点云数据空间索引方法的热潮。R 树或 R*树的每个子块包含一个对象，这些子块可以彼此重叠。文献9提出利用三维 R 树结构管理虚拟环境下的三维建筑物。文献 10 提出使用三维 R 树结构快速索引激 光点云数据。但是

4、，如何有效解决 R 树子块重叠是三维点云数据管理尚未解决的问题。四 叉树索引是一种基于树的空间索引，它按照一定的规则，将已知范围的空间递归地均分成 4 个部分，直到每个子块满足条件为止 11 。文献 12 提出了一种基于四叉树的三维点云 渲染方法，此方法在假设连续点属于同一条扫描线的前提下，只存储每个叶子节点内的点 的位置以节省存储空间。但是，这种方法无法对多扫描仪获取的无序点云建立索引。 八叉 树作为四叉树的3D扩展亦被广泛应用于三维数据索引。文献13提出了基于八叉树的三维点云数据的多尺度可视化方法。文献 14 提出了一种开源的八叉树点云数据索引标准数 据格式，并测试其在海量点云特征提取算法

5、方面的适用性。文献 15 通过哈希表数据结构 优化八叉树结构，实现三维点云数据的快速检索。文献 16 设计了一种基于外存的多分辨 率数据结构，实现了海量点云数据的实时可视化与交互编辑。一般情况下，基于八叉树的树结构比较适合处理三维点云数据，并且该方法有现行开源标准数据格式14 。但是，对车载激光扫描系统采集的三维数据使用八叉树索引具有分布不均等缺点，会出现大量空 的叶节点。这直接造成了点云存储空间的低利用率，并且增加了空间数据查询的复杂度。 相比四叉树结构，八叉树结构需要更多的存储空间，更难实现。快速检索算法通常需要耗费较大的存储空间，在时间和空间之间不能保持一个合理的平衡。KD 树索引在邻域

6、查找效率方面优于八叉树、四叉树以及R 树、R*树索引结构，常被用于单个激光点相邻区域点云数据查找，但对于海量点云数据存储管理与实时可视化，其邻域关系的重建将耗费大量的 计算资源，整体效率低于八叉树索引结构 14,17 。本文提出了一种基于内外存调度的海量三维点云数据管理与实时可视化方法，用户在 台式计算机或网络环境下可以流畅地检索和可视化三维点云。由于区域四叉树是最重要、 应用最广泛的四叉树表示法 18 ，对几何空间的划分没有重叠，通过特定的编码可以快速 查找几何区域所在的行列，同时还可以根据空间对象的稠密程度来确定空间数据的分辨率。 因此，本文在解决海量三维激光点云数据的可视化时，采用双层区

7、域四叉树方法对数据建 立索引，实现海量激光点云数据的管理与动态调度。1 内外存调度的海量点云可视化区域四叉树是将有边界的几何空间划分为连续的4 个相同大小的区域，递归划分该区域为 4 个相同大小的较小的区域，直到得到的区域仅包含 一个几何对象 （见图 1） 。若被划分区域根据相应的判别条件被判别为最小划分单元，那么 该区域将不再继续划分。图 1 四叉树平面分割及其结构图 Fig. 1 Quad-Tree Plane Segmentation and its StructureDiagram图选项激光扫描点云数据处理的首要步骤就是三维点云数据的检索和可视化。海量点云数据 处理的一个难点是如何克服

8、台式计算机有限的内存存储空间。为实现三维点云数据的快速 可视化，本文提出的方案满足以下条件：1）利用高效的数据索引快速检索点云数据；2）将点云数据从外部磁盘动态加载到计算机的主存储器中；3）多细节层次 （levels of detail,LoD） 可视化三维点云。1.1三维点云的双层四叉树索引方法车载激光扫描系统采集的三维点云一般存储在LAS 文件中19，该文件记录每个激光点的坐标和强度。存储千万点级别的LAS 文件可能达到 GB 级。车载激光扫描系统通常沿着某一轨迹（街道、高速公路等）采集三维点云。获得的三维点云可能覆盖了一个较大的范围区域，而其中仅有一小部分区域包含点云数据（ 见图 2）。

9、图 2 车载激光扫描系统采集的激光点云 Fig. 2 A Snapshot of MMS Collecting Point Clouds图选项激光扫描的目的不仅仅是进行可视化，为了使获取的三维激光扫描数据具有较好的查 询性能，应该对点云数据进行有效的管理和检索。但是，如果建立四叉树、 R 树或者八叉 树来索引 LAS 文件中的点云数据，将会导致大量空的叶节点和无效的存储空间。为了解决 这一难题，首先将三维点云沿着扫描路径分成一系列连续区域块，每块仅包含一部分数据。 这样可以通过减少空的叶节点来节约索引文件的存储空间，并有效减少索引树高度，可提 高检索性能以及点云加载的速度。本文提出的方法首先将

10、采集到的三维点云分割成连续的矩形块，对每个矩形内的点用 区域四叉树进行索引，然后对全部矩形块进行四叉树索引。利用双层四叉树结构组织三维 点云的关键步骤为：1）设置最小矩形块的大小（比如 300 mx200 m）。当前车载激光扫描仪的最大扫描范 围约为 150 m。2）采用内存映射文件技术访问磁盘上的LAS 数据文件，实现 LAS 数据的分块读入，分块建立四叉树并记录每块的空间范围，不对LAS 文件执行直接 I/O 操作或内容缓存，降低应用程序对操作系统的内存需求。3）构建四叉树文件索引所有的矩形块，建立树的集群，并按照树之间的相互关系建 立统一的数据检索入口 （见图 3）。图 3 三维点云的双

11、层四叉树结构 Fig. 3 A Two-Level Quad-Tree Data Structure for 3D PointClouds图选项4）存储每块数据文件和相关联的四叉树索引文件。双层四叉树结构由上述 4 个步骤完成 （见图 3）。第一层四叉树管理所有的矩形块，第 二层四叉树管理每个矩形块内的数据点。与LAS 文件相比较，每个数据块只包含一小部分点云数据，存储体积小，能够快速地从硬盘加载到计算机主存储器中。数据块之间无块间 数据内容关联，搭建索引服务器亦可实现海量点云文件的分布式存储管理。1.2三维点云的动态加载由于计算机内存的限制，无法一次性将所有矩形块内的点云 数据加载到计算机主

12、存储器中。可视化的首要步骤是判别可见或近可见的矩形块，然后， 判断当前视景体中的激光点集。矩形块的可见性与用户在三维场景中的视景体范围相关， 一旦确定了视景体的覆盖范围，依据构建的第一级四叉树结构，就可判断出可见矩形块。 最后加载可见矩形块中的激光点到计算机主存储器，以便进一步的可视化。当用户以漫游方式浏览三维点云时，矩形块的可见性发生快速变化，近可见的矩形块 从磁盘加载到主存储器中，不可见的矩形块从主存储器内删除。不同矩形块之间的平滑过 渡至关重要，否则，很难实现海量点云数据的快速可视化。为了满足这一要求，设计邻近 矩形块缓存机制，通过快速检索并加载可视和近可视点到可视化缓存区完成视点移动中

13、的场景平滑过渡。在加载过程中，分配B1 和 B2 两个缓存区。缓存区 B1 存储可见矩形块中的点云，缓存区 B2 存储近可见矩形块中的点云。当可见矩形块变为不可见时，缓存区B2与内存交换以实现可视化；缓存区 B1 和缓存区 B 2 内的点云轮流交换到视频内存，从而进 行不同矩形块之间的平滑过渡。1.3 LoD 可视化与地形 LoD 可视化相比，三维点云的 LoD 可视化要简单得多。由于每 个矩形块都有限定范围，以计算得到的可见矩形块到视点的距离以及可视叶节点到视点的 距离作为选择三维点云 LoD 层次的依据。本文方法将计算得到的距离分成6 个区间，分别为 0 m,100 m 、100 m,30

14、0 m 、300 m,700 m 、700 m,1 500 m 、 1 500 m,2500 m、2 500 m,+。对可视叶节点内的点云数据根据距离间隔进行采样。设计位于6 个间隔区间内的激光点分别按原始点的100%、 90%、 80%、 70%、 50%和 40%进行采样，从而在保证运行效率的前提下实现无明显变化的动态渲染。该方法实现动态LoD 是空间点云密度自适应的，用较高的密度渲染较近的点，用较低的密度渲染较远的点，从而形成对场景的 分层表达。2实验与分析本文利用 C+语言实现海量车载激光扫描点云数据的快速索引、动态调度以及 LoD 场景表达，利用 OpenGL 渲染机对场景进行绘制。

15、实验数据为海南某高速公路3.7 千万个车载激光扫描点。实验环境为In tel Core i7 870(2.93 GHz)处理器、3 GB 内存、GT220 显卡。为验证算法性能，将本文算法与海量激光点云索引管理与八叉树索引方 法14进行对比。八叉树索引方法的实现使用其提供的开源软件包 3DTK20。索引建立阶段，对原始点云文件创建双层四叉树索引并存储为文件，用于管理三维点 云数据。本文四叉树索引方法与八叉树索引方法在建立文件索引耗时、耗内存方面进行比 较的结果如图 4 所示。八叉树索引方法14耗费最大内存 2.1 GB，消耗时间为 559 s。双 层四叉树索引耗费最大内存为 1.3 GB，消耗

16、时间只需 337 s。双层四叉树结构较八叉树结 构简单，计算复杂度小，在同等代码实现效率下，四叉树索引在构建速度方面明显优于八 叉树。在计算资源消耗方面，八叉树索引方法需要把全部点读入内存后才能建立八叉树， 数据大小与消耗内存呈线性关系，构建索引内存消耗随数据量的增加而升高。本文提出的 双层四叉树方法在内存消耗上呈连续马鞍状，内存消耗峰值稳定，不随数据量的增加而不 断上升，优于八叉树索引方法。本文方法建立索引内存消耗可控，使用双层四叉树方法结 构建立索引需要消耗的内存与点云数据大小无关，具有对超内存存储量点云数据建立数据 索引的能力。图 4 建立数据索引消耗的资源与时间比较 Fig. 4 Co

17、mparison of Time and RamConsumptionat Building Index Stage图选项在数据浏览阶段，本文方法与 Elseberg 八叉树索引方法内存消耗比较如图 5 所示。 基于八叉树索引的方法消耗的内存为492 MB,使用本文方法消耗的内存约为50 MB。本文方法不用把数据一次性读入内存，内存消耗较少。由于八叉树索引为整体索引结构，需要 一次性读入全部数据，数据大小与消耗内存以及读入时间成线性关系。当输入数据过于庞 大时，基于八叉树的方法无法载入数据或载入速率非常缓慢。图 6 为利用本文方法与基于 八叉树的方法在浏览帧率方面的比较。双层四叉树索引结构、多线程动态数据调度以及LoD 技术的综合使用降低了海量激光点云数据可视化对硬件带来的压力，浏览帧速度大幅 度优于八叉树索引方法。图 5 数据漫游内存消耗比较 Fig. 5 Comparison of Data Roaming Ram Consumption图选项图 6 数据漫游帧率比较 Fig. 6 Comparison of Rendering Performance图选项图 7 为三维点云动态可视化例图。实验证明，本文提出的方法在内存消耗和可视化速 度方面有较好的性能，更有利于海量点云数据的实时可视化。与八叉