欢迎点云相关产学研的学者和团体加入我们。
octree是一种用于管理稀疏3D数据的树状数据结构,每个内部节点都正好有八个子节点,本小节中我们学习如何用octree在点云数据中进行空间划分及近邻搜索,特别地,解释了如何完成“体素内近邻搜索(Neighbors within Voxel Search)”、“K近邻搜索(K Nearest Neighbor Search)”和“半径内近邻搜索(Neighbors within Radius Search)”。
首先,在PCL(Point Cloud Learning)中国协助发行的书提供光盘的第6章例2文件夹中,打开名为octree_search.cpp的代码文件。
下面解析打开的源代码,我们首先定义并实例化一个PointCloud指针对象,并且用随机点集赋值给它。
pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);
//创建点云数据
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);
}
然后创建一个octree实例,用设置分辨率进行初始化,该octree用它的叶节点存放点索引向量,该分辨率参数描述最低一级octree的最小体素的尺寸,因此octree的深度是分辨率和点云空间维数的函数,如果知道点云的边界框,应该用defineBoundingBox方法把它分配给octree,然后通过点云指针把所有点增加到octree中。
float resolution=128.0f;
pcl::octree::OctreePointCloudSearch<pcl::PointXYZ> octree(resolution); //初始化octree
octree.setInputCloud(cloud); //设置输入点云
octree.addPointsFromInputCloud(); //构建octree
一旦PointCloud和octree联系在一起,我们就能进行搜索操作,这里使用的第一种搜索方法是“体素近邻搜索”,它把查询点所在的体素中其他点的索引作为查询结果返回,结果以点索引的向量的形式保存,因此搜索点和搜索结果之间的距离取决于octree的分辨率参数。
std::vector<int> pointIdxVec; //存储体素近邻搜索的结果向量
if(octree.voxelSearch(searchPoint,pointIdxVec)) //执行搜索,返回结果到pointIdxVec
{
std::cout<<"Neighbors 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;
}
接下来,介绍K近邻搜索,本例中,K被设置成10,“K近邻搜索”方法把搜索结果写到两个分开的向量中,第一个,pointIdxNKNSearch,包含搜索结果(结果点的索引的向量),第二个向量保存相应的搜索点和近邻之间的平方距离。
//K近邻搜索
int K =10;
std::vector<int> pointIdxNKNSearch; //存储k近邻搜索点索引结果
std::vector<float> pointNKNSquaredDistance; //与上面对应的平方距离
std::cout<<"K nearest neighbor 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
<<" (squared distance: "<<pointNKNSquaredDistance[i] <<")"<<std::endl;
}
“半径内近邻搜索”原理和“K近邻搜索”类似,它的搜索结果被写入两个分开的向量中,这两个向量分别存储结果点的索引和对应的平方距离。
//半径内近邻搜索
std::vector<int> pointIdxRadiusSearch;
std::vector<float> pointRadiusSquaredDistance;
float radius =256.0f* rand () / (RAND_MAX +1.0f);
std::cout<<"Neighbors within radius search at ("<<searchPoint.x
<<" "<<searchPoint.y
<<" "<<searchPoint.z
<<") with radius="<< radius <<std::endl;
if (octree.radiusSearch (searchPoint, radius, pointIdxRadiusSearch, pointRadiusSquaredDistance) >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: "<<pointRadiusSquaredDistance[i] <<")"<<std::endl;
利用光盘提供的CMakeLists.txt文件,在cmake中建立工程文件,并生成相应的可执行文件,生成执行文件后,就可以运行了,在cmd中键入命令:
...>octreesearch.exe
运行结果如图1所示,分别打印出不同搜索方式的输出结果。
图1 octree空间搜索实例运行结果
PCL octree组件提供了几个octree类型。它们各自的叶节点特征基本上是不同的。
OctreePointCloudPointVector(等于OctreePointCloud):该octree能够保存每一个叶节点上的点索引列。
OctreePointCloudSinglePoint:该octree类仅仅保存每一个叶节点上的单个点索引。仅仅保存最后分配给叶节点的点索引。
OctreePointCloudOccupancy:该octree不存储它的叶节点上的任何点信息。它能用于空间填充情况检查。
OctreePointCloudDensity:该octree存储每一个叶节点体素中的点的数目。它可以进行空间点集密集成度查询。
如果需要高频率创建octree,请参看octree双缓冲技术实现(Octree2BufBase类)。该类在内存中同时保存了两个类似的octree对象。除了搜索操作之外,也可以用于空间变化检测。此外,高级内存管理减少了octree建立过程中的内存分配和释放操作。双缓冲技术对octree的实现可以通过设置模板参数“OctreeT”实例化不同的OctreePointCloud类。所有的octree都支持octree结构和octree内容的串行化和反串行化。
敬请关注PCL(Point Cloud Learning)中国更多的点云库PCL(Point Cloud Library)相关官方教程。
参考文献:
1.朱德海、郭浩、苏伟.点云库PCL学习教程(ISBN 978-7-5124-0954-5)北京航空航天出版社 2012-10