通俗总结 Octree（八叉树）

第一步建树一次性做好后面不再切盒子重点先用一个大盒子把你所有的点云全部包进去。把这个盒子X/Y/Z三个方向同时对半切一刀 → 切成8个小盒子。挨个看这些小盒子如果小盒子的边长还大于你设定的resolution最小格子边长继续把这个盒子切成8份如果盒子边长 resolution停止切分这个就是最小叶子盒子不再切。每个最小叶子盒子记住落在它内部所有点的编号。✅ 建树完成之后所有小盒子位置固定不会再变不会临时切割。就像把一块豆腐一次性切成很多固定大小的小方块切完就定型了。第二步搜索三种搜索完全不一样给定一个查询点 searchPoint① voxelSearch【八叉树特有】逻辑看这个查询点落在哪一块已经切好的小豆腐块叶子盒子里面直接拿出这一整块豆腐里面全部的点返回⚠️关键点是固定方块里面的点不是“离查询点距离小于resolution”方块边界在建树的时候就固定死了不会跟着查询点移动。形状立方体盒子。举例子小盒子边长128。查询点在这个盒子靠右的位置盒子左边很远的点只要在这个盒子里也会被拿出来。② nearestKSearchK近邻逻辑找离查询点最近的K个点。八叉树只是用来加速查找优先检查查询点附近的盒子不用遍历全部1000个点。输出最近K个和KDTree功能一样只是底层加速结构不同。③ radiusSearch半径搜索逻辑以查询点为球心画一个圆球取出圆球里面所有点。同样利用八叉树快速跳过大量完全不在球内的盒子减少计算。形状球体可以跨好几个小豆腐块。一句话区分3个搜索voxelSearch取【同一个固定小方块】里面所有点方块判定radiusSearch取【查询点为中心的圆球】里面所有点距离判定nearestKSearch找【距离最近K个点】超级简短一句话整体概括八叉树就是预先把整个点云空间一次性切成一堆固定大小的小立方体搜索的时候利用这些预先切好的盒子快速查找点voxelSearch直接拿查询点所在盒子内全部点另外两种是球形/最近点查找八叉树只是用来加速遍历。对比KDTreeKDTree不会切成固定方块没有voxelSearch。#includepcl/point_cloud.h//点云头文件#includepcl/octree/octree.h//八叉树头文件#includeiostream#includevector#includectimeintmain(intargc,char**argv){srand((unsignedint)time(NULL));//用系统时间初始化随机种子与 srand (time (NULL))的区别pcl::PointCloudpcl::PointXYZ::Ptrcloud(newpcl::PointCloudpcl::PointXYZ);// 创建点云数据cloud-width1000;cloud-height1;//无序cloud-points.resize(cloud-width*cloud-height);for(size_t i0;icloud-points.size();i)//随机循环产生点云的坐标值{cloud-points[i].x1024.0f*rand()/(RAND_MAX1.0f);cloud-points[i].y1024.0f*rand()/(RAND_MAX1.0f);cloud-points[i].z1024.0f*rand()/(RAND_MAX1.0f);}/**************************************************************************** 创建一个octree实例用设置分辨率进行初始化该octree用它的页节点存放点索引向量 分辨率参数描述最低一级octree的最小体素的尺寸因此octree的深度是分辨率和点云空间维度 的函数如果知道点云的边界框应该用defineBoundingbox方法把它分配给octree然后通过 点云指针把所有点增加到ctree中。 *****************************************************************************/floatresolution128.0f;pcl::octree::OctreePointCloudSearchpcl::PointXYZoctree(resolution);//初始化Octreeoctree.setInputCloud(cloud);//设置输入点云 这两句是最关键的建立PointCloud和octree之间的联系octree.addPointsFromInputCloud();//构建octreepcl::PointXYZ searchPoint;//设置searchPointsearchPoint.x1024.0f*rand()/(RAND_MAX1.0f);searchPoint.y1024.0f*rand()/(RAND_MAX1.0f);searchPoint.z1024.0f*rand()/(RAND_MAX1.0f);/************************************************************************************* 一旦PointCloud和octree联系一起就能进行搜索操作这里使用的是“体素近邻搜索”把查询点所在体素中 其他点的索引作为查询结果返回结果以点索引向量的形式保存因此搜索点和搜索结果之间的距离取决于octree的分辨率参数 *****************************************************************************************/std::vectorintpointIdxVec;//存储体素近邻搜索结果向量if(octree.voxelSearch(searchPoint,pointIdxVec))//执行搜索返回结果到pointIdxVec{std::coutNeighbors within voxel search at (searchPoint.x searchPoint.y searchPoint.z)std::endl;for(size_t i0;ipointIdxVec.size();i)//打印结果点坐标std::cout cloud-points[pointIdxVec[i]].x cloud-points[pointIdxVec[i]].y cloud-points[pointIdxVec[i]].zstd::endl;}/********************************************************************************** K 被设置为10 K近邻搜索 方法把搜索结果写到两个分开的向量第一个pointIdxNKNSearch包含搜索结果 结果点的索引的向量 第二个向量pointNKNSquaredDistance存储搜索点与近邻之间的距离的平方。 *************************************************************************************///K 近邻搜索intK10;std::vectorintpointIdxNKNSearch;//结果点的索引的向量std::vectorfloatpointNKNSquaredDistance;//搜索点与近邻之间的距离的平方std::coutK nearest neighbor search at (searchPoint.x searchPoint.y searchPoint.z) with KKstd::endl;if(octree.nearestKSearch(searchPoint,K,pointIdxNKNSearch,pointNKNSquaredDistance)0){for(size_t i0;ipointIdxNKNSearch.size();i)std::cout cloud-points[pointIdxNKNSearch[i]].x cloud-points[pointIdxNKNSearch[i]].y cloud-points[pointIdxNKNSearch[i]].z (squared distance: pointNKNSquaredDistance[i])std::endl;}// 半径内近邻搜索std::vectorintpointIdxRadiusSearch;std::vectorfloatpointRadiusSquaredDistance;floatradius256.0f*rand()/(RAND_MAX1.0f);std::coutNeighbors within radius search at (searchPoint.x searchPoint.y searchPoint.z) with radiusradiusstd::endl;if(octree.radiusSearch(searchPoint,radius,pointIdxRadiusSearch,pointRadiusSquaredDistance)0){for(size_t i0;ipointIdxRadiusSearch.size();i)std::cout cloud-points[pointIdxRadiusSearch[i]].x cloud-points[pointIdxRadiusSearch[i]].y cloud-points[pointIdxRadiusSearch[i]].z (squared distance: pointRadiusSquaredDistance[i])std::endl;}}/* * Description: 点云压缩读取本地PCD文件版本https://www.cnblogs.com/li-yao7758258/p/6436117.html * Author: HCQ * Company(School): UCAS * Email: 1756260160qq.com * Date: 2020-10-13 10:10:33 * LastEditTime: 2020-10-27 16:02:18 * FilePath: /pcl-learning/03octree/1point_cloud_compression/point_cloud_compression.cpp */#includepcl/point_cloud.h// 点云类型#includepcl/point_types.h// 点数据类型#includepcl/io/pcd_io.h// PCD文件读写#includepcl/visualization/cloud_viewer.h// 点云可视化类#includepcl/compression/octree_pointcloud_compression.h// 点云压缩类#includestdio.h#includesstream#includestdlib.h#includestring#includeiostream#ifdefWIN32#includewindows.h#definesleep(x)Sleep((x)*1000)#else#includeunistd.h// sleep()#endifintmain(intargc,char**argv){// 读取点云文件优先使用命令行传入的文件名否则使用默认路径std::string pcd_file;if(argc2){pcd_fileargv[1];}else{pcd_file../../../data/table_scene_mug_stereo_textured.pcd;}// 创建点云对象从本地PCD文件加载点云pcl::PointCloudpcl::PointXYZRGB::Ptrcloud(newpcl::PointCloudpcl::PointXYZRGB());if(pcl::io::loadPCDFilepcl::PointXYZRGB(pcd_file,*cloud)0){std::cerrError loading point cloud pcd_filestd::endl;return-1;}std::coutLoaded cloud-points.size() points from pcd_filestd::endl;// 是否在标准输出上打印压缩结果统计信息boolshowStatisticsfalse;// 压缩选项详情在: /io/include/pcl/compression/compression_profiles.h// 使用带颜色的在线快速压缩配置参数集pcl::io::compression_Profiles_e compressionProfilepcl::io::MED_RES_ONLINE_COMPRESSION_WITH_COLOR;// 初始化压缩和解压缩对象压缩对象需要设定压缩参数选项解压缩按照数据源自行判断pcl::io::OctreePointCloudCompressionpcl::PointXYZRGB*PointCloudEncodernewpcl::io::OctreePointCloudCompressionpcl::PointXYZRGB(compressionProfile,showStatistics);pcl::io::OctreePointCloudCompressionpcl::PointXYZRGB*PointCloudDecodernewpcl::io::OctreePointCloudCompressionpcl::PointXYZRGB();// 存储压缩点云的字节流对象std::stringstream compressedData;// 存储解压缩后的输出点云pcl::PointCloudpcl::PointXYZRGB::PtrcloudOut(newpcl::PointCloudpcl::PointXYZRGB());// 压缩点云PointCloudEncoder-encodePointCloud(cloud,compressedData);std::coutCompressed data size: compressedData.str().size() bytesstd::endl;// 解压缩点云PointCloudDecoder-decodePointCloud(compressedData,cloudOut);std::coutDecompressed points: cloudOut-points.size()std::endl;// 可视化解压缩后的点云pcl::visualization::CloudViewerviewer(Point Cloud Compression Example);viewer.showCloud(cloudOut);// 阻塞等待直到关闭可视化窗口while(!viewer.wasStopped()){sleep(1);}// 释放压缩与解压缩实例delete(PointCloudEncoder);delete(PointCloudDecoder);return0;}逐行讲解这份PCL八叉树点云压缩代码整体流程读取本地pcd点云 → 创建八叉树压缩编码器解码器 → 编码成二进制字节流 → 从字节流解码还原点云 → 可视化解压后的点云核心类pcl::io::OctreePointCloudCompression基于八叉树实现有损点云压缩#include pcl/point_cloud.h // 点云容器头文件定义PointCloud模板类 #include pcl/point_types.h // 点类型定义这里要用pcl::PointXYZRGB #include pcl/io/pcd_io.h // PCD文件读写loadPCDFile #include pcl/visualization/cloud_viewer.h // 点云可视化窗口 CloudViewer #include pcl/compression/octree_pointcloud_compression.h // 八叉树点云压缩核心头文件 #include stdio.h #include sstream // stringstream内存里的字节流存放压缩后的二进制数据 #include stdlib.h #include string #include iostream // 跨平台sleep兼容Windows和Linux sleep函数不一样 #ifdef WIN32 #include windows.h #define sleep(x) Sleep((x)*1000) // windows Sleep单位ms所以*1000 #else #include unistd.h // linux下sleep单位是秒 #endifint main(int argc, char **argv) { // 1. 读取PCD文件支持命令行传参 std::string pcd_file; if (argc 2) { // 命令行运行 ./xxx your.pcdargv[1]就是pcd路径 pcd_file argv[1]; } else { // 不传参数使用默认pcd文件 pcd_file ../../../data/table_scene_mug_stereo_textured.pcd; } // 创建点云智能指针PointXYZRGB 带xyz坐标RGB颜色 pcl::PointCloudpcl::PointXYZRGB::Ptr cloud(new pcl::PointCloudpcl::PointXYZRGB()); // 加载PCD到cloud返回0代表读取失败 if (pcl::io::loadPCDFilepcl::PointXYZRGB(pcd_file, *cloud) 0) { std::cerr Error loading point cloud pcd_file std::endl; return -1; } std::cout Loaded cloud-points.size() points from pcd_file std::endl;// 2. 创建八叉树压缩编码器、解码器 bool showStatistics false; // 是否打印压缩详细统计信息耗时、压缩率等 // 压缩预设配置来自compression_profiles.h // MED_RES_ONLINE_COMPRESSION_WITH_COLOR中等分辨率、支持RGB颜色、适合在线实时流 pcl::io::compression_Profiles_e compressionProfile pcl::io::MED_RES_ONLINE_COMPRESSION_WITH_COLOR; // 【编码器】构造参数压缩配置、是否输出统计 pcl::io::OctreePointCloudCompressionpcl::PointXYZRGB *PointCloudEncoder new pcl::io::OctreePointCloudCompressionpcl::PointXYZRGB(compressionProfile, showStatistics); // 【解码器】无参构造不需要配置profile压缩流内部自带配置信息自动解析 pcl::io::OctreePointCloudCompressionpcl::PointXYZRGB *PointCloudDecoder new pcl::io::OctreePointCloudCompressionpcl::PointXYZRGB();✅ 关键点编码器需要预设压缩等级解码器不需要压缩后的字节流里已经保存了八叉树分辨率、颜色配置等信息解码器自动读取。// 3. 执行压缩 encodePointCloud std::stringstream compressedData; // 内存字节流存放压缩后的二进制数据 pcl::PointCloudpcl::PointXYZRGB::Ptr cloudOut(new pcl::PointCloudpcl::PointXYZRGB()); // 核心压缩函数 // 参数原始点云输出字节流 PointCloudEncoder-encodePointCloud(cloud, compressedData); std::cout Compressed data size: compressedData.str().size() bytes std::endl;encodePointCloud内部做的事情根据profile的分辨率构建八叉树体素合并同一个体素内多个点合并成1个体素中心点有损对xyz坐标、RGB颜色做量化编码把编码后的二进制数据写入compressedData内存流 这个compressedData.str()拿到std::string二进制可以直接通过网络socket发送或者写入本地二进制文件保存// 4. 执行解压 decodePointCloud PointCloudDecoder-decodePointCloud(compressedData, cloudOut); std::cout Decompressed points: cloudOut-points.size() std::endl;decodePointCloud读取字节流重建八叉树还原点云到cloudOut⚠️ 重点cloudOut的点数 ≠ 原始cloud点数坐标是近似值有损压缩// 5. 可视化 pcl::visualization::CloudViewer viewer(Point Cloud Compression Example); viewer.showCloud(cloudOut); // 显示解压后的点云 // 阻塞循环一直等待直到关闭可视化窗口 while (!viewer.wasStopped()) { sleep(1); }// 6. 手动释放堆内存 delete (PointCloudEncoder); delete (PointCloudDecoder); return 0; }这里用new创建对象程序结束前必须delete释放现代C推荐用智能指针unique_ptr代替手动new/delete避免内存泄漏。整体逻辑简图PCD文件 → loadPCDFile → 原始点云cloud ↓ Octree编码器 encode → 二进制字节流compressedData ↓ Octree解码器 decode → 解压点云cloudOut ↓ CloudViewer可视化 cloudOut重要补充要点压缩本质八叉树体素量化不是对PCD文本做zip压缩。建树设定体素大小格子里多个点合并为中心点所以是有损。压缩预设选项你可以替换LOW_RES_ONLINE_COMPRESSION_WITHOUT_COLOR // 低分辨率、无颜色压缩最强失真大 MED_RES_ONLINE_COMPRESSION_WITH_COLOR // 当前代码中等分辨率带RGB HIGH_RES_ONLINE_COMPRESSION_WITH_COLOR // 高分辨率带RGB失真最小压缩包更大典型用途机器人/深度相机实时点云网络传输连续帧点云存储。❌ 不适合高精度工业测量坐标有误差。可扩展小修改可选把compressedData.str()写入本地.bin文件存压缩后的点云读取bin文件送入解码器实现离线存储加载打开showStatisticstrue打印压缩耗时、原始大小、压缩倍率。