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