Skip to content

Latest commit

 

History

History
85 lines (57 loc) · 3.23 KB

README.md

File metadata and controls

85 lines (57 loc) · 3.23 KB
Raw

Chamfer distance visualization

Visualization of the Chamfer distance between two point clouds using dash app in both Python and Javascript.

https://www.oliver-ernst.com/chamfer-viz/

Example 1 Example 2 Example 3

Running

Javascript

Navigate to the js directory and run using VSCode's Live Server extension or any other web server of your choice. For example:

cd js
python -m http.server

Python

Navigate to the python directory and install the requirements:

pip install -r requirements.txt

Then run the app:

python app.py

Optionally: specify the port with --port flag or debug mode with --debug flag.

Explanation

  1. Given two sets of points or shapes, usually referred to as Set A and Set B.
  2. For each point in Set A, find the closest point in Set B and calculate the distance between them.
  3. For each point in Set B, find the closest point in Set A and calculate the distance between them.
  4. Sum up all these distances from steps 2 and 3 to obtain the Chamfer distance.

Mathematically, the Chamfer distance can be expressed as:

$$Chamfer distance = Σ(min(dist(A_i, B_j)) + Σ(min(dist(B_i, A_j)))$$

Where:

A_i represents a point in Set A. B_j represents a point in Set B. dist(A_i, B_j) is the distance between point A_i and its closest point in Set B. dist(B_i, A_j) is the distance between point B_i and its closest point in Set A.

Implementation

Chamfer distance uses a KDTree. A KDTree is a data structure that organizes points in a way that enables fast nearest-neighbor queries. Computing the structure for Set B makes it faster to find the nearest neighbors in Set B for each point in Set A (and vice versa).

The use of the KDTree data structure significantly speeds up the computation of nearest neighbors for each point in Sets A and B. Without KDTree, you would need to perform a brute-force search, which can be computationally expensive, especially for large point sets. KDTree organizes the points in a way that allows for efficient nearest-neighbor queries and is commonly used in computational geometry and various data science tasks.

It's important to note that while KD-Trees offer efficient nearest neighbor and range search capabilities, their performance can degrade for very high-dimensional data (often referred to as the "curse of dimensionality"). In such cases, other data structures like ball trees or approximate nearest neighbor algorithms may be more suitable. Nevertheless, KD-Trees remain a valuable tool for solving a wide range of problems involving multi-dimensional data.

References

  • KDtree in JS

  • Basic Chamfer distance implementation

    import numpy as np
from scipy.spatial import KDTree

def chamfer_distance(A, B):
    """
    Computes the chamfer distance between two sets of points A and B.
    """
    tree = KDTree(B)
    dist_A = tree.query(A)[0]
    tree = KDTree(A)
    dist_B = tree.query(B)[0]
    return np.mean(dist_A) + np.mean(dist_B)