# Point Cloud Metrics

Point Cloud Utils has functions to compute a number of commonly used metrics between point clouds.

## Chamfer Distance

The Chamfer distance between two point clouds $$P_1 = \{x_i \in \mathbb{R}^3\}_{i=1}^n$$ and $$P_2 = \{x_j \in \mathbb{R}^3\}_{j=1}^m$$ is defined as the average distance between pairs of nearest neighbors between $$P_1$$ and $$P_2$$ i.e. $$\text{chamfer}(P_1, P_2) = \frac{1}{2n} \sum_{i=1}^n |x_i - \text{NN}(x_i, P_2)| + \frac{1}{2m} \sum_{j=1}^n |x_j - \text{NN}(x_j, P_1)|$$ and $$\text{NN}(x, P) = \text{argmin}_{x' \in P} \|x - x'\|$$ is the nearest neighbor function.

The following code computes the Chamfer distance between two point clouds:

import point_cloud_utils as pcu

# p1 is an (n, 3)-shaped numpy array containing one point per row

# p2 is an (m, 3)-shaped numpy array containing one point per row

# Compute the chamfer distance between p1 and p2
cd = pcu.chamfer_distance(p1, p2)


## Hausdorff distance

The Hausdorff distance between two point clouds $$P_1 = \{x_i \in \mathbb{R}^3\}_{i=1}^n$$ and $$P_2 = \{x_j \in \mathbb{R}^3\}_{j=1}^m$$ is defined as the maxmimum distance between any pair of nearest neighbors between $$P_1$$ and $$P_2$$ i.e. $$\text{hausdorff}(P_1, P_2) = \frac{1}{2} \max_{x \in P_1} |x - \text{NN}(x, P_2)| + \frac{1}{2} \max_{x' \in P_2} |x' - \text{NN}(x', P_1)|$$ and $$\text{NN}(x, P) = \text{argmin}_{x' \in P} \|x - x'\|$$ is the nearest neighbor function.

The following code computes the Hausdorff distance between two point clouds:

import point_cloud_utils as pcu

# p1 is an (n, 3)-shaped numpy array containing one point per row

# p2 is an (m, 3)-shaped numpy array containing one point per row

# Compute the chamfer distance between p1 and p2
hd = pcu.hausdorff_distance(p1, p2)


### One sided Hausdorff distance

In some applications, one only needs the one-sided Hausdorff distance between $$P_1$$ and $$P_2$$, i.e.

$\text{hausdorff}_{P_1 \rightarrow P_2}(P_1, P_2) = \max_{x \in P_1} \|x - \text{NN}(x, P_2)\|$

The following code computes the one-sided Hausdorff distance between two point clouds:

import point_cloud_utils as pcu

# p1 is an (n, 3)-shaped numpy array containing one point per row

# p2 is an (m, 3)-shaped numpy array containing one point per row

# Compute the chamfer distance between p1 and p2
hd_p1_to_p2 = pcu.one_sided_hausdorff_distance(p1, p2)


Note

To get the $$P_2 \rightarrow P_1$$ Hausdorff distance, just swap the arguments to pcu.one_sided_hausdorff_distance

## Earth-Mover's (Sinkhorn) distance

The Earth Mover's distance between two point clouds $$P = \{p_i \in \mathbb{R}^3\}_{i=1}^n$$ and $$Q = \{q_j \in \mathbb{R}^3\}_{j=1}^m$$ is computed as the average distance between pairs of points according to an optimal correspondence $$\pi \in \Pi(P, Q)$$, where $$\Pi(P, Q)$$ is the set of $$n \times m$$ matrices where the rows and columns sum to one. The assignment $$\pi$$ is thus a matrix where $$\Pi_{i,j}$$ is a number between $$0$$ and $$1$$ denoting how much point $$p_i$$ and $$q_j$$ correspond. We can write the EMD formally as: $$\text{EMD}(P, Q) = \min_{\pi \in \Pi(P, Q)} \sum_{i = 1}^n \sum_{j = 1}^m \pi_{i,j} |p_i - q_j| % \langle \pi, D \rangle \qquad D_{ij} = |p_i - q_j|$$

Point Cloud Utils implements the sinkhorn algorithm for computing the (approximate) Earth Mover's Distance. To compute the EMD, run:

import point_cloud_utils as pcu

# p1 is an (n, 3)-shaped numpy array containing one point per row