Hausdorff distance

Components of the calculation of the Hausdorff distance between the green curve X and the blue curve Y.

Let ${\displaystyle (M,d)}$ be a metric space. For each pair of non-empty subsets ${\displaystyle X\subset M}$ and ${\displaystyle Y\subset M}$, the Hausdorff distance between ${\displaystyle X}$ and ${\displaystyle Y}$ is defined as

$${\displaystyle d_{\mathrm {H} }(X,Y):=\max \left\{\,\sup _{x\in X}d(x,Y),\ \sup _{y\in Y}d(X,y)\,\right\},}$$

where ${\displaystyle \operatorname {sup} }$ represents the supremum operator, ${\displaystyle \operatorname {inf} }$ the infimum operator, and where ${\displaystyle d(a,B):=\inf _{b\in B}d(a,b)}$ quantifies the distance from a point ${\displaystyle a\in X}$ to the subset ${\displaystyle B\subseteq X}$.

An equivalent definition is as follows.[3] For each set ${\displaystyle X\subset M,}$ let

$${\displaystyle X_{\varepsilon }:=\bigcup _{x\in X}\{z\in M\mid d(z,x)\leq \varepsilon \},}$$

which is the set of all points within ${\displaystyle \varepsilon }$ of the set ${\displaystyle X}$ (sometimes called the ${\displaystyle \varepsilon }$-fattening of ${\displaystyle X}$ or a generalized ball of radius ${\displaystyle \varepsilon }$ around ${\displaystyle X}$). Then, the Hausedorff distance between ${\displaystyle X}$ and ${\displaystyle Y}$ is defined as

$${\displaystyle d_{H}(X,Y):=\inf\{\varepsilon \geq 0\mid X\subseteq Y_{\varepsilon }{\text{ and }}Y\subseteq X_{\varepsilon }\}.}$$

Equivalently,[1]

$${\displaystyle {\begin{aligned}d_{H}(X,Y)&=\sup _{w\in M}\left|\inf _{x\in X}d(w,x)-\inf _{y\in Y}d(w,y)\right|\\&=\sup _{w\in X\cup Y}\left|\inf _{x\in X}d(w,x)-\inf _{y\in Y}d(w,y)\right|\\&=\sup _{w\in M}|d(w,X)-d(w,Y)|,\end{aligned}}}$$

where ${\displaystyle d(w,X):=\inf _{x\in X}d(w,x)}$ is the smallest distance from the point ${\displaystyle w}$ to the set ${\displaystyle X}$.

• In general, ${\displaystyle d_{\mathrm {H} }(X,Y)}$ may be infinite. If both X and Y are bounded, then ${\displaystyle d_{\mathrm {H} }(X,Y)}$ is guaranteed to be finite.
• ${\displaystyle d_{\mathrm {H} }(X,Y)=0}$ if and only if X and Y have the same closure.
• For every point x of M and any non-empty sets Y, Z of M: d(x,Y) ≤ d(x,Z) + d_H(Y,Z), where d(x,Y) is the distance between the point x and the closest point in the set Y.
• |diameter(Y)-diameter(X)| ≤ 2 d_H(X,Y).[4]
• If the intersection X ∩ Y has a non-empty interior, then there exists a constant r > 0, such that every set X′ whose Hausdorff distance from X is less than r also intersects Y.[5]
• On the set of all subsets of M, d_H yields an extended pseudometric.
• On the set F(M) of all non-empty compact subsets of M, d_H is a metric.
  • If M is complete, then so is F(M).[6]
  • If M is compact, then so is F(M).
  • The topology of F(M) depends only on the topology of M, not on the metric d.

The definition of the Hausdorff distance can be derived by a series of natural extensions of the distance function ${\displaystyle d(x,y)}$ in the underlying metric space M, as follows:[7]

• Define a distance function between any point x of M and any non-empty set Y of M by:

${\displaystyle d(x,Y)=\inf\{d(x,y)\mid y\in Y\}.\ }$

For example, d(1, {3,6}) = 2 and d(7, {3,6}) = 1.

• Define a (not-necessarily-symmetric) "distance" function between any two non-empty sets X and Y of M by:

${\displaystyle d(X,Y)=\sup\{d(x,Y)\mid x\in X\}.\ }$

For example, ${\textstyle d(\{1,7\},\{3,6\})=\sup\{d(1,\{3,6\}),d(7,\{3,6\})\}=\sup\{d(1,3),d(7,6)\}=2.}$

• If X and Y are compact then d(X,Y) will be finite; d(X,X)=0; and d inherits the triangle inequality property from the distance function in M. As it stands, d(X,Y) is not a metric because d(X,Y) is not always symmetric, and d(X,Y) = 0 does not imply that X = Y (It does imply that ${\displaystyle X\subseteq Y}$). For example, d({1,3,6,7}, {3,6}) = 2, but d({3,6}, {1,3,6,7}) = 0. However, we can create a metric by defining the Hausdorff distance to be:

${\displaystyle d_{\mathrm {H} }(X,Y)=\max\{d(X,Y),d(Y,X)\}\,.}$

In computer vision, the Hausdorff distance can be used to find a given template in an arbitrary target image. The template and image are often pre-processed via an edge detector giving a binary image. Next, each 1 (activated) point in the binary image of the template is treated as a point in a set, the "shape" of the template. Similarly, an area of the binary target image is treated as a set of points. The algorithm then tries to minimize the Hausdorff distance between the template and some area of the target image. The area in the target image with the minimal Hausdorff distance to the template, can be considered the best candidate for locating the template in the target. In computer graphics the Hausdorff distance is used to measure the difference between two different representations of the same 3D object[8] particularly when generating level of detail for efficient display of complex 3D models.

If ${\displaystyle X}$ is the surface of earth, and ${\displaystyle Y}$ is the land-surface of earth, then by finding the point Nemo, we see ${\displaystyle d_{H}(X,Y)}$ is around 2,704.8 km.

Oceanic pole of inaccessibility at 49.0273°S 123.4345°W / -49.0273; -123.4345 (Oceanic Pole of Inaccessibility)

A measure for the dissimilarity of two shapes is given by Hausdorff distance up to isometry, denoted D_H. Namely, let X and Y be two compact figures in a metric space M (usually a Euclidean space); then D_H(X,Y) is the infimum of d_H(I(X),Y) along all isometries I of the metric space M to itself. This distance measures how far the shapes X and Y are from being isometric.

The Gromov–Hausdorff convergence is a related idea: we measure the distance of two metric spaces M and N by taking the infimum of ${\displaystyle d_{\mathrm {H} }(I(M),J(N))}$ along all isometric embeddings ${\displaystyle I\colon M\to L}$ and ${\displaystyle J\colon N\to L}$ into some common metric space L.

• Wijsman convergence
• Kuratowski convergence
• Hemicontinuity
• Fréchet distance

• Hausdorff distance between convex polygons.
• Using MeshLab to measure difference between two surfaces A short tutorial on how to compute and visualize the Hausdorff distance between two triangulated 3D surfaces using the open source tool MeshLab.
• MATLAB code for Hausdorff distance: