PCL学习八叉树

简介: 建立空间索引在点云数据处理中有着广泛的应用,常见的空间索引一般 是自顶而下逐级划分空间的各种空间索引结构,比较有代表性的包括BSP树,KD树,KDB树,R树,四叉树,八叉树等索引结构,而这些结构中,KD树和八叉树使用比较广泛八叉树(Octree)是一种用于描述三维空间的树状数据结构。

建立空间索引在点云数据处理中有着广泛的应用,常见的空间索引一般 是自顶而下逐级划分空间的各种空间索引结构,比较有代表性的包括BSP树,KD树,KDB树,R树,四叉树,八叉树等索引结构,而这些结构中,KD树和八叉树使用比较广泛

八叉树(Octree)是一种用于描述三维空间的数据结构八叉树的每个节点表示一个正方体的体积元素,每个节点有八个子节点,这八个子节点所表示的体积元素加在一起就等于父节点的体积。一般中心点作为节点的分叉中心。

 

百度百科释义八叉树(Octree)的定义是:若不为空树的话,树中任一节点的子节点恰好只会有八个,或零个,也就是子节点不会有0与8以外的数目。那么,这要用来做什么?想象一个立方体, 我们最少可以切成多少个相同等分的小立方体?答案就是8个。再想象我们有一个房间,房间里某个角落藏着一枚金币,我们想很快的把金币找出来,聪明的你会怎 么做?我们可以把房间当成一个立方体,先切成八个小立方体,然后排除掉没有放任何东西的小立方体,再把有可能藏金币的小立方体继续切八等份….如此下去, 平均在Log8(房间内的所有物品数)的时间内就可找到金币。因此,八叉树就是用在3D空间中的场景管理,可以很快地知道物体在3D场景中的位置,或侦测 与其它物体是否有碰撞以及是否在可视范围内。

实现八叉树的原理 

  (1). 设定最大递归深度。

  (2). 找出场景的最大尺寸,并以此尺寸建立第一个立方体。

  (3). 依序将单位元元素丢入能被包含且没有子节点的立方体。

  (4). 若没达到最大递归深度,就进行细分八等份,再将该立方体所装的单位元元素全部分担给八个子立方体。

  (5). 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的,则该子立方体停止细分,因为跟据空间分割理论,细分的空间所得到的分配必定较少,若是一样数目,则再怎么切数目还是一样,会造成无穷切割的情形。

  (6). 重复3,直到达到最大递归深度。

八叉树的逻辑结构如下:

假设要表示的形体V可以放在一个充分大的正方体C内,C的边长为2n,形体V=C,它的八叉树可以用以下的递归方法来定义:八 叉树的每个节点与C的一个子立方体对应,

树根与C本身相对应,如果V=C,那么V的八叉树仅有树根,如果V≠C,则将C等分为八个子立方体,每个子立方体 与树根的一个子节点相对应。只要某个子立方体不是完

全空白或完全为V所占据,就要被八等分,从而对应的节点也就有了八个子节点。这样的递 归判断、分割一直要进行到节点所对应的立方体或是完全空白,或是完全为V占

据,或是其大小已是预先定义的体素大小,并且对它与V之交作一定的“舍入”,使 体素或认为是空白的,或认为是V占据的。

                              
                                                                                               

PCL中Octree模块及类介绍

pcl::octree::Octree2BufBase< LeafContainerT, BranchContainerT >    实现了同时存储管理两个八叉树与内存中,可以十分高效的实现八叉树的建立管理等操作,并且节点实现对临近树节点的结构的探测,对应到空间点云,其就可以对空间曲面的动态变化进行探测,在进行空间动态变化探测中非常有用

Public Types

typedef Octree2BufBase< LeafContainerT, BranchContainerT >  OctreeT
typedef BufferedBranchNode< BranchContainerT >  BranchNode
typedef OctreeLeafNode< LeafContainerT >  LeafNode
typedef BranchContainerT  BranchContainer
typedef LeafContainerT  LeafContainer
typedef OctreeDepthFirstIterator< OctreeT Iterator
typedef const OctreeDepthFirstIterator< OctreeT ConstIterator
typedef OctreeLeafNodeIterator< OctreeT LeafNodeIterator
typedef const OctreeLeafNodeIterator< OctreeT ConstLeafNodeIterator
typedef OctreeDepthFirstIterator< OctreeT DepthFirstIterator
typedef const OctreeDepthFirstIterator< OctreeT ConstDepthFirstIterator
typedef OctreeBreadthFirstIterator< OctreeT BreadthFirstIterator
typedef const OctreeBreadthFirstIterator< OctreeT ConstBreadthFirstIterator

 

Public Member Functions

