4.2 k-d tree与八叉树入门级实例解析

4.2.1 在PCL中如何实现快速邻域搜索

本小节中一起学习如何用k-d tree树找到具体点或空间位置的k近邻，然后学习如何找到用户指定的（本例中是随机的）某一半径内的所有近邻。

代码

首先，在本书提供的第4章例1文件夹中，打开名为k-d tree＿search.cpp的代码文件。

解释说明

下面对源代码中的关键语句进行解析。代码首先用系统时间初始化rand()函数的种子，利用时间初始化，每次运行时所产生的随机数都是不同的，或者用户可以用固定的数值或不初始化随机种子，运行程序产生的随机数不变，然后创建点云对象，并用随机数据填充点云对象。

下面的代码块创建了KdTreeFLANN对象，并把我们创建的点云设置成输入，然后创建一个searchPoint变量作为查询点，并且为它分配随机坐标值。

现在创建一个整数（设置成10）和两个向量来存储搜索到的k近邻，两个向量中，一个存储搜索到查询点近邻的索引，另一个存储对应近邻的平方距离。

假设k-d tree对象返回了多于0个近邻，搜索结果已经存储在我们之前创建的两个向量pointIdxNKNSearch、pointNKNSquaredDistance中，并把所有10个近邻的位置打印输出。

下面代码展示找到了给定searchPoint的某一半径（随机产生）内的所有近邻，它重新定义两个向量pointIdxRadiusSearch、pointRadiusSquaredDistance来存储关于近邻的信息。

像之前一样，如果k-d tree对象在指定半径内返回多于0个近邻，它将打印输出向量中存储的点的坐标与距离。

编译并运行该程序

利用提供的CMakeLists.txt文件，在CMake中建立工程文件，并生成相应的可执行文件。生成可执行文件后，就可以运行了，在CMD中键入命令：

运行之后即可看到类似图4-3所示的结果，这里打印输出了所有近邻的点坐标以及对应的平方距离值。

4.2.2 在PCL中如何实现点云压缩

点云由庞大的数据集组成，这些数据集通过距离、颜色、法线等附加信息来描述空间三维点。此外，点云能以非常高的速率被创建出来，因此需要占用相当大的存储资源，一旦点云需要存储或者通过速率受限制的通信信道进行传输，提供针对这种数据的压缩方法就变得十分有用。PCL库提供了点云压缩功能，它允许编码压缩所有类型的点云，包括“无序”点云，它具有无参考点和变化的点尺寸、分辨率、分布密度和点顺序等结构特征。而且，底层的八叉树数据结构允许从几个输入源高效地合并点云数据。

下面，我们解释单个点云和点云数据流是如何高效压缩的，在给出的例子中，我们用PCL点云压缩技术来压缩用OpenNIGrabber抓取到的点云。

代码

首先，在本书提供的第4章例2文件夹中，打开名为point＿cloud＿compression.cpp的代码文件。

解释说明

下面详细解析打开的源代码。从主函数开始，首先创建一个新的SimpleOpenNIViewer实例并调用它的run()方法。

在run（）函数中，创建PointCloudCompression类的对象来编码和解码，这些对象把压缩配置文件作为配置压缩算法的参数，所提供的压缩配置文件为OpenNI兼容设备采集到的点云预先确定的通用参数集。本例中，使用MED＿RES＿ONLINE＿COMPRESSION＿WITH＿COLOR配置参数集，它应用5立方毫米的编码精度并且允许彩色纹理成分编码，并进一步优化，用于快速在线压缩。压缩配置文件的完整列表及其配制方法可以在文件“/io/include/pcl/compression/compression＿profiles.h”中找到。在 PointCloudCompression 构造函数中使用MANUAL＿CONFIGURATION属性就可以手动设置压缩算法全部参数。

下面的代码为OpenNI兼容设备实例化一个新的采集器，并且启动循环回调接口，每从设备获取一帧数据，就调用回调函数一次，这里的回调函数实现数据压缩和可视化解压缩结果。

在OpenNIGrabber采集循环执行的回调函数cloud＿cb＿中，我们首先把获取到的点云压缩到stringstream缓冲区，下一步是解压缩，它对压缩了的二进制数据进行解码，存储在新的点云对象中，解码了的点云被发送到点云可视化对象中进行实时可视化。

编译并运行该程序

利用提供的CMakeLists.txt文件，在CMake中建立工程文件，并生成相应的可执行文件，生成执行文件后，就可以运行了，在CMD中键入命令。

可以看到图4-4所示的结果，左边为实时可视化带RGB纹理信息的点云结果，此时缩放可视化结果可以看到经过压缩后点云进行了重采样，纹理信息有所丢失，但数据量有所减小，在实际应用当中需折中取舍。右边则为实时压缩信息输出，可以看出压缩的帧数、点数、压缩率等信息。

压缩配置文件

