三维点云处理 2.2 KD-tree

一、kd树一维情况下使用二叉树进行最邻近查找的方法已讲解完毕。一维数据较为简单实际应用中多为二维或三维数据。kd树k-dimensional tree适用于任意维度空间其基本原理与二叉树类似区别在于需要在每个维度上轮流构建二叉树。该算法比二叉树晚15年发明因其复杂度更高。示意图显示红色方框表示沿某一轴切割随后依次在绿色和蓝色方向切割实现在三维xyz方向上轮流构建二叉树。1.kd树构造kd树的构建需在每个维度上构建二叉树。与二叉树不同kd树的末端节点可包含多个点通过参数leaf size控制末端节点容纳的点数上限。构建过程分为三步判断点数是否足够多若足够则进行切割选择切割维度并确定超平面位置使左右两侧点数均衡迭代执行上述步骤完成构建1) 节点配置末端节点可设置为叶子节点leaf通过leaf size参数定义其容纳点数上限。构建时需判断当前节点点数是否超过leaf size若未超过则作为叶子节点终止切割若超过则选择切割维度并确定超平面位置确保左右子树点数均衡迭代执行直至所有节点满足leaf size限制2) 划分策略切割策略分为两种策略类型切割逻辑优缺点轮流切割按固定顺序切换切割维度如x→y→z→x实现简单但可能因数据分布不均导致树不平衡自适应切割根据当前数据分布选择方差最大的维度切割树更平衡但计算复杂度略高实际应用中两种策略性能差异较小通常采用轮流切割法。3) 示例详解以二维点集A-I为例构建kd树leaf size1第一层切割沿x轴切割超平面S1左侧5个点右侧3个点第二层切割左侧沿y轴切割超平面S2左侧2个点AB右侧3个点AB需继续切割超平面S3因leaf size1第三层切割DE沿x轴切割超平面S4最终每个子区域仅含1个点关键点每次切割后需切换维度直至所有区域点数≤leaf size。4) 节点表达kd树节点需包含以下属性axis当前切割维度如x/y/zvalue超平面位置坐标left/right左右子节点指针indices当前节点包含的数据点索引is_leaf标记是否为叶子节点示例绿色区域节点需记录切割维度y轴、超平面位置S2、左右子树含DE和AB及对应点索引。5) 建树过程建树代码核心逻辑终止条件当前节点点数≤leaf size时标记为叶子节点选择切割维度按轮转策略x→y→z→x或自适应策略选择排序与切割按选定维度排序点集取中位数作为超平面位置递归构建左右子树优化方向中位数查找可优化为O(n)算法如快速选择降低时间复杂度至O(n log n)。6) 时间复杂度和空间复杂度复杂度分析时间复杂度基础实现O(n log² n)每层O(n log n)排序共log n层优化后O(n log n)使用O(n)中位数算法空间复杂度O(n log n)需存储每层节点索引实用技巧近似中位数随机采样部分点计算中位数降低排序开销均值替代中位数牺牲平衡性换取计算速度实际应用中效果良好2.kd数-kNN搜索构建完成后进入kNN搜索阶段。查找过程与构建过程类似通过判断查询点在切平面的左侧或右侧决定搜索方向。kd树末端叶子节点可能包含多个数据点需进行多点对比但不影响算法整体结构。1) kNN搜索步骤步骤1从根节点出发根据查询点与切平面的位置关系选择搜索方向左/右步骤2递归搜索直至叶子节点计算当前最近距离并建立候选圆步骤3回溯时判断其他区域是否与候选圆相交相交则必须搜索可能存在更近点不相交则剪枝跳过该区域所有点核心判断条件若查询点位于某区域内部则必须搜索该区域若查询点到切平面的距离小于当前最近距离则需搜索相邻区域2) kNN搜索代码递归终止条件到达叶子节点时暴力比对所有数据点更新结果集非叶子节点处理优先搜索查询点所在侧子树根据当前最近距离决定是否搜索对侧子树结果集维护动态保持按距离排序的k个最近邻点3.kd数-radius-NN搜索radius-NN与kNN的主要差异在于使用固定半径值替代动态更新的最近距离结果集存储所有落在指定半径范围内的点。实现难度通常低于kNN因无需维护动态排序的候选集。4.kd数搜索复杂度理想情况复杂度构建平衡kd树时间复杂度为O(n log n)最近邻搜索时间复杂度为O(log n)极端情况不平衡树可能导致搜索退化为O(n)实际应用中数据分布通常均匀极少出现最坏情况以下为AI生成的文稿笔记的内容一、kd数一维情况下使用二叉树进行最邻近查找的方法已讲解完毕。一维数据较为简单实际应用中多为二维或三维数据。kd树k-dimensional tree适用于任意维度空间其基本原理与二叉树类似区别在于需要在每个维度上轮流构建二叉树。该算法比二叉树晚15年发明因其复杂度更高。示意图显示红色方框表示沿某一轴切割随后依次在绿色和蓝色方向切割实现在三维xyz方向上轮流构建二叉树。1.kd树构造kd树的构建需在每个维度上构建二叉树。与二叉树不同kd树的末端节点可包含多个点通过参数leaf size控制末端节点容纳的点数上限。构建过程分为三步判断点数是否足够多若足够则进行切割选择切割维度并确定超平面位置使左右两侧点数均衡迭代执行上述步骤完成构建1) 节点配置末端节点可设置为叶子节点leaf通过leaf size参数定义其容纳点数上限。构建时需判断当前节点点数是否超过leaf size若未超过则作为叶子节点终止切割若超过则选择切割维度并确定超平面位置确保左右子树点数均衡迭代执行直至所有节点满足leaf size限制2) 划分策略切割策略分为两种策略类型切割逻辑优缺点轮流切割按固定顺序切换切割维度如x→y→z→x实现简单但可能因数据分布不均导致树不平衡自适应切割根据当前数据分布选择方差最大的维度切割树更平衡但计算复杂度略高实际应用中两种策略性能差异较小通常采用轮流切割法。3) 示例详解以二维点集A-I为例构建kd树leaf size1第一层切割沿x轴切割超平面S1左侧5个点右侧3个点第二层切割左侧沿y轴切割超平面S2左侧2个点AB右侧3个点AB需继续切割超平面S3因leaf size1第三层切割DE沿x轴切割超平面S4最终每个子区域仅含1个点关键点每次切割后需切换维度直至所有区域点数≤leaf size。4) 节点表达kd树节点需包含以下属性axis当前切割维度如x/y/zvalue超平面位置坐标left/right左右子节点指针indices当前节点包含的数据点索引is_leaf标记是否为叶子节点示例绿色区域节点需记录切割维度y轴、超平面位置S2、左右子树含DE和AB及对应点索引。5) 建树过程建树代码核心逻辑终止条件当前节点点数≤leaf size时标记为叶子节点选择切割维度按轮转策略x→y→z→x或自适应策略选择排序与切割按选定维度排序点集取中位数作为超平面位置递归构建左右子树优化方向中位数查找可优化为O(n)算法如快速选择降低时间复杂度至O(n log n)。6) 时间复杂度和空间复杂度复杂度分析时间复杂度基础实现O(n log² n)每层O(n log n)排序共log n层优化后O(n log n)使用O(n)中位数算法空间复杂度O(n log n)需存储每层节点索引实用技巧近似中位数随机采样部分点计算中位数降低排序开销均值替代中位数牺牲平衡性换取计算速度实际应用中效果良好2.kd数-kNN搜索构建完成后进入kNN搜索阶段。查找过程与构建过程类似通过判断查询点在切平面的左侧或右侧决定搜索方向。kd树末端叶子节点可能包含多个数据点需进行多点对比但不影响算法整体结构。1) kNN搜索步骤步骤1从根节点出发根据查询点与切平面的位置关系选择搜索方向左/右步骤2递归搜索直至叶子节点计算当前最近距离并建立候选圆步骤3回溯时判断其他区域是否与候选圆相交相交则必须搜索可能存在更近点不相交则剪枝跳过该区域所有点核心判断条件若查询点位于某区域内部则必须搜索该区域若查询点到切平面的距离小于当前最近距离则需搜索相邻区域2) kNN搜索代码递归终止条件到达叶子节点时暴力比对所有数据点更新结果集非叶子节点处理优先搜索查询点所在侧子树根据当前最近距离决定是否搜索对侧子树结果集维护动态保持按距离排序的k个最近邻点3.kd数-radius-NN搜索radius-NN与kNN的主要差异在于使用固定半径值替代动态更新的最近距离结果集存储所有落在指定半径范围内的点。实现难度通常低于kNN因无需维护动态排序的候选集。4.kd数搜索复杂度理想情况复杂度构建平衡kd树时间复杂度为O(n log n)最近邻搜索时间复杂度为O(log n)极端情况不平衡树可能导致搜索退化为O(n)实际应用中数据分布通常均匀极少出现最坏情况