Skip to content

Hausdorff divergence

The Hausdorff divergence measures how far each point of one cloud is from the other cloud, in both directions. At small blur it is the symmetric nearest-neighbour distance used by ICP (iterative closest point) registration; at large blur it becomes a kernel distance. It does not try to match masses: it only cares about supports, which makes it robust to uneven sampling.

Definition

remblais implements the divergence of Feydy et al. (AISTATS 2019). With ε = blurᵖ and the softmin

softmin_ε(μ)(z) = −ε log Σ_w μ(w) exp(−C(z, w) / ε),

let a = softmin_ε(α) and b = softmin_ε(β). Then

H_ε(α, β) = ½ ⟨α, b − a⟩ + ½ ⟨β, a − b⟩.

As the blur goes to 0, H_ε tends to ½ ⟨α, d(·, supp β)⟩ + ½ ⟨β, d(·, supp α)⟩, where d(z, S) is the cost from z to the nearest point of S: the symmetric ICP cost.

Usage

import torch
from remblais import SamplesLoss

device = "cuda"

x = torch.rand(2_000, 2, device=device)
y = torch.rand(1_000, 2, device=device) + 0.1

hausdorff = SamplesLoss("hausdorff", p=2, blur=0.01)
print(hausdorff(x, y))

The gradient is exact (no iterations, no extrapolation), so it suits registration loops:

x.requires_grad_()
[g] = torch.autograd.grad(hausdorff(x, y), [x])
print(g.shape)

With potentials=True, the loss returns F = b − a on x and G = a − b on y, so that H = ½(⟨α, F⟩ + ⟨β, G⟩).

Difference with GeomLoss

GeomLoss 0.3.1 documents "hausdorff" but routes it to the kernel norms: without a kernel argument, the call raises KeyError. remblais keeps this routing when kernel is given (see custom kernels) and computes the divergence above otherwise.

The multiscale backend has no truncation for this loss: it computes the exact result with the online backend.