FLANN (Fast Library for Approximate Nearest Neighbours)

FLANN (Muja & Lowe, 2009) is a library for approximate nearest-neighbour search in high-dimensional spaces, built to make large-scale descriptor matching practical. Exact brute-force matching costs $O(n \cdot m \cdot d)$ for $n$ query and $m$ database descriptors of dimension $d$ , and exact tree search collapses to nearly linear scan in high dimensions. FLANN’s position is pragmatic: accept finding the true nearest neighbour only, say, 95% of the time in exchange for one or two orders of magnitude speed-up — a trade that feature matching tolerates well, since downstream ratio tests and RANSAC discard bad matches anyway.

The two core index structures

Randomized kd-tree forest. Instead of one kd-tree searched exhaustively, FLANN builds several trees whose split dimensions are chosen randomly among the few dimensions of highest variance. All trees are searched simultaneously through a single shared priority queue ordered by distance to the splitting boundary, and the search stops after a fixed budget of leaf checks. Because each tree partitions the space differently, the true neighbour that falls on the wrong side of a split in one tree is usually found in another. This is the method of choice for float descriptors (SIFT’s 128-D, SuperPoint’s 256-D).

Priority search k-means tree. The data is recursively partitioned with k-means into $K$ clusters per node (branching factor), building a hierarchy that respects the natural clustering of the data rather than axis-aligned cuts. Queries descend to the closest cluster and backtrack through a priority queue of unexplored branches. This often wins when higher precision is required.

For binary descriptors (ORB, BRIEF), FLANN provides a multi-probe LSH index instead — Hamming space has no meaningful axis-aligned splits, but bit-sampling hash functions are naturally locality-sensitive there.

Automatic algorithm configuration

FLANN’s signature feature is picking the algorithm for you: given a dataset, a target search precision (fraction of true nearest neighbours returned), and weights expressing how much you care about build time and memory versus query time, it cross-validates on a sample of the data and returns the best index type and parameters (number of trees, branching factor, leaf-check budget). This matters because the optimal structure genuinely depends on the data distribution and the required precision — there is no single winner.

The knobs that matter

Whether tuned automatically or by hand, FLANN’s behaviour comes down to a few parameters:

Number of trees (randomized kd-forest): more trees raise recall per leaf-check budget at the cost of memory and build time; a handful of trees is typical.
checks — the budget of leaf visits per query: the single most direct accuracy/speed dial at search time. More checks asymptotically approach exact search.
Branching factor and iterations (k-means tree): coarser vs. finer hierarchies, and how hard k-means works during the build.
Target precision (auto-tuned mode): the fraction of queries whose true nearest neighbour must be returned; FLANN searches the parameter space to meet it at minimum cost.

A useful mental model: the index defines which candidates get examined, and checks defines how many — accuracy failures show up not as wrong distances but as a correct neighbour that was simply never visited.

Use in a matching pipeline

A typical SLAM/SfM matching stage with FLANN:

Build an index over the descriptors of the reference image (or the map’s landmark descriptors).
For each query descriptor, retrieve the 2 approximate nearest neighbours.
Apply Lowe’s ratio test — accept only if $d_1 / d_2 < 0.8$ — to discard ambiguous matches.
Feed surviving matches to geometric verification (RANSAC on an essential matrix or PnP model).

In OpenCV this is cv::FlannBasedMatcher, the drop-in alternative to cv::BFMatcher; note that for ORB it must be configured with the LSH index, since the default kd-tree assumes float descriptors. Approximation adds one caveat: the ratio test compares approximate first and second neighbours, so aggressive speed settings slightly change which matches survive.

Why it matters for SLAM

Matching cost scales with map size, and SLAM systems match constantly: feature-to-map tracking, loop-closure candidate verification, relocalization against thousands of keyframes, and offline SfM matching across image collections (COLMAP uses FLANN-style approximate search). Brute force is fine for two images with a few thousand ORB features (Hamming + popcount is very fast), but against a large map or a large vocabulary, sub-linear approximate search is what keeps the front-end real-time. FLANN is also the standard answer for nearest-neighbour queries on 3D point clouds (via its integration in PCL), where kd-trees operate in their low-dimensional comfort zone — e.g., correspondence search inside ICP.