void  setMaxVoxelIndex (unsigned int max_voxel_index_arg)
  Set the maximum amount of voxels per dimension. 设置在各个维度的最大的体素个数
void  setTreeDepth (unsigned int depth_arg)
  Set the maximum depth of the octree. 设置八叉树的深度,需要在初始化八叉树时设置
unsigned int  getTreeDepth () const
  Get the maximum depth of the octree  获得八叉树的深度
LeafContainerT *  createLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg)
  Create new leaf node at (idx_x_arg, idx_y_arg, idx_z_arg). 创建叶节点
LeafContainerT *  findLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg)
  Find leaf node at (idx_x_arg, idx_y_arg, idx_z_arg). 找出页节点
bool  existLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg) const
  Check for the existence of leaf node at (idx_x_arg, idx_y_arg, idx_z_arg). 判断在(idx_x_arg, idx_y_arg, idx_z_arg)对应的叶子节点是否存在
void  removeLeaf (unsigned int idx_x_arg, unsigned int idx_y_arg, unsigned int idx_z_arg)
  Remove leaf node at (idx_x_arg, idx_y_arg, idx_z_arg). 移除在(。。。)的节点
std::size_t  getLeafCount () const
  Return the amount of existing leafs in the octree.返回八叉树叶子的个数
std::size_t  getBranchCount () const 
  Return the amount of existing branches in the octree. 返回八叉树分支的个数
void  deleteTree ()
  Delete the octree structure and its leaf nodes. 删除八叉树结构包括节点
void  deletePreviousBuffer ()
  Delete octree structure of previous buffer. 删除另一个缓存区对应的八叉树的结构及其字节点
void  deleteCurrentBuffer ()
  Delete the octree structure in the current buffer删除当前缓存区对应的八叉树的结构及其字节点
void  switchBuffers ()
  Switch buffers and reset current octree structure. 交换缓存区中对应的八叉树的结构和其叶子节点
void  serializeTree (std::vector< char > &binary_tree_out_arg, bool do_XOR_encoding_arg=false)
  Serialize octree into a binary output vector describing its branch node structure.
void  serializeTree (std::vector< char > &binary_tree_out_arg, std::vector< LeafContainerT * > &leaf_container_vector_arg, bool do_XOR_encoding_arg=false)
  Serialize octree into a binary output vector describing its branch node structure and and push all DataT elements stored in the octree to a vector.串行化输出八叉树结构
void  serializeLeafs (std::vector< LeafContainerT * > &leaf_container_vector_arg)
  Outputs a vector of all DataT elements that are stored within the octree leaf nodes.
void  serializeNewLeafs (std::vector< LeafContainerT * > &leaf_container_vector_arg)
  Outputs a vector of all DataT elements from leaf nodes, that do not exist in the previous octree buffer
void  deserializeTree (std::vector< char > &binary_tree_in_arg, bool do_XOR_decoding_arg=false)
  Deserialize a binary octree description vector and create a corresponding octree structure.
void  deserializeTree (std::vector< char > &binary_tree_in_arg, std::vector< LeafContainerT * > &leaf_container_vector_arg, bool do_XOR_decoding_arg=false)
  Deserialize a binary octree description and create a corresponding octree structure.

 更多详细查看  docs.pointclouds.org/trunk/classpcl_1_1octree_1_1_octree2_buf_base.html#aeea7ecfd6ebe82e93d3c7bb869355502

应用实例

点云由海量的数据集组成,这些数据集通过距离 颜色  法线  等附加信息来描述空间的三维点,此外,点云还能易非常高的速度被创建出来,因此需要占用相当大的存储资源,一旦点云需要存储或者通过速率受限制的通信信道进行传输,提供针对这种数据的压缩方法就变得十分有用,PCL 提供了点云的压缩功能,它允许编码压缩所有类型的点云,

点云压缩示意图:

                                                             octreeCompression

新建工程ch3_2,新建文件 point_cloud_compression.cpp

#include <pcl/point_cloud.h>                         // 点云类型
#include <pcl/point_types.h>                          //点数据类型
#include <pcl/io/openni_grabber.h>                    //点云获取接口类
#include <pcl/visualization/cloud_viewer.h>            //点云可视化类

#include <pcl/compression/octree_pointcloud_compression.h>   //点云压缩类

#include <stdio.h>
#include <sstream>
#include <stdlib.h>

#ifdef WIN32
# define sleep(x) Sleep((x)*1000)
#endif

class SimpleOpenNIViewer
{
public:
  SimpleOpenNIViewer () :
    viewer (" Point Cloud Compression Example")
  {
  }
/************************************************************************************************
  在OpenNIGrabber采集循环执行的回调函数cloud_cb_中,首先把获取的点云压缩到stringstream缓冲区,下一步就是解压缩,
  它对压缩了的二进制数据进行解码,存储在新的点云中解码了点云被发送到点云可视化对象中进行实时可视化
*************************************************************************************************/
  
