- Hausdorff distance
The Hausdorff distance, or Hausdorff metric, measures how far two compact non-empty
subset s of ametric space are from each other. It is named afterFelix Hausdorff .Informally, the Hausdorff distance between two sets of points, is the longest distance an adversary can force you to travel by choosing a point in one of the two sets, from where you then must travel to the other set.
Definitions
Let X and Y be two compact subsets of a metric space M. The Hausdorff distance dH(X,Y) is the minimal number r such that the closed r-neighborhood of any x in X contains at least one point y of Y and vice versa. In other words, if d(x, y) denotes the distance in M, then
: d_{mathrm H}(X,Y) = max{,sup_{x in X} inf_{y in Y} d(x,y),, sup_{y in Y} inf_{x in X} d(x,y),}mbox{,} ! where sup represents the
supremum and inf theinfimum .This distance function turns the set of all non-empty compact subsets of M into a
metric space , say F(M). The topology of F(M) depends only on the topology of M. If M is compact, then so is F(M). If M is complete, then so is F(M).Hausdorff distance can be defined in essentially the same way for non-empty
closed and bounded subsets of M, but taking aninfimum over r instead of a minimum. (In a general metric space, closed and bounded subsets are more general than compact subsets. For instance in the space of continuous real-valued functions on [0,1] metrized with the sup-norm, the closed unit ball is closed and bounded but not compact.) If we allow closed unbounded subsets then the distance may takeinfinite values. When working with non-compact subsets, the topology of F(M) depends on the metric on M and not only on its topology. The Hausdorff distance between general subsets can be defined as the Hausdorff distance between their closures. It gives a pre-metric (or pseudometric) on the set of all subsets of M (the Hausdorff distance between any two sets with the same closure is zero).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 aEuclidean space ); then DH(X,Y) is the infimum of dH(I(X),Y) along allisometri es I of the metric space "M" to itself. This distance measures how far the shapes X and Y are from being isometric.Motivation
The definition of the Hausdorff distance appears complex and arbitrary at first, but it can be derived by a series of natural extensions of the distance function "d"("x", "y") in the underlying metric space "M", as follows: [cite book
last = Barnsley
first = Michael
authorlink = Michael Barnsley
title = Fractals Everywhere
publisher = Morgan Kaufmann
date = 1993
pages = Ch. II.6
isbn = 0120790696]
*Define a distance function between any point "x" of "M" and any non-empty set "Y" of "M" by:::d(x,Y)=inf_{y in Y} d(x,y), .
: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:
::d(X,Y)=sup_{x in X} d(x,Y), .
: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 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 nowrap|1="d"("X","Y") = 0 does not imply that nowrap|1="X" = "Y". For example, nowrap|1="d"( [1,7] , [3,6] ) = 2, but nowrap|1="d"( [3,6] , [1,7] ) = 0. However, we can create a metric by defining the Hausdorff distance to be:::d_{mathrm H}(X,Y) = max{d(X,Y),d(Y,X) } , .
Applications
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. [ [http://www.cs.cornell.edu/vision/hausdorff/hausmatch.html Hausdorff-Based Matching ] ]
See also
*
Gromov-Hausdorff convergence
*Wijsman convergence References
* Munkres, James; "Topology", Prentice Hall; 2nd edition (December 28, 1999). ISBN 0131816292.
External links
* http://planetmath.org/encyclopedia/HausdorffMetric.html
* [http://www-math.mit.edu/phase2/UJM/vol1/HAUSF.PDF Completeness and Total Boundedness of the Hausdorff Metric] (pdf)
* http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html
Wikimedia Foundation. 2010.