PCL中outofcore模块---基于核外八叉树的大规模点云的显示

这里主要针对PCL库中outofcore做一些介绍，查询外网文献以及相关模块的相关资料写出以下内容，该模块就是为了实现大规模点云的载入与显示，渲染等问题。

什么是outofcore

outofcore，可以理解为使用内存映射的方法，来处理大规模点云无法载入到内存的问题，并且这里暂且将其翻译为“核外八叉树”，因为根据PCL中的实现方法，就是以八叉树的方法实现了内存映射的算法。

在PCL中基于外存（out of core）的数据处理方法，借助于八叉树理论在完成大规模点云的前提处理，并使用一种八叉树领域的搜索方法构建出散乱数据的拓扑结构。在可视化与计算机图形学领域，基于外核的算法是涉及用来处理大数据量模型运行在有限内存中的方法，简单来说，通过限制访问到一个小的，处于高速缓存中的模型的字块实现的。

首先我们看一下PCL 的Outofcore的模块介绍，该模块介绍是就是通过内存映射的方法以及八叉树的数据结构实现大规模点云的存储，数据位于某些辅助存储介质上基于目录的八叉树层次结构中，并且PCL——outofcore提供了构造和遍历outofcore八叉树的框架，其他的辅助函数在后面将会具体讲解。

PCL中的outofcore模块是由Urban Robotic整合起来，并且在ＰＣＬ中实现了相关的例程，本文是在查阅了大量的相关资料的基础上总结而成，其中难免会有一些理解错误，
该模块翻译成中文可以翻译为核外八叉树，主要针对点云的处理，同时也可以扩展成为网格或者体素的表示形式，outofcore支持空间索引数据存储和快速的数据访问，并且只有部分数据从硬盘加载到运行的内存中，以便能够快速的可视化。

所以该框架能够满足一下几种条件：
（1）大数据，框架能够处理大量的点云或者大空间的数据
（2）支持非均匀数据，采集的点云从分布，密度以及精度上都是变化的，
（3）支持数据查询，能够有效的搜索数据，查找数据等操作
（4）数据更新，在大量数据集中能够实现数据的添加和删除等操作，比如滤波操作，
（5）能够保存数据质量，避免了简化重采样或者有损压缩。

Out-of-core octree（核外八叉树）其实就是运行内存不足以载入大量的数据情况下，采用内存映射的方法，并且将数据存储为八叉树的形式保存在硬盘上。

为了满足数据查询的要求，这里采用了八叉树存储结构【以前的文章介绍过八叉树】八叉树是基于空间驱动的分区方法，如果数据分布严重的不均匀，这种方法可能会有严重不平衡的缺点，在这种情况下提出了使用KDtree，需要较少的内存用于树结构并且能够快速的实现数据的访问，但是一般pcl中的实现是主要使用了八叉树只希望该模块能够支持快速的数据更新，并且八叉树是非常适合的实现核外实现的算法，因为每个级别的分区都是相同的，因此不需要读取额外的信息。

一般来说这种方法很少有开源的方案供大家使用，其中PCL中就是一个较好的实现了核外八叉树模块的算法，开源的模块中只关注核外的八叉树实现以及可视化的部分，并且树的深度或者分辨率完全由用户自行定义。

以上是PCL1.7版本以上outofcore模块实现核外八叉树的类，其中对cJSON的依赖关系作为pcl_outofcore的依赖项已经链接在一起，并且将函数已经封装到两个独立的类OutofcoreOctreeNodeMetadata和OutofcoreOctreeMetadata

 PCL中实现outofcore的文件概括介绍

outofcore模块中实现核外八叉树的四个主要的hpp文件

１．octree.hpp

2. octree2.hpp

３.octree ram container.hpp

4. octree disk container.hpp

头文件：

(a) octree base.h

(b) octree base node.h

(c) octree abstract node container.h∗

(d) metadata.h∗: 实现metadata的抽象类

(e) outofcore node data.h∗：实现核外节点层级的数据文件的接口（tree.oct idx）

(f) outofcore base data.h∗：实现和外八叉树高层级数据接口（tree.octree JSON file）

(g) OutofcoreDepthFirstIterator.h∗:核外八叉树的深度优先迭代器，可以直接访问外部节点的类

(h) OutofcoreIteratorBase.h∗: 基于pcl中octree模块中迭代器的抽象迭代器的类

(i) octree disk container.h: 磁盘容器的IO

(j) octree ram container.h: 核外八叉树的核心数据结构（不再需要了）

(k) outofcore node data.h: 包含主节点数据结构以及用于插入和查询的递归方法

(l) boost.h: 包含pcl outofcore中所需的所有boost头文件

(m) cJSON.h: 为了与PCL构建系统兼容，已进行了较小的修改

模板实现类的文件：

(a)octree base.hpp

(b) octree base node.hpp

(c) octree disk container.hpp

(d) octree ram container.hpp

(e) OutofcoreDepthFirstIterator.hpp

(f) OutofcoreIteratorBase.hpp

源文件

(a) cJSON.cpp

(b) outofcore node data.cpp

(c) outofcore base data.cpp

Outofcore节点的格式

在磁盘上每个内部节点和叶子节点最多可以包含两个文件，

*.oct idx 以oct_idx为后缀的JSON数据文件，格式为：

{
”version”:3 ,
”bb_min”:[xxx,yyy,zzz],
”bb_max”:[xxx,yyy,zzz],
”bin”:”pathtodata.pcd ”
}