压缩配置文件为PCL点云编码器定义了参数集，并针对压缩从OpenNI采集器获取的普通点云进行了优化设置。请注意，解码对象不需要用参数表示，因为它在解码时检测并获取对应的编码参数配置。下面的压缩配置文件是可用的。

LOW＿RES＿ONLINE＿COMPRESSION＿WITHOUT＿COLOR：分辨率1cm³，无颜色，快速在线编码。

LOW＿RES＿ONLINE＿COMPRESSION＿WITH＿COLOR：分辨率1cm³，有颜色，快速在线编码。

MED＿RES＿ONLINE＿COMPRESSION＿WITHOUT＿COLOR：分辨率5mm³，无颜色，快速在线编码。

MED＿RES＿ONLINE＿COMPRESSION＿WITH＿COLOR：分辨率5mm³，有颜色，快速在线编码。

HIGH＿RES＿ONLINE＿COMPRESSION＿WITHOUT＿COLOR：分辨率1mm³，无颜色，快速在线编码。

HIGH＿RES＿ONLINE＿COMPRESSION＿WITH＿COLOR：分辨率1mm³，有颜色，快速在线编码。

LOW＿RES＿OFFLINE＿COMPRESSION＿WITHOUT＿COLOR：分辨率1cm³，无颜色，高效离线编码。

LOW＿RES＿OFFLINE＿COMPRESSION＿WITH＿COLOR：分辨率1cm³，有颜色，高效离线编码。

MED＿RES＿OFFLINE＿COMPRESSION＿WITHOUT＿COLOR：分辨率5mm³，无颜色，高效离线编码。

MED＿RES＿OFFLINE＿COMPRESSION＿WITH＿COLOR：分辨率5mm³，有颜色，高效离线编码。

HIGH＿RES＿OFFLINE＿COMPRESSION＿WITHOUT＿COLOR：分辨率5mm³，无颜色，高效离线编码。

HIGH＿RES＿OFFLINE＿COMPRESSION＿WITH＿COLOR：分辨率5mm³，有颜色，高效离线编码。

MANUAL＿CONFIGURATION：允许为高级参数化进行手工配置。

高级参数化

为了能完全控制压缩相关的参数，PointCloudCompression类的构造函数可以在初始化时附加压缩参数。请注意，为了能够进行高级参数化，compressionProfile＿arg参数需要被设置成MANUAL＿CONFIGURATION。

下面解释高级参数化设置。

compressionProfile＿arg：为了启用高级参数化，该参数应该被设置成MANUAL＿CONFIGURATION。

showStatistics＿arg：把压缩相关的统计信息打印到标准输出。

pointResolution＿arg：定义点坐标的编码精度，该参数应该设置成小于传感器精度的一个值。

octreeResolution＿arg：该参数定义展开了的八叉树的体素大小，较大的体素分辨率使得压缩更快，但是压缩质量下降，这在较高的帧速率（上传速率）和压缩效率中间进行了折中设置。

doVoxelGridDownDownSampling＿arg：如果激活该参数，那么只编码分层八叉树的数据结构，解码对象在体素中心生成点，通过这种方法，点云在压缩期间被下采样，同时达到了较高的压缩性能。

iFrameRate＿arg：点云压缩模式对点云进行差分编码压缩，用这种方法，对新引入的点云和之前编码的点云之间的差分进行编码，以便获得最大压缩性能，iFrameRate＿arg允许指定数据流中的某一帧速率，在这一速率下传输的点云就不进行差分编码压缩（和视频编码中的I/P帧类似）。

doColorEncoding＿arg：该选项启用彩色纹理成分编码压缩。

colorBitResolution＿arg：该参数定义每一个彩色成分编码后所占比特数。

PCL点云数据流压缩的命令行工具

PCL应用程序工具中包含点云数据流压缩命令行工具openni＿stream＿compression.exe，用户可以可以查看选项的完整列表（注意：屏幕上的输出可能不同）。该工具可以在安装好的PCL的bin目录下找到。用户可以自行试验，看看其强大的功能，具体参看其命令行帮助提示。例如它可以通过网络进行点云压缩传输。

为了通过TCP/IP传输压缩点云，可以用下面的命令启动服务器。

它会监听6666端口，看是否有接入连接请求，用下面的命令开启客户端。

远程采集到的点云可以通过点云查看工具在本地显示，笔者测试结果如图4-5所示。

4.2.3 基于八叉树的空间划分及搜索操作

八叉树是一种用于管理稀疏3D数据的树状数据结构，每个内部节点都正好有八个子节点，本小节中我们学习如何用八叉树在点云数据中进行空间划分及近邻搜索，特别地，解释了如何完成“体素内近邻搜索(Neighbors within Voxel Search)”“K近邻搜索(K Nearest Neighbor Search)”和“半径内近邻搜索(Neighbors within Radius Search)”。

代码

首先，在本书提供的第4章例3文件夹中，打开名为octree＿search.cpp的代码文件。

解释说明

下面解析打开的源代码。我们首先定义并实例化一个PointCloud指针对象，并且用随机点集赋值给它。

