张 蕊，李广云，王 力，李明磊

(1． 信息工程大学，河南 郑州 450052； 2． 华北水利水电大学，河南 郑州 450045)

一、引 言

海量激光点云数据的存储和处理技术是目前地理信息系统和测量系统的一个重要研究方向。由车载系统所获取的建筑物坐标数据或三维激光扫描系统所获取的实测场景数据一般为全离散矢量距离点构成的“点云”数据[1]，为给后期点云数据的高效处理做准备，目前传统的技术是预先基于内存对点云构建索引以实现数据的有效存储[2-3]，当每个数据文件只有KB或MB时，该技术效果显著。

然而对于海量离散点云数据，数量级达到了GB或甚至为TB，并由于单机内存的限制，无法再根据传统的基于全内存的方法对数据进行处理。文献[4—7]中提出了几种基于外存或数据库的数据存储方法，无法满足点云数据后期处理过程中的交互需求[8]。为达到在现有计算机硬件水平下进行海量点云数据快速处理的效果，近年来计算机领域延伸和发展了许多新技术，其中以Google的GFS和Hadoop的HDFS(hadoop distributed file system)最为著名，本文基于HDFS对海量点云数据文件的分块策略提出了新的方法。

二、基于Hadoop的HDFS存储系统

大数据技术包括大数据的存储、计算、管理到恢复等多个方面。其中大数据的存储策略是大数据高效处理过程中需要解决的首要关键问题。Hadoop/MapReduce在大数据存储与数据处理方面扮演着重要的角色。Hadoop是一个基于云计算平台的分布式系统基础架构，是一个用来处理大规模数据的软件平台，能可靠地存储和处理PB级数据，且可通过普通机器组成的服务集群来存储和处理数据，服务集群可达数千个节点[8]。

Hadoop是一种典型的主从式结构，主要由HDFS和MapReduce组成，其结构如图1所示。其中HDFS负责对海量数据进行分布式存储，具有可靠性高、扩展性强、成本低等优势，它的开源性、高容错性及可以部署在廉价的硬件设备上的特点是其成为云存储研究的热点之一[9]。

图1 Hadoop基础架构

文件系统是支持上层应用的基础。Hadoop由于有HDFS在底层作支撑，可以方便地实现“计算向存储的迁移”，这与传统的并行处理技术MPI(message passing interface)有本质区别，处理TB或PB级的海量数据具有很大的优势。HDFS分布式文件系统体系结构如图2所示，HDFS由一个名字节点(Namenode)和多个数据节点(Datanode)组成。Namenode是集群中的中心服务器，负责管理文件系统的命名空间(Namespace)以及客户端对文件的访问。数据节点通常是多个，一个节点运行一个数据节点进程，负责管理它所在节点上的数据存储[10]。

图2 HDFS体系结构

三、海量激光点云数据的数据结构

为描述由激光扫描仪所测量的各个扫描点的详细信息，本文把点云数据的数据结构设计为

(ID,ρ,θ,α,x,y,z,I,nx,ny,nz,R,G,B)

如图3所示，由此可获得扫描点极坐标(ρ,θ,α)，根据极坐标原理即可得扫描点P的三维坐标

(1)

I表示回光强度；nx、ny、nz表示由点P的KNN拟合出曲面获取的法向三分量，如图4所示；R、G、B表示相机采集照片贴图后每点的色彩信息。

图3 激光扫描仪三维坐标系

图4 法向三分量示意图

基于激光点云数据的特点，并结合海量数据的存储技术，本文提出底层采用基于Hadoop的分布式文件系统HDFS存储数据，在存储文件之前需要对文件进行分块处理，采用的分块方法直接影响对数据的处理和检索效率。

四、文件分块策略

在文件分布式存储过程中，文件分割是其中一个关键步骤。HDFS采用了 64 MB的固定文件分块大小，这个尺寸远远大于传统文件系统的分块甚至是文件的大小，每个块及其副本都以普通Linux文件的形式保存在块服务器上。如何在文件分布式存储时对文件进行分割，将文件以最优分块大小进行存储，是海量数据存储的一项核心技术，本文对此提出了3种解决方案。

1. 定长分块(fixed-size partition，FSP)

FSP是通过HDFS配置好的块大小对文件进行切分，对文件中的激光点云数据进行顺序扫描，将点云数据按水平方向均匀分割为若干个大小的数据块，然后将每个数据块分别存储在HDFS系统中的各个数据节点上，把对一个文件的访问请求转变为对多个文件分块的访问请求，从而达到系统负载均衡，提高数据的高吞吐率。

FSP算法的优点是简单、性能高，但它对数据插入和删除非常敏感，处理十分低效，不能根据内容变化作调整和优化。

2. 变长分块(content-defined partition，CDP)

CDP是将文件分割成长度大小不等的分块策略。文献[11]提出制定一个分组因子向量，当需要存储文件时，先得到该文件的大小，通过将文件大小与分组因子进行比较，得到最优分块大小。

本文考虑基于文件内容对文件进行数据切分，对不同物体扫描的数据存放在不同的数据块中。CDP最大的好处为对同一物体扫描得到的数据被分割到一个数据块中，对数据进行读取时只需访问当前块，无需访问多个数据块。但此方法有可能会引起有的数据块过大，而有的数据块过小。

