三维点云处理 2.1 binary_search_tree

一、最邻近问题三维点云处理中的最邻近问题是指对于点云中的每一个点如何快速找到离其最近的其他点。常见的解决方法包括kd树和八叉树。1.二叉树二叉树是其他树结构的基础主要用于处理一维数据点。1) 最邻近问题最邻近查找包括两种方法k近邻kNN对于目标点红色查找距离最近的k个点绿色。半径近邻radius NN以目标点为圆心查找半径范围内的所有点蓝色。2) 最邻近问题的重要性最邻近问题在点云处理中应用广泛包括法向量分析需选择邻域点。上采样、下采样及噪声去除均依赖邻域查找。聚类、深度学习和特征提取后续课程将涉及。现有开源库如PCL、FLANN的实现效率较低尤其在GPU上表现不佳。3) 点云最邻近问题困难点云最邻近问题的难点包括不规则性点云分布无固定规律。三维数据量指数增长网格法存在内存与分辨率矛盾。海量数据处理需求以64线激光雷达为例每秒需处理220万点暴力搜索复杂度达60亿次运算/50毫秒。传统超级计算机如曙光4000A也难以满足实时处理需求因此需依赖高效算法如kd树、八叉树。4) 内容结构本节课程结构如下二叉树处理一维数据。kd树适用于任意维度以二维为例通过超平面分割空间。八叉树专为三维数据设计优于kd树的三维适应性。5) 共同核心思想空间分割是核心思想具体包括跳过无关区域通过worst distance如根号2排除远距离区间。快速终止搜索若目标邻域已确定可提前结束搜索。2.二叉树1) 二叉树的定义二叉树的特性左子节点值小于根节点。右子节点值大于根节点。左右子树均为二叉树。节点结构包含key、左子节点、右子节点及附加信息如value。2) 二叉树的构建或插入构建二叉树的步骤构建二叉树的步骤初始插入根节点如100。后续节点按规则比较小于当前节点则向左子树插入。大于当前节点则向右子树插入。递归直至找到空位。插入元素的代码实现代码实现通过递归完成核心逻辑为若key小于当前节点递归插入左子树。若key大于当前节点递归插入右子树。数据生成与插入过程插入过程示例随机数组通过逐节点比较完成构建value字段可存储原始索引。3) 二叉树插入复杂度复杂度分析不平衡二叉树退化为链表复杂度O(n)。平衡二叉树深度为log(n)复杂度O(log n)。理想情况下平衡二叉树显著提升效率。4) 二叉树搜索查找数据点是否存在于二叉树中可通过递归或循环实现。存在时返回对应数据点不存在时返回空值。二叉树搜索递归递归实现步骤如下比较关键字key与根节点值若相等则直接返回该节点根据二叉树性质选择查找方向若key小于当前节点值则仅需查找左子树反之仅需查找右子树递归终止条件当查找到空节点时返回空值二叉树搜索迭代迭代实现需借助栈结构使用current_node变量替代递归中的root参数动态记录当前查找节点比较逻辑与递归完全一致通过循环实现节点值的比较与方向选择时间复杂度与递归相同均为二叉树深度O(h)二叉树搜索的优缺点递归与迭代特性对比特性递归实现迭代实现实现难度更简单直观需手动维护状态空间复杂度O(n)栈空间O(1)额外空间适用场景CPU环境GPU环境编译器优化可自动转为迭代无优化空间现代CPU环境下推荐使用递归实现但GPU环境需采用迭代方式。5) 二叉树的深度优先遍历深度优先遍历分为三种类型中序遍历(In-order)按左子树-根节点-右子树顺序访问输出结果为有序序列前序遍历(Pre-order)按根节点-左子树-右子树顺序访问适用于树结构复制后序遍历(Post-order)按左子树-右子树-根节点顺序访问适用于节点删除操作6) 二叉树的1NN搜索1NN搜索的目标与定义1NN搜索目标是在二叉树中查找与给定查询点距离最近的节点。查询点存在与否不影响算法逻辑。搜索方法的引入与比较传统排序二分查找法虽有效但为引入后续kd树等数据结构采用基于二叉树特性的搜索方法。二叉树1NN搜索的具体步骤搜索流程如下初始化最坏距离(Worst Distance)根节点与查询点的距离方向选择根据查询点与当前节点值的比较结果选择子树距离更新发现更近节点时更新最坏距离剪枝优化当某子树不可能存在更近节点时跳过搜索算法优化跳过区域的策略空间划分策略是算法核心根据二叉树性质将搜索空间划分为左右子区域通过最坏距离判断可跳过的区域显著减少不必要的节点比较操作7) 二叉树的kNN搜索kNN搜索与1NN搜索的区别kNN与1NN算法框架完全一致区别仅在于最坏距离的计算方式。kNN搜索中的最快距离Worst Distance最坏距离确定方法维护容量为k的有序结果容器容器末尾元素值即为当前最坏距离随着搜索进行动态更新容器内容kNN搜索算法的实现实现要点结果容器初始化预填充极大值容量固定为k节点插入机制保持容器元素有序性搜索方向优化优先搜索更可能包含近邻点的子树提前终止条件当最坏距离降为0时可提前终止8) 二叉树的Radius NN搜索Radius NN搜索与KNN搜索相比更为简单原因在于搜索半径已预先给定。KNN搜索需要通过动态调整容器来确定最近距离而Radius NN搜索仅需收集所有距离小于给定半径的点即可。两者代码结构高度相似主要差异体现在以下三点函数命名不同KNN与Radius NNRadius NN不存在距离为零的特殊情况半径参数不会为零结果容器设计使得两种算法的核心逻辑完全一致9) 应用案例例题:二叉树kNN/Radius NN搜索实验采用包含100个数字的数据库分别执行以下操作KNN搜索查找与目标点最近的5个点计算次数从暴力搜索的100次降至7次Radius NN搜索查找半径20范围内的所有点同样仅需7次对比运算时间复杂度分析最优情况平衡二叉树下为O(log n)最差情况退化为链式结构时达O(n)实际应用二叉树结构通常不会极端退化3.内容总结二叉树结构仅适用于一维数据的最近邻搜索原因如下依赖维度可比性一维数据可直接通过大小关系判断距离而高维数据缺乏此类直接关联分支定界算法本质最近邻搜索可视为最小化问题二叉树通过计算距离下界如查询点9与节点3的距离6决定是否剪枝分支扩展局限性原始二叉树无法直接应用于KD树、八叉树等高维数据结构的最邻近搜索场景