PaperlayerView exact revision on arXiv

Source-linked AI summary

A Near-Linear Time Algorithm for the Chamfer Distance

Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal, Erik Waingarten

arXiv:2307.03043v1cs.DScs.CGcs.GRcs.LG

TL;DR

Chamfer distance is useful for point-cloud comparison, but naive computation is quadratic and difficult to scale. The paper combines coarse nearest-neighbor estimates with importance sampling to obtain a near-linear-time approximation, while showing that reporting an equally accurate mapping is conditionally much harder. Experiments demonstrate faster and more sample-efficient computation than brute force and uniform sampling.

  • Problem

    The quadratic cost of naive Chamfer-distance computation makes it difficult to apply to large datasets.

  • Method

    The algorithm obtains coarse nearest-neighbor distance estimates and uses them for importance sampling to estimate Chamfer distance.

  • Results

    The method is approximately 5x faster than brute-force KD-tree computation and 50% faster than uniform sampling on ShapeNet at comparable relative error.

  • Takeaways & Limitations

    Estimating Chamfer distance can be near-linear and practical, whereas reporting a similarly accurate mapping is conditionally near-quadratic.

  • Takeaways & Limitations

    Uniform-sampling approaches can fail on datasets with skewed nearest-neighbor distance distributions, motivating an input-structure-robust method.

Abstract

