LSH (Locality-Sensitive Hashing)

局部敏感哈希（Locality-Sensitive Hashing，LSH）是一种近似最近邻搜索技术，其基本思想很简单：对描述子进行哈希，使相似的描述子发生碰撞（落入同一个桶）的概率很高，而不相似的描述子碰撞概率很低。这样,一次查询只需要与其所在桶中的少数候选进行比较,而不必与整个数据库比较。

局部敏感性质

对于距离度量$d(\cdot,\cdot)$，一族哈希函数$\mathcal{H}$被称为$(r, cr, p_1, p_2)$-敏感的，如果对任意两点$\mathbf{p}, \mathbf{q}$满足：

• 若$d(\mathbf{p}, \mathbf{q}) \leq r$，则$\Pr[h(\mathbf{p}) = h(\mathbf{q})] \geq p_1$，
• 若$d(\mathbf{p}, \mathbf{q}) \geq cr$，则$\Pr[h(\mathbf{p}) = h(\mathbf{q})] \leq p_2$，

且$p_1 > p_2$，$c > 1$。用文字来说：距离近的点很可能碰撞，距离远的点不太可能碰撞。

对于汉明距离下的二进制描述子（ORB、BRIEF、AKAZE的MLDB），自然的哈希族是位采样（bit sampling）：$h(\mathbf{x}) = x_i$，其中$i$是随机选定的位位置。两个长度为$n$、相差$d_H$个比特位的描述子发生碰撞的概率为

该概率恰好随距离增大而降低——局部敏感性质是免费获得的。

放大：k个比特位，L个哈希表

单个随机比特是一个非常弱的哈希，因此LSH沿两个方向进行放大：

• 拼接（AND）：用$k$个哈希函数构造每个表的键，$g(\mathbf{x}) = (h_1(\mathbf{x}), \dots, h_k(\mathbf{x}))$。单个表的碰撞概率变为$(1 - d_H/n)^k$——更大的$k$会使桶更小、更具选择性，减少误检。
• 多表（OR）：构造$L$个独立的哈希表并全部查询。真正的邻居在至少一个表中发生碰撞的概率为

调整$k$和$L$在精度与速度、内存之间进行权衡：更具选择性的键（大$k$）需要更多的表（大$L$）来保持召回率。

多探测LSH（Multi-probe LSH）

标准LSH需要许多哈希表才能达到良好的召回率,这会消耗大量内存。多探测LSH观察到：如果一个真正的邻居没有落入查询所在的桶，它很可能落入了一个相邻的桶——其键仅在少数几个位置上有所不同。多探测查询不是增加更多的表,而是生成一个由扰动键组成的探测序列（先翻转键的一个比特，再翻转两个……），按其可能包含邻居的可能性排序，并在同一个表中检查这些额外的桶。这样能以数倍更少的表数达到相近的召回率，代价是每次查询需要更多次探测。OpenCV基于FLANN的LSH索引正好暴露了这些调节参数：表的数量、键的大小$k$，以及多探测层级。

对SLAM的意义

基于特征的SLAM系统每帧会产生数千个二进制描述子，必须将它们与包含数百万描述子的地图或关键帧数据库进行匹配。暴力匹配是精确的但复杂度为$O(nm)$；kd树在处理高维二进制数据时性能会严重退化。LSH是二进制描述子的标准答案——这正是FLANN为ORB/BRIEF数据选择的方法——它支撑着快速重定位以及回环检测候选检索,能在毫秒级内将一组查询描述子与庞大的地图进行匹配。理解$k$/$L$/多探测之间的权衡,能让你为自己的平台调节召回率与延迟之间的平衡。

相关条目

• FLANN
• Kd-tree
• 暴力匹配
• ORB
• HBST