然后创建一个八叉树实例，用设置分辨率进行初始化，该八叉树用它的叶节点存放点索引向量，该分辨率参数描述最低一级八叉树的最小体素的尺寸，因此八叉树的深度是分辨率和点云空间维数的函数，如果知道点云的边界框，应该用defineBoundingBox方法把它分配给八叉树，然后通过点云指针把所有点增加到八叉树中。

一旦PointCloud和八叉树联系在一起，我们就能进行搜索操作，这里使用的第一种搜索方法是“体素近邻搜索”，它把查询点所在的体素中其他点的索引作为查询结果返回，结果以点索引的向量的形式保存，因此搜索点和搜索结果之间的距离取决于八叉树的分辨率参数。

接下来，介绍k近邻搜索，本例中，k被设置成10，“k近邻搜索”方法把搜索结果写到两个分开的向量中，第一个，pointIdxNKNSearch，包含搜索结果（结果点的索引的向量），第二个向量保存相应的搜索点和近邻之间的平方距离。

“半径内近邻搜索”原理和“k近邻搜索”类似，它的搜索结果被写入两个分开的向量中，这两个向量分别存储结果点的索引和对应的平方距离。

编译并运行该程序

利用提供的CMakeLists.txt文件，在CMake中建立工程文件，并生成相应的可执行文件，生成执行文件后，就可以运行了，在CMD中键入命令。

运行结果如图4-6所示，分别打印出不同搜索方式的输出结果。

八叉树部分类关键点说明

PCLoctree组件提供了几个八叉树类型。它们各自的叶节点特征基本上是不同的。

OctreePointCloudPointVector（等于OctreePointCloud）：该八叉树能够保存每一个叶节点上的点索引列。

OctreePointCloudSinglePoint：该八叉树类仅仅保存每一个叶节点上的单个点索引。仅仅保存最后分配给叶节点的点索引。

OctreePointCloudOccupancy：该八叉树不存储它的叶节点上的任何点信息。它能用于空间填充情况检查。

OctreePointCloudDensity：该八叉树存储每一个叶节点体素中的点的数目。它可以进行空间点集密集程度查询。

如果需要高频率创建八叉树，请参看八叉树双缓冲技术实现（Octree2BufBase类）。该类在内存中同时保存了两个类似的八叉树对象。除了搜索操作之外，也可以用于空间变化检测。此外，高级内存管理减少了八叉树建立过程中的内存分配和释放操作。双缓冲技术对八叉树的实现可以通过设置模板参数“OctreeT”实例化不同的OctreePointCloud类。所有的八叉树都支持八叉树结构和八叉树内容的串行化和反串行化。

4.2.4 无序点云数据集的空间变化检测

八叉树是一种用于管理稀疏3D数据的树状数据结构，本小节中我们学习如何利用八叉树实现用于多个无序点云之间的空间变化检测，这些点云可能在尺寸、分辨率、密度和点顺序等方面有所差异。通过递归地比较八叉树的树结构，可以鉴定出由八叉树产生的体素组成之间的区别所代表的空间变化，此外，我们解释了如何使用PCL的八叉树“双缓冲”技术，以便能实时地探测多个点云之间的空间组成差异。

代码

首先，在本书提供的第4章例4文件夹中，打开名为octree＿change＿detection.cpp的代码文件。

解释说明

首先实例化OctreePointCloudChangeDetector类，并定义它的体素分辨率。

然后创建点云实例cloudA，用随机点数据填充，所生成的点数据用于建立八叉树对象。

点云cloudA是参考点云，用其建立的八叉树对象描述它的空间分布OctreePointCloudChangeDetector类继承自Octree2BufBase类，Octree2BufBase类允许同时在内存中保存和管理两个八叉树，另外，它应用了内存池，该机制能够重新利用已经分配了的节点对象，因此减少了在生成多个点云八叉树对象时昂贵的内存分配和释放操作。通过访问“octree.switchBuffers()”，重置了八叉树对象的缓冲区，但把之前的八叉树数据仍保留在内存中。

现在我们实例化第二个点云对象cloudB并用随机点数据填充它，该点云用于建立新的八叉树结构，该新的八叉树与前一个cloudA对应的八叉树共享八叉树对象，但同时在内存中驻留。

为了获取存在于cloudB的点集R（此R并没有cloudA中元素），可以调用getPointIndices-FromNewVoxels方法，通过探测两个八叉树之间体素的不同来实现。它返回cloudB中新加点的索引的向量，通过索引向量可以获取R点集。很明显，这样就探测了cloudB相对于cloudA变化的点集，但是只能探测在cloudA上增加的点集，而不能探测在cloudA上减少的点集。

最后，我们把结果输出到std::cout数据流，打印到标准输出设备上。

编译并运行该程序

利用提供的CMakeLists.txt文件，在CMake中建立工程文件，并生成相应的可执行文件，生成可执行文件后，就可以运行了，在CMD中键入如下命令。

运行结果如图4-7所示，打印输出了在cloudA上增加的点集。