from arXiv · show

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 $\text{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, the 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 the Chamfer distance with a near-linear running time. Specifically, our algorithm runs in time $O(nd \log (n)/\varepsilon^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 \emph{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.

1 Introduction

Chamfer distance is widely used for comparing point clouds, but its straightforward computation is quadratic and difficult to scale. The paper presents a near-linear-time approximation for estimating it, alongside a conditional near-quadratic lower bound for reporting approximate mappings.

  • 1 Introduction: Chamfer distance and its weighted generalization are widely used to measure point-cloud dissimilarity in machine learning, computer vision, and computer graphics.The distance is also connected to relaxed Earth Mover Distance.
  • 1 Introduction: The naive Chamfer-distance algorithm has quadratic running time, limiting its use on large datasets.Nearest-neighbor-based approximations still face dimension-dependent or approximation-factor limitations.
  • 1.1 Our Results: The paper gives the first near-linear-time (1 + ε)-approximation algorithm for estimating Chamfer distance.For ℓ1 and ℓ2 metrics, the algorithm estimates the distance up to 1 ± ε with 99% probability and is described as easy to implement.
  • 1.1 Our Results: Under the Hitting Set Conjecture, reporting a (1 + ε)-approximate mapping requires nearly quadratic time even for Manhattan distance.This contrasts with the paper’s near-linear-time estimation algorithm, showing that estimation is significantly easier than reporting.
  • 1.1 Our Results: Experiments show the method is effective across low- and high-dimensional datasets and scales to billion-scale data.The method is reported as over 5x faster than brute force, 5–10x more sample efficient than uniform sampling, and up to 50x faster than optimized brute force on Big-ANN-Benchmarks.

2 Algorithm and Analysis

The paper combines CrudeNN importance estimates with randomized sampling to estimate Chamfer distance in near-linear time under metrics supported by locality-sensitive hashing. Its analysis establishes accuracy, runtime, and implementation guarantees while addressing skewed nearest-neighbor contributions.

  • Uniform vs Importance Sampling: Importance sampling addresses skewed nearest-neighbor contributions, whereas uniform sampling may require Ω(n) samples and a quadratic runtime for 1% relative error.Uniform sampling remains unbiased, but its sample complexity is poor when only a small fraction of points contributes substantially.
  • Chamfer-Estimate: The estimator samples points from A using probabilities proportional to D_a and averages their explicitly computed nearest-neighbor distances to estimate CH(A, B).CrudeNN outputs the weights, and Chamfer-Estimate constructs the distribution before sampling.
  • Analysis: The analysis bounds estimator variance and combines CrudeNN with sampling to obtain the stated accuracy and runtime, with CrudeNN itself running in O(dn log(n/ε)) time.The proof uses the over-estimated total weight and Lemmas 2.2 and 2.3 before applying the sampling bound.
  • Obtaining importance sampling probabilities: CrudeNN directly constructs over-estimates D_a of each point's nearest-neighbor distance, avoiding the extra poly(log n) factors of approximate nearest-neighbor black-boxes.Its randomized partitions use locality-sensitive hashing across distance scales, yielding an expected O(log n)-approximation and setting λ = log n.

3 Experiments

Experiments evaluate Chamfer estimation across low- and high-dimensional datasets, varying scales and difficult distance distributions. Importance sampling improves sample efficiency and runtime over uniform sampling and brute-force baselines, including large-scale settings.

  • Small Scale: On ShapeNet, three grid levels make crude estimates within a factor of 2 of true nearest-neighbor values, and the top 30 candidates contain the exact nearest neighbor over 98% of the time.This reduces the number of point clouds requiring exact computation by more than 1000x compared with naive brute force.
  • Small Scale: At least 5x fewer samples achieve the same relative error on ShapeNet, while the text-embedding dataset exceeds 10x sample-complexity improvement over uniform sampling.The ShapeNet comparison uses 10 samples versus 50+ for uniform sampling; the text-embedding comparison shows an even wider gap.
  • Small Scale: The algorithm is approximately 5x faster than brute-force KD-tree computation and 50% faster than uniform sampling on ShapeNet at about 2% relative error.For the Federalist Papers dataset, it uses 20 samples versus at least 450 and achieves a 2x speedup over uniform sampling.
  • Outliers: Uniform sampling retains high relative error until an outlier is sampled, typically requiring Ω(n) samples, whereas importance sampling decreases error smoothly as samples increase.The outlier experiment uses Gaussian point clouds in R^100 with one added outlier, stressing skewed nearest-neighbor distances.
  • Large Scale: For DEEP1B and Turing, importance sampling requires fewer samples than uniform sampling at comparable accuracy, while reducing k or W worsens approximation quality and sample complexity.The best reported parameter choice for both datasets is 64 × 10^6; these experiments target billion-scale datasets in hundreds of dimensions.
  • Large Scale: On DEEP1B, the 16 × 2 · 10^5 configuration reaches 1% relative error in approximately 1785 seconds, versus over 2200 seconds for uniform sampling, which is over 23% slower.The method uses approximately 980 samples, while uniform sampling requires more than 1750; the runtime gap increases at smaller relative errors.

4 Lower Bound for Reporting the Alignment

The paper studies whether a near-linear-time approximation can report a near-optimal mapping for Chamfer distance, rather than only estimate its value. Under the Hitting Set Conjecture, such reporting requires nearly quadratic time even in logarithmic-squared dimension.

  • The reporting task asks for g : A → B whose total mapping cost is within a factor 1 + ε of the Chamfer distance.
  • The hardness applies to Manhattan distance and is stated for randomized algorithms under the Hitting Set Conjecture.
  • The lower bound is obtained by reducing from Hitting Set, whose conjectured hardness concerns instances with dimension Θ(log^2 n).
  • Under the Hitting Set Conjecture, reporting a mapping with cost within 1 + ε of CH requires Ω(N^(2−δ)) time for every constant δ > 0 when D = Θ(log^2 N) and ε = Θ(1).

5 Conclusion

The paper presents an implementable near-linear-time approximation algorithm for estimating Chamfer distance and contrasts it with a conditional near-quadratic lower bound for reporting a mapping. Its core strategy combines coarse nearest-neighbor estimates with importance sampling.

  • The algorithm estimates Chamfer distance within a 1 + ε factor in near-linear time and is easy to implement in practice.
  • A conditional lower bound shows that reporting a Chamfer-distance mapping of comparable quality requires nearly quadratic time.
  • The experiments compare the method favorably with brute-force computation and uniform sampling.
  • The approach combines fast estimates of coarse nearest-neighbor distances with importance sampling for large-scale, high-dimensional data analysis.

A Deferred Analysis from Section 2

This appendix completes the estimator analysis by combining multiscale locality-sensitive hashing, bounded-aspect-ratio decompositions, and concentration arguments. The resulting procedure achieves relative-error estimation with near-linear dependence on the input size.

  • For each point, the estimator overestimates its nearest-neighbor distance while importance sampling controls the aggregate estimator variance.
  • Multiscale hashing uses locality-sensitive collisions to search across distance scales, with close points colliding frequently and far points infrequently.
  • The running time is O(dn log(n/ε)) when hash-function evaluations take O(d) time.
  • The construction partitions inputs into O(n) pairs with polynomially bounded aspect ratio, then combines their estimates to approximate CH(A, B).
  • The resulting estimator is a (1 ± ε) relative-error approximation to CH(A, B), after applying Markov’s and Chebyshev’s inequalities.

A.1 Analysis for CrudeNN

The CrudeNN analysis bounds the probability that a hashed candidate is much farther than the true nearest neighbor by separating collision failures across coarse and fine scales. Integrating these bounds yields the required expected-distance control, with logarithmic-scale evaluation cost.

  • The hashing scale parameter is related to the point’s nearest-neighbor distance, while the analysis chooses a logarithmic oversampling parameter c = Θ(log n).
  • CrudeNN’s error analysis separates oversized estimates into two bad events: early collisions with far points and later collisions after all nearer scales fail.
  • The analysis controls the tail probability of CrudeNN’s estimate by bounding the contributions from these two events and integrating across distance ranges.
  • Evaluating O(log(n/ε)) hash functions on n points, each in O(d) time, gives the running-time bound.

A.2 Locality-Sensitive Hashing at Every Scale

The section constructs locality-sensitive hashes at every scale, with collision behavior controlled by the ℓ1 distance and scale parameter. These hashes support reductions, embeddings, and crude Chamfer-distance estimation while preserving distance up to the stated approximation factors.

  • A.2 Locality-Sensitive Hashing at Every Scale: Each hash evaluation takes O(d) time, making the scale-specific construction implementable across all points.
  • A.2 Locality-Sensitive Hashing at Every Scale: The hash family separates points when some coordinate exceeds r or a random threshold falls between them, while collision requires every coordinate difference to be at most r.The construction samples a random threshold vector z from [0,r]^d.
  • A.2 Locality-Sensitive Hashing at Every Scale: A standard embedding extends the construction from ℓ1 to ℓ2 without changing the Chamfer distance of mapped points by more than a (1 ± ε)-factor.The embedding adds an extra O-term to the running time for processing all points.
  • A.2 Locality-Sensitive Hashing at Every Scale: The aspect-ratio reduction partitions points with LSH and adds O(log n) coordinates so distant pairs are separated while the Chamfer increase remains an O(ε) relative term.The added random vector has norm ε · η/(cn), and the additive increase is O(εη/c).
  • A.2 Locality-Sensitive Hashing at Every Scale: A crude poly(n)-approximation can be obtained in O(nd) + O(n log n) time by projecting with a p-stable sketch and solving one-dimensional nearest-neighbor queries.For p = 2 the sketch uses Gaussian coordinates, while p = 1 uses independent Cauchy variables.

B Deferred Analysis from Section 4

The deferred analysis reduces Hitting Set to approximate Chamfer distance by encoding orthogonality as two separated ℓ1 distances. An approximate Chamfer oracle then enables recursive elimination of many non-hitting vectors, establishing the stated hardness consequence.

  • B Deferred Analysis from Section 4: The reduction maps orthogonal pairs to ℓ1 distance 4d + 2 and nonorthogonal pairs to distance at least 4d + 4, with O(d)-time evaluations.The construction is attributed to Lemma 4.3 from [Roh19].
  • B Deferred Analysis from Section 4: For h hitting vectors, the constructed Chamfer distance is nA(4d + 2) + 2h, so distinguishing h = 0 would solve Hitting Set.
  • B Deferred Analysis from Section 4: The recursive subroutine samples t = c log(n)/ε vectors, invokes the approximate Chamfer algorithm, identifies a set M, and recurses on A − M.It first directly checks sampled vectors and then uses the reported mapping to identify vectors matched at distance 4d + 2.
  • B Deferred Analysis from Section 4: Figure 7 depicts the reduction from Hitting Set to (1 + ε)-approximate Chamfer distance implemented through ALG.
  • B Deferred Analysis from Section 4: With high probability, at most ε · nA vectors are hitting vectors when the oracle is invoked, so the mapping cost forces removal of at least half the remaining vectors.The mapping cost is C = m(4d + 2) + (nA −m)(4d + 4) = nA(4d + 4) −2m.
Loading 2307.03043v1…