一种联合瓦片索引的车载海量点云数据管理方法

谢 洪，胡晓斌，龚 珣

(1. 武汉大学测绘学院，湖北 武汉 430079； 2. 武汉市测绘研究院博士后创新实践基地，湖北 武汉 430022)

一种联合瓦片索引的车载海量点云数据管理方法

谢 洪1,2，胡晓斌1，龚 珣1

(1. 武汉大学测绘学院，湖北 武汉 430079； 2. 武汉市测绘研究院博士后创新实践基地，湖北 武汉 430022)

为了高效支持大范围车载移动激光扫描海量点云数据的可视化及后续处理，提出了一种联合全球统一划分瓦片索引的车载海量点云管理与调度方法。在分析车载点云空间分布特性基础上，有机联合瓦片索引及随机采样八叉树等空间索引结构，建立了一套面向海量车载移动扫描点云的高效管理及调度机制。试验证明，该方法能够高效支持大范围海量车载点云数据的调度、交互及动态更新等过程，并能够有效地支撑分割、分类等后处理过程。

车载移动扫描；海量点云数据；瓦片索引；管理与动态调度

通过三维激光扫描技术获取目标高精度、高密度的表面几何及纹理信息目前已逐渐成为测绘及相关领域所广泛使用的一种技术手段，而其中车载移动激光扫描技术能够通过灵活集成激光扫描仪、GPS及IMU等多类型传感器[1]，快速获取如公路、隧道、铁路等大范围长距离目标及其周边场景的密集三维点云数据，在道路测量与资产管理[2]、轨道交通[3]、城市模型重建[4]等领域正取得越来越重要的应用。目前，在点云相关应用及研究中，点云分割与分类[5]、兴趣目标提取识别[6]及目标模型重建[7- 8]是国内外学者主要研究关键及热点问题。但需要注意的是，随着研究区域及扫描场景的不断扩大、扫描传感器性能的不断提升，车载移动扫描每千米数据达到GB级，街区尺度下的数据可达到数十至几百GB级，给现有处理算法带来了数据适应性和效率问题。因此，为了能够有效地支持车载点云的后续处理过程，建立高效的车载海量点云管理和动态调度机制用于支撑后处理过程中的查询及动态更新等过程是首要核心问题。

目前，针对海量点云数据的管理研究，主要集中在针对机载及地面静态扫描点云数据的索引组织及内外存调度策略两个方面。文献[9—12]中利用外存或数据库提出了几种不同的点云管理方法，但只针对数据可视化或流数据处理方式，难以满足交互及更新处理需求。文献[13]针对机载点云提出了一种利用顺序四叉树的数据组织方法，较好实现了自适应点云绘制问题，但四叉树不能较好顾及车载点云的三维空间特性。文献[9]利用关系数据库结合二三维混合索引研究了一种以静态扫描各站点云为管理单元的索引方法，难以适用于车载连续扫描条件下的点云组织管理。文献[14]利用随机八叉树提出了一种支持点云高效动态更新的方法，能够解决小区域高密度海量点云数据组织问题，但对于车载城市尺度下线状分布的扫描点云数据，会造成索引深度过大或不均衡树而导致调度及更新效率仍难以满足实际需求。文献[15]针对车载点云利用3DOR树提出了一种多细节层次点云数据组织方法问题，保证了良好的空间适应性和利用率，但R树结构构建过程相对复杂，且不利于索引节点的线性编码存储及查询过程。

分层瓦片索引是目前国内外通用的一种网络地图索引方式，同时也是TMS、WMTS等国际通用地图服务标准协议中的核心内容，能够高效支撑区域级至全球范围的多分辨率栅格数据的LOD调度。为有效支撑大范围海量车载扫描点云的管理与调度，在车载点云分布特性及处理需求分析基础上，本文提出一种联合瓦片索引及随机八叉树结构的海量点云数据管理方法，并设计合理的索引结构存储方法及自适应LOD调度与更新机制，能够有效支撑车载海量点云的后续处理过程。

1 车载海量点云数据索引及存储策略

从车载点云数据特征及调度与处理分析需求来看：①车载点云数据主要包括目标表面离散三维坐标、强度、时间等信息，包含丰富高程信息，但平面分布沿轨迹呈线性分布。另外，点云是车载激光扫描的主要输出数据，在平均采样间隔为3 cm条件下每千米采样点约为3500万，las格式的文件大小约为1 GB，普通街区下点云数据量可达几十GB。②在处理过程中，除了需要支持高效率的海量点云自适应LOD调度外，还需要有效支持基于车载点云的交互测图、分割与分类等后处理过程中的交互查询、原始las调度、动态更新等过程。