春天就要来临了，这群地球上有名的长途旅行家也要开始为每年的春季大迁徙做准备了。每年春季的3—4月，夏季的7—8月，是驯鹿家族的迁徙时间。那时候，家族中的老老少少齐动身，凭着惊人的耐受力开始路途遥远的大迁徙。

3. 混合分块法

如果变长分块方法可行，能否把定长分块和变长分块结合起来，充分发挥二者的优势，弥补各自的缺陷，是需要研究的另一个难点。

五、试验结果与分析

本文采用的测试环境为具有6个节点的服务集群，其中一台为NameNode，五台为DataNode，硬件环境CPU为Intel core i5-3230M 2.6 GHz，3级缓存，内存8 GB，网络100 Mbps LAN。数据文件大小375.274 MB，存储了4个模型的三维点云数据，点数为9 854 757。然后，先后采用传统方法(即不分块)、定长分块和变长分块方法分别对测试数据进行处理，试验结果如下所述。

1．传统方法试验

4个模型的三维点云放在一个文件中，不分块，处理过程为：

1) 读取第一个模型的数据；

2) 按八叉树进行划分；

3) 每个点在八叉树中寻找KNN，按最小二乘平面拟合计算点法向；

4) 按步骤1)—3)依次处理其余三部分数据，处理结果见表1。

表1 用传统方法对点云数据进行处理

2． FSP试验

4个模型的三维点云按每块64 MB进行切分，共分为6块，最后一块大小为54.849 MB，处理过程为：

1) 6个数据块存储在一组DataNode中；

2) 每个节点进程需要判断是否从相邻数据块中读取数据(本块中的当前块数据是否完全)，然后将完整的数据块按八叉树进行划分；

3) 各个进程中数据块中的各点在相应八叉树中寻找KNN，计算点法向；

4) 一个节点可能包含多个块的部分数据，依次执行步骤1)—3)，处理结果见表2。

3． CDP试验

4个模型的三维点云按内容进行切分，共分为4个数据块，对点云数据进行读取时只需访问当前块，处理过程为：

1) 4个数据块分别存储在一组DataNode中；

2) 每个节点进程都将所处理数据按八叉树进行划分；

3) 各个数据块中各点在相应八叉树中寻找KNN，计算点法向，处理结果见表3。

表2 用FSP法对点云数据进行处理

表3 用CDP法对点云数据进行处理

由试验结果可以看出，对点云数据进行分块存储的效果明显优于传统方法。

六、后续工作

对海量数据的存储是大数据处理的第一步，存储策略的选择直接影响到对海量数据的计算和处理效率。对其他数据存储技术，如数据复制、数据压缩、重复数据删除及存储虚拟化技术等是后续需要研究的工作。

其次，原始的数据存放在HDFS分布式文件系统中，而用户习惯通过某种DBMS(database management system)来存取数据。因为这样能够隐藏文件系统底层技术，方便对数据的管理和用户操作，可采用分布式数据库系统HBase存取数据，对数据表中数据进行分区处理的海量数据管理技术是后续需要研究的一个重点。

七、结束语

HDFS文件系统对海量数据进行分布式存储，具有可靠性高、扩展性强、成本低等优势，正好满足当前海量激光点云数据的存储需求。本文首先构建了海量激光点云数据的数据结构，在此基础上提出了3种海量点云数据文件的分块方法，并通过仿真试验验证了定长分块和按内容分块的有效性，对于混合分块方法的有效性需进一步研究和验证。

参考文献：

[1] 李婕,钟若飞,赵文吉. 车载激光点云海量数据的管理与快速显示[J].系统仿真学报，2008,20(S1):33-39.

[2] 谢洪.基于地面三维激光扫描技术的海量点云模型重建关键算法研究[D].郑州：信息工程大学，2013.

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

[4] KlEIN J, KROKOWSKI J, FISCHER M. The Randomized Sample Tree： a Data Structure for Interactive Walkthroughs in Externally Stored Virtual Environments[C]∥Proceedings of the ACM Symposium on Virtual Reality Software and Technology.[S.l.]:VRST,2002:137-146.

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

[6] BOUBEKEUR T, SCHLICK C. Interactive Out-of-core Texturing with Point-sampled Textures[C]∥Proceedings of the 3rd Eurographics.[S.l.]:IEEE,2006:67-73.

[7] PAJAROLA R. Stream-processing Points[C]∥Proc. VIS’05.[S.l.]:IEEE,2005:239-246.

[8] 邰建华. Hadoop平台下的海量数据存储技术研究[D]. 大庆：东北石油大学，2012:1-8.

[9] 王永洲.基于HDFS的存储技术的研究[D]. 南京：南京邮电大学， 2013:13-44.

[10] 张为民,唐剑锋,罗治国,等. 云计算深刻改变未来[M]. 北京：科学出版社，2009.

[11] 李晖, 樊凯, 王康,等. 云存储系统中可变分块大小的块数据分块方法:中国,201110350575 [P]. 2012-06-20.