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 R^{3}}_{i = 1}^{n}$ and $P_{2} = {x_{j} \in R^{3}}_{j = 1}^{m}$ is defined as the average distance between pairs of nearest neighbors between $P_{1}$ and $P_{2}$ i.e. $chamfer (P_{1}, P_{2}) = \frac{1}{2 n} \sum_{i = 1}^{n} | x_{i} - NN (x_{i}, P_{2}) | + \frac{1}{2 m} \sum_{j = 1}^{n} | x_{j} - NN (x_{j}, P_{1}) |$ and $NN (x, P) = {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
p1 = pcu.load_mesh_v("point_cloud_1.ply")

# p2 is an (m, 3)-shaped numpy array containing one point per row
p2 = pcu.load_mesh_v("point_cloud_2.ply")

# 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 R^{3}}_{i = 1}^{n}$ and $P_{2} = {x_{j} \in 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. $hausdorff (P_{1}, P_{2}) = \frac{1}{2} max_{x \in P_{1}} | x - NN (x, P_{2}) | + \frac{1}{2} max_{x^{'} \in P_{2}} | x^{'} - NN (x^{'}, P_{1}) |$ and $NN (x, P) = {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
p1 = pcu.load_mesh_v("point_cloud_1.ply")

# p2 is an (m, 3)-shaped numpy array containing one point per row
p2 = pcu.load_mesh_v("point_cloud_2.ply")

# 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.

{hausdorff}_{P_{1} \to P_{2}} (P_{1}, P_{2}) = max_{x \in P_{1}} ‖ x - 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
p1 = pcu.load_mesh_v("point_cloud_1.ply")

# p2 is an (m, 3)-shaped numpy array containing one point per row
p2 = pcu.load_mesh_v("point_cloud_2.ply")

# 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} \to 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 R^{3}}_{i = 1}^{n}$ and $Q = {q_{j} \in R^{3}}_{j = 1}^{m}$ is computed as the average distance between pairs of points according to an optimal correspondence $π \in Π (P, Q)$ , where $Π (P, Q)$ is the set of $n \times m$ matrices where the rows and columns sum to one. The assignment $π$ is thus a matrix where $Π_{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: $EMD (P, Q) = min_{π \in Π (P, Q)} \sum_{i = 1}^{n} \sum_{j = 1}^{m} π_{i, j} | 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
p1 = pcu.load_mesh_v("point_cloud_1.ply")

# p2 is an (m, 3)-shaped numpy array containing one point per row
p2 = pcu.load_mesh_v("point_cloud_2.ply")

# Compute the chamfer distance between p1 and p2
emd, pi = pcu.earth_movers_distance(p1, p2)