Comparing Images Using the Hausdorff Distance.
The Hausdorff distance measures the extent to which each point of a model set lies near some point of an image set and vice versa. Thus, this distance can be used to determine the degree of resemblance between two objects that are superimposed on one another. Efficient algorithms for computing the Hausdorff distance between all possible relative positions of a binary image and a model are presented. The focus is primarily on the case in which the model is only allowed to translate with respect to the image. The techniques are extended to rigid motion. The Hausdorff distance computation differs from many other shape comparison methods in that no correspondence between the model and the image is derived. The method is quite tolerant of small position errors such as those that occur with edge detectors and other feature extraction methods. It is shown that the method extends naturally to the problem of comparing a portion of a model against an image.
Introduction
A central problem in pattern recognition and computer vision is determining the extent
to which one shape differs from another. Pattern recognition operations such as correlation
and template matching (cf. [17]) and model-based vision methods (cf. [4, 8, 11])
can all be viewed as techniques for determining the difference between shapes. We have
recently been investigating functions for determining the degree to which two shapes
differ from one another. The goal of these investigations has been to develop shape
comparison methods that are efficient to compute, produce intuitively reasonable re-
sults, and have a firm underlying theoretical basis. In order to meet these goals, we
argue that it is important for shape comparison functions to obey metric properties (see
[3] for related arguments).
In this paper we present algorithms for efficiently computing the Hausdorff distance
between all possible relative positions of a model and an image. (The Hausdorff distance
is a max-min distance defined below.) We primarily focus on the case in which
the model and image are allowed to translate with respect to one another, and then
briefly consider extensions to handle the more general case of rigid motion. There are
theoretical algorithms for efficiently computing the Hausdorff distance as a function of
translation [12, 14] and rigid motion [13]. Here we provide provably good approximation
algorithms that are highly efficient both in theory and in practice. These methods
operate on binary rasters, making them particularly well suited to image processing and
machine vision applications, where the data are generally in raster form. The three key
advantages of the approach are: (i) relative insensitivity to small perturbations of the
image, (ii) simplicity and speed of computation, and (iii) naturally allowing for portions
of one shape to be compared with another.
We discuss three different methods of computing the Hausdorff distance as a function
of the translation of a model with respect to an image. The first of these methods is
similar in many ways to binary correlation and convolution, except that the Hausdorff
distance is a nonlinear operator. The second method extends the definition of the
distance function to enable the comparison of portions of a model to portions of an
image. The third method improves on the first two, by using certain properties of the
Hausdorff distance to rule out many possible relative positions of the model and the
image without having to explicitly consider them. This speeds up the computation by
several orders of magnitude. All three of these methods can be further sped up using
special-purpose graphics hardware (in particular a z-buffer). We present a number of
examples using real images. These examples illustrate the application of the method
to scenes in which a portion of the object to be identified is hidden from view. Then
finally we show how the methods can be adapted to comparing objects under rigid
motion (translation and rotation).
1.1 The Hausdorff Distance
Given two finite point sets g, the Hausdorff distance
is defined as
where
min b2B
and k \Delta k is some underlying norm on the points of A and B (e.g., the L 2 or Euclidean
norm).
The function h(A; B) is called the directed Hausdorff distance from A to B. It
identifies the point a 2 A that is farthest from any point of B, and measures the
distance from a to its nearest neighbor in B (using the given norm k \Delta k). That is,
h(A; B) in effect ranks each point of A based on its distance to the nearest point of
B, and then uses the largest ranked such point as the distance (the most mismatched
point of A). Intuitively, if h(A; d, then each point of A must be within distance
d of some point of B, and there also is some point of A that is exactly distance d from
the nearest point of B (the most mismatched point).
The Hausdorff distance, H(A;B), is the maximum of h(A; B) and h(B; A). Thus
it measures the degree of mismatch between two sets, by measuring 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. Thus the notion of resemblance encoded by this distance is that
each member of A be near some member of B and vice versa. Unlike most methods
of comparing shapes, there is no explicit pairing of points of A with points of B (for
example many points of A may be close to the same point of B). The function H(A;B)
can be trivially computed in time O(pq) for two point sets of size p and q respectively,
and this can be improved to O((p
It is well known that the Hausdorff distance, H(A;B), is a metric over the set of all
closed, bounded sets (cf., [9]). Here we restrict ourselves to finite point sets, because
that is all that is necessary for raster sensing devices. It should be noted that the
Hausdorff distance does not allow for comparing portions of the sets A and B, because
every point of one set is required to be near some point of the other set. There is,
however, a natural extension to the problem of measuring the distance between some
subset of the points in A and some subset of the points in B, which we present in
Section 3.
The Hausdorff distance measures the mismatch between two sets that are at fixed
positions with respect to one another. In this paper we are primarily interested in
measuring the mismatch between all possible relative positions of two sets, as given by
the value of the Hausdorff distance as a function of relative position. That is, for any
group G, we define the minimum Hausdorff distance to be
If the group G is such that, for any g 2 G and for any points x 1
then we need only consider transforming one of the sets:
This property holds when G is the group of translations and k \Delta k is any norm, and also
when G is the group of rigid motions and k \Delta k is the Euclidean norm.
In the cases we consider here (translations and rigid motions), the minimum Hausdorff
distance obeys metric properties (as was shown in [12] and [13]). That is, the function
is everywhere positive, and has the properties of identity, symmetry and triangle
inequality. These properties correspond to our intuitive notions of shape resemblance,
namely that a shape is identical only to itself, the order of comparison of two shapes
does not matter 1 and two shapes that are highly dissimilar cannot both be similar to
some third shape. This final property, the triangle inequality, is particularly important
in pattern matching applications where several stored model shapes are compared
to an unknown shape. Most shape comparison functions used in such applications do
not obey the triangle inequality, and thus can report that two highly dissimilar model
shapes are both similar to the unknown shape. This behavior is highly counter-intuitive
(for example, reporting that some unknown shape closely resembles both an 'elephant'
and a 'hatrack' is not desirable, because these two shapes are highly dissimilar).
1 Actually the order of comparison does matter in some psychophysical studies. One interesting
property of the Hausdorff distance in this regard is the fact that the directed distance h(A; B) is not
symmetric.

Figure

1: Two sets of points illustrating the distances H(A;B) and M T (A; B).
We focus primarily on the case where the relative positions of the model with respect
to the image is the group of translations. Without loss of generality we fix the set A
and allow only B to translate. The minimum value of the Hausdorff distance under
translation is then defined as,
where H is the Hausdorff distance as defined in equation (1), and \Phi is the standard
Minkowski sum notation (i.e., B \Phi Bg). For example, Figure 1 shows two
sets of points, where the set A is illustrated by dots and the set B by crosses. H(A;B)
is large because there are points of A that are not near any points of B and vice versa.
however, because there is a translation of B that makes each point
of A nearly coincident with some point of B and vice versa. We generally refer to the
set A as the 'image' and the set B as the `model', because it is most natural to view
the model as translating with respect to the image.
We now turn to the problem of efficiently computing H(A;B) and M T (A; B). The
organization of the remainder of the paper is as follows. We first discuss how to compute
H(A;B) for finite sets of points in the plane. The basic idea is to define a set of functions
measuring the distance from each point of A to the closest point of B (and vice versa),
as a function of the translation t of the set B. In section 3 we show how to extend
the method to the problem of comparing portions of the sets A and B (e.g., as occurs
when instances are partly occluded). Then in section 4 we discuss an implementation
of the Hausdorff distance computation for raster data, where the sets A and B are
represented in terms of binary rasters. This implementation is in many ways similar
to binary correlation. In section 5 we show how to improve the basic implementation,
by ruling out many possible translations of B without explicitly considering them. We
then present some examples, and contrast the method with binary correlation. Finally,
we consider the case of rigid motion (translation and rotation), and present an example
for this problem.
Computing H(A;B) and M T (A; B)
From the definition of the Hausdorff distance in equations (1) and (2), we have
min b2B
min a2A
If we define
a2A
That is, H(A;B) can be obtained by computing d(a) and d 0 (b) for all a 2 A and
respectively. The graph of d(x), f(x; g, is a surface that has been
called the Voronoi surface of B [14]. This surface gives for each location x the distance
from x to the nearest point b 2 B. For points in the plane one can visualize this surface
as a sort of 'egg carton', with a local minimum of height zero corresponding to each
and with a 'cone-shape' rising up from each such minimum. The locations at
which these cone-shapes intersect define the local maxima of the surface. Thus note
that the local maxima are equidistant from two or more local minima (hence the name
Voronoi surface, by analogy to Voronoi diagrams that specify the locations equidistant
from two or more points of a given set [16]). The graph of d 0 (x) has a similar shape,
with a 'cone-shape' rising up from each point of A.
A Voronoi surface, d(x), of a set B has also been referred to as a distance transform
(e.g., [10]), because it gives the distance from any point x to the nearest point in a
set of source points, B. Figure 2 illustrates a set of points and a top-down view of a
corresponding Voronoi surface, where brighter (whiter) portions of the image correspond
to higher portions of the surface. The norm used in the figure is L 2 .
We now turn to calculating the Hausdorff distance as a function of translation,
min b2B
min a2A
min b2B
min a2A

Figure

2: A set of points and a corresponding Voronoi surface.
That is, H(A;B \Phi t) is simply the maximum of translated copies of the Voronoi surfaces
d(x) and d 0 (x) (of the sets B and A respectively). Now define f A
the upper envelope (pointwise maximum) of p copies of the function d(\Gammat), which have
been translated relative to each other by each a 2 A. This gives for each translation
t the distance of the point of A that is farthest from any point of B \Phi t. That is,
f A \Delta) is the directed Hausdorff distance given in equation (2).
The directed Hausdorff distance f B defined analogously. Now
H(A;B \Phi t) is simply the maximum of the two directed distance functions. Thus, we
define
a2A
where H(\Delta; \Delta) is the Hausdorff distance as defined in (1). That is, the function f(t) specifies
the Hausdorff distance between two sets A and B as a function of the translation
t of the set B. Efficient theoretical algorithms for computing f(t) were developed in
[14]. There it was shown that if A and B contain respectively p and q points in the
plane, then the function f(t) can be computed in time O(pq(p
the L 1 , L 2 or L1 norm. This running time can be improved to O(pq log pq) when using
the L 1 or L1 norms [7]. These methods are quite complicated to implement, and are
substantially less efficient in practice than the rasterized approximation methods that
we investigate in sections 4 and 5.
Comparing Portions of Shapes
In many machine vision and pattern recognition applications it is important to be able
to identify instances of a model that are only partly visible (either due to occlusion or
to failure of the sensing device to detect the entire object). Thus we wish to extend
the definition of the Hausdorff distance to allow for the comparison of portions of two
shapes. This will allow both for scenes that contain multiple objects, and for objects
that are partially hidden from view.
3.1 Partial distances based on ranking
The Hausdorff distance can naturally be extended to the problem of finding the best
partial distance between a model set B and an image set A. For simplicity we first
consider just the directed Hausdorff distance from B to A, h(B; A). The computation
of h(B; simply determines the distance of the point of the model B that is farthest
from any point of the image A. That is, each point of B is ranked by the distance to
the nearest point of A, and the largest ranked point (the one farthest from any point
of determines the distance.
Thus a natural definition of 'distance' for K of the q model points (1 - K - q) is
given by taking the K-th ranked point of B (rather than the largest ranked one),
th
min a2A
where K th
b2B denotes the K-th ranked value in the set of distances (one corresponding
to each element of B). That is, for each point of B the distance to the closest point of
A is computed, and then the points of B are ranked by their respective values of this
distance. The K-th ranked such value, d, tells us that K of the model points B are each
within a distance d of some image point (and when all the points are considered,
and the value is simply the directed Hausdorff distance h(B; A)). This definition of
the distance has the nice property that it automatically selects the K 'best matching'
points of B, because it identifies the subset of the model of size K that minimizes the
directed Hausdorff distance.
In general, in order to compute the partial directed 'distance' hK (B; A), we specify
some fraction 0 - f 1 - 1 of the points of B that are to be considered. Each of the q
points of B is ranked by the distance to the nearest point of A. The K-th ranked such
value, given by equation (4), then gives the partial 'distance', where
K-th ranked value can be computed in O(q) time using standard methods such as those
in [1]. In practice, it takes about twice as long as computing the maximum.
This partial distance measures the difference between a portion of the model and the
image: the K points of the model set which are closest to points of the image set. One
key property of this method is that it does not require one to pre-specify which part of
the model is to be compared with the image. This is because the computation of the
directed Hausdorff distance determines how far each model point is from the nearest
image point, and thus automatically selects the K points of the model that are closest
to image points. In Section 6 we illustrate this partial matching capability, and contrast
it with correlation. We find that the directed partial Hausdorff 'distance' works well
for partial matches on images where correlation does not.
The partial bidirectional Hausdorff 'distance' is now naturally defined as
This function clearly does not obey metric properties, however it does obey weaker
conditions that provide for intuitively reasonable behavior. These conditions are, in
effect, that metric properties are obeyed between given subsets of A and B (of size L
and K respectively). In order to specify these properties more precisely, we need to
understand something about the subsets of A and B that achieve the minimum partial
'distance':
there exist sets A L ' A and BK ' B such that
d. Each of A L and BK will have exactly min(K; L) elements.
There are also "large" subsets of A and B which achieve the distance d:
there exist sets A 0
For proofs of these claims, see Appendices A and B.
It follows immediately that the identity and symmetry properties hold with respect
to A 0
K , because H(\Delta; \Delta) obeys these properties. Intuitively, this means that for
the partial 'distance' with some given K;L, the order of comparison does not matter,
and the distance is zero exactly when the two minimizing subsets A 0
K are the
same.
For the triangle inequality the minimizing subsets may be different when comparing
A with B than when comparing B with C. Thus in general the triangle inequality can
be violated. In the restricted case that the same subset B 0
is the minimizer of
HLK (A; B) and HKM (B; C) then by definition
Intuitively, this means that if two sets are compared with the same portion of a third
set (denoted B 0
K above) then the triangle inequality holds. For practical purposes this
is a reasonable definition: if two models both match the same part of a given image
then we expect the models to be similar to one another. On the other hand if they
match different parts of an image then we have no such expectation.
4 The Minimum Hausdorff Distance for Grid Points
We now turn to the case in which the point sets lie on an integer grid. This is appropriate
for many computer vision and pattern recognition applications, because the data are
derived from a raster device such as a digitized video signal. Assume we are given two
sets of points such that each point a 2 A and
coordinates. We will denote the Cartesian coordinates of a point
a 2 A by (a x ; a y ), and analogously (b x B. The characteristic function of
the set A can be represented using a binary array A[k; l] where the k; l-th entry in the
array is nonzero exactly when the point (k; l) 2 A (as is standard practice). The set B
has an analogously defined array representation B[k; l].
As in the continuous case in the previous section, we wish to compute the Hausdorff
distance as a function of translation by taking the pointwise maximum of a set of
Voronoi surfaces. In this case, however, the point sets from which these surfaces are
derived are represented as arrays, where the nonzero elements of the arrays correspond
to the elements of the sets.
For the two sets A and B, we compute the rasterized approximations to their respective
Voronoi surfaces d 0 (x) and d(x). These distance arrays, or distance transforms,
specify for each pixel location (x; y) the distance to the nearest nonzero pixel of A or B
respectively. We use the notation D 0 [x; y] to denote the distance transform of A[k; l],
and D[x; y] to denote the distance transform of B[k; l]. That is, the array D 0 [x; y] is
zero wherever A[k; l] is one, and the other locations of D 0 [x; y] specify the distance to
the nearest nonzero point of A[k; l]. There are a number of methods for computing the
rasterized Voronoi surface, or distance transform (e.g., [5, 15]), which we discuss briefly
below.
Proceeding with the analogy to the continuous case, we can compute the pointwise
maximum of all the translated D and D 0 arrays to determine the Hausdorff distance as
a function of translation (only now we are limited by the rasterization accuracy of the
integer grid):
In order for F [x; y] to be small at some translation must be that the distance
transform D[x; y] is small at all the locations A \Psi is small at all
the locations B \Phi In other words, every point (nonzero pixel) of the translated
model array B[k+x must be near some point (nonzero pixel) of the image array
A[k; l], and vice versa.
When the input points have integer coordinates, it is straightforward to show that
the minimum value of F [x; y] is very close to the minimum value of the exact function
f(t). In other words, the rasterization only introduces a small error compared to the
true distance function. Specifically,
a translation which minimizes F [x; y]. (There may be
more than one translation with the same, minimum, F value). Let t
translation which minimizes f(t 1 ), the exact measure. Then F [x differs from f(t 1 )
by at most 1, when the norm used, k \Delta k, is any L p norm.
For a proof of this claim see Appendix C. Note also that when
translation with integer coordinates x and y, then F [x; the rasterized function
is simply a sampling of the exact function.
Thus the minimum value of the rasterized approximation, F [x; y], specifies the minimum
Hausdorff distance under translation to an accuracy of one unit of quantization.
However, it should be noted that the translation minimizing F [x; y] is not necessarily
close to the translation t which actually minimizes f(t). To see an example of this, let
k be any odd number, and let A be the set f(0; 0); (k; be the set
0)g. Then the translation t which minimizes f(t) (in the exact case) is
In the rasterized case, however, M T (A;
with three translations which generate this minimum value: ((k +1)=2; 0),
0). Thus there there may be minimizing translations in the rasterized
case that are arbitrarily far away from the minimizing translation in the exact case.
This is not a problem, however, since the value of H(A;B \Phi t) for each of these translations
is the same (and the value at each translation must be within 1:0 of the exact
minimizing value). In other words all three of these matches have the same cost in
both the exact and rasterized cases, and this cost is nearly the exact minimum cost. In
practice we generally enumerate all minimizing translations.
The function f(t) and its rasterized approximation F [x; y] specify the Hausdorff
distance H(A;B \Phi t) as a function of the translation t. The directed Hausdorff distance
h(B \Phi t; A) is also useful for comparing two bitmaps. In particular, in order to identify
possible instances of a 'model' B in a cluttered `image' A, it is often desirable to simply
ensure that each portion of the model is near some portion of the image (but not
necessarily vice versa). We denote by FB [x; y] the directed Hausdorff distance from B
to A as a function of the translation (x; y) of B,
This measures the degree to which B[k; l] resembles A[k; l], for each translation (x; y) of
B. When each nonzero pixel of B[k near some nonzero pixel of A[k; l] then
the distance will be small. If on the other hand, some nonzero pixel of B[k
is far from all nonzero pixels of A[k; l] then the distance will be large. The directed
distance from A to B is analogously given by FA [x;
that F [x; y] is simply the pointwise maximum of these two directed distance functions.
4.1 Computing the Voronoi surface array D[x; y]
There are many methods of computing a distance transform (or rasterized approximation
to a Voronoi surface). In this section we summarize some of the approaches that
we have used for computing the distance transform D[x; y] of a binary array E[x; y]
(where we denote the nonzero pixels of E[x; y] by the point set E).
One method of computing D[x; y] is to use a local distance transform algorithm
such as that in [5], [10] or [15]. In practice we use a two-pass serial algorithm that
approximates the distance transform using a local mask to propagate distance values
through the array (such as that of [5]). Better distance values can be obtained using a
method such as that of [15] which produces distance transform values that are exact for
the L 1 and L1 norms, and are exact up to the machine precision for the L 2 norm. This
algorithm first processes each row independently. For each row of E[x; y], it calculates
the distance to the nearest nonzero pixel in that row, i.e. for each (x; y) it finds \Deltax such
that E[x + \Deltax; y] 6= 0 or E[x \Gamma \Deltax; y] 6= 0, and that \Deltax is the minimum non-negative
value for which this is true. It then scans up and down each column independently,
using the \Deltax values and a look-up table which depends on the norm being used, to
determine D[x; y].
Another method that we have used to compute distance transforms takes advantage
of specialized graphics hardware for rendering and z-buffering. The form of D[x; y] is,
as noted in Section 2, an 'egg carton': the lower envelope of a collection of cone-shapes,
one cone-shape for each point e (each nonzero pixel of E[x; y]), with its point at
. The exact form of the cone-shapes depends on the norm being used. For the L 1
norm the shapes are pyramids with sides of slope \Sigma1, oriented at 45 ffi with respect to
the coordinate axes. For the L1 norm they are again pyramids, but oriented parallel
to the coordinate axes. For the L 2 norm they are cones of slope 1.
The computation of D[x; y] is simply to take the pointwise minimum, or lower
envelope, of the cone-shapes rendered as described above. Consider the operations
performed by a graphics rendering engine set up to perform orthographic (rather than
perspective) projection, and set up to view this collection of surfaces from 'below'. It can
render the cones and perform visibility calculations quickly using a z-buffer. Suppose
that location in the z-buffer contains value d. Then the closest surface to the
viewer which intersects the line away. This means that the lower
envelope of the 'egg carton' is at height d at (x; y), and so D[x; d. Thus we simply
render each of the cones described above into a z-buffer doing orthographic projection
(i.e., with a view from z = \Gamma1). The running time of this method is O(p), where p
is the number of points in the set E. This is because each source point results in the
rendering of a single cone, and then the z-buffering operation is constant-time. With
current graphics hardware tens of thousands of polygons per second can be rendered in
a z-buffer, and thus it is possible to compute D[x; y] in a fraction of second. For the L 1
and L1 norms, D[x; y] is computed exactly; for the L 2 norm, there may be some error
in the computed D[x; y], which depends on the resolution of the z-buffer being used.
4.2 Computing the Hausdorff distance array F [x; y]
The Hausdorff distance as a function of translation, F [x; y], defined in equation (6) can
also be computed either using graphics hardware or standard array operations. For
simplicity of discussion, we focus on the computation of the directed distance from the
model to the image, FB [x; y] (the computation of FA [x; y] is analogous). Recall that
F [x; y] is just the maximum of these two directed distances.
Above we saw that FB [x; y] can be defined as the maximum of those values of D 0 [x; y]
(the distance transform of A[k; l]) that are selected by elements of B for each translation
(x; y) of B. Alternately, this can be viewed as the maximization of D 0 [x; y] shifted by
each location where B[k; l] takes on a nonzero value,
This maximization can be performed very rapidly with special-purpose graphics hardware
for doing pan and z-buffer operations. We simply pan D 0 [x; y] and accumulate
a pointwise maximum (upper envelope) using a z-buffer. In practice, for most current
graphics hardware this operation is not fast because it involves repeatedly loading the
z-buffer with an array from memory.
A second way of computing FB [x; y], using standard array operations, arises from
viewing the computation slightly differently. Note that (8) is simply equivalent to
maximizing the product of B[k; l] and D 0 [x; y] at a given relative position,
In other words, the maximization can be performed by 'positioning' B[k; l] at each
location (x; y), and computing the maximum of the product of B with D 0 .
In order to compute FB [x; y] using the method of equation (9), the array B[k; l] is
simply positioned centered at each pixel of the distance transform D 0 [x; y]. The value
of FB [x; y] is then the maximum value obtained by multiplying each entry of B[k; l] by
the corresponding entry D As B[k; l] is just a binary array, this amounts
to maximizing over those entries of D are selected by the nonzero
pixels of B[k; l]. That is, we can view the nonzero model pixels as probing locations
in the Voronoi surface of the image, and then FB [x; y] is the maximum of these probe
values for each position (x; y) of the model B[k; l].
This form of computing the directed Hausdorff distance under translation is very
similar to the binary correlation of the two arrays B[k; l] and A[k; l],
l
The only differences are that the array A[k; l] in the correlation is replaced by the
distance array D 0 [x; y] in equation (the distance to the nearest pixel of A[k; l]), and
the summation operations in the correlation are replaced by maximization operations.
It should be noted that the directed Hausdorff distance is very insensitive to small
errors in pixel locations, because the Voronoi surface, D 0 [x; y], reports the distance to
the nearest point of A[k; l]. Thus if pixels are slightly perturbed, the value of A[k; l]
only changes a small amount. In binary correlation, however, there is no such notion of
spatial proximity. Either pixels are directly superimposed or not. Binary correlation is
one of the most commonly used tools in image processing, and we will further examine
the relation between our method and correlation in Section 6.
4.3 Matching portions of the model and image
We can use the partial distance HLK (A; B \Phi t), given in equation (5), to define a version
of F [x; y] which allows portions of a model and image to be compared. For a given
translation fractions f 1 and f 2 representing the fraction of the nonzero
model and image pixels to be considered, respectively, let
and redefine
th
th
a2A
this is the same as the old version of
F [x; y].
When we are considering the partial distance between an image and a model, the
model is often considerably smaller than the image, reflecting the fact that in many
tasks a given instance of the model in the image will occupy only a small portion of the
image. In this case, the above definition of partial distance is not ideal for the directed
distance from the image to the model, H L because we must define L, the
number of image pixels that will be close to model pixels. This number, L, however
will depend on how many objects are in the image.
A natural way to compute a partial distance from the image to the model is to
consider only those image points that are near the current hypothesized position of
the model, since those farther away are probably parts of other imaged objects. In
practice, it is sufficient to consider only the image pixels which lie 'underneath' the
current position of the model: if we are computing F [x; y] and the model is m pixels by
pixels, then we compute a different version of FA [x; y] that considers just the points
of A[k; l] that are under the model at its given position, B[k
x-k!m+x
y-l!n+y
Note, that given this definition of comparing just a portion of the image to the
model, it is possible to further compute the 'partial distance' of this portion of the
image against the model. This can be done by combining this definition with the
ranking-based partial distance. We can do this by adjusting the value of L depending
on how many image pixels lie under the model at its given position (because we are
computing a partial distance with just this portion of the image). In other words we
let r is the number of nonzero image pixels which are 'underneath'
the translated model at the current translation. For this, the definition of FA [x; y] in
equation (10) would be modified to use L th instead of max.
Efficient Computation of F [x; y]
The na-ive approach to computing F [x; y], described in equation (6) of Section 4, can
take a significant time to run, because it considers every possible translation of the
model within the given ranges of x and y. We have developed some 'pruning' techniques
that decrease this running time significantly. These techniques take advantage of the
fact that, in typical applications, once F [x; y] has been computed, it will generally be
scanned to find all entries which are below some threshold, - . We can use this to
generate the (x; y) values where F [x; y] - directly, without generating all of F [x; y].
We present here some of the techniques which we have found to be useful.
The effects of these speedup techniques vary depending on the image and the model
being used. They are more effective when the image is sparse, and when the model has
a large number of points. In our work we have seen speedups of a factor of 1000 or
more over the na-ive approach. Some image/model pairs take only fractions of a second
to compare (some illustrative timings will be presented with the examples below).
5.1 Ruling out circles
We wish to compute the Hausdorff distance as a function of translation, F [x; y], given
a binary 'image' A[k; l] and a `model' B[k; l]. Let the bounds on A be
and the bounds on B be 0 - . While the array
F [x; y] is in principle of infinite extent, its minimum value must be attained when the
translated model overlaps the image in at least one location, so we only consider the
portion where \Gammam b
One property of FB [x; y] is that its slope cannot exceed 1. That is, the function
does not decrease more rapidly than linearly. Thus if FB [x
then FB [x; y] cannot be less than - in a circle of radius about the point
(The actual shape of the "circle" depends on the norm used; it is a true circle for L 2 ).
In other words, if the value of FB [x is large at some location, then it cannot be
small in a large area around that location. This fact can be used to rule out possible
translations near
)k. This is true for all
values of f 1 (the fraction of nonzero model pixels considered).
For a proof of this claim, see Appendix D. We use this fact in the algorithm detailed
below in order to speed up the computation.
This property does not necessarily hold for FA [x; y]. If we are considering only the
portion of the image under the model, as in Subsection 4.3, we might have a location
where moving the model by one pixel 'shifts' some image points into or out of the
window, which can change the value of FA [x; y] by a large amount. This also implies
that the property does not necessarily hold for F [x; y]. In practice, however, this is not
much of an issue because generally it is only for the image array that we wish to skip
over parts of a large array (e.g., by ruling out circles). The model array is usually small
enough that we do not need this technique.
5.2 Early scan termination
We may also obtain a speedup by not computing FB [x; y] completely if we can deduce
partway through the computation that it will be greater than - . Recall that FB is
computed by maximizing over all the locations of D are 'selected'
by nonzero pixels of B[k; l]. That is, each nonzero pixel of B[k; l] in effect probes a
location in the Voronoi surface of A[k; l], and we maximize over these probe values.
Thus if a single probe value is over the threshold - at translation (x; y), then we know
that F [x; y] must be over - (it is the maximum over all the probe values). Thus we can
stop computing FB for this translation, because it is over threshold.
An analogous result holds for the partial distances. Let qc. The value of
is the K-th ranked value of D 0 [b x
where are q such locations). We probe D 0 in q places, and maintain
a count of the number of these values from D 0 which exceed - . If this count exceeds
we know that the K-th ranked value must be greater than - , and so FB [x; y] ? - ,
so we need probe no more locations for the translation (x; y). In fact, we can determine
the minimum possible value FB [x; y] could have at this location, by assuming that the
unprobed values are all 0 and calculating the K-th ranked value of this set of values.
We can use this to eliminate nearby values of (x; y) from consideration. This method
works best for large values of f 1 .
5.3 Skipping forward
A third technique relies on the order in which the space of possible translations is
scanned. We must be scanning the distance transform array in some order; assume
that the order is a row at a time, in the increasing x direction. In other words, for some
y, we first consider FB to FB [m a \Gamma 1; y]. In this
case, it is possible to quickly rule out large sections of this row by using a variant of
the distance transform.
Let D 0
+x [x; y] be the distance in the increasing x direction to the nearest location
where D 0 [x; y] - , and 1 if there is no such location (in practice, D 0
would be
set to a large value if there is no such location; a value greater than the width of the
array is sufficiently large). Formally,
\Deltax
Note that D 0
. We can use D 0
+x [x; y] to determine how far we would
have to move in the increasing x direction to find a place where FB [x; y] might be no
greater than - . Let
GB [x; th
If GB [x; y] is 0, then K of the values of D 0
+x probed must have been 0, and so K of
the values of D 0 which would be probed in the computation of FB [x; y] would be - .
Further, if GB [x; not only do we know that FB [x; y] ? - , but also
(The proof of this is similar to the proof of
claim 4 and is omitted). We can therefore immediately increment x by \Deltax, and skip
a section of this row. Note also that we do not need to compute FB [x; y] at all if we
compute GB [x; y] and find that it is nonzero. Early scan termination can be applied to
this computation.
This method has the advantage over ruling out circles that it does not require any
auxiliary data structures to be maintained; once GB [x; y] has been computed, x can
be immediately incremented. The ruling out circles method must keep track of what
translations have been ruled out, and updating this map can be time-consuming.
5.4 Interactions between speedup methods
These techniques may be used in combination with each other. However, using one
technique may affect the efficiency of others. Interactions to be noted are:
ffl Using early scan termination greatly degrades the effect of both ruling out circles
and skipping forward. Early scan termination will generally give a value for
FB [x; y] which is only a small amount greater than - , and so very few locations
will be ruled out; continuing the scan could increase the value computed, thereby
saving work later.
A possible solution for this is to terminate the scan when FB [x; y] has been shown
to be greater than - +R, where R is some value, so that on a terminated scan, a
circle of radius at least R could be ruled out; similarly, terminate the scan when
GB [x; y] has been shown to be at least R. The value of R is arbitrary, and can be
adjusted for best performance.
ffl The order in which translations are considered can be arbitrary if skipping forward
is not used. The optimal order may well not consider adjacent translations
successively, as this will tend to consider translations which are on the edges of
ruled out circles, and so much of the neighborhood has already been ruled out.
Considering a translation in a "clear" area would provide more opportunity for
ruling other translations out.
5.5 An Efficient Algorithm
These observations give us an algorithm which will produce a list of values where
F [x; y] - quite efficiently.
Algorithm 1 Given two input binary image arrays, A[k; l] and B[k; l], two fractions
threshold - 0, generate a list T of (translation, value)
pairs ((x; y); v) such that Use the given fractions of B[k; l] and
A[k; l] for each translation (x; y) of B[k; l]. Consider only a fraction of that part of
A[k; l] which is covered by the translated B[k; l].
1. Let the bounds of A[k; l] be a and the bounds of B[k; l]
be
2. Compute the array D[x; y] that specifies the distance to the closest nonzero pixel
of B[k; l], making D[x; y] the same size as B[k; l].
3. Compute the array D 0 [x; y] that specifies the distance to the closest nonzero pixel
of A[k; l], making D 0 [x; y] with \Gammam b
(see Subsection 4.3).
4. Compute the array D 0
+x [x; y] that specifies the distance to the closest pixel (in the
increasing x direction) of D 0 [x; y] which is less than or equal to - . Make D 0
the same size as D 0 [x; y].
5. Let the number of model pixels considered be
6. Create an array, M [x; y], the same size as D 0 [x; y]. This will contain the minimum
possible value that FB [x; y] could have, given the information we have accumu-
lated. Initialize M [x; y] to zero.
7. Create two lists, T and T 0 . Initialize both to empty.
8. For each translation, let the number of image pixels considered be
where r is the number of nonzero pixels in A[k; l] that are covered by the current
position of B[k; l].
9. For each translation (x; y) of B[k; l] (scanned in reading order: top to bottom,
left to right),
(a) If M [x; y] ? - , then we need not consider this translation at all, and should
proceed to the next one. Otherwise,
(b) Set o to zero.
(c) For each b 2 B, consider D 0
+x [b x +x; b y +y]. If it is greater than R, increment
o. Also consider D during this process,
then
i. Take the smallest of the D 0
+x values which we have seen that exceeded
0. Call this \Deltax.
ii. Take the smallest of the D 0 values which we have seen that exceeded - .
Call this v 0 .
iii. For each value
This only needs
to be done for the M [x a radius of v need
not be done at all for any (x 0 ; y 0 ) which has previously been considered
in step 9.
iv. Skip to the next translation, (x+ \Deltax; y) (if x+ \Deltax - m a , go to the start
of the next row).
(d) If never exceeds q \Gamma K, then let v 0 be the K-th ranked value of the q values
from D 0 generated in step 9c. This will be - , since no more than q \Gamma K of
these values can be greater than - . Add ((x; to the list T 0 .
10. The list T 0 now contains all the (translation, value) pairs ((x;
. For each ((x; y); v 0 ) on the list T 0
(a) Consider the values of A[a x ; a y ]D[a x \Gamma x; a y \Gamma y], for all points a 2 A such
that x - a x ! x +m b and y - a y compute the L-th ranked value.
(Recall that r is the number of points of A that lie under
B[k; l] for the current translation (x; y), as described in Subsection 4.3.) Call
this value v. We know that F [x;
(b) If v is less than or equal to - , add ((x; to the list T .
This algorithm can also be used to produce a list of translations where the directed
Hausdorff 'distance' from the model to the image is less than - , by halting after step 9
and using the list T 0 .
6 Examples
We now consider some examples in order to illustrate the performance of the Hausdorff
distance methods developed above, using some image data from a camera in our
laboratory. The first test image is shown in Figure 3. This binary image is 360 \Theta 240
and was produced by applying an edge operator (similar to [6]) to a grey-level camera
image. The computation of the Hausdorff distance under translation was done using
an implementation written in C of the algorithm described above.
The model to be compared with the first test image is shown in Figure 4. The outline
around the figure delineates the boundary of the bitmap representing the model. The
model is 115 \Theta 199 pixels. Comparing this model against this image with
approximately twenty seconds on a Sun-4 (SPARCstation
2). This produced two matches, at (87; 35) and (87; 36). Figure 5 shows the match at
overlaid on the image. As a comparison, the na-ive approach from Subsection 4.2
takes approximately 5000 seconds to perform this comparison process.
We also ran the algorithm on the image and model shown in Figures 6 and 7, using
0:35. The image is 256 \Theta 233 and the model is 60 \Theta 50. Four
matches were found, at (99; 128), (100; 128), (99; 129) and (100; 129). Figure 8 shows
the match at (99; 129) overlaid on the image. The computation took approximately 5
seconds.
Our third test case consists of the image and model shown in Figures 9 and 10, using
0:5. The image is 360 \Theta 240 and the model is 38 \Theta 60. The

Figure

3: The first test image.

Figure

4: The first object model.

Figure

5: The first test image overlaid with the best match.

Figure

The second test image.

Figure

7: The second object model.

Figure

8: The second test image overlaid with the best match.
model was digitized from a different can, held at approximately the same orientation
and same distance from the camera. Four matches were found, at (199; 95), (199; 98),
(200; 98) and (199; 99).

Figure

11 shows the match at (199; 95) overlaid on the image.
The computation took approximately 1.4 seconds.
If several models are to be compared against the same image, then the distance
transform of the image need only be computed once. Our implementation takes about
one second to compute the distance transform of a 256 \Theta 256 image on a Sun-4 (SPARC-
station 2). Once this has been computed, the comparisons can take as little as one half
second per model (256 \Theta 256 images, 32 \Theta 32 model). The time taken depends on the - ,
f 1 and f 2 values used; larger - and smaller f 1 values increase the time taken. A more
cluttered image will also increase the time.
In order to compare the directed Hausdorff distance with correlation, we computed
the correlation of the stump model in Figure 7 with the second test image. We defined
a 'match' to be a translation where the correlation function was at a local peak. For
this image, the correlation performed poorly. There were eight incorrect matches which
had a higher correlation value than the correct match, and the correct match had a
peak value of only 77% of the largest peak. None of the incorrect matches was close
(spatially) to the correct match.
Hence we see support from these examples for our theoretical claim that the partial
Hausdorff 'distance' works well on images where the locations of image pixels have been
perturbed. Moreover, these same images cannot be handled well by correlation.
7 The Hausdorff Distance Under Rigid Motion
The methods we have described for computing the Hausdorff distance under translation
can be naturally extended to computing the Hausdorff distance under rigid motion
(translation and rotation). In this case, we require that the norm used be the Euclidean
norm (L 2 ). As before, we fix the set A and allow the set B to move (in this case rotate
and translate). The minimum value of the Hausdorff distance under rigid (Euclidean)
motion, ME (A; B), then gives the best transformation of B with respect to A,
(R ' B) \Phi t) (11)
where H is the Hausdorff distance as defined in equation (1), (R ' B) \Phi
Bg, and R ' is the standard rotation matrix. This distance is small exactly when there

Figure

9: The third test image.

Figure

10: The third object model.

Figure

11: The third test image overlaid with the best match.
is a Euclidean transformation that brings every point of B near some point of A and
vice versa.
We can compute a rasterized approximation to the minimum Hausdorff distance
under rigid motion. As above, the basic idea is to compute the Hausdorff distance for
all transformations of the model at the appropriate level of rasterization, and then find
the minima for which the distance is below some threshold, - . For translations, the
appropriate level of rasterization is again single pixels. For rotation, we want to ensure
that each consecutive rotation moves each point in the model by at most one pixel.
Each point b j in the set B is being rotated around the center of rotation, c r , on a circle
of radius r . This means that the rasterization interval in ', \Delta', should
be arctan(1=r k ) where r k is the radius of rotation of the point in B which is furthest
from the center of rotation.
Our current implementation is restricted to computing only the directed Hausdorff
distance from the model, B, to the image, A. This is analogous to FB [x; y] as defined
in equation (7). Furthermore, we consider only complete shapes (no partial distances).
Recall that the Hausdorff distance computation can be thought of as probing locations
in the Voronoi surface of the image corresponding to the transformed model points.
The probe values for each transformation are then maximized in order to compute the
distance for that transformation. For rigid motion, we build a structure which gives for
each model point a list of the locations that the point moves through as it rotates, one
location for each rasterized '. These locations are relative to the center of rotation and,
for each model point, this list describes a circle about the center of rotation.
Consider the problem of determining the minimum (directed) Hausdorff distance
under rotation for a fixed translation t, min ' h((R ' B) \Phi t; A). We first initialize to zero
an array, Q, containing an element for each ' value. During the computation, this array
will contain the minimum possible value of the Hausdorff distance for each rotation, on
the basis of the points that have been probed thus far. For each point we probe the
distance transform of the image at each relative rotated location, and maximize these
probe values with the corresponding values in the array Q. Once all points in B have
been considered, the array Q gives the directed Hausdorff distance for each discrete
rotation at the current translation:
We perform this computation for each rasterized translation t. This algorithm is analogous
to the na-ive algorithm for the translation-only case.
As in the translation-only case, many possible translations and rotations of B may
be ruled out without explicitly considering them. We have begun to investigate speedup
techniques for Euclidean motion and now describe the methods that have proven successful

First, we choose as the center of rotation that point of B which is closest to the
centroid of the model. This both reduces the number of rasterized ' values which we
need to consider and also explicitly makes the center of rotation be a point in B. This
is useful since the center of rotation does not move as ' changes. Thus, if at a given
translation we probe the center point first and find that the distance transform at that
point is greater than - , then we know that there are no good rotations of the model at
this translation.
Points of B that are close to the center of rotation will not pass through many
distinct grid points as they rotate about it. In building the model rotation structure,
we can therefore store only the distinct grid points through which each point of B
rotates. In addition, we also store the range of rasterized ' values that each of these
distinct points corresponds to. This compression of the rotation structure eliminates
a large number of extraneous probes. However, a single probe may now be used to
update several consecutive entries in Q.
Techniques analogous to ruling out circles and early scan termination can also be
used in '-space to prune the search for good transformations of the model.
If we find that for some rotation ' and point b 2 B the distance from R '
the nearest point in A is v and v ? - , then all rotations which bring b into the circle of
radius centered at R ' may be eliminated from consideration. These are the
rotations in the range ' \Sigma cos r is the radius of rotation of
point b. If all values of ' may be ruled out. Note that a conservative
approximation to this range is ' \Sigma (v \Gamma -)=r, which may be used if cos \Gamma1 is too expensive
to compute. Considering the points in order of increasing radius of rotation makes it
likely that large ' ranges will be eliminated early on, as a single large probe value for
one of the "inner" points will rule out more ' values than it would for one of the "outer"
points.
By maintaining a list of ruled-out regions of '-space, the transformations resulting in
a Hausdorff distance greater than - can be quickly discarded. As noted in subsection 5.4,
combining early scan termination with ruling out circles for the translation-only case
may result in only small areas being ruled out. This same problem holds in '-space,
and again, a possible solution is to delay early termination until we can guarantee that
the terminated scan eliminates at least some minimum radius circle.
It is also possible to use pruning techniques in both rotation and translation simul-
taneously. One possible technique is to use the Q array generated for one translation
to eliminate some ' values for an adjacent translation. Since the slope of the distance
transform cannot exceed 1, in moving to an adjacent translation each probe value could
at worst decrease by 1. Thus, any angle for which the lower bound on the Hausdorff
distance is greater than - + 1 at the current translation can also be ruled out at all
adjacent translations. In practice, however, we found that the extra overhead involved
actually slowed down the computation.
Finally, to illustrate the performance of our current implementation, we use an image
of some children's blocks on a table. This example is taken from a demonstration in
which a robot arm locates blocks on the table using the Hausdorff distance under rigid
motion and then uses the blocks to build an object the user has specified. Figure 12
shows the edge detector output for the 360 \Theta 240 grey-level camera image of the blocks.
The block model is shown in Figure 13 and is simply a square 31 pixels on each side.
Matching this model against the image using local minima are found
below threshold, corresponding to four rotations for each of the 15 blocks which are
completely in the field of view. The matches are shown overlaid on the original image
in

Figure

14. Note that because we are only computing the directed distance from
the model to the image, even the blocks that contain letters imprinted in the upward
facing side are recognized. At each translation and rotation of the model, we merely
require that there is an image point within three pixels of each point in the transformed
model. This is exactly what is needed for this application, though large black areas
in the image would present problems because spurious matches would be found. This
matching takes approximately 216 seconds on a SPARCstation 2. Taking advantage of
the symmetry of this particular model would allow a four-fold increase in speed for this
application.
With more time spent optimizing our pruning techniques, the running time should
be greatly improved, especially considering the improvement achieved over the na-ive
algorithm for the translation-only case.

Summary

The Hausdorff distance under translation measures the extent to which each point of a
translated 'model' set lies near some point of an `image' set and vice versa. Thus this

Figure

12: A test image showing some blocks.

Figure

13: The block model.

Figure

14: The test image blocks overlaid with each matched block.
distance reflects the degree of resemblance between two objects (under translation). We
have discussed how to compute the Hausdorff distance under translation efficiently for
binary image data. The method compares a 32 \Theta 32 model bitmap with a 256 \Theta 256
image bitmap in a fraction of a second on a SPARCstation 2.
The computation of the directed Hausdorff distance under translation is in many
ways similar to binary correlation. The method is more tolerant of perturbations in the
locations of points than correlation because it measures proximity rather than exact
superposition. This is supported by empirical evidence as well as by the theoretical
formulation of the problem. The partial Hausdorff 'distance' between a model and
an image has been illustrated to work well on examples where correlation fails. We
have also extended our algorithms to work with rigid motion. It is an open problem
to develop efficient methods, both theoretically and in practice, for computing the
Hausdorff distance under other transformation groups.
A Proof of Claim 1
Proof. Let A 0 be the points in A for which there is some point in B within d:
Similarly, let B 0 be the points in B for which there is some point in A within d. We
must have jA th
that there are at least L points in A which are closer than d to some point in B (and
similarly there are K points in B which are closer than d to some point in A). Also,
since k \Delta k is symmetrical (i.e. ka \Gamma all the 'neighbors' of any point in A 0
must be in B 0 and vice versa.
The problem now reduces to finding A L ' A 0 and BK ' B 0 having min(K; L) points
each such that We will show that this is possible by building A L and
BK one element at a time, while maintaining the invariant that
that for each element of A L there is some element of BK within d and vice versa).
Base case: Pick any point a from A 0 . Put it into A L . Find any point b in B 0 such that
There must be at least one. Put b into BK . Then
Induction step: Suppose that A L and BK each have n ! min(K; L) elements and
that d. There are now two cases:
ffl Suppose that there exist a 2 A
Then if we add a to A L and b to BK we will have increased the size of each
set to n maintaining the invariant.
ffl Suppose that no such a and b exist. Then pick any point a 2 A
consider its 'neighbors': points in B 0 \Phi t within d. It must have at least one
since it is a member of A 0 . All the neighbors must be in BK already, so it
has at least one neighbor in BK . Similarly, every point has at
least one neighbor in A L . Picking any point in A 0 \Gamma A L and any point in
adding them to A L and BK respectively increases the size of
each set to n maintains the invariant, since every point in the new
A L has a neighbor in the new BK and vice versa.
Since there are at least L elements in A 0 and K elements in B 0 , we will not run
out of elements in A achieving min(K; L) elements in
A L and BK .
This process builds A L and BK by ensuring that whenever a pair of points are added,
they will each have neighbors in the augmented sets, which maintains the desired invariant

B Proof of Claim 2
Proof. We will be using A 0 , B 0 , A L and BK from the proof of Claim 1 to construct A 0
K . Suppose (without loss of generality) that K - L. Now, pick any K \Gamma L points
from (there must be at least this many points since jBK
K be the union of BK and these points. For each of the new points, pick
one of its neighbors from A 0 . Let A 0
L be the union of A L and these neighboring points.
will be at most K and at least L, since jA L L, and all these neighbors might
have been members of A L . Thus, L - jA 0
every point in B 0
has a neighbor (within d) in A 0
L and vice versa, we know that
we must have equality since if
strictly less than d, then HLK (A; B)
would also be strictly less than d, since A 0
K would then be minimizing subsets
of sizes at least L and K respectively.
C Proof of Claim 3
Proof. We can see from the definitions of D and D 0 that if x and y are integers, and
and so the
minimum value of F [x; y] is no smaller than the minimum value of f(t): F [x
is a norm, it satisfies the triangle inequality. Let a be any point. d(a) is
the distance from a to the nearest point of B, and so there is a point b in B such that
a 0 be any other point. Then
Similarly, d 0 (b any two points b and b 0 .
If t and t 0 are any two translations, then
1 ) be the grid point closest to
1 and y 0
1 are the integers which
is an L p norm,
D Proof of Claim 4
Proof. From the proof of claim 3, we know that
We know that
of the nonzero model pixels are within v 1 of some nonzero image pixel: there
exist
Now consider the computation of v 2 . We will be 'probing' the values of D 0 [b x
(among others). But since
there are at least K nonzero model pixels which are at most v 1
away from some nonzero image pixel when the model is translated by
the computation of v 2 computes the K-th ranked value of these distances, we will have



--R

Data Structures and Algorithms.
Measuring the resemblance of polygonal shapes.
An efficiently computable metric for comparing polygonal shapes.

Distance transforms in digital images.
A computational approach to edge detection.

General Topology.
Euclidean distance mapping.
Grimson with T.
Efficiently computing the Hausdorff distance for point sets under translation.
On dynamic Voronoi diagrams and the minimum hausdorff distance for point sets under Euclidean motion in the plane.
The upper envelope of Voronoi surfaces and its applications.
Distance transforms: Properties and machine vision applica- tions
Computational Geometry.
Digital Picture Processing
--TR
Three-dimensional object recognition
Computational geometry: an introduction
Model-based recognition in robot vision
A computational approach to edge detection
Distance transformations in digital images
Computing the minimum Hausdorff distance for point sets under translation
Object recognition by computer
An Efficiently Computable Metric for Comparing Polygonal Shapes
The upper envelope of Voronoi surfaces and its applications
Distance transforms
On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane
Data Structures and Algorithms
Digital Picture Processing

--CTR
Istvn Szatmri , Csaba Rekeczky , Tams Roska, A Nonlinear Wave Metric and its CNN Implementation for Object Classification, Journal of VLSI Signal Processing Systems, v.23 n.2-3, p.437-447, Nov.&slash;Dec. 1999
Haikel Salem Alhichri , Mohamed Kamel, Multi-resolution image registration using multi-class Hausdorff fraction, Pattern Recognition Letters, v.23 n.1-3, p.279-286, January 2002
Daniel P. Huttenlocher , Ryan H. Lilien , Clark F. Olson, View-Based Recognition Using an Eigenspace Approximation to the Hausdorff Measure, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.9, p.951-955, September 1999
Haikel Salem Alhichri , Mohamed Kamel, Multi-resolution image registration using multi-class Hausdorff fraction, Integrated image and graphics technologies, Kluwer Academic Publishers, Norwell, MA, 2004
Robert W. Frischholz , Ulrich Dieckmann, BioID: A Multimodal Biometric Identification System, Computer, v.33 n.2, p.64-68, February 2000
Robust Hausdorff distance measure for face recognition, Pattern Recognition, v.40 n.2, p.431-442, February, 2007
Sugata Mukhopadhyay , Brian Smith, Passive capture and structuring of lectures, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.477-487, October 30-November 05, 1999, Orlando, Florida, United States
Klara Kedem , Yana Yarmovski, Curve based stereo matching using the minimum Hausdorff distance, Proceedings of the twelfth annual symposium on Computational geometry, p.415-418, May 24-26, 1996, Philadelphia, Pennsylvania, United States
Mirela Tanase , Remco C. Veltkamp, Part-based shape retrieval, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore
Clark F. Olson, Maximum-Likelihood Image Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.6, p.853-857, June 2002
Wang , Yan Zhang , Jufu Feng, On the Euclidean Distance of Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.8, p.1334-1339, August 2005
Longin Jan Latecki , Rolf Lakmper, Shape Similarity Measure Based on Correspondence of Visual Parts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.10, p.1185-1190, October 2000
Herbert Ramoser , Josef Birchbauer , Horst Bischof, Computationally efficient and reliable fingerprint mosaicking on embedded hardware using minutiae, Machine Graphics & Vision International Journal, v.13 n.4, p.401-415, October 2004
Muhammad Saleem , Adil Masood Siddiqui , Imran Touqir, Efficient feature correspondence for image registration, Proceedings of the 6th WSEAS International Conference on Signal, Speech and Image Processing, p.101-104, September 22-24, 2006, Lisbon, Portugal
R. J. Lpez-Sastre , S. Lafuente-Arroyo , P. Siegmann , P. Gil-Jimnez , A. Vazquez-Reina, Recognition of mandatory traffic signs using the Hausdorff distance, Proceedings of the 5th WSEAS International Conference on Signal Processing, Computational Geometry & Artificial Vision, p.216-221, September 15-17, 2005, Malta
Thomas P. Moran , Eric Saund , William Van Melle , Anuj U. Gujar , Kenneth P. Fishkin , Beverly L. Harrison, Design and technology for Collaborage: collaborative collages of information on physical walls, Proceedings of the 12th annual ACM symposium on User interface software and technology, p.197-206, November 07-10, 1999, Asheville, North Carolina, United States
Gang Wei , Ishwar K. Sethi, Omni-face detection for video/image content description, Proceedings of the 2000 ACM workshops on Multimedia, p.185-189, October 30-November 03, 2000, Los Angeles, California, United States
Oscar Firschein, Defense Applications of Image Understanding, IEEE Expert: Intelligent Systems and Their Applications, v.10 n.5, p.11-17, October 1995
Sergey Brin, Near Neighbor Search in Large Metric Spaces, Proceedings of the 21th International Conference on Very Large Data Bases, p.574-584, September 11-15, 1995
Ramin Zabih , Justin Miller , Kevin Mai, A feature-based algorithm for detecting and classifying production effects, Multimedia Systems, v.7 n.2, p.119-128, March 1999
Thomas Kmpke, Convex Translation Estimation, Journal of Intelligent and Robotic Systems, v.21 n.3, p.287-300, March 1998
Chyuan-Huei Thomas Yang , Shang-Hong Lai , Long-Wen Chang, Hybrid image matching combining Hausdorff distance with normalized gradient matching, Pattern Recognition, v.40 n.4, p.1173-1181, April, 2007
Yannis E. Ioannidis , Viswanath Poosala, Histogram-Based Approximation of Set-Valued Query-Answers, Proceedings of the 25th International Conference on Very Large Data Bases, p.174-185, September 07-10, 1999
Huanfeng Ma , David Doermann, Adaptive Hindi OCR using generalized Hausdorff image comparison, ACM Transactions on Asian Language Information Processing (TALIP), v.2 n.3, p.193-218, September
Kwok-Wai Cheung , Dit-Yan Yeung , Roland T. Chin, Bidirectional Deformable Matching with Application to Handwritten Character Extraction, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.8, p.1133-1139, August 2002
Didier Coquin , Philippe Bolon, Quantitative assessment of image filtering: comparison of objective metrics, Imaging and vision systems: theory, assessment and applications, Nova Science Publishers, Inc., Commack, NY, 2001
Christina de Juan , Bobby Bodenheimer, Cartoon textures, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France
Dawn Lawrie , Daniela Rus, A self-organized file cabinet, Proceedings of the eighth international conference on Information and knowledge management, p.499-506, November 02-06, 1999, Kansas City, Missouri, United States
Zhenfeng Zhu , Ming Tang , Hanqing Lu, A new robust circular Gabor based object matching by using weighted Hausdorff distance, Pattern Recognition Letters, v.25 n.4, p.515-523, March 2004
Xilin Yi , Octavia I. Camps, Line-Based Recognition Using A Multidimensional Hausdorff Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.9, p.901-916, September 1999
Michail Vlachos , Zografoula Vagena , Philip S. Yu , Vassilis Athitsos, Rotation invariant indexing of shapes and line drawings, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
Giancarlo Iannizzotto , Massimo Villari , Lorenzo Vita, Hand tracking for human-computer interaction with Graylevel VisualGlove: turning back to the simple way, Proceedings of the 2001 workshop on Perceptive user interfaces, November 15-16, 2001, Orlando, Florida
Nicolae Duta , Anil K. Jain , Marie-Pierre Dubuisson-Jolly, Automatic Construction of 2D Shape Models, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.5, p.433-446, May 2001
Daniela Rus , James Allan, Structural Queries in Electronic Corpora, Multimedia Tools and Applications, v.6 n.2, p.153-169, March 1998
Baofeng Guo , Kin-Man Lam , Kwan-Ho Lin , Wan-Chi Siu, Human face recognition based on spatially weighted Hausdorff distance, Pattern Recognition Letters, v.24 n.1-3, p.499-507, January
Claudio Uras , Alessandro Verri, Computing Size Functions from Edge Maps, International Journal of Computer Vision, v.23 n.2, p.169-183, June 1997
Alignment Using Distributions of Local Geometric Properties, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.10, p.1031-1043, October 1999
Charng-da Lu , Daniel A. Reed, Compact application signatures for parallel and distributed scientific codes, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-10, November 16, 2002, Baltimore, Maryland
Bageshree Shevade , Hari Sundaram , Lexing Xie, Modeling personal and social network context for event annotation in images, Proceedings of the 2007 conference on Digital libraries, June 18-23, 2007, Vancouver, BC, Canada
Yaoyao Gu , Yuan Tian , Eylem Ekici, Real-time multimedia processing in video sensor networks, Image Communication, v.22 n.3, p.237-251, March, 2007
Philip L. Worthington , Edwin R. Hancock, Object Recognition Using Shape-from-Shading, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.5, p.535-542, May 2001
J. Rucklidge, Efficiently Locating Objects Using the Hausdorff Distance, International Journal of Computer Vision, v.24 n.3, p.251-270, Sept./Oct. 1997
Frank Hoffmann , Klaus Kriegel , Carola Wenk, Matching 2D patterns of protein spots, Proceedings of the fourteenth annual symposium on Computational geometry, p.231-239, June 07-10, 1998, Minneapolis, Minnesota, United States
Maylor K. Leung , Yee-Hong Yang, First Sight: A Human Body Outline Labeling System, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.4, p.359-377, April 1995
Hyungjun Park, An error-bounded approximate method for representing planar curves in B-splines, Computer Aided Geometric Design, v.21 n.5, p.479-497, May 2004
Lihua Zhang , Wenli Xu , Cheng Chang, Genetic algorithm for affine point pattern matching, Pattern Recognition Letters, v.24 n.1-3, p.9-19, January
Stphane Derrode , Faouzi Ghorbel, Shape analysis and symmetry detection in gray-level objects using the analytical Fourier-Mellin representation, Signal Processing, v.84 n.1, p.25-39, January 2004
Haikel Salem Alhichri , Mohamed Kamel, Virtual circles: a new set of features for fast image registration, Pattern Recognition Letters, v.24 n.9-10, p.1181-1190, 01 June
Davi Geiger , Tyng-Luh Liu , Robert V. Kohn, Representation and Self-Similarity of Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.1, p.86-99, January
T. M. Breuel, On the use of interval arithmetic in geometric branch and bound algorithms, Pattern Recognition Letters, v.24 n.9-10, p.1375-1384, 01 June
C. Gope , N. Kehtarnavaz, Affine invariant comparison of point-sets using convex hulls and hausdorff distances, Pattern Recognition, v.40 n.1, p.309-320, January, 2007
Steven M. Seitz , Charles R. Dyer, View-Invariant Analysis of Cyclic Motion, International Journal of Computer Vision, v.25 n.3, p.231-251, Dec. 1997
Gun Park , Kyoung Mu Lee , Sang Uk Lee , Jin Hak Lee, Recognition of partially occluded objects using probabilistic ARG (attributed relational graph)-based matching, Computer Vision and Image Understanding, v.90 n.3, p.217-241, June
Ercan E. Kuruoglu , Vern T. Tan, Document image retrieval without OCRing using a video scanning system, Proceedings of the 2000 ACM workshops on Multimedia, p.233-236, October 30-November 03, 2000, Los Angeles, California, United States
Giancarlo Iannizzotto , Antonio Puliafito , Lorenzo Vita, Using the Median Distance to Compare Object Shapes in Content-BasedImage Retrieval, Multimedia Tools and Applications, v.8 n.2, p.197-217, March 1999
Helmut Alt , Oswin Aichholzer , Gnter Rote, Matching shapes with a reference point, Proceedings of the tenth annual symposium on Computational geometry, p.85-92, June 06-08, 1994, Stony Brook, New York, United States
Daniela Rus , Devika Subramanian, Multi-media RISC informatics: retrieving information with simple structural components, Proceedings of the second international conference on Information and knowledge management, p.283-294, November 01-05, 1993, Washington, D.C., United States
Lixin Fan , Kah Kay Sung, Model-based varying pose face detection and facial feature registration in video images, Proceedings of the eighth ACM international conference on Multimedia, p.295-302, October 2000, Marina del Rey, California, United States
N. Bourbakis , P. Yuan , S. Makrogiannis, Object recognition using wavelets, L-G graphs and synthesis of regions, Pattern Recognition, v.40 n.7, p.2077-2096, July, 2007
Daming Shi , Robert I. Damper , Steve R. Gunn, Offline handwritten Chinese character recognition by radical decomposition, ACM Transactions on Asian Language Information Processing (TALIP), v.2 n.1, p.27-48, March
Zhengrong Ying , David Castaon, Partially Occluded Object Recognition Using Statistical Models, International Journal of Computer Vision, v.49 n.1, p.57-78, August 2002
Pavel Zezula , Pasquale Savino , Giuseppe Amato , Fausto Rabitti, Approximate similarity retrieval with M-trees, The VLDB Journal  The International Journal on Very Large Data Bases, v.7 n.4, p.275-293, December 1998
David M. Mount , Nathan S. Netanyahu , Jacqueline Le Moigne, Improved algorithms for robust point pattern matching and applications to image registration, Proceedings of the fourteenth annual symposium on Computational geometry, p.155-164, June 07-10, 1998, Minneapolis, Minnesota, United States
Gilbert Pradel , Philippe Hoppenot, Symbolic Trajectory Description in Mobile Robotics, Journal of Intelligent and Robotic Systems, v.45 n.2, p.157-180, February  2006
Vincent Oria, Robust and fast similarity search for moving object trajectories, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
Paolo Ciaccia , Marco Patella , Pavel Zezula, A cost model for similarity queries in metric spaces, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.59-68, June 01-04, 1998, Seattle, Washington, United States
Thomas B. Sebastian , Benjamin B. Kimia, Curves vs. skeletons in object recognition, Signal Processing, v.85 n.2, p.247-263, February 2005
Ross Cutler , Larry S. Davis, Robust Real-Time Periodic Motion Detection, Analysis, and Applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.781-796, August 2000
Md. Al-Amin Bhuiyan , Hiromitsu Hama, 3D Reconstruction of parametric curves: recovering the control points, Machine Graphics & Vision International Journal, v.13 n.4, p.307-328, October 2004
Aaron Wallack , Dinesh Manocha, Robust Algorithms for Object Localization, International Journal of Computer Vision, v.27 n.3, p.243-262, May 1, 1998
Byeong Hwan Jeon , Kyoung Mu Lee , Sang Uk Lee, Face detection using a first-order RCE classifier, EURASIP Journal on Applied Signal Processing, v.2003 n.1, p.878-889, January
Haesevoets , Bart Kuijpers, Time-dependent affine triangulation of spatio-temporal data, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA
Yoram Gdalyahu , Daphna Weinshall, Flexible syntactic matching of curves and its application to automatic hierarchal classification of silhouettes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.12, p.1313-1328, December 1999
Thomas M. Breuel, Implementation techniques for geometric branch-and-bound matching methods, Computer Vision and Image Understanding, v.90 n.3, p.258-294, June
Davi Geiger , Tyng-Luh Liu , Michael J. Donahue, Sparse Representations for Image Decompositions, International Journal of Computer Vision, v.33 n.2, p.139-156, Sept. 1999
Masaki Hilaga , Yoshihisa Shinagawa , Taku Kohmura , Tosiyasu L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.203-212, August 2001
Xiaofeng Ren , Charless C. Fowlkes , Jitendra Malik, Learning Probabilistic Models for Contour Completion in Natural Images, International Journal of Computer Vision, v.77 n.1-3, p.47-63, May       2008
Rafael Murrieta-Cid , Carlos Parra , Michel Devy, Visual Navigation in Natural Environments: From Range and Color Data to a Landmark-Based Model, Autonomous Robots, v.13 n.2, p.143-168, September 2002
D. -G. Sim , R. -H. Park , R. -C. Kim , S. U. Lee , I. -C. Kim, Integrated Position Estimation Using Aerial Image Sequences, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.1, p.1-18, January 2002
Giuseppe Amato , Fausto Rabitti , Pasquale Savino , Pavel Zezula, Region proximity in metric spaces and its use for approximate similarity search, ACM Transactions on Information Systems (TOIS), v.21 n.2, p.192-227, April
Michael Lindenbaum , Shai Ben-David, VC-Dimension Analysis of Object Recognition Tasks, Journal of Mathematical Imaging and Vision, v.10 n.1, p.27-49, Jan. 1999
Carlos Orrite , J. Elias Herrero, Shape matching of partially occluded curves invariant under projective transformation, Computer Vision and Image Understanding, v.93 n.1, p.34-64, January 2004
Facundo Mmoli , Guillermo Sapiro, Comparing point clouds, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France
Claire Kenyon , Yuval Rabani , Alistair Sinclair, Low distortion maps between point sets, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Pedro F. Felzenszwalb , Daniel P. Huttenlocher, Pictorial Structures for Object Recognition, International Journal of Computer Vision, v.61 n.1, p.55-79, January 2005
Vassilis Athitsos , Marios Hadjieleftheriou , George Kollios , Stan Sclaroff, Query-sensitive embeddings, ACM Transactions on Database Systems (TODS), v.32 n.2, p.8-es, June 2007
Andrew B. Kahng, Classical floorplanning harmful?, Proceedings of the 2000 international symposium on Physical design, p.207-213, May 2000, San Diego, California, United States
J. Y. Kaminski , Amnon Shashua, Multiple View Geometry of General Algebraic Curves, International Journal of Computer Vision, v.56 n.3, p.195-219, February-March 2004
Daniela Rus , Devika Subramanian, Customizing information capture and access, ACM Transactions on Information Systems (TOIS), v.15 n.1, p.67-101, Jan. 1997
David W. Jacobs , Daphna Weinshall , Yoram Gdalyahu, Classification with Nonmetric Distances: Image Retrieval and Class Representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.6, p.583-600, June 2000
Jing Huang , S. Ravi Kumar , Mandar Mitra , Wei-Jing Zhu , Ramin Zabih, Spatial Color Indexing and Applications, International Journal of Computer Vision, v.35 n.3, p.245-268, Dec. 1999
Gun Park , Kyoung Mu Lee , Sang Uk Lee, Color-based image retrieval using perceptually modified Hausdorff distance, Journal on Image and Video Processing, v.2008 n.1, p.1-10, January 2008
Anarta Ghosh , Nicolai Petkov, A cognitive evaluation procedure for contour based shape descriptors, International Journal of Hybrid Intelligent Systems, v.2 n.4, p.237-252, December 2005
S. Belongie , J. Malik , J. Puzicha, Shape Matching and Object Recognition Using Shape Contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.509-522, April 2002
David Jacobs , Ronen Basri, 3-D to 2-D Pose Determination with Regions, International Journal of Computer Vision, v.34 n.2-3, p.123-145, Nov. 1999
Yongsheng Gao , S. C. Hui , A. C. M. Fong, A Multi-View Facial Analysis Technique for Pervasive Computing, v.2 n.1, p.38-45, January
Haili Chui , Anand Rangarajan, A new point matching algorithm for non-rigid registration, Computer Vision and Image Understanding, v.89 n.2-3, p.114-141, February
Gilbert Pradel , Philippe Hoppenot, Symbolic environment representation by means of frescoes in mobile robotics, Robotica, v.23 n.4, p.527-537, July 2005
Manuele Bicego , Umberto Castellani , Vittorio Murino, A hidden Markov model approach for appearance-based 3D object recognition, Pattern Recognition Letters, v.26 n.16, p.2588-2599, December 2005
Ronen Basri , David W. Jacobs, Recognition Using Region Correspondences, International Journal of Computer Vision, v.25 n.2, p.145-166, Nov. 1997
Philip Fast and Effective Retrieval of Medical Tumor Shapes, IEEE Transactions on Knowledge and Data Engineering, v.10 n.6, p.889-904, November 1998
Anarta Ghosh , Nicolai Petkov, Robustness of Shape Descriptors to Incomplete Contour Representations, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.11, p.1793-1804, November 2005
Jianping Fan , Xingquan Zhu , Kayvan Najarian , Lide Wu, Accessing Video Contents through Key Objects over IP, Multimedia Tools and Applications, v.21 n.1, p.75-96, September
Schmid , Andrew Zisserman, The Geometry and Matching of Lines and Curves Over Multiple Views, International Journal of Computer Vision, v.40 n.3, p.199-233, Dec. 2000
Seong G. Kong , Jingu Heo , Faysal Boughorbel , Yue Zheng , Besma R. Abidi , Andreas Koschan , Mingzhong Yi , Mongi A. Abidi, Multiscale Fusion of Visible and Thermal IR Images for Illumination-Invariant Face Recognition, International Journal of Computer Vision, v.71 n.2, p.215-233, February  2007
Congxia Dai , Yunfei Zheng , Xin Li, Pedestrian detection and tracking in infrared imagery using shape and appearance, Computer Vision and Image Understanding, v.106 n.2-3, p.288-299, May, 2007
Thomas Funkhouser , Patrick Min , Michael Kazhdan , Joyce Chen , Alex Halderman , David Dobkin , David Jacobs, A search engine for 3D models, ACM Transactions on Graphics (TOG), v.22 n.1, p.83-105, January
Yefeng Zheng , Huiping Li , David Doermann, A Parallel-Line Detection Algorithm Based on HMM Decoding, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.5, p.777-792, May 2005
Mark A. Ruzon , Carlo Tomasi, Edge, Junction, and Corner Detection Using Color Distributions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.11, p.1281-1295, November 2001
Ming-Hsuan Yang , David J. Kriegman , Narendra Ahuja, Detecting Faces in Images: A Survey, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.1, p.34-58, January 2002
A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999
Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
shape comparison methods;image comparison;image processing;binary image;translation;position error tolerance;hausdorff distance;rigid motion