 void  cloud_cb_ (const pcl::PointCloud<pcl::PointXYZRGBA>::ConstPtr &cloud)
  {
    if (!viewer.wasStopped ())
    {
      // 存储压缩点云的字节流对象
      std::stringstream compressedData;
      // 存储输出点云
      pcl::PointCloud<pcl::PointXYZRGBA>::Ptr cloudOut (new pcl::PointCloud<pcl::PointXYZRGBA> ());

      // 压缩点云
      PointCloudEncoder->encodePointCloud (cloud, compressedData);

      // 解压缩点云
      PointCloudDecoder->decodePointCloud (compressedData, cloudOut);


      // 可视化解压缩的点云
      viewer.showCloud (cloudOut);
    }
  }
/**************************************************************************************************************
 在函数中创建PointCloudCompression类的对象来编码和解码,这些对象把压缩配置文件作为配置压缩算法的参数
 所提供的压缩配置文件为OpenNI兼容设备采集到的点云预先确定的通用参数集,本例中使用MED_RES_ONLINE_COMPRESSION_WITH_COLOR
 配置参数集,用于快速在线的压缩,压缩配置方法可以在文件/io/include/pcl/compression/compression_profiles.h中找到,
  在PointCloudCompression构造函数中使用MANUAL——CONFIGURATION属性就可以手动的配置压缩算法的全部参数
******************************************************************************************************************/
  void run ()
  {

    bool showStatistics = true;  //设置在标准设备上输出打印出压缩结果信息

    // 压缩选项详情在: /io/include/pcl/compression/compression_profiles.h
    pcl::io::compression_Profiles_e compressionProfile = pcl::io::MED_RES_ONLINE_COMPRESSION_WITH_COLOR;

    // 初始化压缩和解压缩对象  其中压缩对象需要设定压缩参数选项,解压缩按照数据源自行判断
    PointCloudEncoder = new pcl::io::OctreePointCloudCompression<pcl::PointXYZRGBA> (compressionProfile, showStatistics);
    PointCloudDecoder = new pcl::io::OctreePointCloudCompression<pcl::PointXYZRGBA> ();
    /***********************************************************************************************************
    下面的代码为OpenNI兼容设备实例化一个新的采样器,并且启动循环回调接口,每从设备获取一帧数据就回调函数一次,,这里的
    回调函数就是实现数据压缩和可视化解压缩结果。
   ************************************************************************************************************/
    //创建从OpenNI获取点云的抓取对象
    pcl::Grabber* interface = new pcl::OpenNIGrabber ();

    // 建立回调函数
    boost::function<void
    (const pcl::PointCloud<pcl::PointXYZRGBA>::ConstPtr&)> f = boost::bind (&SimpleOpenNIViewer::cloud_cb_, this, _1);

    //建立回调函数和回调信息的绑定
    boost::signals2::connection c = interface->registerCallback (f);

    // 开始接受点云的数据流
    interface->start ();

    while (!viewer.wasStopped ())
    {
      sleep (1);
    }

    interface->stop ();

    // 删除压缩与解压缩的实例
    delete (PointCloudEncoder);
    delete (PointCloudDecoder);

  }

  pcl::visualization::CloudViewer viewer;

  pcl::io::OctreePointCloudCompression<pcl::PointXYZRGBA>* PointCloudEncoder;
  pcl::io::OctreePointCloudCompression<pcl::PointXYZRGBA>* PointCloudDecoder;

};

int
main (int argc, char **argv)
{
  SimpleOpenNIViewer v;  //创建一个新的SimpleOpenNIViewer  实例并调用他的run方法
  v.run ();

  return (0);
}

 编译后运行的结果如下:

图示为带有RGB纹理信息的实时可视化结果,缩放可视化结果看到经过压缩后点云进行了重采样,纹理信息有所丢失,但数据量有所减小,在实际应用中需要折中取舍

同时在压缩和解压缩的过程中  因为设置compressedData为true所以在标准输出上打印处压缩率帧数等信息:

 

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

