Kd-Tree

kd 树(k 维树,Bentley 1975)是一种针对 $\mathbb{R}^d$ 中点集的二叉空间划分结构,能让最近邻查询在平均情况下具有亚线性代价。它是回答”找到最近的那个(或那些)点”这一问题在低维几何数据——尤其是 3D 点云——上的默认答案,并且以随机化森林的形式,也是高维浮点描述子近似匹配的实用工具。

构建

每个内部节点都用一个轴对齐的超平面来划分点集:

1. 选择一个分裂维度——经典做法是按深度循环遍历各维度($x, y, z, x, \dots$),或者更好的做法是选择该节点中点集方差/散布最大的维度。
2. 选择分裂值——通常是坐标的中位数,这能保证得到深度为 $O(\log n)$ 的平衡树。
3. 在两个子集上递归,直到节点中的点数少于叶子大小阈值。

使用中位数的中位数或预先排序,构建代价为 $O(n \log n)$;树中每个点只存储一次。

最近邻搜索

一个查询点 $\mathbf{q}$ 首先下降到包含它的叶子节点($O(\log n)$ 次比较),并把在该叶子中找到的最优点作为当前候选,其距离为 $r_{\text{best}}$。然后搜索会回溯:在返回路径上的每个节点处,只有当分裂平面比当前最优值更近时才需要访问另一侧的子树,即仅当

时才需要访问,其中 $q_k$ 是查询点在该节点分裂维度 $k$ 上的坐标,$s$ 是分裂值——从几何上讲,只有当以 $\mathbf{q}$ 为中心、半径为 $r_{\text{best}}$ 的超球与该平面相交时才需要访问。否则整个子树都会被剪枝。同样的方案也可用于 k 近邻查询(维护一个大小为 $k$ 的最优堆)和半径搜索。

在低维情况下($d \lesssim 10$),剪枝非常有效,平均查询代价为 $O(\log n)$。

维度灾难

随着 $d$ 增大,距离会趋于集中——最近邻和最远邻在距离上变得相对接近——剪枝球几乎会与每一个分裂平面相交,导致搜索退化为几乎是一次完整的线性扫描,同时还要额外承担树遍历的开销。粗略来说,精确的 kd 树搜索需要 $n \gg 2^d$ 才能优于暴力搜索;SIFT 的 128 维远远超出了精确搜索适用的范围。两种补救办法定义了现代实践:

• 最佳优先搜索(Best-bin-first,BBF)(Beis & Lowe,1997):使用优先队列按节点到查询点的距离顺序探索节点,并在达到固定的叶子检查预算后停止,返回目前找到的最优候选。这把 kd 树变成了一种带有可调精度/速度旋钮的近似方法——正是为 SIFT 匹配而提出的。
• 随机化 kd 树森林:构建多棵具有随机化分裂维度选择(在方差最大的若干维度中选取)的树,并通过一个共享的优先队列对它们进行搜索;在某一棵树中因分裂不佳而被”隐藏”的邻居,可以通过另一棵树找到。这是 FLANN 的核心索引之一。

需要注意,kd 树是在 L2 距离下比较原始向量——对于在汉明距离下的二值描述子,LSH 或 HBST 才是合适的结构。

kd 树在 SLAM 中出现的场景

• ICP 与点云配准:对应关系求解步骤——为场景中的每个点找到模型中最近的点,每次迭代都要做——本质上是一批 3D 最近邻查询;PCL、Open3D 和 libpointmatcher 都使用 kd 树(FAST-LIO2 构建了一种可增量更新的变体,ikd-Tree,以避免随着地图增长而反复重建)。
• 描述子匹配:在 SfM 和重定位流程中,对 SIFT/SuperPoint 类描述子进行近似最近邻搜索(通过 FLANN)。
• 地图查询:用于局部地图提取的半径搜索、法向估计的邻域搜索、关键帧位置查找,以及网格/surfel 邻居搜索。

对SLAM的意义

最近邻搜索是 SLAM 系统中执行次数最多的基本操作之一——出现在激光雷达或 RGB-D 流程的每一次 ICP 迭代中,出现在特征流程的每一个匹配阶段中,也出现在诸如法向估计和降采样等建图操作中。了解 kd 树的机制能让你知道它何时是合适的工具(3D 点:非常出色;128 维描述子:仅在近似/森林形式下适用;二值描述子:并非合适的工具),也能解释建立在它之上的各种库的设计(FLANN 的索引、PCL 的搜索模块、ikd-Tree)。它同样是一个反复出现的系统瓶颈:针对不断增长的地图,选择重建还是更新的策略,直接影响着实时激光雷达里程计的架构设计。

相关条目

• FLANN
• Brute-force matching
• LSH
• Point cloud
• ICP