A Near-Linear Time Algorithm for the Chamfer Distance

For any two point sets A,B subset ℝd of size up to n, the Chamfer distance from A to B is defined as CH(A,B)=suma ∈ A minb ∈ B dX(a,b), where dX is the underlying distance measure (e.g., the Euclidean or Manhattan distance). The Chamfer distance is a popular measure of dissimilarity between point clouds, used in many machine learning, computer vision, and graphics applications, and admits a straightforward O(d n2)-time brute force algorithm. Further, the Chamfer distance is often used as a proxy for the more computationally demanding Earth-Mover (Optimal Transport) Distance. However, the quadratic dependence on n in the running time makes the naive approach intractable for large datasets. We overcome this bottleneck and present the first (1+ε)-approximate algorithm for estimating the Chamfer distance with a near-linear running time. Specifically, our algorithm runs in time O(nd log (n)/varepsilon2) and is implementable. Our experiments demonstrate that it is both accurate and fast on large high-dimensional datasets. We believe that our algorithm will open new avenues for analyzing large high-dimensional point clouds. We also give evidence that if the goal is to report a (1+varepsilon)-approximate mapping from A to B (as opposed to just its value), then any sub-quadratic time algorithm is unlikely to exist.