最近邻搜索问题的体素，K-D树，八叉树方法

最近邻搜索问题的体素，K-D树，八叉树方法

引用

CSDN

1.

https://blog.csdn.net/qq_54375651/article/details/139271735

最近邻搜索是计算机科学中一个重要的问题，广泛应用于机器学习、数据挖掘等领域。本文将介绍几种常见的最近邻搜索方法，包括暴力搜索、体素方法、K-D树和八叉树，并通过实验对比它们的性能。

暴力搜索

暴力最近邻搜索是最简单直观的最近邻计算方法，无需辅助数据结构。如果只搜索单个最近邻，则算法称为暴力单点最近邻搜索；如果搜索k个最近邻，则算法称为暴力k点近邻搜索。暴力近邻搜索准确率和召回率都为100%，但计算时间过长。

应用暴力k点最近邻搜索方法查找点x在点集Y={y1,⋯,yn}中的k点最近邻的步骤：

1. 计算x到点集Y中所有点的距离
2. 对第1步的结果进行排序，选择距离最短的k个点

栅格与体素方法

当查找某点在点集中的单个最近邻时，在二维情况下，可将原始空间划分为正方形栅格；在三维情况下，可将原始空间划分为立方体体素，并仅在查询点附近栅格或体素中查找。这种方法能很大程度缩小查找的范围。

通过引入哈希函数，将相同体素中的点映射为相同哈希值，便于快速确定点集中位于查询点附近或体素中的点。哈希函数hash:R3→R定义为

hash(x)=((x1∗n1)xor(x2∗n2)xor(x3∗n3))modN

其中n1,n2,n3是三个大质数，N是大整数，可取n1=73856093,n2=471943,n3=83492791,N=10000000

哈希函数需要与将位置坐标映射到体素序号的函数Voxel:R3→R3搭配使用，其定义为

Voxel(x)=[round(x1r);round(x2r);round(x3r)]T

其中round:R→Z为四舍五入函数，r表示分辨率，即体素的边在原始空间中的欧式长度

应用体素方法三维查找点x在三维点集Y={y1,⋯,yn}中的k点最近邻的步骤：

1. 将点集Y中每个点y映射为Voxel(y)，再计算哈希值hash(Voxel(y))，以此建立哈希表
2. 记V={[0,0,0]T,[1,0,0]T,[-1,0,0]T,[0,1,0]T,[0,-1,0]T,[0,0,1]T,[0,0,-1]T}
3. 令x的待查找最近邻集合N(x)=∅
4. 循环选取V中的元素v，在每次循环中，记选取的元素为v，计算哈希值hash(Voxel(x)+v)，通过查询哈希表将点云Y中具有相同哈希值的点加入N(x)
5. 应用暴力单点最近邻搜索方法，查找点x在N(x)中的k点最近邻，并将该最近邻作为点x在Y中的k点最近邻

K-D树

K-D树（K-Dimensional Tree）是借鉴了”对排序后的容器进行查找可以大幅节省时间“这一思想，

K-D树中规定：

• 每个非叶子节点都有左右两个分枝
• 叶子节点表示原始空间中的点
• 非叶子节点存储一个分割轴和一个分割阈值，来表达在节点中包含的点不完全一致的情况下，如何分割左分枝和右分枝，例如yi=thre存储为轴i和阈值thre，表示左分枝取节点中在第j维上小于thre的元素，右分枝取节点中在第j维上大于等于thre的元素

根据点集Y={y1,⋯,yn}构建K-D树的过程可以看成执行建树函数BuildKDTree(Y,nullptr)，该函数采用递归方式定义，最终可通过root访问整个K-D树，其定义为：

BuildKDTree(S,∗root)

1. 记当前节点n为根节点root
2. 若|S|=1

• 记n为叶子节点，退出

3. 若|S|>1

