📘

Nearest Neighbor Distance Ratio (NNDR) Check

EasyArrays, Sorting, Geometry 📚 Computer 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:

Compute distances from target $[0,0]$ to each candidate using Euclidean distance:
- To $[1,0]$ : $d_1 = \sqrt{(1-0)^2 + (0-0)^2} = 1$
- To $[10,0]$ : $d_2 = \sqrt{(10-0)^2 + (0-0)^2} = 10$
Sort distances: nearest neighbor distance $d_1 = 1$ (index 0), second nearest $d_2 = 10$ (index 1).
Compute NNDR: $\text{NNDR} = d_1 / d_2 = 1 / 10 = 0.1$ .
Compare with threshold: $0.1 < 0.5$ , so the match is accepted and we return the index of the nearest neighbor, which is 0.

More from Computer Vision 1

Semi-Global Matching Cost AggregationHard Compute Depth Map from DisparityMedium Stereo Rectification CheckEasy Oriented BRIEF DescriptorHard Gaussian Scale SpaceMedium

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

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.