Brute Force Matching

Brute force compares every descriptor against every other one, which is slow but exact and the baseline every faster matcher must beat.

Brute force scores all query train pairs and keeps exact nearest neighbors.

Why Does This Exist?

Approximate matchers trade recall for speed, which hides bugs during development. Brute force gives the exact answer: every query against every train vector with the right metric. That makes it the reference for testing faster indexes and the right default for small sets.

For the wider pipeline, read feature matching. Come here for exact knn semantics, cross check, and cost math.

Think of It Like This

Checking every locker

You lost a key with a red tag. Fast search checks likely lockers first and may quit early. Brute force opens every locker in order. Slow, certain, and simple to reason about.

Exact search plays that role for descriptors. The analogy stops at scale: lockers number in hundreds, while descriptor sets reach millions, where opening all doors stops being an option.

How It Actually Works

With $m$ query and $n$ train descriptors of dimension $d$ , cost is $O(m n d)$ distance operations. OpenCV BFMatcher picks NORM_L2 for SIFT and SURF, NORM_HAMMING for ORB, BRIEF, and BRISK. knnMatch(k=2) returns the two best per query for the ratio test. Cross check mode keeps only mutual best pairs.

Worked numbers

Match $800$ SIFT queries against $1{,}000$ train vectors with $d = 128$ . That is $800{,}000$ pairs times $128$ multiply adds, about $102$ million operations. On CPU that runs in tens of milliseconds, fine for a photo pair. Scale to $100{,}000$ database vectors and the same query needs $80$ million pairs, which pushes you to FLANN. A query with distances $d_1 = 180$ and $d_2 = 320$ passes ratio $0.56$ at threshold $0.75$ .

Watch Out For

Hamming flag on float descriptors

Passing SIFT floats with NORM_HAMMING compiles yet ranks garbage. Match the norm to the descriptor family, or exact search returns exactly wrong neighbors.

Using it as a production index

Brute force on a million image database means seconds per query and blown memory. Prototype with it, measure recall, then move large search to FLANN or a vector index.

The Quick Version

Scores all $m \times n$ pairs with the matching metric.
Exact, simple, and the recall baseline.
Cost grows as $O(m n d)$ , fine for pairs, fatal for huge databases.
Use knn with $k = 2$ for ratio filtering.
Cross check trims one way false friends.