可能最近的项目和数据结构之类的杠上了开始恶补一些数据结构的知识加上学习PCL经常会使用kd-treeoctree之类的作为知识储备也好或者觉得其实这些也挺有趣的记录下来方便以后查阅也罢总之还是会努力加油的啦O(∩_∩)O哈哈~八叉树Octree是一种用于描述三维空间的树状数据结构每个根节点有8个子节点理想情况下也许就是八叉树名字的由来。我们先从一维开始如何快速的在x轴上找到一个理想的数一般以0为基准会问大于0还是小于零也就是说一维的情况下就是以二叉树为代表做查找或者插入等操作。那么在二维的情况下呢这个最直观了在白纸上就能这么分把一整块区域分成四块如下图所示然后对每块在进行细分这就是四叉树。三维呢西瓜都吃过吧怎么切三刀把西瓜平均分成八分这用到的就是八叉树的原理啦然后把每一块再进行细分直到达到最大的level数或者说已经分到了体素级别了。什么叫体素voxel在二维图像中通常都会说像素就是表示二维图像的最小单位当然还有亚像素一般情况下还是用像素作为基本的单位对应到三维就是体素如果长度为1可能理解起来就是一个非常小的立方体如果存在则这个小立方体是填充状态如果是空的就代表没有数据。查找对应的数据在通常情况下规模是八分之一的缩小的。极端情况下比如说你查找的数是蹲在墙角的那么找它的时间会长一些。这段代码主要做的工作就是在随机生成的点云中利用KNN或者RadiusSearch在构造好的octree中查找指定的点云。#include iostream #includepcl/point_cloud.h #includepcl/octree/octree_search.h #include vector #include ctime #include boost/concept_check.hpp int main(int argc, char ** argv) { srand((unsigned int) time (NULL)); pcl::PointCloudpcl::PointXYZ::Ptr cloud(new pcl::PointCloudpcl::PointXYZ); //generate pointcloud data cloud-width 1000; cloud-height 1; cloud-points.resize(cloud-width *cloud-height); for(size_t i 0; i cloud-points.size(); i) { cloud-points[i].x 1024.0f * rand() / (RAND_MAX 1.0f); cloud-points[i].y 1024.0f * rand() / (RAND_MAX 1.0f); cloud-points[i].z 1024.0f * rand() / (RAND_MAX 1.0f); } //分辨率描述了最小体元素的长度为128如果点云的边界框是已知的应该使用defineBoundingBox的方法分配给octree float resolution 128.0f; pcl::octree::OctreePointCloudSearchpcl::PointXYZ octree (resolution); octree.setInputCloud(cloud); octree.addPointsFromInputCloud(); pcl::PointXYZ searchPoint; searchPoint.x 1024.0f * rand() / (RAND_MAX 1.0f); searchPoint.y 1024.0f * rand() / (RAND_MAX 1.0f); searchPoint.z 1024.0f * rand() / (RAND_MAX 1.0f); std::vectorint pointIdxVec; if(octree.voxelSearch(searchPoint, pointIdxVec)) { std::cout Neighbour within voxel search at ( searchPoint.x searchPoint.y searchPoint.z ) std::endl; for(size_t i 0; i pointIdxVec.size(); i) { std::cout cloud-points[pointIdxVec[i]].x cloud-points[pointIdxVec[i]].y cloud-points[pointIdxVec[i]].z std::endl; } } int K 10; std::vectorint pointIdxNKNSearch; std::vectorfloat pointNKNSquaredDistance; std::cout K nearest neighbour search at ( searchPoint.x searchPoint.y searchPoint.z ) with K K std::endl; if(octree.nearestKSearch(searchPoint, K, pointIdxNKNSearch, pointNKNSquaredDistance) 0) { for(size_t i 0; i pointIdxNKNSearch.size(); i) std::cout cloud-points[pointIdxNKNSearch[i]].x cloud-points[pointIdxNKNSearch[i]].y cloud-points[pointIdxNKNSearch[i]].z ( square distance: pointNKNSquaredDistance[i] ) std::endl; } std::vectorintpointIdxRadiusSearch; std::vectorfloat pointRadiusSquareDistance; float radius 256.0f * rand() / (RAND_MAX 1.0f); std::cout Neighbours within radius search at ( searchPoint.x searchPoint.y searchPoint.z ) with radius radius std::endl; if(octree.radiusSearch(searchPoint, radius, pointIdxRadiusSearch, pointRadiusSquareDistance) 0) { for(size_t i 0; i pointIdxRadiusSearch.size(); i) std::cout cloud-points[pointIdxRadiusSearch[i]].x cloud-points[pointIdxRadiusSearch[i]].y cloud-points[pointIdxRadiusSearch[i]].z (squared distance: pointRadiusSquareDistance[i] ) std::endl; } }数据是随机取得每次实验结果可能会有所不同O(∩_∩)O哈哈~什么叫“organized” point cloud什么又叫“unorganized” point cloud看paper的时候有些疑惑后来查了资料得知“unorganized” LZ感觉翻译过来总是怪怪的就不翻译了就是指点云的特征会有所不同例如会有不同的尺寸分辨率密度或者排序没有一个特别统一的形式。对于“organized”的点云通常是指有固定宽度或者高度的单个深度图对于一些数据的分析相对来说可能快一些例如直接用rgbd相机获取的点云应该就是属于organized的下面这段代码的主要工作是随机生成两个点云都构造成ocree检索点云B中体素上的点如果在点云A中不存在就返回点的indices#include iostream #include vector #include ctime #include pcl/point_cloud.h #include pcl/octree/octree.h #include boost/iterator/iterator_concepts.hpp int main(int argc, char **argv) { srand((unsigned int) time (NULL)); //octree resolution - side length of octree voxels float resolution 32.0f; //Instantiate octree-based point cloud change detection class pcl::octree::OctreePointCloudChangeDetectorpcl::PointXYZ octree(resolution); pcl::PointCloudpcl::PointXYZ::Ptr cloudA(new pcl::PointCloudpcl::PointXYZ); cloudA-width 128; cloudA-height 1; cloudA-points.resize(cloudA-width * cloudA-height); for(size_t i 0; i cloudA-points.size(); i) { cloudA-points[i].x 64.0f * rand() / (RAND_MAX 1.0f); cloudA-points[i].y 64.0f * rand() / (RAND_MAX 1.0f); cloudA-points[i].z 64.0f * rand() / (RAND_MAX 1.0f); } //add points from cloudA to octree octree.setInputCloud(cloudA); octree.addPointsFromInputCloud(); //switch octree buffers: this resets octree but keeps previous tree structure in memery octree.switchBuffers(); pcl::PointCloudpcl::PointXYZ::Ptr cloudB(new pcl::PointCloudpcl::PointXYZ); cloudB-width 128; cloudB-height 1; cloudB-points.resize(cloudB-width * cloudB-height ); for(size_t i 0; i cloudB-points.size(); i) { cloudB-points[i].x 64.0f * rand() / (RAND_MAX 1.0f); cloudB-points[i].y 64.0f * rand() / (RAND_MAX 1.0f); cloudB-points[i].z 64.0f * rand() / (RAND_MAX 1.0f); } //add points from cloudB to octree octree.setInputCloud(cloudB); octree.addPointsFromInputCloud(); std::vectorint newPointIdxVector; //get vector of point indices from octree voxel which did not exist in previous buffers octree.getPointIndicesFromNewVoxels(newPointIdxVector); //Output points std::cout Output from getPointIndicesFromNewVoxels: std::endl; for(size_t i 0; i newPointIdxVector.size(); i) std::cout i # Index: newPointIdxVector[i] point: cloudB-points[newPointIdxVector[i]].x cloudB-points[newPointIdxVector[i]].y cloudB-points[newPointIdxVector[i]].z std::endl; return 0; }参考地址http://www.pointclouds.org/documentation/tutorials/octree.php#octree-searchhttp://www.pointclouds.org/documentation/tutorials/octree_change.php#octree-change-detection