1 引 言

欧洲空间数据研究组织EuroSDR指出三维城市建模能力需要具备高覆盖度、高逼真度和高更新率,意味着对三维城市建模技术提出更好、更快、更廉价和更智能的要求,而这恰恰是传统三维建模手段的弱项^[1]。三维激光扫描技术和多角度摄影测量密集匹配技术为三维建模旺盛需求和有限人力物力资源间的冲突提供解决方案。RIEGL的VMX-250、TopCon的IP-S2和Optech的Lynx已是实际运行的移动测图系统^[2]。最新的移动测图系统装备多个激光扫描仪,动态获取厘米级密度的海量三维激光点云,精度可达5 cm^[3]。移动测图系统的原始数据采集率为360 GB/h,假设以30~40 km/h行驶,每千米道路数据采集量为10 GB,一个小城区的数据采集量可能高达若干TB,前所未有的数据采集速度和高分辨率要求对三维激光点云数据高效管理面临更为严峻的挑战^[4]。

随着高分辨率车载激光扫描系统的普及应用，大量散乱点云数据的快速处理成为国际研究的焦点。点云数据后处理如简化滤波、语义分割和特征提取等交互操作受限于数据管理和可视化的性能，极大地制约了快速获取点云数据的综合应用能力^{[5, 6]}。在计算机图形学领域,发展了多种专门的数据组织方法加速绘制效率和质量，但多关注单个目标的点云数据,难以有效处理复杂场景的地物目标数据。由于点云数据量大且分辨率高，一种有效的处理策略是顾及细节层次的自适应可视化。Surfels^[7]和Qsplat^[8]是多细节层次点表达模型的两个最具代表性的实现方法,它们的预处理过程均很费时,不平衡的树状结构容易导致树深过高进而致使查询效率恶化。之后,计算机图形领域的绝大多数方法基本是上述两种方法的改进,如采用并行处理方法和图形处理器提高绘制效率,或者实现外存缓存机制等^[9]。

在空间信息科学领域,文献^[10]提出基于顺序四叉树的数据组织方法管理机载激光点云,采用分段文件映射技术随机抽取不同细节的点云,并关联到相应层的节点中,很好地实现了自适应点云绘制,然而随机抽取方式不能保证对车载激光点云也具有良好简化结果,过深树高引发频繁迭代计算也是影响管理效率的隐患。文献^[11]的方法与之类似,它们仍然是一种二维数据管理方法,难以最好地支持视锥体裁剪等可视化算子。文献^[12]采用八叉树和平衡二叉树的嵌套结构管理海量点云,顾及了树状结构的平衡性问题,但是采用单一维度作为二叉树剖分依据没有顾及三维空间特性。文献^[13]采用空间数据分布方法将海量点云分配至多个服务器,采用并行访问技术提高数据管理效率,是利用计算机集群管理点云的有益尝试。

三维R树可以根据目标数据自适应地调整索引结构,目标分布状态对其影响较小,是一种有前途的三维空间索引方法^{[14, 15]}。理论上,三维R树的动态更新和自适应调整能力非常适合分布散乱、密度不均的三维点云应用。然而,由于算法复杂、点云数量庞大等诸多原因,至今未见R树成功管理点云的文献发表。

本文利用八叉树的快速收敛能力，提出一种八叉树和R树集成的新三维索引方法—3DOR树，显著提升大规模点云的R树索引创建效率，并采用一种顾及多细节层次的三维R树索引扩展结构高效生成多细节层次点云模型，支持大规模车载激光点云的高效管理和自适应可视化。本文研究内容可以描述如图 1。

图 1 本文研究框架 Fig. 1 The framework of this study

图选项

R树索引能够很好地适应空间数据分布特点,且能提供稳健高效的空间查询能力^[16]。R树索引生成方法分为动态方法和静态方法,动态生成方法更符合空间数据管理要求,但是每个点均要经过节点选择和节点分裂等复杂操作才能插入到索引结构中,对于数以亿计的点云数据来说并不现实,需要寻求一种更高效的索引创建方法,本文采用一种动静结合的方式构建三维R树索引结构,兼具静态方法的高效率和动态方法的自适应性。

下面是结合三维R树和八叉树(octree)的索引创建算法(3D Oct-Rtree,简称3DOR树)描述，图 2是3DOR树创建流程图。给三维R树设定扇出(fanout)参数,即每个节点允许包含最大元组数目和最小元组数目,采用八叉树剖分三维空间,节点收敛条件是每个叶节点中的点数目小于等于最大元组数目。八叉树分裂过程中,满足扇出参数条件的子节点将重新计算范围,以叶节点身份插入到三维R树中。点数小于扇出参数最小值的子节点中的点输出至数组,按顺序重组为满足扇出参数的叶节点逐一插入到R树,过程中不对数组中的点重新空间排序,原因是这些点相对邻近,重新排序代价高且意义不大。对于无法保证满足扇出参数的情况,添加其中的点到全局点数组中,待八叉树剖分结束后,以单点身份逐一插入R树。