• 记n为非叶子节点，计算S中的点在各轴上的方差，选择方差最大的轴i作为分割轴，取平均数mi=1|S|∑y∈Syi作为分割阈值
• 遍历y∈S，若yi<mi，则插入n的左子节点；若yi⩾mi，则插入n的右子节点；若S中的多个点完全一致，则只保留一个点，并将节点n记为叶子节点
• 记全部插入到n左子节点上的点组成的点集为SL，递归调用BuildKDTree(SL)，构建K-D树；记全部插入到n右子节点上的点组成的点集为SR，递归调用BuildKDTree(SR)，构建K-D树

通过包含6个点的点集{[2,3]T,[5,4]T,[9,6]T,[4,7]T,[8,1]T,[7,2]T}构建的K-D树如下

从已构建完成的K-D树T中查找点x的k个最近邻的过程可看成首先定义Dk=∅，dmax=+∞，再执行k点最近邻搜索树函数SearchKDTree_k(T,x,k,Dk,dmax)，最终Dk成为x的k点最近邻集合，该函数采用递归方式定义，其定义为：

SearchKDTree_k(T,x,k,&Dk,&dmax)

1. 初始化当前节点n为T的根节点
2. 若n是叶子节点

• 计算n上的点y与x的距离d(x,y)，若d(x,y)<dmax，则Dk=Dk∪{y}，若此时|Dk|>k，则删除Dk中到查询点距离最大的点，并重新计算dmax={maxy∈Dkd(x,y)|Dk|=k+∞|Dk|<k
• 退出

3. 若n是非叶子节点

• 确定x在分割超平面的侧，也即计算x落在的子树n→ChildKDTreei,i∈{1,2}。同时得到另一侧子树n→ChildKDTreej,j={1,2}\i
• 递归调用SearchKDTree_k(n→ChildKDTreei,x,k,Dk,dmax)，在n的该侧子树中搜索x的k点最近邻
• 计算x到分割超平面的垂直距离为dsplit，若dsplit<dmax，则递归调用SearchKDTree_k(n→ChildKDTreej,x,k,Dk,dmax)，在n的另一侧子树中搜索x的k点最近邻；若dsplit⩾dmax，则跳过n的另一侧子树
• 退出

查找点x=[6;5]T在上例点集中的两个最近邻，搜索流程如下图，结果为{[5;4]T,[4;7]T}

在上述的K-D树搜索过程中，最关键的部分是剪枝，即不继续在另一侧搜索k点最近邻，剪枝的条件是可以判定树形结构的另一侧不存在比现有结果更近的最近邻，判定条件如下

dsplit⩾dmax

在该剪枝条件下，K-D树准确率和召回率方面都可以做到100%，但可能会遇到去很远的分枝查找k点最近邻的情况，时间成本高。为解决该问题，可以添加一个比例因子0<α<1，可将剪枝判定条件改为

dsplit⩾αdmax

可见剪枝条件被放宽，无法判定另一侧子树中是否存在比现有结果更近的最近邻。应用该剪枝条件，可使K-D树k点最近邻查找速度加快，但不再能保证找到严格的k点最近邻，这种做法称为近似最近邻（Approximate Nearest Neighbour，ANN）

八叉树

八叉树（Octo Tree，Octree)

根据点集Y={y1,⋯,yn}构建八叉树树的过程可以看成执行建树函数BuildOcTree(Y,O,1,nullptr)，该函数采用递归的方式定义，最终可通过root访问整个八叉树，二者定义为：

BuildOcTree(S,box,depth,∗root)

1. 初始化当前节点n为根节点root
2. 若depth=1

• 计算Y中的点在各轴上的最小值mini=miny∈Yyi,i=1,2,3和最大值maxi=maxy∈Yyi,i=1,2,3，这些最大值最小值组成表示包围盒的向量box=[min1,max1,min2,max2,min3,max3]T

3. 若|S|=0

• 退出

4. 若|S|=1

• 记n为叶子节点，退出

5. 若|S|>1

