📘

Nearest Neighbor Distance Ratio (NNDR) Check

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.

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.

📘