FLANN Approximate Matching

FLANN indexes descriptors with trees or hashes so large photo collections match in milliseconds at a small recall cost.

FLANN routes each query through a descriptor index instead of scanning all vectors.

Why Does This Exist?

Brute force dies on large collections because every query scans every vector. Retrieval over thousands of photos needs sublinear search. FLANN, Fast Library for Approximate Nearest Neighbors, picks and tunes an index for your descriptor type.

Float descriptors get randomized KD trees or hierarchical k-means. Binary strings get multi-probe LSH. You trade a few points of recall for orders of magnitude less time. For pair matching basics, see feature matching.

Think of It Like This

Library card catalogs

Brute force walks every shelf for each request. FLANN builds card catalogs first: one sorted by subject for float books, one by hash drawers for binary pamphlets. Most queries stop after a few drawers.

The catalog sometimes misses a book filed oddly. That miss is the recall cost. The analogy stops at tuning: trees, checks, and hash tables need sizing to your data.

How It Actually Works

Build an index over train descriptors once, then query it per image. KD trees split float space along high variance dims with several randomized trees. LSH hashes binary strings into buckets and probes nearby buckets. Key knobs are tree count, search checks, and hash table count plus key size.

Worked numbers

Index $200{,}000$ SIFT vectors with $5$ KD trees and $50$ checks. A query visits thousands of leaves instead of $200{,}000$ vectors, often $20$ times faster at $95$ percent recall versus exact search. For $500{,}000$ ORB strings, $12$ hash tables with key size $20$ and multi-probe level $2$ give similar behavior. Measure recall against brute force on a sample: if exact finds $1{,}000$ true pairs and FLANN finds $950$ , recall is $0.95$ . Raise checks or tables until recall meets your geometry needs.

Watch Out For

KD trees on binary strings

Randomized trees assume Euclidean splits. On ORB bits they crawl and miss. Use LSH for binary descriptors and KD trees or k-means for floats, or speed collapses.

Untuned defaults on new data

Default checks suit demos, not your database size. Too few checks tanks recall silently, and RANSAC later starves. Benchmark recall versus brute force whenever descriptor count or type changes.

The Quick Version

Indexes train descriptors once, queries many times.
KD trees suit SIFT and SURF floats, LSH suits binary strings.
Checks, trees, and tables trade recall against latency.
Benchmark against brute force recall on your own sample.
Right choice for retrieval over thousands of images.