A Near-Linear Time Algorithm for the Chamfer Distance
summary
Claim: a one-plus-epsilon approximation to Chamfer distance in near-linear time, roughly O(d n log n / ε^2), achieved by computing crude nearest-neighbor estimates, converting them to sampling probabilities and doing importance sampling with ANN-style estimates on O((log n)/ε^2) samples. Core tool is a random-shift quadtree per level (HST-like) to get unbiased distance sketches. Empirically it beats kd-tree baselines with a few-percent error and is parallelizable; a fine-grained lower bound rules out producing approximate correspondences in the same time under the hitting-set conjecture.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:05What is Chamfer distance
- 4:33Chamfer vs earthmover distance
- 10:24Applications
- 13:18Prior work
- 19:14Algorithm overview
- 25:26Hierarchically well-separated trees for approximation
- 36:20Experimental results
- 47:53Open questions
- 53:28Q&A
related talks
01h 01mNearest Neighbor Methods II
44mSomething for Almost Nothing: Advances in Sub-Linear Time Algorithms
01h 05mNearest Neighbor Methods I
48mHolder Homeomorphisms and Approximate Nearest Neighbors
42mDistribution-Specific Analysis of Nearest Neighbor Search and Classification
40mEfficient Reductions for k-Nearest Neighbor Search
01h 01mRecent Advances in Algorithmic Heavy-Tailed Statistics
31mNearest Neighbor Based Greedy Coordinate Descent