The Hausdorff Distance

The basis of our methodology is the median Hausdorff distance which is a similarity measure between two arbitrary point sets. The classical Hausdorff distance between two (finite) sets of points, $A$ and $B$, is defined as

$$h(A,B) = \max_{a\in A}\min_{b\in B} \Vert a-b\Vert$$ (1)

Here, $h(A,B)$, the directed distance from $A$ to $B$, will be small when every point of $A$ is near some point of $B$. This distance is too fragile for practical tasks: for example, a single point in $A$ that is far from anything in $B$ will cause $h(A,B)$ to be large. A natural way to take care of this problem is to replace equation 1 with

$$h^f(A,B) = f^{th}_{a\in A}\min_{b\in B} \Vert a-b\Vert ,$$ (2)

where $f^{th}_{x\in X}g(x)$ denotes the $f$-th quantile value of $g(x)$over the set $X$, for some value of $f$ between zero and one. When $f=0.5$ we get the modified median Hausdorff distance which we use in our method.

Let $B$ be a point set representing the reference shape, $A$ the measured point set. As already mentioned, we assume that $B$ is complete, dense and precise, while $A$ may be incomplete, sparse and noisy. $B$ is obtained either analytically, or as the result of a careful, high-resolution, off-line measurement.