Near-Linear Time Algorithm for the Chamfer Distance

For any two point sets A,B \subset \mathbb{R} d of size up to n, the Chamfer distance from A to B is defined as \texttt{CH}(A,B) \sum_{a \in A} \min_{b \in B} d_X(a,b), where d_X 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 n 2) -time brute force algorithm. Further, Chamfer distance is often used as a proxy for the more computationally demanding Earth-Mover (Optimal Transport) Distance. However, the \emph{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 \epsilon) -approximate algorithm for estimating Chamfer distance with a near-linear running time. Specifically, our algorithm runs in time O(nd \log (n)/\epsilon 2) and is implementable. Our experiments demonstrate that it is both accurate and fast on large high-dimensional datasets.