Hausdorff distance
Encyclopedia
In mathematics
, the Hausdorff distance, or Hausdorff metric, also called Pompeiu
–Hausdorff distance, measures how far two subset
s of a metric space
are from each other. It turns the set of non-empty compact
subsets of a metric space into a metric space in its own right. It is named after Felix Hausdorff
.
Informally, two sets are close in the Hausdorff distance if every point of either set is close to some point of the other set. The Hausdorff distance is the longest distance you can be forced to travel by an adversary who chooses a point in one of the two sets, from where you then must travel to the other set. In other words, it is the farthest point of a set that you can be to the closest point of a different set.
It seems that this distance was first introduced by Hausdorff in his book "Grundzüge der Mengenlehre
" the first edition published in 1914.
Let X and Y be two non-empty subsets of a metric space (M, d). We define their Hausdorff distance by
where sup represents the supremum
and inf the infimum
.
Equivalently
,
where
,
that is, the set of all points within
of the set 
(sometimes called the 
-fattening of 
or a generalized ball of radius 
around 
).
, then
.
For instance, consider the metric space of the real numbers
with the usual metric 
induced by the absolute value,
.
Take
.
Then
. However 
because 
, but 
.
, then dH(X,Y) is guaranteed to be finite.
We have dH(X,Y) = 0 if and only if X and Y have the same closure
.
On the set of all non-empty subsets of M, dH yields an extended pseudometric
.
On the set F(M) of all non-empty compact subsets of M, dH is a metric. If M is complete, then so is F(M). 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 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 particularly when generating level of detail
for efficient display of complex 3D models.
); then DH(X,Y) is the infimum of dH(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 dH(I(M),J(N)) along all isometric embeddings I:M→L and J:N→L into some common metric space L.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the Hausdorff distance, or Hausdorff metric, also called Pompeiu
Dimitrie Pompeiu
-Biography:After studying in Dorohoi and Bucharest, he went to France, where he studied mathematics at the University of Paris . He obtained a Ph.D. degree in mathematics in 1905 with a thesis, On the continuity of complex variable functions, written under the direction of Henri Poincaré...
–Hausdorff distance, measures how far two subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
s of a metric space
Metric space
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
are from each other. It turns the set of non-empty compact
Compact space
In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...
subsets of a metric space into a metric space in its own right. It is named after Felix Hausdorff
Felix Hausdorff
Felix Hausdorff was a Jewish German mathematician who is considered to be one of the founders of modern topology and who contributed significantly to set theory, descriptive set theory, measure theory, function theory, and functional analysis.-Life:Hausdorff studied at the University of Leipzig,...
.
Informally, two sets are close in the Hausdorff distance if every point of either set is close to some point of the other set. The Hausdorff distance is the longest distance you can be forced to travel by an adversary who chooses a point in one of the two sets, from where you then must travel to the other set. In other words, it is the farthest point of a set that you can be to the closest point of a different set.
It seems that this distance was first introduced by Hausdorff in his book "Grundzüge der Mengenlehre
Grundzüge der Mengenlehre
Grundzüge der Mengenlehre is an influential book on set theory written by Felix Hausdorff.First published in April 1914, Grundzüge der Mengenlehre was the first comprehensive introduction to set theory...
" the first edition published in 1914.
Definition
where sup represents the supremum
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
and inf the infimum
Infimum
In mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
.
Equivalently
,where
,that is, the set of all points within
of the set (sometimes called the -fattening of or a generalized ball of radius around ).Remark
It is not true in general that if, then .For instance, consider the metric space of the real numbers
with the usual metric induced by the absolute value, .Take
.Then
. However because , but .Properties
In general, dH(X,Y) may be infinite. If both X and Y are boundedBounded set
In mathematical analysis and related areas of mathematics, a set is called bounded, if it is, in a certain sense, of finite size. Conversely, a set which is not bounded is called unbounded...
, then dH(X,Y) is guaranteed to be finite.
We have dH(X,Y) = 0 if and only if X and Y have the same closure
Closure (topology)
In mathematics, the closure of a subset S in a topological space consists of all points in S plus the limit points of S. Intuitively, these are all the points that are "near" S. A point which is in the closure of S is a point of closure of S...
.
On the set of all non-empty subsets of M, dH yields an extended pseudometric
Pseudometric space
In mathematics, a pseudometric space is a generalized metric space in which the distance between two distinct points can be zero. In the same way as every normed space is a metric space, every seminormed space is a pseudometric space...
.
On the set F(M) of all non-empty compact subsets of M, dH is a metric. If M is complete, then so is F(M). If M is compact, then so is F(M).
The topology
Topological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
of F(M) depends only on the topology of M, not on the metric d.
Motivation
The definition of the Hausdorff distance can be derived by a series of natural extensions of the distance function d(x, y) in the underlying metric space M, as follows:- Define a distance function between any point x of M and any non-empty set Y of M by:
-
.
- For example, d(1, [3,6]) = 2 and d(7, [3,6]) = 1.
- Define a distance function between any two non-empty sets X and Y of M by:
-
.
- For example, d([1,7], [3,6]) = d(1, [3,6]) = 2.
- If X and Y are compact then d(X,Y) will be finite; d(X,X)=0; and d inherits the triangle inequalityTriangle inequalityIn mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side ....
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 does not imply that (It does imply that
). For example, , but . However, we can create a metric by defining the Hausdorff distance to be:
Applications
In computer visionComputer vision
Computer vision is a field that includes methods for acquiring, processing, analysing, and understanding images and, in general, high-dimensional data from the real world in order to produce numerical or symbolic information, e.g., in the forms of decisions...
, 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
Edge detection
Edge detection is a fundamental tool in image processing and computer vision, particularly in the areas of feature detection and feature extraction, which aim at identifying points in a digital image at which the image brightness changes sharply or, more formally, has discontinuities...
giving a binary image
Binary image
A binary image is a digital image that has only two possible values for each pixel. Typically the two colors used for a binary image are black and white though any two colors can be used. The color used for the object in the image is the foreground color while the rest of the image is the...
. 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
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
the Hausdorff distance is used to measure the difference between two different representations of the same 3D object particularly when generating level of detail
Level of detail
In computer graphics, accounting for level of detail involves decreasing the complexity of a 3D object representation as it moves away from the viewer or according other metrics such as object importance, eye-space speed or position....
for efficient display of complex 3D models.
Related concepts
A measure for the dissimilarity of two shapes is given by Hausdorff distance up to isometry, denoted DH. Namely, let X and Y be two compact figures in a metric space M (usually a Euclidean spaceEuclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
); then DH(X,Y) is the infimum of dH(I(X),Y) along all isometries
Isometry
In mathematics, an isometry is a distance-preserving map between metric spaces. Geometric figures which can be related by an isometry are called congruent.Isometries are often used in constructions where one space is embedded in another space...
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 dH(I(M),J(N)) along all isometric embeddings I:M→L and J:N→L into some common metric space L.
External links
- http://planetmath.org/encyclopedia/HausdorffMetric.html
- Completeness and Total Boundedness of the Hausdorff Metric (pdf)
- http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html
- 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 MeshLabMeshLabMeshLab, is a free 3D mesh processing software program; MeshLab, started in late 2005, is an open-source general-purpose system aimed to help the processing of the typical not-so-small unstructured 3D models that arise in the pipeline of processing of the data coming from 3D scanning...
. - MATLAB code for Hausdorff distance: http://www.mathworks.com/matlabcentral/fileexchange/27905-hausdorff-distance