图 2 3DOR树创建流程图 Fig. 2 Flow chart of the 3DOR-Tree construction procedure

图选项

算法描述：点云的空间索引创建算法。

算法输入：点元组集合,R树扇出参数为[i_min,i_max]。

算法输出：三维R树索引结构。

步骤1：计算包含所有点集的最小包围盒(minX,minY,minZ,maxX,maxY,maxZ),并以(minX,minY,minZ)为起算点,计算包含所有点集的最小立方体范围,作为八叉树根节点范围,全部点均是节点node中的元组,并创建两个点数组Array1和Array2。

步骤2：如果元组数目大于i_max,则将空间均匀分为8个子节点Child_i(i=0,1,…,7),并将点分配至对应的子节点,进入步骤3；如果node中元组数目小于等于i_max,则停止分裂。 步骤3：清空Array1,逐一遍历子节点Child_i,如果Child_i中的点数目小于i_min,将其中的点加入Array1中,令Array1中的点数目为iPtNum,进入步骤4。

步骤4：如果iPtNum小于i_min,将数组中所有点逐一插入Array2中；如果iPtNum大于等于i_min且小于等于i_max,则将数组中所有点打包为叶节点插入R树中；如果iPtNum大于i_max且小于等于2i_max,将点均分为两个叶节点,插入R树中；如果iPtNum大于2i_max,k为iPtNum/i_max取整,将数组前(k-1)i_max个点,均分(k-1)个叶节点插入R树,剩余点数iRestNum为iPtNum-(k-1)i_max,如果iRestNum等于i_max,则将其作为一个叶节点插入到R树,如果大于i_max (必然小于2i_max),则将其均分为两个叶节点,插入R树中。

步骤5：逐一遍历子节点Child_i,如果Child_i中的点数目大于i_max,则令node为Child_i,进入步骤2。

步骤6：逐一遍历子节点Child_i,如果Child_i中的点数目大于等于i_min且小于等于i_max,则将节点中的点组成叶节点插入R树。

步骤7：所有八叉树分支分裂结束后,将Array2中的点以元组身份逐一插入R树。

步骤8：退出。

本方法利用八叉树分配邻近点至相同或相邻节点中,通过以节点为插入单元的策略批量插入点,避免了逐点插入的费时操作,显著地提高索引生成效率,同时仍然采用动态生成方法构建R树,使得树形结构具有很好的空间适应性,保证平衡树状结构和良好空间利用率。图 3是某点云数据的八叉树叶节点层(分裂参数为100,即大于100个点要分裂节点)和3DOR树结构叶节点层(扇出参数为40和100)。

图 3 八叉树和3DOR树的叶节点层 Fig. 3 Leaf nodes in Octree and 3DOR-tree

图选项

对于车载激光点云测图应用需要高效交互性能来说,启用多细节层次策略成为合理甚至必须的选择,即根据视距和软硬件性能实时选择合适细节层次表示点云场景。关于R树和多细节层次场景结合的已有研究均试图采用R树的天然层次结构实现目标查询和细节层次查询的双重功能^{[17, 18, 19]}。然而,应用R树节点包围盒作为低细节层次描述,忽略单个目标的LOD(level of details)描述需求,也不能满足可视化精度要求。

传统R树索引方法仅在叶节点中管理目标模型,本文扩展结构使得中间节点也能管理目标模型。叶节点层管理全部和最精细的目标,从每个子节点按照某种规则挑选一个最有代表性的目标作为较粗层次目标模型集合存于父节点中,因此上层节点中的目标数目和子节点数目相等。举例说明,从每个子节点中选择一个距离目标集合重心最近的目标作为上层节点的目标。

本文方法借助R树的层次结构,叶节点代表最高的细节层次,中间节点代表中等的细节层次,根节点代表最低的细节层次。每层被设置一个适用范围,包括最近距离和最远距离,相邻层的适用范围无缝拼接。同层中所有节点的适用范围相同,当视点和节点的距离落于该范围内,即访问节点中的点模型。在全景描绘时,只需访问根节点中的点模型,随着视点接近,视域逐渐减小,关注细节逐渐提高,从根节点访问其子节点,根节点中的点仅是其子节点中的重要目标,因此关注的目标集合有所增加,细节层次增强。LOD选取距离原则的详细解释可以参考文献^[20]。图 4是点云的多细节层次描述效果。

图 4 点云的多细节层次描述 Fig. 4 LOD representation of point clouds

图选项