可以使用OutofcoreOctreeNodeMetadata类直接访问此JSON数据。此类将接口抽象到磁盘上的JSON数据，因此从理论上讲，该格式可以轻松更改为XML，YAML或其他所需格式。

*.pcd pcd文件包含与该节点关联的所有点云的标准格式（v7 +）PCD文件。该文件同样也适用于所有叶子节点，但仅适用于内部（“分支”）节点（如果已构建LOD）。通过OutofcoreOctreeDiskContainer类可以访问此文件。

根节点包含了一个附件的文件

*.octree 其中包含有关八叉树结构的高级信息。格式为：

{
”name”:”test,
”version”:3,
”pointtype”:”urp”,        #(needs to be changed ∗)
”lod”:3,                  #depth of the tree
”numpts”:[X0,X1,X2, ... ,XD] , #total number of points at each LOD
”coordsystem”:”ECEF”           #the tree is not affected by this value
}

如果想使用PCL 中的outofcore模块只需要添加

#include <pcl/outofcore/outofcore.h>

#include <pcl/outofcore/outofcore_impl.h>

具体实现后面将会更加具体例程的解释

PCL中outofcore模块实现了该算法具有哪些特点

点云的插入
（１）addPointCloud
（２）addPointCloud and genLOD
使用addPointCloud的方法可以公开的访问并且将点云插入到外部的八叉树中，NaN无效点将会被忽略，所有点将以全密度插入到叶子节点中，可以通过迭代的调用addPointClooud的方法将多个点云插入到外部的八叉树中，并且建议使用结构PointCloud2来表示点云

点云查询
点云的查询使用：queryBoundingBox
该函数是为了outofcore构建的八叉树为点云查找提供的公共接口，该方法被重载，并且根据传递的参数，将返回位于指定深度的查询边界框内的所有点，或返回其并集将包含查询边界框内所有点的所有PCD文件列表。

深度级别（LOD level of Depth）：多分辨率的核外八叉树
构建LOD的方法: buildLOD, addPointCloud and genLOD
核外八叉树的一个关键特性是所谓的“深度层次”简称LOD，按照习惯将八叉树的根级成为0级，每一级都是i-1级别八倍采样，（这里我理解为金字塔结构）深度级别是通过随机下采样每个级别的点数来构建，此百分比可以通过OutOfcoreCreeBase类中的setSamplePercent的方法来设置，这一参数也是可以在创建点云的多分辨率表示的时候进行设置，可以达到快速的进行渲染的效果，渲染的过程中，可以基于某些查询的方法，比如体素到视点的距离，访问点云所需要的分辨率，当然也可以通过所在层级以及深度，边界框进行访问

buildLOD：buildLOD使用多分辨率方法重新构建outofcore八叉树的LOD。每个分支节点是其叶子的子采样的并集。子采样的百分比由setSamplePercent确定，默认为0.125^depth-maxdepth  LOD算法的细节请查看【5】

实现从大规模点云生成核外八叉树的文件系统的代码以及可视化的代码：https://www.cnblogs.com/li-yao7758258/p/12011234.html

根据上面的处理的代码的实现提示:

使用深度参数化的方法
pcl_outofcore_process −depth 4 −gen_lod data01.pcd data02.pcd myoutofcoretree

要创建叶节点体素大小不超过50 cm的多分辨率outofcore八叉树，使用如下：
pcl _outofcoreprocess −resolution 0. 50 −genlod data01.pcd data02.pcd myotheroutofcoretree

在PCL中使用OutCore算法可以使用自带的工具里的可执行文件 构造过程可以通过深度或分辨率参数化。如果指定了分辨率（即最大叶尺寸），则自动计算深度。如果设置的树太深：LOD的构建可能需要很长时间

pcl_outofcore_viewer 使用不同的深度可视化的结果

这里使用了不同的分辨率的形式可视化，对于大规模的点云，根据不同的视角来显示点云，对于可视化的部分我们加载进来，对于不需要的部分，我们可以不用加载进来。这也是为什么能够提高可视化的效率。

下面这是使用了真实的PCD点云数据，来做实验例程。该PCD文件是一个大规模的街景点云，该点云有200MB

该点云直接可视化的结果，我们可以看到点云的数量以及加载的时间

我们分别使用了生成了不同的深度和不同分辨率的核外八叉树文件

使用我们outofcore_viewer可视化的结果

该算法针对更大的点云采用上述的方法生成核外八叉树的形式，也可以很好实现点云的可视化

References
[1] PCL Urban Robotics Code Sprint Blog. http://www.pointclouds.org/blog/urcs.
[2] Point Cloud Library Documentation: Module outofcore. https://docs.pointclouds.org/trunk/
group__outofcore.html.
[3] Urban Robotics. http://www.urbanrobotics.net.
[4] Adam Stambler. osgpcl: OpenSceneGraph Point Cloud Library Cloud Viewer. https://github.com/
adasta/osgpcl, 2012.
[5] Claus Scheiblauer and Michael Wimmer. Out-of-core selection and editing of huge point clouds. Computers & Graphics, 35(2):342–351, April 2011.

关于我们

目前微信交流群不断壮大，由于人数太多，目前有两个群，为了鼓励大家分享，我们希望大家能在学习的同时积极分享，将您的问题或者小总结投稿发到群主邮箱主邮箱[e-mail]。