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:
target=[0,0], candidates=[[1,0],[10,0]], threshold=0.5
0
-
Compute distances from target [0,0] to each candidate using Euclidean distance:
- To [1,0]: d1=(1−0)2+(0−0)2=1
- To [10,0]: d2=(10−0)2+(0−0)2=10
-
Sort distances: nearest neighbor distance d1=1 (index 0), second nearest d2=10 (index 1).
-
Compute NNDR: NNDR=d1/d2=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.