PCL中Kd树理论
k-d树（k-dimensional树的简称），是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。
01 Kd简介
K-D树是二进制空间分割树的特殊的情况。用来组织表示K维空间中点的几何，是一种带有其他约束的二分查找树，为了达到目的，通常只在三个维度中进行处理因此所有的kd_tree都将是三维的kd_tree,kd_tree的每一维在指定维度上分开所有的字节点，在树的根部所有子节点是以第一个指定的维度上被分开。
K-D树算法可以分为两大部分，一部分是有关k-d树本身这种数据结构建立的算法，另一部分是在建立的k-d树上如何进行最邻近查找的算法。
02 应用背景
比如SIFT算法中做特征点匹配的时候就会利用到k-d树。而特征点匹配实际上就是一个通过距离函数在高维矢量之间进行相似性检索的问题。针对如何快速而准确地找到查询点的近邻，现在提出了很多高维空间索引结构和近似查询的算法，k-d树就是其中一种。
索引结构中相似性查询有两种基本的方式：一种是范围查询（range searches），另一种是K近邻查询（K-neighbor searches）。范围查询就是给定查询点和查询距离的阈值，从数据集中找出所有与查询点距离小于阈值的数据；K近邻查询是给定查询点及正整数K，从数据集中找到距离查询点最近的K个数据，当K=1时，就是最近邻查询（nearest neighbor searches）。
03 实例
先以一个简单直观的实例来介绍k-d树算法。假设有6个二维数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二维空间内（如图1中黑点所示）。k-d树算法就是要确定图1中这些分割空间的分割线（多维空间即为分割平面，一般为超平面）。下面就要通过一步步展示k-d树是如何确定这些分割线的。
k-d树算法可以分为两大部分，一部分是有关k-d树本身这种数据结构建立的算法，另一部分是在建立的k-d树上如何进行最邻近查找的算法。
03 构建算法
k-d树是一个二叉树，每个节点表示一个空间范围。表1给出的是k-d树每个节点中主要包含的数据结构。
从上面对k-d树节点的数据类型的描述可以看出构建k-d树是一个逐级展开的递归过程。表2给出的是构建k-d树的伪码。
以上述举的实例来看，过程如下：
由于此例简单，数据维度只有2维，所以可以简单地给x，y两个方向轴编号为0,1，也即split={0,1}。
（1）确定split域的首先该取的值。分别计算x，y方向上数据的方差得知x方向上的方差最大，所以split域值首先取0，也就是x轴方向；
（2）确定Node-data的域值。根据x轴方向的值2,5,9,4,8,7排序选出中值为7，所以Node-data = （7,2）。这样，该节点的分割超平面就是通过（7,2）并垂直于split = 0（x轴）的直线x = 7；
（3）确定左子空间和右子空间。分割超平面x = 7将整个空间分为两部分，如图2所示。x < = 7的部分为左子空间，包含3个节点{（2,3），（5,4），（4,7）}；另一部分为右子空间，包含2个节点{（9,6），（8,1）}。
如算法所述，k-d树的构建是一个递归的过程。然后对左子空间和右子空间内的数据重复根节点的过程就可以得到下一级子节点（5,4）和（9,6）（也就是左右子空间的'根'节点），同时将空间和数据集进一步细分。如此反复直到空间中只包含一个数据点，如图1所示。最后生成的k-d树如图3所示。
04 PCL中k-d树的最邻近查找
在k-d树中进行数据的查找也是特征匹配的重要环节，其目的是检索在k-d树中与查询点距离最近的数据点。这里先以一个简单的实例来描述最邻近查找的基本思路。
星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行'回溯'操作：算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中先从（7,2）点开始进行二叉查找，然后到达（5,4），最后到达（2,3），此时搜索路径中的节点为<（7,2），（5,4），（2,3）>，首先以（2,3）作为当前最近邻点，计算其到查询点（2.1,3.1）的距离为0.1414，然后回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以（2.1,3.1）为圆心，以0.1414为半径画圆，如图4所示。发现该圆并不和超平面y = 4交割，因此不用进入（5,4）节点右子空间中去搜索。
再回溯到（7,2），以（2.1,3.1）为圆心，以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入（7,2）右子空间进行查找。至此，搜索路径中的节点已经全部回溯完，结束整个搜索，返回最近邻点（2,3），最近距离为0.1414。
一个复杂点了例子如查找点为（2，4.5）。同样先进行二叉查找，先从（7,2）查找到（5,4）节点，在进行查找时是由y = 4为分割超平面的，由于查找点为y值为4.5，因此进入右子空间查找到（4,7），形成搜索路径<（7,2），（5,4），（4,7）>，取（4,7）为当前最近邻点，计算其与目标查找点的距离为3.202。然后回溯到（5,4），计算其与查找点之间的距离为3.041。以（2，4.5）为圆心，以3.041为半径作圆，如图5所示。可见该圆和y = 4超平面交割，所以需要进入（5,4）左子空间进行查找。此时需将（2,3）节点加入搜索路径中得<（7,2），（2,3）>。回溯至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为1.5。回溯至（7,2），以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如图6所示。至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。k-d树查询算法的伪代码如表3所示。
那么各种编程语言实现Kd tree的代码网址：
https://rosettacode.org/wiki/K-d_tree
PCL中关于K-D树的算法已经实现，是实现其他算法的基础，比如在使用滤波算法，配准等算法都会使用该接口。既然有轮子，就不要自己造轮子了。
资源
三维点云论文及相关应用分享
【点云论文速读】基于激光雷达的里程计及3D点云地图中的定位方法
3D目标检测：MV3D-Net
三维点云分割综述（上）
3D-MiniNet: 从点云中学习2D表示以实现快速有效的3D LIDAR语义分割（2020）
win下使用QT添加VTK插件实现点云可视化GUI
JSNet：3D点云的联合实例和语义分割
大场景三维点云的语义分割综述
PCL中outofcore模块---基于核外八叉树的大规模点云的显示
基于局部凹凸性进行目标分割
基于三维卷积神经网络的点云标记
点云的超体素(SuperVoxel)
基于超点图的大规模点云分割
更多文章可查看：点云学习历史文章大汇总
SLAM及AR相关分享
【开源方案共享】ORB-SLAM3开源啦！
【论文速读】AVP-SLAM：自动泊车系统中的语义SLAM
【点云论文速读】StructSLAM:结构化线特征SLAM
SLAM和AR综述
常用的3D深度相机
AR设备单目视觉惯导SLAM算法综述与评价
SLAM综述(4)激光与视觉融合SLAM
Kimera实时重建的语义SLAM系统
SLAM综述(3)-视觉与惯导，视觉与深度学习SLAM
易扩展的SLAM框架-OpenVSLAM
高翔：非结构化道路激光SLAM中的挑战
SLAM综述之Lidar SLAM
基于鱼眼相机的SLAM方法介绍
往期线上分享录播汇总
第一期B站录播之三维模型检索技术
第二期B站录播之深度学习在3D场景中的应用
第三期B站录播之CMake进阶学习
第四期B站录播之点云物体及六自由度姿态估计
第五期B站录播之点云深度学习语义分割拓展
第六期B站录播之Pointnetlk解读
[线上分享录播]点云配准概述及其在激光SLAM中的应用
[线上分享录播]cloudcompare插件开发
[线上分享录播]基于点云数据的 Mesh重建与处理
[线上分享录播]机器人力反馈遥操作技术及机器人视觉分享
[线上分享录播]地面点云配准与机载点云航带平差
点云PCL更多活动请查看：点云PCL活动之应届生校招群
扫描下方微信视频号二维码可查看最新研究成果及相关开源方案的演示：
如果你对本文感兴趣，请点击“原文阅读”获取知识星球二维码，务必按照“姓名+学校/公司+研究方向”备注加入免费知识星球，免费下载pdf文档，和更多热爱分享的小伙伴一起交流吧！
以上内容如有错误请留言评论，欢迎指正交流。如有侵权，请联系删除
扫描二维码
关注我们
让我们一起分享一起学习吧！期待有想法，乐于分享的小伙伴加入免费星球注入爱分享的新鲜活力。分享的主题包含但不限于三维视觉，点云，高精地图，自动驾驶，以及机器人等相关的领域。
分享及合作方式：群主微信“920177957”（需要按要求备注） 联系邮箱：[email protected]，欢迎企业来联系公众号展开合作。
点一下“在看”你会更好看耶
更多相关：
-
当一个IT组织开始走到需要实施网络边缘的旅程时，他们很快意识到面对的挑战与他们在传统数据中心内所经历的挑战不同。 第一个挑战是空间。与更大的核心或区域数据中心同类产品相比，许多边缘站点的物理尺寸更小，因此，需要仔细计划好，尝试在未为其专门设计的空间中安装硬件。 第二个挑战是运行环境。还必须解决的可能面对的冷热温度变化 ，天气，无...
-
单向循环链表单链表的一个变形是单向循环链表, 链表的最后一个节点的next域不再为None, 而是指向链表的头节点.单向循环链表如图所示:单向循环链表同样单向循环链表也是要使用python来对它的基本功能进行一个封装. 总体大致的功能如下:is_empty() 判断链表是否为空length() 返回链表的长度travel() 遍历ad...
-
题目： 二叉搜索树与双向链表 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 为了让您更好地理解问题，以下面的二叉搜索树为例： 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一...
-
题目：删除链表的节点 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。 返回删除后的链表的头节点。 注意：此题对比原题有改动 示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为...
-
【从零开始的ROS四轴机械臂控制】（一）- 实际模型制作、Solidworks文件转urdf与rviz仿真 一、模型制作 1.实际模型制作 2.Solidworks模型制作 二、Solidworks文件转urdf 1.sw_urdf_exporter插件 2.添加坐标系和转轴 3.导出urdf文件 三、rivz仿真...
-
关注我的头条号，获取更多运维相关知识。你想了解哪方面的运维知识，请评论区告诉我，我会尽快更新~MySQL 数据库，基本上运维都会接触到，而对于数据库的性能优化，想必是大家比较关注的，下面分享一些调优技巧。先决条件安装 MySQL，版本大于 5.7有部分数据操作系统、数据库管理员权限MySQL 系统性能优化在系统层面，调整硬件和软件选项...
-
spring data jpa提供了多种查询方式，如下：方法名称查询继承Repository接口测试代码方法名称中支持的关键字(官方文档提供)使用JPA命名查询在User实体中定义jpql(类似于hql)jpql(百度百科)继承JpaRepository接口测试使用@Query查询和命名查询不同的是，将jpql写到了 dao 方法上，...
-
转自：http://www.cnblogs.com/fish-li/archive/2011/06/06/2073626.html 对于SqlServer的优化来说，可能优化查询是很常见的事情。关于数据库的优化，本身也是一个涉及面比较的广的话题，本文只谈优化查询时如何看懂SqlServer查询计划。由于我对SqlServer的认识...
-
一.实现基础功能之一（记账） 一个记账本最基础之一的功能就是记账，所以也是首先要解决的问题，我选择了上学期使用的MySQL数据库来对账本进行存储。 我选择记账的方法是分开记账，就是支出放在一个表，收入放在一个表，这样在数据库方面会比较的直观的看到，但是在显示的时候就会产生部美观的问题，就是支出和收入都是分开来的，没有办法按照时...
-
在Navicat中，我们选中一个表，双击打开，这是如果要新建查询这个表的sql语句，可以直接用快捷键 ctrl+q 会自动打开查询窗口，并直接写好 sql：select * from （当前打开的表名） 我们直接在后面补全查询条件即可，非常方便。 转载于:https://www.cnblogs.com/libin6505/...