胡敏捷 谢 洪

（1.上海船舶研究设计院，上海201203；2.武汉大学，湖北 武汉400439）

0 前言

随着计算机技术飞速进步，基于矢量图形信息的三维可视化和基于实景影像信息的三维可视化技术应用越来越广泛。激光扫描技术作为一种三维空间信息的实时采集手段，以日新月异的速度发展［1］。目前，相位式激光扫描仪的扫描速度可达每秒近百万点，一次扫描可以采集被测对象表面上亿点的三维空间坐标，形成GB级的点云数据。因此，必须建立有效的数据结构来实现快速索引机制，才能开展后续的数据处理分析。

八叉树（Octree）是一种用于描述三维空间的数状数据结构。这种方法即可以看成是四叉树方法在三维空间的推广，也可以认为是用三维体素阵列表示形体方法的一种改进。八叉树的每个节点表示正方体的体积元素，每个节点有八个子节点，将八个子节点所表示的体积元素加在一起就等于父节点的体积。

1 数据管理

1.1 建立点云数据八叉树索引

在建立八叉树的过程中，八叉树的根节点为激光点云数据的外接包围盒，从根节点开始进行空间八方向划分，形成八个子节点立方体，其中一部分含有点，一部分不包含点。不包含点的立方体成为叶节点，不再继续划分，含有点的立方体成为新的父节点继续划分，直到所有立方体中包含的点数小于设定阈值。在基于数据库的点云管理时，每一个目标所对应的点云数据作为一个表空间，八叉树的每一层节点数据均作为一个单独的表存储。根据Morton编码在表空间中建立对应数据的索引表实现快速访问。利用数据库的二进制数据类型来存储每层节点中的点云数据，以便实现多分辨率的分层数据的存储和快速访问。在基于硬盘文件的管理时，同样可以类似于数据库的存储方式来采用多文件的方式存储八叉树的各层节点数据。点云八叉树的索引如图1所示。

图1 点云八叉树索引

1.2 海量点云数据管理和动态更新

图2 量化格网的基本结构

针对点云数据的管理，根据点云数据文件的大小主要提供三种不同的管理方式：①对于点云数据量处于几百GB级别的数据，采用基于Oracle数据库的管理方式，对原始点云数据建立八叉树索引并存入数据库，并根据八叉树索引实现海量点云数据在浏览、量测等操作时的数据动态调度；②对于点云数据量处于几百MB到几十GB级的数据，可采用直接基于硬盘外存（out of core）的八叉树索引多文件（multifile）点云管理方式，并通过动态调度引擎（Dynamic Swap Engine）来进行八叉树节点的动态调度，以实现点云的多层次细节处理；③对于点云数据量为几十MB的数据，可直接采用基于内存（in-core）的管理方式，即将点云数据全部读入内存以便高效的点云后处理操作。

在海量点云数据的处理过程中，为了实现海量点云的快速高效的动态更新，采用八叉树内节点格网量化方法进行点云数据的重采样，将简化的多分辨率点云数据存储到相应的中间节点中，并在此基础上进行点云数据的动态更新操作。

格网量化方法对于八叉树中的每一个内节点，首先建立一个单元个数为k3的格网（其中k的大小可以为128），然后将内节点所对应区域中的所有采样点都量化到对应的格网单元中，并选择一个采样点来表示该格网单元。为了在动态更新过程中正确修改相关格网单元，每个格网单元都存储一个权值用于记录该单元中采样点的个数（如图2所示）。该权值对于在点云动态更新的过程中有着十分重要的作用。同时，针对量化格网的存储问题，采用一个哈希（hash）函数来存储量化格网。根据采样点量化的XYZ坐标，可以通过一个伪随机哈希函数访问动态哈希表中的某一数据块，从而获得内节点中对应格网单元的采样信息。

格网量化技术能够支持点云的删除与插入动态更新的高效实现。对于通过空间划分已经建好的点云多分辨率层次结构而言，动态插入一个点需要区分以下两种情况：待插入点可能位于八叉树的根节点所对应的空间区域之中，也可能在其之外。对于第一种情况，首先从根节点处开始遍历，找到待插入点所处的最底层节点。如果该节点是叶节点，则将新的采样点插入其中，如果其为中间节点，则根据待插入点的位置建立一个新的叶节点。此外，为了更新多分辨率层次信息，在遍历的过程中还需要从根节点开始逐层向下将新的采样点插入到下层子节点所维护的量化格网中，根据需要修改格网单元代表点的属性值并将计数器加一，直到叶节点为止（如图3）。当待插入点位于八叉树的根节点所对应的空间区域之外时，可扩大原有的根节点包围盒范围，并且将原根节点变为新根节点的一个子节点，然后根据待插入点的位置建立一个新的叶节点用于存放该插入点。此时必须计算新根节点的多分辨率层次信息，并由上而下逐层重复以上计算，直到旧的根节点为止。具体做法即采用与情况一相同的格网量化算法更新上述中间节点所维护的量化格网，修改与之对应的量化点云重采样点集，从而完成整个多分辨率层次结构的更新操作。

图3 点云数据的动态插入

点云数据动态删除操作相对比较简单，具体做法为：首先找到待删除点所在的叶节点，然后从该叶子节点所维护的点集列表中删除该点。之后从叶子节点开始逐层向上更新上层父节点所维护的量化格网（如图4所示）。对于在此过程中访问的每一个中间节点，根据待删除点的位置找到与之对应的量化格网单元，将其计数权值减一，并修改代表点的属性信息。如果计数权值变为零，该格网单元实体将会从存储量化格网数据的哈希表中删除。

2 数据存储、访问及查询

