本文主要是介绍kd-tree理论以及在PCL 中的代码的实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
(小技巧记录:博客园编辑的网页界面变小了使用Ctrl ++来变大网页字体)通过雷达,激光扫描,立体摄像机等三维测量设备获取的点云数据,具有数据量大,分布不均匀等特点,作为三维领域中一个重要的数据来源,点云主要是表征目标表面的海量点的集合,并不具备传统网格数据的几何拓扑信息,所以点云数据处理中最为核心的问题就是建立离散点间的拓扑关系,实现基于邻域关系的快速查找。
k-d树 (k-dimensional树的简称),是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。K-D树是二进制空间分割树的特殊的情况。用来组织表示K维空间中点的几何,是一种带有其他约束的二分查找树,为了达到目的,通常只在三个维度中进行处理因此所有的kd_tree都将是三维的kd_tree,kd_tree的每一维在指定维度上分开所有的字节点,在树 的根部所有子节点是以第一个指定的维度上被分开。
k-d树算法可以分为两大部分,一部分是有关k-d树本身这种数据结构建立的算法,另一部分是在建立的k-d树上如何进行最邻近查找的算法。
构建算法
k-d树是一个二叉树,每个节点表示一个空间范围。表1给出的是k-d树每个节点中主要包含的数据结构。
域名 | 数据类型 | 描述 |
Node-data | 数据矢量 | 数据集中某个数据点,是n维矢量(这里也就是k维) |
Range | 空间矢量 | 该节点所代表的空间范围 |
split | 整数 | 垂直于分割超平面的方向轴序号 |
Left | k-d树 | 由位于该节点分割超平面左子空间内所有数据点所构成的k-d树 |
Right | k-d树 | 由位于该节点分割超平面右子空间内所有数据点所构成的k-d树 |
parent | k-d树 | 父节点 |
先以一个简单直观的实例来介绍k-d树算法。假设有6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},数据点 位于二维空间内(如图1中黑点所示)。k-d树算法就是要确定图1中这些分割空间的分割线(多维空间即为分割平面,一般为超平面)。下面就要通过一步步展 示k-d树是如何确定这些分割线的。
virtual void pcl::KdTree< PointT >::setInputCloud | ( | const PointCloudConstPtr & | cloud, |
const IndicesConstPtr & | indices = IndicesConstPtr () | ||
) |
virtual int pcl::KdTree< PointT >::nearestKSearch | ( | int | index, |
int | k, | ||
std::vector< int > & | k_indices, | ||
std::vector< float > & | k_sqr_distances | ||
) | const |
#include <pcl/point_cloud.h> //点类型定义头文件 #include <pcl/kdtree/kdtree_flann.h> //kdtree类定义头文件 #include <iostream> #include <vector> #include <ctime>int main (int argc, char** argv) {srand (time (NULL)); //用系统时间初始化随机种子//创建一个PointCloud<pcl::PointXYZ>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);}//创建KdTreeFLANN对象,并把创建的点云设置为输入,创建一个searchPoint变量作为查询点pcl::KdTreeFLANN<pcl::PointXYZ> kdtree;//设置搜索空间 kdtree.setInputCloud (cloud);//设置查询点并赋随机值 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);// K 临近搜索//创建一个整数(设置为10)和两个向量来存储搜索到的K近邻,两个向量中,一个存储搜索到查询点近邻的索引,另一个存储对应近邻的距离平方int K = 10;std::vector<int> pointIdxNKNSearch(K); //存储查询点近邻索引std::vector<float> pointNKNSquaredDistance(K); //存储近邻点对应距离平方//打印相关信息std::cout << "K nearest neighbor search at (" << searchPoint.x << " " << searchPoint.y << " " << searchPoint.z<< ") with K=" << K << std::endl;if ( kdtree.nearestKSearch (searchPoint, K, pointIdxNKNSearch, pointNKNSquaredDistance) > 0 ) //执行K近邻搜索 {//打印所有近邻坐标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;}/**********************************************************************************下面的代码展示查找到给定的searchPoint的某一半径(随机产生)内所有近邻,重新定义两个向量pointIdxRadiusSearch pointRadiusSquaredDistance来存储关于近邻的信息********************************************************************************/// 半径 R内近邻搜索方法 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 ( kdtree.radiusSearch (searchPoint, radius, pointIdxRadiusSearch, pointRadiusSquaredDistance) > 0 ) //执行半径R内近邻搜索方法 {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;}return 0; }
这篇关于kd-tree理论以及在PCL 中的代码的实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!