A Near-Linear Time Algorithm for the Chamfer Distance
share
For any two point sets A,B ⊂ℝ^d of size up to n, the Chamfer distance from A to B is defined as CH(A,B)=∑_a ∈ Amin_b ∈ 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, 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)/ε^2) 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+ε)-approximate mapping from A to B (as opposed to just its value), then any sub-quadratic time algorithm is unlikely to exist.
READ FULL TEXT