1.1 海量点云索引与组织策略

在深入理解车载点云数据可视化及处理需求的基础上，本文提出的车载点云数据索引与组织策略如图1所示。

图1 点云索引与组织策略

在图1的组织结构中，针对车载点云数据的联合管理，其核心策略是：以瓦片多级金字塔为基础索引，选定某一个适合的层级对扫描点云数据进行区块划分，并在区块内对分段点云构建随机八叉树LOD索引[14]。索引构建流程如图2所示。

图2 点云索引构建流程

具体组织方法策略阐述如下：

(1) 全球统一瓦片索引结构：将全球的坐标范围(经度-180°～180°，纬度-90°～90°)划分为不同级别的瓦片，下一级瓦片的大小是上一级的1/4，0级瓦片大小为9°×9°，n级瓦片大小为(9/2n)°×(9/2n)°。瓦片数据可以通过瓦片坐标(瓦片层级，瓦片行号，瓦片列号)来进行快速索引。

(2) 车载点云分段与构建分段索引：由于车载点云沿车载轨迹连续线性分布，而且在其解算或后期处理过程中一般需要分段处理。为此，在车载点云索引组织过程中，本文提出并采用一种沿POS轨迹进行测段划分并针对每个测段进行随机八叉树LOD结构构建的方法，实现海量车载点云数据的二级调度。沿POS轨迹的测段划分如图3所示(内部小矩形表示在车载点云处理过程中的按照点数约束输出的单个无组织点云文件，外部大矩形表示对POS轨迹按长度(一般约为1 km)并根据轨迹寻找其所属的多个点云文件的划分结果。

图3 沿POS轨迹的点云测段划分

(3) 瓦片索引关联点云分段索引：该过程主要将分段点云索引与某个固定层级的某个瓦片进行关联对应，其目的主要是联合瓦片索引及点云分段索引形成二级调度框架。若轨迹每段长度近似为1 km，则其对应瓦片层级为10层，可按式(1)进行近似估计(即该层级瓦片边界长度等于轨迹长度，Lpos表示轨迹长度；Nlayer表示瓦片层级数)

(1)

在确定层级后，选择与分段点云的二维外包盒相交面积最大的瓦片作为该点云的索引瓦片，并设置该瓦片的关联标识为1。通过实现瓦片与点云索引数据的对应，以提高后期索引调度及处理效率。

1.2 基于多级文件目录的索引结构存储

在设计车载移动扫描各类型数据的索引组织结构基础上，合理地进行索引结构的存储也是影响数据调度效率及多源数据处理过程的关键因素，需要在有效支持调度的同时，满足高效的可视化及后期处理需求。为此，根据前述设计的索引组织结构，提出了一种基于多级目录磁盘文件存储的索引结构存储方法：由于不同层级的瓦片具有唯一编码，因此可以利用多级目录结构来表达瓦片索引结构，并进一步将分段点云索引数据存储于对应层级的瓦片文件目录下。多级文件目录的索引存储结构如图4所示。

图4 基于多级文件目录的索引结构存储

图4中，第M层瓦片中编号为“M-i”表示第M层瓦片中的第i行，“点云M-i-k”中存储对应第i行与第k列的分段点云索引文件，“索引文件L”至“索引文件Q”表示按文献[14]的存储方式进行随机八叉树索引文件存储。

2 动态调度及处理与更新过程

2.1 基于视点的车载点云LOD调度

根据前述设计的点云二级索引及存储结构，设计并采用一种基于视点的车载点云LOD调度方法的调度过程如图5所示。具体调度过程为：①根据视点位置、高度及范围快速计算当前视图范围内需要显示的瓦片层级和瓦片行列号。②根据需渲染的瓦片范围，快速获取对应于该范围的分段点云所在瓦片层级的瓦片行列号，并判断对应的存储目录下是否存在分段点云索引文件；如果存在，则进一步根据当前瓦片的分辨率调度分段点云随机八叉树索引中与其最接近的索引层节点进行可视条件判断与调度渲染；如果最为接近的为根节点且与瓦片分辨率差异过大，则不进行渲染或仅渲染根节点外包盒。③在视点移动过程中，重复前述①—②过程，同时将视点范围外的节点数据加入到缓存队列或直接删除，动态加载前述过程中需要渲染的瓦片数据。由于点云分段数据调度过程相互独立，因此各自的卸载和加载过程可以利用多线程并行进行，以提高数据的动态调度效率。

图5 基于视点的车载多源索引数据联合调度

2.2 处理与更新过程

在车载点云数据后续处理过程中，一般分为局部和整体处理两种方式：局部处理，可以直接调度点云分段八叉树索引节点进行处理；整体处理，由于采用了文件夹式的索引存储方式，只需要在对应的点云文件夹保存原始的las格式或其他所需格式的点云原始数据即能满足整体处理过程中的数据调度需求。

点云数据的更新过程主要指在现有调度结构中增加新采集的分段点云，由于论文设计的管理方法中各分段点云索引构建和存储过程相互独立，因此只需要利用前述点云索引策略构建点云分段索引并与对应层级瓦片关联即可。

3 试验与分析

在试验中，基于Visual Studio平台采用C++实现了本文方法，算法运行平台为Windows7 64位系统，主要硬件配置为Intel Core I7及8 GB内存，显卡为Nvidia GeForce GTX 550 Ti，渲染和调度过程分别采用单独线程进行处理。

3.1 试验数据

为了验证本文方法对点云数据量的适应性和调度的有效性，采用不同点云数据量的两组数据作为试验数据，分别记为试验数据A及B。数据A为某高速道路扫描点云，采集轨迹长度约为18 km，点云平均采样间隔为4 cm，平均每段点云数据约为1600万(500 m/段)，点云数据量约为5.4亿；数据B中轨迹长度为66 km，点云平均采样间隔为6 cm，平均每段点云数据约为1100万(500 m/段)，点云数据量约为15亿。

3.2 试验结果与分析

根据式(1)计算得到点云分段随机索引八叉树的存储层为11层，分段点云数据采用随机八叉树构建索引(叶节点中点个数阈值设置为50 000)，并设置当点云随机索引八叉树根节点与瓦片分辨率差异大于5倍时，仅渲染根节点及外包盒。试验效果如图6所示。

图6 调度与查询更新及处理结果

从两组车载海量多源试验数据的调度结果来看，本文所提方法能够有效支持多源数据的动态调度与渲染过程(图6(a)、(b)、(c)、(g)、(h)、(i))。同时，该结构能够有效支撑基于海量车载点云的点查询、线面绘制等交互(图6(d)、(j))、后续分割与分类处理(图6(e)、(k))及动态更新(图6(f)、(l))。

为了验证算法的优势，分别统计了两组点云的索引构建时间(单线程处理)、在不同视点及视点变换下的动态调度时间及渲染点数、调度中最小最大帧率、分段点云更新耗时等重要指标，其中视点分别依次取区域正视条件下离区域中心高度1000 m、300 m、100 m、30 m、5 m的5个视点，动态调度时间是指依次从远到近的5个视点间进行变换时完成数据动态调度过程所耗时间，变换过程中最小最大帧率是指视点变化时动态调度开始和结束时的渲染帧率，分段点云更新时间是指将新采集的某一分段点云数据(las格式，分段长度与各数据的分段长度一致)增加到现有组织索引数据中的耗时。统计结果见表1。

表1 渲染与调度的相关指标统计

从表1可以看出，针对不同密度不同大小的两组数据，本文方法在动态调度过程中最小帧率保持在20以上，最大帧率保持在35以上，表明结合多线程调度能够保证流畅的海量数据调度与渲染效率。从动态调度时间比较来看，两组数据都具有类似且高效的调度过程，表明本文方法具有良好的数据量适应性，但需要注意的是，尽管数据A的整体数据量相对较少，但其动态调度时间却相对较长，其原因主要在于数据A的分段数据量密度较大导致分段索引树结构深度相对较大。另外，从索引构建耗时和分段点云更新耗时来看，本文方法能够高效率地支撑索引构建及更新过程，且整体构建耗时近似等于单段索引更新时间与段数乘积，其原因主要在于各分段数据的索引构建过程和调度过程相互独立，均只与瓦片索引相关联，因此其构建耗时和更新耗时仅与单段数据的大小及分段数目相关。而且本文方法支持分段点云的多线程并行进行索引构建和更新处理，可进一步的提高效率。

4 结 语

为了高效支持车载海量点云数据的可视化与后续处理，联合瓦片索引及随机采样八叉树等空间索引结构，本文提出了一种新的组织管理与二级调度方法，并设计了一种多级目录磁盘文件存储的索引结构存储方式。试验证明，该方法能够高效率支持大范围海量车载多源数据的高效调度、交互及动态更新等过程。下一步的工作主要是基于该统一框架下的车载多源异构数据的联合组织管理方法的研究。

[1] 董震,杨必胜.车载激光扫描数据中多类目标的层次化提取方法[J].测绘学报,2015,44(9):980- 987.

[2] GUAN H,LI J, YU Y, et al. Using Mobile LiDAR Data for Rapidly Updating Road Markings[J]. IEEE Transactions on Intelligent Transportation Systems, 2015,16(5):2457- 2466.

[3] ARASTOUNIA M. Automated Recognition of Railroad Infrastructure in Rural Areas from LiDAR Data[J]. Remote Sensing,2015, 7(11):14916- 14938.

[4] 樊琦,姚顽强,陈鹏.基于 Cyclone 的三维建模研究[J].测绘通报,2015(5):76- 79.

[5] YANG B S,DONG Z,ZHAO G,et al. Hierarchical Extraction of Urban Objects from Mobile Laser Scanning Data[J]. ISPRS Journal of Photogrammetry and Remote Sensing,2015(99)：45- 57.

[6] 杨莎莎,李永强,李框宇.基于车载LiDAR数据的单株树提取[J].测绘工程,2014,23(8):23- 27.

[7] NAN L L,SHARF A,ZHANG H,et al. SmartBoxes for Interactive Urban Reconstruction[J]. ACM Transactions on Graphics,2010,29(4):1- 10.

[8] 戴彬,钟若飞,胡竞.基于车载激光扫描数据的城市地物三维重建研究[J].首都师范大学学报(自然科学版),2011,32(3):89- 96.

[9] 王晏民,郭明.大规模点云数据的二维与三维混合索引方法[J].测绘学报,2012,41(4):605- 612.

[10] KLEIN J,KROKOWSKI J,FISCHER M,et al.The Randomized Sample Tree:A Data Structure for Interactive Walkthroughs in Externally Stored Virtual Environments[J].Presence:Teleoperators and Virtual Environments,2004,13(6):617- 637.

[11] BOUBEKEUR T,SCHLICK C.Interactive Out- of- core Texturing with Point- Sampled Textures[C]∥Eurographics Symposium on Point- Based Graphics. AirelaVille: Eurographics Association,2006.

[12] WAND M,BERNER A,BOKELOH M,et al.Processing and Interactive Editing of Huge Point Clouds from 3D Scanners[J].Computers&Graphics,2008, 32(2):204- 220.

[13] 黄先锋,陶闯,江万寿,等.机载激光雷达点云数据的实时渲染[J].武汉大学学报(信息科学版)， 2005,30(11):975- 978.

[14] 谢洪,吴博义,赵展.一种新的海量点云数据管理方法研究[J].遥感信息,2013,28(6):26- 32.

[15] 龚俊,柯胜男,朱庆.一种八叉树和三维R树集成的激光点云数据管理方法[J].测绘学报,2012, 41(4):597- 604.

An Organization Method of Vehicle- borne Massive Point Cloud DataUsing Tile Indexing

XIE Hong1,2,HU Xiaobin1,GONG Xun1

(1. School of Geodesy and Geomatics of Wuhan University, Wuhan 430079，China; 2. Postdoctors Innovation and Practice Base of WuhanGeomatics Institute, Wuhan 430022，China)

To improve the efficiency of visualization and processing for vehicle- borne mobile scanning point cloud data,combined with the global tile indexing, a novel organization and swapping approach is presented.Based on the spatial distribution analysis of concerning data,a novel mechanism is established to manage the massive data effectively,integrating the tile indexing and random sampling octree appropriately. The implemented experiments show it performs well in the process of data swapping,inquiring,dynamic updating for massive urban- block data,as well as the extended post- processing progress including segmentation,classification,et al.

vehicle- borne mobile scanning;massive point cloud data;tile indexing; organization and dynamic swapping

2016- 07- 05;

2017- 02- 03

国家自然科学基金(41401527)；测绘地理信息公益性行业科研专项(201512008)；武汉市测绘研究院博士后创新实践基地科研项目(WGF2016001)

谢 洪(1987—)，男，博士，讲师，研究方向为三维激光测量。E- mail: hxie@sgg.whu.edu.cn

谢洪，胡晓斌，龚珣.一种联合瓦片索引的车载海量点云数据管理方法[J].测绘通报，2017(3)：17- 21.

10.13474/j.cnki.11- 2246.2017.0075

P234.4

A

0494- 0911(2017)03- 0017- 05