**Hausdorff Distance Image Comparison**

Given two sets of points and , the Hausdorff distance is defined as

where

The function *h(A,B)* is called the *directed* Hausdorff
`distance' from *A* to *B* (this function is not symmetric and thus is
not a true distance). It identifies the point that is
farthest from any point of *B*, and measures the distance from *a* to
its nearest neighbor in *B*. Thus the Hausdorff distance, *H(A,B)*,
measures the degree of mismatch between two sets, as it reflects the
distance of the point of *A* that is farthest from any point of *B*
and vice versa. Intuitively, if the Hausdorff distance is *d*, then
every point of *A* must be within a distance *d* of some point of *B*
and vice versa. It is well known that the Hausdorff distance is a
metric over the set of all closed, bounded sets - it obeys the
properties of identity, symmetry and triangle inequality.

One way to understand the directed Hausdorff measure is to think of it
in terms of set containment. Let ,
where is a disk of radius and *+* is the
Minkowski sum (for two point sets *P* and *Q*, ). Intuitively, *B'* is the set
obtained by replacing each point of *B* with a disk of radius
, and taking the union of all of these disks. By definition
if and only if , because in
order for every point of *A* to be within distance of *B* it
must be contained in *B'*.

The Hausdorff distance is very sensitive to even a single ``outlying''
point of A or B. For example, consider , where the
point *x* is some large distance *D* from any point of *A*. In this
case *H(A,B)=D* - it is determined solely by the point *x*. Thus
rather than using *H(A,B)* we use a generalization of the Hausdorff
distance (which does not obey the metric properties on *A* and *B*,
but does obey them on *specific subsets* of *A* and *B*). This
generalized Hausdorff measure is given by taking the *k*-th ranked
distance rather than the maximum, or largest ranked one,

where denotes the *k*-th ranked value (or equivalently the
quantile of *m* values). For example, when *k=m* then
is , and thus this measure is the same as .
When *k=m/2* then the median of the *m* individual point distances
determines the overall distance. Therefore this measure generalizes
the directed Hausdorff measure, by replacing the maximum with a
quantile.

In terms of set containment, if and only if there
is some such that , where
contains *k* points of *A*. Thus we can think of as
partitioning *A* into two sets, which is ``close to'' (within
of) *B* and the ``outliers'' . This is in practice an
important aspect of the generalized Hausdorff measure: it separately
accounts for perturbations (by the distance ) and for outliers
(by the rank *k*).

In general, we are interested in using the Hausdorff distance to
identify instances of some ``model'' bitmap *M* in some image bitmap
*I*. The image may contain multiple instances of the model (or no
model), the instances may be transformed in some manner, parts may be
missing, and there may be other portions of the image for which there
is no model. We will limit ourselves here to the case in which the
model simply undergoes translation, but more complex transformations
are possible in this framework. One way to phrase this problem is
that we seek all translations such that . The parameter *k* tells us how many of the model points
should be near image points in order to classify a given translation
as an instance of the model (i.e., we allow *m-k* of the *m* model
points to be outliers). The parameter tells us how close
each non-outlying model point must be to some image point.

There are several techniques for computing the set of all such
translations. The most straightforward method is dilation and correlation.
In order to find each translation such that , we form and then compute the
correlation of *M* with *I'*. For each translation *t* of *M*
with respect to *I'*, the correlation determines *p*, how many
points of *M + t* are superimposed with *I'* (the logical
**and** of *M+ t* and *I'*). Any translation where is a translation where an instance was found, i.e. for which
. We refer to *p/m* as the Hausdorff
fraction for a given translation *t* (at some fixed ), and to
*k/m* as the *threshold* fraction, as this normalizes the
quantities by the number of model points. Intuitively, the Hausdorff
fraction measures the percentage of *M + t* that lies near
(within of) points of *I*.

The computation of alone does not
necessarily find very good instances of *M* in *I*, rather it finds
portions of *I* that could contain *M* plus some other points. For
instance, a totally filled in image will match any model at any
translation. Thus we often use the other direction of the generalized
Hausdorff measure, , to ``verify'' those
translations where it was found that .
Rather than using the entire image, *I*, however, we use just the
portion of the image that is covered by the translated model *M+
t* (e.g., if *M* is represented as a bitmap, then the portion of the
image that is within the extent of that bitmap). This verification,
or reverse Hausdorff fraction, ensures that a given portion of the
points in the image (covered by the model array) are actually near
points of *M+ t*. It thereby rules out situations such as a
totally filled in image matching any model.

Copyright 1994 Cornell University