KD-Tree 学习笔记

学习资料:

1.B站 - 一只叫小花的猫
2.语雀 - 双愚:kdtree
3.B站视频:学习kdtree的前置知识:KNN算法

KD树简介与背景

  k-d树,是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索。关于kd树的背景,它主要是一种解决特征点匹配问题的算法,kd树就是一种高维空间索引结构和近似查询的算法。
  关于特征匹配算子,可以分为两类,第一种就是线性扫描法,但是这种方法将数据集中的点与查询点逐一进行距离比较,也就是穷举,缺点很明显,搜索效率较低。其次就是建立数据索引,而kdtree正是这样一种方法,其基本思想就是对搜索空间进行层次划分,划分空间没有重叠。

KD树的结构

下面这段话选自语雀 - 双愚:kdtree


看似较为复杂,其实一点都不复杂,二叉排序树学过吧,其实kdtree有些地方与二叉排序树有点相似,即左小右大,但是严格上来讲,又不是完全的相似,来看下面的图:kdtree的构造过程:

有这样的一些点集,在坐标系中画出这些点,首先我们按照垂直于x轴进行划分,如图(1),找到每个点的横坐标,2、3、4、7、8、9,取中位数为(4+7)/ 2 = 5.5,那么既然与4和7的距离都是1.5,所以我们可以取7作为一个划分的标准,分成左右两块,这时就把点(7,2)加入到树中,接着我们就按照y轴进行划分,取左右两块分别划分,与上面的逻辑是相同的,划分完毕再把点加入到树中,要注意左小右大,以此类推即可划分成功。注意:当一科kdtree的子树结点只有一个孩子时,不存在左右孩子这种说法。

KD树查找最邻近点算法

如图(选自上面b站视频):

在这里我们想找(3, 4.5)的邻近点,分为以下几个步骤:

  1. 首先看树根,这里记为第1层,树根是x(1)(这里我们把x(1)看为x轴,x(2)看为y轴),因为要找横轴为3的点,故找比7小的,这时到达(5,4)。
  2. (5,4)在y的行中,所以这时我们看4,由于4.5>4, 这时进入到(4, 7)。
  3. 到达叶子结点(4, 7),这时我们把它作为当前最临近点,计算到(3, 4.5)的距离为2.69。
  4. 开始回溯,到(5, 4),距离为2.06,更新最邻近点。这时我们发现,(3, 4.5)与(5, 4)连线为半径做圆,与y=4超平面相交,那么这时还需要进入到另一个子空间进行查找,也就是得回溯到(2, 3)这里,计算后,距离为1.8。
  5. 再次做圆,此圆与x=7并不相交,故不用进入到根结点右子树进行查找。结束。

KD树上的KNN算法

KD树相关函数

PCL中类pcl::KdTree<PointT>是kd-tree数据结构的实现。并且提供基于FLANN进行快速搜索的一些相关子类与包装类。具体可以参考相应的API。下面给出2个类的具体用法。

  1. pcl::search::KdTree < PointT >
    pcl::search::KdTree<PointT>pcl::search::Search< PointT >的子类,是pcl::KdTree<PointT>的包装类。包含(1) k 近邻搜索;(2) 邻域半径搜索。
    示例代码:
#include <pcl/io/pcd_io.h>
#include <pcl/point_types.h>
#include <pcl/search/kdtree.h> // 包含kdtree头文件
typedef pcl::PointXYZ PointT;
int main()
{
	pcl::PointCloud<PointT>::Ptr cloud(new pcl::PointCloud<PointT>);
	pcl::io::loadPCDFile("read.pcd", *cloud);
	// 定义KDTree对象
	pcl::search::KdTree<PointT>::Ptr kdtree(new pcl::search::KdTree<PointT>);
	kdtree->setInputCloud(cloud); // 设置要搜索的点云,建立KDTree
	std::vector<int> indices; // 存储查询近邻点索引
	std::vector<float> distances; // 存储近邻点对应距离的平方
	PointT point = cloud->points[0]; // 初始化一个查询点
	
	// 查询距point最近的k个点
	int k = 10;
	int size = kdtree->nearestKSearch(point, k, indices, distances);
	std::cout << "search point : " << size << std::endl;
	// 查询point半径为radius邻域球内的点
	double radius = 2.0;
	size = kdtree->radiusSearch(point, radius, indices, distances);
	std::cout << "search point : " << size << std::endl;
	system("pause");
	return 0;
}
  1. pcl::KdTreeFLANN < PointT >
    pcl::KdTreeFLANN<PointT>pcl::KdTree<PointT>的子类,可以实现同样的功能。
#include <pcl/io/pcd_io.h>
#include <pcl/point_types.h>
// 包含相关头文件
#include <pcl/kdtree/kdtree_flann.h>
typedef pcl::PointXYZ PointT;
int main()
{
	pcl::PointCloud<PointT>::Ptr cloud(new pcl::PointCloud<PointT>);
	pcl::io::loadPCDFile("read.pcd", *cloud);
	pcl::KdTreeFLANN<pcl::PointXYZ> kdtree; //创建KDtree
	kdtree.setInputCloud(cloud); // 设置要搜索的点云,建立KDTree
	std::vector<int> indices; // 存储查询近邻点索引
	std::vector<float> distances; // 存储近邻点对应距离的平方
	PointT point = cloud->points[0]; // 初始化一个查询点
	
	// 查询距point最近的k个点
	int k = 10;
	int size = kdtree.nearestKSearch(point, k, indices, distances);
	std::cout << "search point : " << size << std::endl;
	// 查询point半径为radius邻域球内的点
	double radius = 2.0;
	size = kdtree.radiusSearch(point, radius, indices, distances);
	std::cout << "search point : " << size << std::endl;
	system("pause");
	return 0;
}

热门相关:辰少的霸道专宠:强婚88次   末日终战   重生娘子在种田   奉旨成婚:悍妃训夜王   退婚后我嫁给了前任他叔