由于文件大小的限制,大规模点云工程采用工程-点云-点层次模式组织点云数据。车载激光点云采集过程中,每隔几百万个点分段为单个点云,单个点云的原始文本文件数据量为数百兆字节,某个应用中的点云集合即为点云工程,一个小型城镇的点云工程可能高达数十GB。本文采用自定义的文件结构组织大规模车载激光点云,目的是为了提高数据管理效率,其方法也可实现于商业数据库管理系统。

以自定义文件系统方式为例，点云工程是包含众多点云的目录,点云是单个二进制数据文件,图 5是本文数据组织方法描述。每个点云包括头部分和实体部分,头部分包括点云的整体信息,如版本号、总数据量、R树扇出参数(子节点数目的最大最小值)、总点数、R树总层数、空间范围、中心点坐标、压缩标志以及根节点地址等。点坐标是实际点坐标减去中心点坐标的差值,这样坐标可以采用较少有效位数表示,有利于采用4字节单精度浮点类型表示点坐标,另外,如果空间范围在各坐标轴上的长度小于655.35 m且精度要求在厘米级(车载激光扫描数据精度可达到厘米级),将坐标值乘以100然后用2字节短整数类型表示点坐标,数据量减少75%。

图 5 点云工程数据组织方法 Fig. 5 Data organization method of point cloud project

图选项

点云的实体部分采用三维R树索引结构管理点数据,R树索引结构包括根节点、中间节点和叶节点。本文的多细节层次生成方法中,上层节点从每个子节点中选取一个点作为低细节层次描述,为避免重复存储和处理,选取点将从子节点移出至上层节点,这样中间节点和叶节点中的点数目要减1。为了实现缓存机制,即根据视域条件动态调度数据,父节点记录子节点的首地址,即子节点相对文件起始位置的偏移量。R树存储结构可以分为按广度遍历存储顺序和按深度遍历存储顺序组织。广度遍历存储顺序指按节点层的次序存储节点数据,从根节点开始,将节点按层顺序依次记录到文件中,负面影响是父节点和子节点无法集中存储；深度遍历存储顺序指从根节点开始,然后记录其各个子树,负面影响是中间层的兄弟节点无法集中存储。图 6(a)和(b)分别是广度遍历存储和深度遍历存储的原理。

图 6 广度和深度遍历存储原理描述 Fig. 6 Principal description of breadth and depth traversal storage

图选项

点云工程数据规模通常很大,超出主存容量和图形绘制硬件处理能力,一般打开工程时仅调度上面数层节点中的点数据以描述全景,当视点逼近局部场景时,将通过父节点依次访问子节点直至叶节点,因此广度优先存储和深度优先存储方式均不能完全满足高效调度的要求。本文采用二者混合方案来最大限度提升数据调度效率。以叶节点层为第0层,例如全景显示第2层及以上节点中的点数据时,将第2层及以上层采用广度优先存储,最下两层按照深度优先存储,至于具体以第几层为分界线,将根据总数据量决定,如果数据量小可以下调,如果数据量大可以上调。图 7是本文方法的原理描述,其中第2层是分界线。本文方法采用文件映射技术访问点云文件,每个父节点记录所有子节点地址,采用类似于访问内存方法根据节点地址访问节点外存数据。本文方法将极有可能连续访问的节点数据集中存储,有利于提高外存访问效率。

图 7 混合存储方式原理描述 Fig. 7 Principal description of mixed storage

图选项

单点数据内容包括三维坐标、颜色以及强度等信息,可以根据应用需要扩展单点结构。如果采取压缩方式存储,三维坐标值采用2字节短整型表示,相对于双精度浮点型表示,数据量减少75%,可以显著减少数据调度量,提升外存访问效率。另外,为最大限度提升三维可视化效率,点数据应当按照图形绘制硬件特点进行组织,例如,采用OpenGL绘制引擎时,可以将节点中的点数据组织成VBO顶点缓冲形式,直接送入绘制管线处理。 5 试验结果与分析

本试验采用测试数据是车载激光扫描移动测图系统采集的真实数据,是中国某小型城镇的真彩色三维点云数据。车辆行驶耗费20 min扫描该镇全部道路,获取详细的街道、房屋立面、树木以及电线等点模型。原始数据包含92个点云文件,每个点云文件包含200多万个点,总数据量约为14.6 GB(包含坐标、颜色、时间等数据),总点数为2.2亿。测试环境配置如下：笔记本电脑,CPU Intel Duo T7500,内存1 GB。 5.1 索引创建效率测试

索引创建效率关系到应用成败,如果索引创建需要十几个小时甚至更长,即使查询效率满足交互要求,也不能适应实际应用需要。由于格网索引的格网尺寸难以确定,且大量空格网容易导致空间利用率极低,本文不予比较测试。本文分别对八叉树、三维动态R树和3DOR树生成算法进行效率测试。其中,八叉树参数为100,即节点中点数目小于等于100时停止分裂,三维R树的扇出参数为40和100,而3DOR树中,八叉树分裂参数为100,R树扇出参数为40和100。