2.1 索引数据存储与访问

图4 点云数据的动态删除

针对海量点云多分辨率层次结构数据的存储与动态调度，其基本思想是将点云八叉树中的节点数据存储在外存磁盘文件中，然后根据用户的观察视点参数只将那些用于绘制或编辑的节点导入到内存中进行绘制并提供交互。当改变原始数据中的某一个采样点时，只需要访问整条遍历路径（从根节点至叶节点）上的节点即可，一般情况下被访问的节点个数十分少。在进行绘制时，由于视场角度与屏幕分辨率的限制，只有一小部分的节点会被绘制，而大多数的节点不会被使用。首先在内存中维护了一小块空间用于存储需要使用的节点数据，然后建立一个标准的LRU队列用于交换不使用的节点数据。对于那些被修改的节点数据，需要重写回到硬盘上，而那些未发生变化的节点数据则直接删除。由于数据操作具有一定的连贯性，在访问某一节点时会根据相邻原则先预提取一些节点数据（例如待处理点的父节点、子节点和兄弟节点），这样就使得在下一步数据操作中可以直接访问这些节点，而不用从外存中读取数据，从而提高了数据的访问速度。为了有效隐藏外存访问延迟，可利用多线程技术为节点数据的预提取操作建立一个独立的线程，使得预提取操作能与内核处理同时进行，从而进一步加快了数据访问速度。关于节点数据的外存文件存储，可将其存储到多个文件中，每个文件由固定尺寸的数据块组成，不同文件存储不同大小的块，块的大小以2的阶次方增加。具体做法如下：

首先根据节点数据的大小依式（1）得到文件编号fn；

然后将该节点数据存入到此文件中，并确定其所处的数据块位置编号。

使用这一方法可以减少数据访问时间。这是因为在访问节点时由于文件fn是由若干个大小为2 fn的数据块组成，每个数据块只需要一次查询操作便能直接获得（如图5所示）。

图5 基于块的点云数据存储方式

2.2 动态调度与绘制机制

图7 外存场景交互绘制框架

对于点云数据量处于百万级到千万级甚至更高级的点云数据，基于计算机内存以及渲染限制，为了实现海量数据的实时动态调度，通过动态调度引擎［2］，采用前向投影（Forward Mapping algorithm）算法，根据观察视点进行八叉树节点的动态调度以实现点云的LOD浏览。海量点云动态调度示意图如图6所示。

结合视点相关的层次细节、可见性剔除和外存绘制技术，采用一种大规模外存场景的交互绘制算法，算法的框架如图7所示。首先对场景进行空间分割，将场景表示为一个场景图；然后采用连续分层层次细节模型（Continuous Hierarchical Level Of Detail，CHLOD）进行组织，场景图层次在绘制时保留在内存中，而场景CHLOD模型存储在外存；同时将视点空间划分为多个视点单元，并为每个视点单元计算恰好满足单元内任意视点屏幕像素误差的场景图节点列表，称为cell-front。在实时绘制时，对当前视点单元的cell-front进行层次可见性剔除，并对可见节点的CHLOD模型进行视点相关的局部细化。为了减少磁盘访问造成的延迟，采用多线程技术，利用相邻视点单元之间cell-front的变化设计有效的预取机制，从而使CPU、GPU和IPO三者的效率能够得到充分发挥。

2.3 邻域查询

对于点云的临近点查询、邻域选取［3］等操作，采用二级K-D树来对一级八叉树索引中的叶节点建立高效快速的邻近点查询索引。由于一级八叉树中的叶节点包含点云数目较小，能够快速高效的动态建立更为精细的K-D索引，以充分支持点云的滤波、分割、建模等点云数据后处理操作。基于八叉树和K-D树相结合的二级索引机制如图8所示。

图8 结合八叉树和K-D树的二级索引机制

对于八叉树中叶节点中，为了实现单点的K邻域查询以便于后期的滤波、简化、特征提取等操作，由于叶节点中的数据量较小，可以采用K-D树构建查询索引并设计包含该索引的点云数据共享格式。K-D树是二叉检索树的扩展，树的每一层将空间分层两个。树的顶层节点按一维进行划分，下一层节点按另一维进行划分，以此类推。K-D树划分通常用来查找高维空间距离相近的向量，是一种便于空间中点搜索的数据结构。首先按X轴寻找分割线，即计算所有点的x值的平均值，以最接近这个平均值的点的x值将空间分成两部分;然后在分成的子空间中按Y轴寻找分割线，将其各分成两部分;分割好的子空间在按X轴分割，依此类推;最后直到分割的区域内最后一个点。这样的分割过程就对应于一个二叉树。二叉树的分支节点就对应于一条分割线，而二叉树的每个叶节点就对应一个点。这样，点的拓扑关系就建立了。

3 结语

本文采用了一种基于八叉数的点云管理方法。该方法借助八叉树细粒度地划分点云的三维空间，避免了海量点云的逐点插入操作，显著提升索引效率。保证了深度平衡的树状结构，实现良好的空间查询效率。通过研究点云数据动态更新、索引数据的存储、动态调度与绘制、领域的查询等技术，形成了一套高效快速的海量点云数据管理方法。本文研究不仅为大规模点云数据提供管理支持，而且还可为点云后处理如点云压缩、自动构网提供支持。

［1］徐源强，高井祥，王坚.三维激光扫描技术［J］.测绘信息与工程，2010（4）：9-10.

［2］孟放.大型三维点云数据的交互绘制研究［D］.北京：北京大学，2005.

［3］周儒荣，张丽艳，苏旭.海量散乱点的曲面重建算法研究［J］.软件学报，2001（2）：91-97.