• 赋值{min1=box1,max1=box2min2=box3,max2=box4min3=box5,max3=box6
• 计算包围盒在各个轴上的中心位置ci=min+i+maxi2,i=1,2,3
• 计算8个子节点的表示包围盒的向量：
  box1=[min1,c1,min2,c2,min3,c3]T，box2=[c1,max1,min1,c2,min3,c3]T
  box3=[min1,c1,c2,max2,min3,c3]T，box4=[c1,max1,c2,max2,min3,c3]T
  box5=[min1,c1,min2,c2,c3,max3]T，box6=[c1,max1,min1,c2,c3,max3]T
  box7=[min1,c1,c2,max2,c3,max3]T，box8=[c1,max1,c2,max2,c3,max3]T
• 遍历y∈S，在循环内部遍历各子节点，根据各子节点的包围盒确定y应当落在的子节点：若{boxj1⩽y1⩽boxj2boxj3⩽y2⩽boxj4boxj5⩽y3⩽boxj6，则插入第j个子节点
• 记插入到各子节点的点组成的点集为Sj,j=1,⋯,8，对8个子节点分别递归调用BuildOcTree(Sj,boxj,depth+1)，构建八叉树

从已构建完成的八叉树T中查找点x的k个最近邻的过程可以看成看成首先定义Dk=∅，dmax=+∞，再执行k点最近邻搜索树函数SearchOcTree_k(T,x,k,Dk,dmax)，最终Dk成为x的k点最近邻集合，该函数采用递归方式定义，其定义为：

SearchOcTree_k(T,x,k,&Dk,&dmax)

1. 初始化当前节点n为T的根节点，box为表示n的包围盒的向量
2. 若n是叶子节点

• 计算n上的点y与x的距离d(x,y)，若d(x,y)<dmax，则Dk=Dk∪{y}，若此时|Dk|>k，则删除Dk中到查询点距离最大的点，并重新计算dmax={maxy∈Dkd(x,y)|Dk|=k+∞|Dk|<k
• 退出

3. 若n是非叶子节点

• 若x落在n的包围盒的外面
• 遍历n的每个子节点，递归调用SearchOcTree_k(n→ChildOcTreei,x,k,Dk,dmax)
• 退出
• 若x落在n的包围盒的里面
• 计算x落在哪个子节点的包围盒中，也即确定x落在的子树n→ChildOcTreei,i∈{1,⋯,8}。同时得到其他子树n.ChildOcTreej,j∈{1,⋯,8}\i
• 递归调用SearchOcTree_k(n→ChildOcTreei,x,k,Dk,dmax)，在n的该子树中搜索x的k点最近邻
• 遍历n的其他子节点，计算x到其他各子节点包围盒各面距离的最大值dboxj=max{|x1−boxj1|,|x2−boxj2|,|x2−boxj3|,|x2−boxj4|,|x3−boxj5|,|x3−boxj6|}，若dboxj<dmax，则递归调用SearchOcTree_k(n→ChildOcTree,x,k,Dk,dmax)，在n的子树中搜索x的k点最近邻；若dboxj⩾dmax，则跳过n的子树n→ChildOcTreej
• 退出

上述八叉树搜索过程也涉及剪枝，即不继续在对应子树中搜索k点最近邻，剪枝判定条件如下

dboxj⩾dmax

在该剪枝条件下，八叉树准确率和召回率方面都可以做到100%，但可能会遇到去很远的分枝查找k点最近邻的情况，时间成本高。为解决该问题，同样可以添加一个比例因子0<α<1，可将剪枝判定条件改为

dboxj⩾αdmax

剪枝条件被放宽，无法判定对应子树中是否存在比现有结果更近的最近邻。应用该剪枝条件，可使八叉树k点最近邻查找速度加快，但不再能保证找到严格的k点最近邻。

实验：不同单点最近邻搜索方法对比

现有两组三维点云，采用多线程版本的不同方法查找第一组点云中每个点在第二组点云中的最近邻所需的时间，准确率，召回率如下