采用一份包含2 426 454个点的点云数据测试索引创建效率,表 1中有八叉树、3DOR树以及三维动态R树的创建效率对比。八叉树深度不平衡,叶节点树深从1到17不等。3DOR树深度平衡,树深为4。三维动态R树深度平衡,树深为5。从测试数据可知,本文的3DOR索引方法创建效率满足准实时要求,树深平衡,并且树深比另两种方法小。原因是,3DOR树本质上仍是R树索引结构,且叶节点基本是满负荷,从而节点数目减少和深度减小。较小的树深直接减少迭代运算层数,有利于显著改善算法效率。 本文对总数据量14.6 GB的点云工程创建索引,总耗费时间约为40 min。 5.2 空间利用率测试

相对于CPU计算和主存访问效率,外存访问效率低两个数量级以上且改善空间有限,数据量大小直接关系到后续外存数据调度效率,进而影响用户体验。点云工程数据量往往大于主存容量,动态调度和数据缓存机制成为必须采用的策略。本文通过中心点平移方法将双精度浮点型数据转化为单精度浮点型,进一步将单精度浮点型转化为短整型,并清除冗余点(距离小于1 cm视为冗余点),数据量压缩显著,表 1中有文本格式、Pointools商业格式和本文结构的数据量对比。不难看出,原始文本数据转化为本文数据格式,压缩率超过全球业界领先者Pointools。

如果用户打开和全景显示工程的等待时间过长,将严重影响用户体验。采用Pointools商业平台将试验数据转化为其特有POD格式并组织成为工程后,试验环境打开工程耗时超过4 min。由于是商业平台,无法测算其效率瓶颈。值得指出的是,当工程打开后,该商业平台可以保证后续交互操作的流畅性。

本文方法中,点云工程包含2亿多个点,扇出参数为40和100,第2层及以上点云模型不会超过10万个点(2×10⁸/(40×40)),因此打开工程只需调度第2层及以上的点云模型。第2层以上按照广度优先遍历方法进行存储,后续访问时按照广度优先遍历顺序即可将所需节点外存数据依次读取,不会出现跳跃访问,最大限度地提高数据访问效率,试验结果表明耗时仅需4 s,图 8是点云工程的全景图。另外,本文设计试验测试深度优先存储方法的访问效率,节点数据重新按照深度优先遍历方式存储,打开整个工程耗时3 min,相比于本文方法,效率下降明显。

图 8 点云工程全景 Fig. 8 Full scene of point cloud project

图选项

本试验环境允许的数据缓存容量不超过200兆,单帧绘制点数不超过500万个,如果超过容许值将自动清理缓冲区。当视点落于场景中近距离浏览地物目标时,自适应可视化机制下最高细节层次作用范围的最远距离一般保持在15 m左右,即使显著改变视点位置,所需调度数据量也不会超过10 MB,调度时间不超过2 s。试验采用多线程机制调度数据,并不影响主线程绘制任务,实现点云场景多细节层次描述效果。 5.4 空间查询效率测试

车载激光扫描平台的一项重要任务是三维测图,捕捉三维点成为应用成败的关键。如果不借助空间索引功能,从场景中数以亿计的点集中搜索目标点将会效率极低。本文借助三维R树索引能力,捕捉目标点没有明显停顿,符合交互测图要求。试验过程测试多个环节,如捕捉点、场景移动和连线等功能,均能实现流畅交互操作。图 9是本试验平台的测图结果,其中包括天线和建筑物墙面等测图成果。

图 9 试验平台三维测图效果 Fig. 9 3D mapping in experimental platform

图选项

大规模点云管理和可视化是阻碍点云应用的难题,本文采用一种集成八叉树和三维R树的新方法,借助八叉树细粒度地划分点云的三维空间,通过将八叉树叶节点组织为R树叶节点的策略,避免了海量点云的逐点插入操作,显著提升索引创建效率,由于依然采用动态插入方法创建三维R树,保证了深度平衡的树状结构,实现良好的空间查询效率。基于R树的天然层次结构,本文还提出了一种点云场景多细节层次模型生成方法和点云数据层次组织结构。本文研究不仅为大规模点云自适应可视化提供管理支持，同时也为激光点云深度利用提供理论和方法支持。

当前单点包含4~6个属性值,随着传感器技术的发展,未来极可能翻倍甚至更多,通过自动分类和目标提取还可以产生更加丰富的语义信息,也给点云管理带来新挑战。语义可以视为点云的另一种细节层次,后续研究将面向数据融合和语义管理的点云管理方法,实现同全景影像、矢量图形以及语义信息的集成应用。