LOW_RES_ONLINE_COMPRESSION_WITHOUT_COLOR,             //分别率为  1   cm^3   无颜色      快速在线编码
      LOW_RES_ONLINE_COMPRESSION_WITH_COLOR,                 //分别率为  1    cm^3   有颜色      快速在线编码

      MED_RES_ONLINE_COMPRESSION_WITHOUT_COLOR,             //分别率为  5    mm^3   无颜色      快速在线编码
      MED_RES_ONLINE_COMPRESSION_WITH_COLOR,                    //分别率为  5    mm^3   有颜色      快速在线编码

      HIGH_RES_ONLINE_COMPRESSION_WITHOUT_COLOR,         //分别率为  1    mm^3   无颜色      快速在线编码
      HIGH_RES_ONLINE_COMPRESSION_WITH_COLOR,                 //分别率为  1    mm^3   有颜色      快速在线编码

      LOW_RES_OFFLINE_COMPRESSION_WITHOUT_COLOR,       //分别率为  1    cm^3   无颜色      高效离线编码
      LOW_RES_OFFLINE_COMPRESSION_WITH_COLOR,              //分别率为  1    cm^3   有颜色      高效离线编码

      MED_RES_OFFLINE_COMPRESSION_WITHOUT_COLOR,      //分别率为  5    mm^3   无颜色      高效离线编码
      MED_RES_OFFLINE_COMPRESSION_WITH_COLOR,             //分别率为  5    mm^3   有颜色      高效离线编码

      HIGH_RES_OFFLINE_COMPRESSION_WITHOUT_COLOR,     //分别率为  1    mm^3   无颜色      高效离线编码
      HIGH_RES_OFFLINE_COMPRESSION_WITH_COLOR,              //分别率为  1    mm^3   有颜色      高效离线编码
      MANUAL_CONFIGURATION                                                   //允许为高级参数化进行手工配置

微信公众号号可扫描二维码一起共同学习交流

未完待续*********************************************8888

相关文章
|
4月前
|
C++
C++ PCL SACSegmentationFromNormals setAxis 轴向的选择
C++ PCL SACSegmentationFromNormals setAxis 轴向的选择
82 2
|
C++ 计算机视觉
vs安装pcl库,遇到的问题总结(全)
vs安装pcl库,遇到的问题总结(全)
397 0
|
传感器 编解码 索引
|
数据可视化 算法
|
机器学习/深度学习 存储 算法
PCL中使用FLANN库(1)
FLANN库全称是Fast Library for Approximate Nearest Neighbors,它是目前最完整的(近似)最近邻开源库。不但实现了一系列查找算法,还包含了一种自动选取最快算法的机制,在一个度量空间X给定一组点P=p1,p2,…,pn,这些点必须通过以下方式进行预处理,给第一个新的查询点q属于X,快速在P中找到距离q最近的点,即最近邻搜索问题。
2198 0
|
传感器 数据挖掘 索引
PCL中使用FLANN库(2)
接着上一篇的介绍继续 关于在使用readHeader函数读取点云数据头的类型的代码(Read a point cloud data header from a PCD file.) pcl::PCLPointCloud2 cloud; int version; Eigen:...
1972 0
|
Ubuntu C++ Windows
VS2017安装PCL1.8.1
很多使用在windows环境下编译和使用PCL,这样让我想试试,所以就迫不得已的放弃使用Ubuntu环境,但是我还是建议使用Ubuntu系统,毕竟在Ubuntu下几条命令就搞定了,为了迎合在window使用PCL开发kinect,今天就试着在vS下配置和使用PCL,习惯了一边安装一边记录,首先安装VS2017,直接就是百度的界面提示所安装的VS2017 (1)下载PCL-1.
2140 0
PCL常见错误集锦
来自微信公众号的分享 我刚刚开始接触PCL,懂的东西也很少,所以总是出现各种各样的问题,每次遇见问题的时候要查找各种各样的资料,很费时间。所以,今天我把我遇见的常见问题分享给大家,讲解的步骤尽量详细,让和我一样基础差的小伙伴能尽快进入到PCL点云库的学习中,希望能和大家进步。
1410 0
|
算法 数据挖掘 定位技术
PCL中分割方法的介绍(3)
(3)上两篇介绍了关于欧几里德分割,条件分割,最小分割法等等还有之前就有用RANSAC法的分割方法,这一篇是关于区域生成的分割法, 区 域生长的基本 思想是: 将具有相似性的像素集合起来构成区域。首先对每个需要分割的区域找出一个种子像素作为生长的起点,然后将种子像素周围邻域中与种子有相同或相似性质的像素 (根据事先确定的生长或相似准则来确定)合并到种子像素所在的区域中。
2283 0
|
算法 数据挖掘 资源调度
PCL中分割方法的介绍(2)
(2)关于上一篇博文中提到的欧几里德分割法称之为标准的距离分离,当然接下来介绍其他的与之相关的延伸出来的聚类的方法,我称之为条件欧几里德聚类法,(是我的个人理解),这个条件的设置是可以由我们自定义的,因为除了距离检查,聚类的点还需要满足一个特殊的自定义的要求,就是以第一个点为标准作为种子点,候选其周...
1670 0