Nearest Neighbor Distance Ratio (NNDR) Check

easyFREEFeature Detection and MatchingArrays, Sorting, GeometryComputer Vision 1

When matching feature descriptors between images, the Nearest Neighbor Distance Ratio (NNDR) test filters out ambiguous matches. A match is reliable only if:

NNDR = d₁ / d₂ < threshold

where d₁ is the distance to nearest neighbor and d₂ is distance to second nearest.

Given a target descriptor and list of candidates, return the index of the nearest neighbor if NNDR < threshold, otherwise return -1.

Constraints:

1 ≤ |descriptor| ≤ 128
|candidates| ≥ 2
0.0 < threshold < 1.0

Examples:

| Input | Output | |-------|--------| | target=[0,0], candidates=[[1,0],[10,0]], T=0.5 | 0 | | target=[0,0], candidates=[[1,0],[2,0]], T=0.5 | -1 |

Example

Input

target=[0,0], candidates=[[1,0],[10,0]], threshold=0.5

Output

Reasoning

Inputs: target is one feature descriptor, here the 2-D point $(0, 0)$ . candidates holds descriptors from the other image, $(1, 0)$ at index 0 and $(10, 0)$ at index 1. threshold $= 0.5$ is the largest ratio still counted as unambiguous.
Distances: the Euclidean distance to $(1, 0)$ is $\sqrt{(1-0)^2 + (0-0)^2} = 1$ , and to $(10, 0)$ it is $\sqrt{10^2 + 0^2} = 10$ .
Nearest two: the closest candidate is index 0 with $d_1 = 1$ ; the runner-up has $d_2 = 10$ .
Ratio test: $\text{NNDR} = d_1 / d_2 = 1/10 = 0.1$ . Since $0.1 < 0.5$ , the match is accepted and the output is the nearest candidate's index, 0.
Notice: the output is a position in candidates, not a distance. In the second example the runner-up sits at distance 2, so the ratio is $1/2 = 0.5$ , which is not strictly below $0.5$ . Two near-equal candidates make the match ambiguous, so the answer becomes -1.

Learn this in

Feature Detection and MatchingCV Study Plan Multi-View Geometry3D Computer Vision

More from Computer Vision 1

Semi-Global Matching Cost Aggregationhard Compute Depth Map from Disparitymedium Stereo Rectification Checkeasy Oriented BRIEF Descriptorhard Gaussian Scale Spacemedium

Concept primer

1. Background Knowledge

The Nearest Neighbor Distance Ratio (NNDR) test, introduced by David Lowe in SIFT (2004), is the gold standard for feature matching. It compares the distances to the two nearest neighbors:

$\text{NNDR} = \frac{d_1}{d_2}$

where $d_1$ is distance to nearest neighbor and $d_2$ is distance to second nearest.

Intuition: A distinctive feature should have a much closer match than any alternative. A low ratio indicates high confidence.

Typical thresholds:

0.7-0.8 for high precision
0.9 for high recall

2. Algorithm Approach

Compute distances from target to all candidates
Find two smallest distances ( $d_1$ , $d_2$ )
Compute ratio $d_1/d_2$
Accept match if ratio < threshold

3. Step-by-Step Strategy

Iterate through candidates computing Euclidean distances
Sort by distance to find nearest two
Handle edge case where $d_2 = 0$
Return matched index or -1

4. Common Pitfalls

Division by zero when $d_2 = 0$
Confusing $d_1/d_2$ vs $d_2/d_1$
Using wrong distance metric (should be Euclidean for SIFT)

5. Time & Space Complexity

Aspect	Complexity
Time	O(n·d) where n=candidates, d=dimensions
Space	O(n) for storing distances