FLANN (Fast Library for Approximate Nearest Neighbours)

FLANN(Muja & Lowe,2009)是一个在高维空间中进行近似最近邻搜索的库,其构建目的是让大规模描述子匹配变得切实可行。精确暴力匹配的代价为 $O(n \cdot m \cdot d)$ (其中 $n$ 为查询描述子数、 $m$ 为数据库描述子数、 $d$ 为维度),而精确树搜索在高维情况下会退化为几乎线性的扫描。FLANN 的立场是务实的:接受只有大约 95% 的概率能找到真正的最近邻,以换取一到两个数量级的加速——这种取舍对特征匹配而言完全可以接受,因为后续的比值测试和 RANSAC 本来就会丢弃错误匹配。

两种核心索引结构

随机化 kd 树森林。 FLANN 不是构建单一的、被穷尽搜索的 kd 树,而是构建多棵树,其分裂维度是在方差最大的少数几个维度中随机选择的。所有树通过一个共享的、按到分裂边界距离排序的优先队列同时被搜索,搜索在达到固定的叶子检查预算后停止。由于每棵树对空间的划分方式不同,在某一棵树中落在分裂错误一侧的真实邻居,通常能在另一棵树中被找到。这是浮点型描述子(SIFT 的 128 维、SuperPoint 的 256 维)的首选方法。

优先级搜索 k-均值树。 数据在每个节点用 k-均值递归划分为 $K$ 个簇(分支因子),构建出一个尊重数据自然聚类结构的层级,而不是轴对齐的切分。查询下降到最近的簇,并通过一个未探索分支的优先队列进行回溯。当需要更高精度时,这种方法往往更胜一筹。

对于二值描述子(ORB、BRIEF),FLANN 提供的是多探针 LSH 索引——汉明空间中不存在有意义的轴对齐分割,但位采样哈希函数在该空间中天然具有局部敏感性。

自动算法配置

FLANN 的标志性功能是替你选择算法:给定一个数据集、一个目标搜索精度(返回真实最近邻的比例),以及表达你对构建时间和内存相对于查询时间的重视程度的权重,它会在数据的样本上进行交叉验证,并返回最优的索引类型和参数(树的数量、分支因子、叶子检查预算)。这一点很重要,因为最优结构真正取决于数据分布和所需精度——不存在单一的赢家。

关键旋钮

无论是自动调优还是手动调优,FLANN 的行为归结为几个参数:

树的数量(随机化 kd 森林):树越多,在给定叶子检查预算下召回率越高,但代价是内存和构建时间;通常使用少量几棵树。
checks——每次查询的叶子访问预算:这是搜索时最直接的精度/速度旋钮。检查次数越多,越渐近逼近精确搜索。
分支因子与迭代次数(k-均值树):更粗或更细的层级,以及构建过程中 k-均值的努力程度。
目标精度(自动调优模式):必须返回其真实最近邻的查询比例;FLANN 会在参数空间中搜索,以最小代价达到该目标。

一个有用的心理模型:索引决定哪些候选会被检查,而 checks 决定检查多少——精度失败并不表现为距离计算错误,而是表现为一个正确的邻居根本没有被访问到。

在匹配流程中的用法

一个典型的 SLAM/SfM 匹配阶段中使用 FLANN 的流程:

在参考图像的描述子(或地图的路标描述子)上构建索引。
对每个查询描述子,检索 2 个近似最近邻。
应用Lowe 比值测试——仅当 $d_1 / d_2 < 0.8$ 时才接受——以丢弃有歧义的匹配。
将存活下来的匹配送入几何验证(在本质矩阵或 PnP 模型上做 RANSAC)。

在 OpenCV 中,这对应 cv::FlannBasedMatcher,是 cv::BFMatcher 的即插即用替代品;需要注意的是,对于 ORB,必须将其配置为 LSH 索引,因为默认的 kd 树假设的是浮点型描述子。近似带来一个注意事项:比值测试比较的是近似的第一和第二邻居,因此激进的速度设置会稍微改变哪些匹配能够存活下来。

对SLAM的意义

匹配代价随地图规模增长,而 SLAM 系统需要不断地进行匹配:特征到地图的跟踪、回环检测候选的验证、针对数千个关键帧的重定位,以及跨图像集合的离线 SfM 匹配(COLMAP 使用类似 FLANN 的近似搜索)。对于只有几千个 ORB 特征的两张图像,暴力匹配完全够用(汉明距离配合 popcount 非常快),但面对一个大地图或大词汇表,亚线性的近似搜索才是保证前端实时运行的关键。FLANN 也是 3D 点云上最近邻查询的标准答案(通过其在 PCL 中的集成),在那里 kd 树能在其低维的舒适区内运作——例如 ICP 内部的对应搜索。