HBST (Hamming Binary Search Tree)

HBST(Schlegel & Grisetti,2018)是一种针对二值描述子(ORB、BRIEF、BRISK、FREAK)的二叉搜索树,能够以对数代价在汉明空间中回答近似最近邻查询,并且——这对 SLAM 至关重要——支持在搜索的同时进行增量插入。它被提出作为一种轻量级、无需词汇表的替代方案,用以取代视觉词袋(DBoW2)和 FLANN-LSH 进行回环检测:它不是把描述子量化到一个预训练的词汇表中,而是随着轨迹的推进直接对原始描述子建立索引。

树是如何构建的

一个二值描述子是一个固定长度的比特串 $\mathbf{d} \in \{0,1\}^D$ (例如 ORB 中 $D = 256$ ),用汉明距离(不同比特的数量,通过 XOR + popcount 计算)进行比较。

每个内部节点存储一个单一的比特索引 $k \in \{0, \dots, D-1\}$ 。若某描述子的第 $k$ 位为 0,则路由到左子树,为 1 则路由到右子树。
每个叶子存储一组描述子(带有负载信息——在 SLAM 中,即该描述子来自哪个图像/关键帧索引及关键点)。
当一个叶子超过最大规模时,会被分裂:为其所持有的描述子选择一个分裂比特,并将它们重新分配到两个子节点中。

选择分裂比特的原则是均衡性:对叶子中所有描述子,计算每个候选比特的均值 $\bar{d}_k$ ,并选择均值最接近 $0.5$ 的比特——即最能均匀划分该集合的比特。这样,在 $N$ 个描述子上得到的平衡树深度约为 $\log_2 N$ ,每次查询只需经过一条从根到叶的路径。

搜索——以及为什么它是近似的

一个查询描述子 $\mathbf{q}$ 在每个节点上读取自身对应索引位置的比特值(深度为 $h$ 需做 $h$ 次比特测试)从而下降到树中,最终落入单个叶子,并仅在该叶子的描述子范围内通过汉明距离进行穷举匹配(接受距离低于阈值 $\tau$ 的匹配)。总代价为 $O(\log N + L)$ (叶子大小为 $L$ ),而暴力搜索的代价为 $O(N)$ 。

其代价就是近似性:如果一个真实匹配的描述子恰好在用于分裂的某个比特上与查询不同,它就会被路由到另一个叶子而被漏掉。这种情况的概率随树的深度和描述子噪声增大而增大。HBST 接受这一点,因为地点识别并不需要找到每一个匹配——它只需要足够多一致的匹配来为正确的关键帧投票,之后的几何验证会清理掉误判。

增量式的搜索兼插入

正是这个操作让 HBST 契合 SLAM 的在线场景:对于每一张新图像,其描述子被沿树下降一次,在同一次遍历中,树(1)报告与目前已索引的所有内容的匹配,并(2)插入新的描述子(对溢出的叶子进行分裂)。数据库随轨迹增长,无需离线训练阶段、无需词汇文件、也无需定期重建。匹配按过往图像聚合——每一个匹配上的描述子都为其所属的关键帧投一票——得票高的关键帧成为回环检测候选,随后通过几何方式进行验证(例如在 RANSAC 内使用本质矩阵或 PnP)。

对于一个包含 $N$ 个描述子、最大叶子大小为 $L$ 的数据库,总结其代价如下:

插入:一次从根到叶的下降, $O(\log N)$ ,外加偶尔发生的叶子分裂。
查询: $O(\log N)$ 次比特测试 + 叶子内 $O(L)$ 次汉明比较。
内存:原始描述子加上每个内部节点一个比特索引——没有哈希表,没有词汇表。
旋钮:最大叶子大小 $L$ (更深的树、更快的叶子 vs. 更好的召回率)以及匹配阈值 $\tau$ 。

与其他方案的比较

暴力匹配是精确的,但与数据库规模呈线性关系——对两帧图像没问题,但面对数千个关键帧就无能为力。
BoW(DBoW2/DBoW3) 需要预训练的词汇表;量化会丢失描述子细节,但倒排索引极快且内存占用很小。
FLANN-LSH 也能增量式处理二值描述子,但在典型的回环检测负载下需要多个哈希表,内存和延迟更高。
HBST 用可控的一部分召回率损失,换来直接的描述子级匹配(关键点对应关系是免费得到的,可直接送去做几何验证),同时查询非常快且无需训练。

对SLAM的意义

回环检测必须每隔几帧就针对一个不断增长的数据库查询”我以前见过这个吗?“,并且要在实时预算内完成。对于已经计算了二值描述子的基于特征的系统而言,HBST 是一个干净、自洽的答案:无需分发词汇表(一个 DBoW2 的 ORB 词汇文件是一个庞大的二进制资产)、单一结构即可同时给出图像级与关键点级的对应关系,并且查询时间沿轨迹呈对数增长。它也是研究汉明空间索引精度-速度权衡的一个很好的案例研究——将它与 LSH 和 BoW 进行比较,能加深你对这三者的理解。