Relaxing the Triangle Inequality in Pattern Matching.
Any notion of closeness in pattern matching should have the property that if A is close to B, and B is close to C, then A is close to C. Traditionally, this property is attained because of the triangle inequality d(B, C), where d represents a notion of distance). However, the full power of the triangle inequality is not needed for this property to hold. Instead, a relaxed triangle inequality suffices, of the form d(B, C)), where c is a constant that is not too large. In this paper, we show that one of the measures used for distances between shapes in (an experimental version of) IBMs QBIC1 (Query by Image Content) system (Niblack et al., 1993) satisfies a relaxed triangle inequality, although it does not satisfy the triangle inequality.
Introduction
Traditionally, databases have been used to store and retrieve textual and numerical information.
More recently, applications such as multimedia have led to the development of database systems that
can handle images. One such system is the QBIC ("Query by Image Content") system (Niblack
et al., 1993), developed at the IBM Almaden Research Center. An experimental version of the
QBIC system (henceforth in this paper called simply "QBIC") can search for images by various
visual characteristics such as color, shape, and texture. While the result of a query to a traditional
database is usually some specific set of items (e.g., the names of all employees in the computer
science department), the result of a query to a database of images might not be so well-defined.
Consider, for example, a query that should return all items that look like a tree; such a query could
be entered by having the user draw the desired tree-like shape on a screen, or by extracting the
shape from a visual scene. Questions of the form "Does the shape D in the database look like
the query tree shape Q?" do not have definite yes/no answers (unlike questions of the form "Is
employee E in the computer science department?"). Rather, the answer to such a question is more
reasonably given as a numerical "distance" that measures how well the shape D matches the shape
Q. The answer to the query could then be an ordered list of shapes from the database, ordered
by how closely they match the query shape Q. This raises the issue of how to define a measure of
"distance" between shapes.
There is an extensive literature about various ways to define distances between shapes. These
include methods based on turning angles (Arkin et al., 1990; McConnell et al., 1991), on the
Hausdorff distance (Huttenlocher et al., 1992), on various forms of moments (Kim and Kim, 1997;
Taubin and Cooper, 1991), and on Fourier descriptors (Jain, 1989).
Mehtre, Kankanhalli and Lee (1997) and Mumford (1991) discuss and compare various ap-
proaches. Scassellati et al. (1994) compare methods on the basis of how well they correspond to
human perceptual distinctions. In Section 2, we discuss a particular distance measure between
shapes, that is one of the measures used in the QBIC system. Intuitively, it measures how well
the boundary of one shape matches the boundary of the other, allowing either boundary to stretch
when doing the matching. A variation of this method provided the best overall results in the
Scassellati et al. study.
Let us reconsider the problem we mentioned earlier, where Q is a shape, and where we wish to
obtain an ordered list of shapes from the database, ordered by how closely they match Q. Let us
say that as in the QBIC system, we wish to see the best 10 matches, and then upon request the next
best 10 matches, and so on. This is a computationally expensive process, for several reasons. For a
given shape D in the database, computing the distance between Q and D may well be expensive in
itself: for example, for the distance measure used in QBIC that is discussed in Section 2, a dynamic
programming algorithm is used that has quadratic complexity. Furthermore, even if we wish to see
only the best 10 matches, we may have to compute the distance between Q and every shape D in
the database: this is because there is no obvious indexing mechanism that can be used.
A potential avenue for speeding up the search is to preprocess the database, clustering shapes
according to their distance amongst themselves. Then, for example, if we have found that Q is far
from the database shape D 1 , and if the preprocessing tells us that D 1 is close to another database
shape D 2 , we might be able to infer that Q is sufficiently far from D 2 that we do not need to actually
compute the distance between Q and D 2 . Similarly, if Q is close to D 1 , and if the preprocessing
tells us that D 1 is far from D 2 , we might be able to infer that Q is sufficiently far from D 2 . For
this to work, we must be able to relate the distance between Q and D 2 to the distance between Q
and D 1 and the distance between D 1 and D 2 , for example, by the triangle inequality. The triangle
inequality for a distance measure d states that, for all A, B, and C,
In considering similarity measures between shapes, Arkin et al. (1990) say that such a measure
should be a metric. In particular, they say:
The triangle inequality is necessary since without it we can have a case in which d(A; B)
and d(B; C) are both very small, but d(A; C) is very large. This is undesirable for pattern
matching and visual recognition applications.
The theme of this paper is that we agree completely that a distance measure d where d(A; B)
and d(B; C) are both very small, but where d(A; C) is very large, is certainly undesirable. Instead,
we want a distance measure d to have the property that if A is close to B, and B is close to C,
then A is close to C. But to obtain this property, it is not necessary that d satisfy the triangle
inequality. Instead, it is sufficient for d to satisfy a "relaxed triangle inequality" of the form
where c is a constant that is not too large. We show that a measure used for distances between
shapes in the QBIC system satisfies a relaxed triangle inequality, although it does not satisfy the
triangle inequality.
What if we are in a scenario where a relaxed triangle inequality holds? Recalling the situation
described above, where we know distances d(Q; we want to conclude
something about d(Q; D 2 ), if d satisfies (1) and is symmetric we can infer the bounds
The first two inequalities correspond to the situations described earlier, where we conclude that Q is
sufficiently far from D 2 , without actually computing this distance. The third inequality corresponds
to a situation where we conclude that Q is sufficiently close to D 2 , by knowing that Q is close to
and that D 1 is close to D 2 . We note that this last case might not provide useful information
in a system such as QBIC, where we want to know, in the case of close matches, just how close the
match is (because the results are presented in sorted order based on closeness of match).
The remainder of the paper has three sections and an appendix. In Section 2, we formally define
the distance NEM r , one of the measures used in the QBIC system. In Section 3, the definition is
illustrated by an example. In Section 4, we sketch the proof of the relaxed triangle inequality; the full
proof is given in the appendix. We give the definitions and results in greater generality than for the
specific application to distances between shapes. The relaxed triangle inequality for shape distance
follows immediately from the more general results. We also show in Section 4 that the value of the
constant c we give in the relaxed triangle inequality is essentially the best possible within the more
general framework. However, for the specific application to shape distance, some smaller constant
might be possible, particularly when restricted to shapes meeting some naturalness property. In
Section 4 we remark on ways that the relaxed triangle inequality might be improved, by using
extra information contained in the boundary matching between two shapes (that is, in addition to
the NEM r -distance obtained from the boundary matching). An example of extra information that
could be helpful is the amount of stretching done. Such improvements may be necessary for the
relaxed triangle inequality to be useful in practice.
Even though the technical results in this paper apply to a specific distance measure, the results
carry a more general message: A distance measure should not be judged unsuitable simply because
it does not satisfy the triangle inequality; it might be possible to prove that the measure satisfies a
relaxed triangle inequality. Our specific results give a concrete example of this, by proving that a
natural measure of distance between shapes satisfies a relaxed triangle inequality, although it does
not satisfy the triangle inequality.
2 The Distance Measure NEM r
One intuitively appealing way to measure the distance between shapes is to measure how well the
boundary of one shape matches the boundary of the other, allowing either boundary to stretch
when doing the matching. This measure has been used, for example, in (Cortelazzo et al., 1994) for
trademark shapes and in (McConnell et al., 1991) for ice floes. As in (Cortelazzo et al., 1994), we
call this distance measure nonlinear elastic matching (NEM). After we define this measure formally,
we shall show that NEM does not satisfy the niceness property we discussed in the introduction:
it is possible for the NEM-distance between A and B to be small, and the NEM-distance between
and C to be small, with the NEM-distance between A and C being large. That NEM does not
satisfy the triangle inequality was known previously (cf. (Cortelazzo et al., 1994)); we show further
that it does not even satisfy a relaxed triangle inequality.
Niblack and Yin (1995) defined a modified version of NEM, which is essentially one of the methods
implemented in the QBIC system. It is related to a distance notion described in (McConnell
et al., 1991). Niblack and Yin's definition depends on a parameter r, a positive number, which we
call the stretching penalty. The idea, informally, is that we add to the distance an amount equal to
r times the amount of stretching that was done to make the two boundaries match. Thus, we pay a
penalty for excessive stretching. Letting NEM r denote the modified measure, we show that NEM r
satisfies a relaxed triangle inequality (1) with constant
increases. As we shall show in Section 3, the version of the NEM-distance involving a stretching
penalty as described in (McConnell et al., 1991) does not satisfy a relaxed triangle inequality.
We now consider the definition of NEM r . Fix some stretching penalty r - 0. (Although we
are primarily interested in the case r ? 0, we allow is equivalent to NEM, so
we get the definition of NEM as a special case.) Shortly, we shall define the distance NEM r (X; Y )
between two sequences
In general, we allow m 6= n and we allow the elements x i and y j of the sequences to belong to some
metric space S with distance metric b. We refer to (S; b) as the base. In particular, we assume that
b is symmetric and satisfies the triangle inequality for all points in S, and that b(x;
We show that the NEM r -distance satisfies a relaxed triangle inequality for any r ? 0 and
any S that is bounded, i.e., such that b sup is finite, where
The constant c in the relaxed triangle inequality depends on r and b sup . In the application to shape
matching, as we shall now discuss, the elements x i and y j represent tangent angles, and b measures
the difference between two angles. Hence, in this case,
so
We now discuss Niblack and Yin's approach to shape matching. We assume that each shape is
given by a simple (non-self-intersecting) closed curve in the plane. We measure how well a particular
point a on the boundary of one shape matches a particular point b on the boundary of another
shape as the difference between the tangent angle to the boundary at point a and the tangent angle
to the boundary at point b. Thus, we begin by replacing each shape by a sequence of tangent angles
taken at some number n of points spaced equally in distance around the boundary of the shape.
is the sequence of tangent angles for the first shape, and
the sequence of tangent angles for the second shape, then the NEM r -distance between the shapes
is taken to be the NEM r -distance (which we shall define shortly) between the sequences X and
Y . The NEM r -distance between two shapes depends on the "starting points" on the boundaries of
the two shapes (that is, where the comparisons begin). Ideally, the distance between two shapes
should be taken as the min of the distance over all possible starting points. In fact, Niblack and
Yin (1995) focus on this issue of starting points, based, for example, on the shape's moments. In
this paper, we shall not consider this issue: we will assume that the starting points are given. It
is easy to see that our results on the existence of a relaxed triangle inequality would continue to
hold even if we were to define the distance by taking the min of the distance over all possible
starting points. In the QBIC system, there is a fixed number of points, equally spaced around the
boundary of the shape, and so the starting point determines the sequence. Other papers consider
notions of distance that depend only on the shapes. For example, in (Arkin et al., 1990), where
a distance function is given for polygonal shapes, this distance function does not depend on any
other parameters such as auxiliary points taken along the boundary.
When we say that NEM r satisfies a relaxed triangle inequality NEM r (A; C) - c(NEM r (A; B)+
NEM r (B; C)), we mean that the constant c does not depend on the length of the sequences A; B; C.
In the application to shape matching, this means that c does not depend on the number of sample
points. Specifically, we show that works if the same number of sample points is
used for all shapes. If the number of sample points varies from shape to shape, we still obtain a
relaxed triangle inequality, but with the larger constant -=r). (One can imagine weaker
versions of the concept of a relaxed triangle inequality where the "constant" c might depend on the
dimensionality of the space from which the points A; B; C are drawn. However, for NEM r there is
no need to weaken it in this way.)
We return to the definition of NEM r (X; Y ). An (m; n)-mapping is a set
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta
\Theta

Figure

1: A minimal (9; 9)-mapping. The stretch-cost of this mapping is 6r.
where we call each pair hi; ji 2 M an edge, satisfying the following conditions:
1. Every number in f1; is the first component i of some edge hi;
2. Every number in f1; ng is the second component j of some edge hi;
3. No two edges "cross", that is, there do not exist
M .
An n)-mapping M is minimal if no proper subset of M is an (m; n)-mapping. Note that in
any minimal mapping, there cannot be three edges since the subset obtained by
removing the edge hi 0 ; ji is a mapping. For example, Figure 1 shows a minimal (9; 9)-mapping. We
sometimes refer to an (m; n)-mapping simply as a mapping when m and n are clear from context
or unimportant.
An edge hi; ji 2 M is a stretch-edge (of M) if either hi \Gamma . For an
edge hi; ji in the mapping M , define the stretch-cost of hi; ji with respect to M , as
r if hi; ji is a stretch-edge of M
For example, in the mapping shown in Figure 1, the edges h2; 3i; h3; 5i; h5; 6i; h6; 6i; h7; 6i and h9; 9i
are stretch-edges and each has stretch-cost r, while the other edges have stretch-cost 0.
the distance-cost of hi; ji with respect to the sequences X; Y , as
The stretch-cost and the distance-cost of the mapping M , the latter with respect to the sequences
Y , are defined by summing the respective costs of all edges in M ; that is
The (total) cost of M is given by
Finally,
is an (m; n)-mapping g:
In the sequel, we abbreviate d-cost(M;
the sequences X and Y are clear from context. Similarly, for an edge e in a mapping M , we may
abbreviate s-cost(e; M) by s-cost(e) when M is clear.
Clearly the value of NEM r (X; Y ) does not change if we minimize over only the minimal (m; n)-
mappings. It is also easy to see that NEM r (X; Y
n)-mapping M , the set of edges obtained by reversing the first and second components of each
edge in M gives an (n; m)-mapping M 0 having the same stretch-cost and the same distance-cost as
M .
Although this definition of NEM r (X; Y ) involves a search over a number of mappings that grows
exponentially in the minimum of m and n, it is well known that functions such as NEM r (X; Y )
can be computed in time O(mn) by dynamic programming (see, for example, (McConnell et al.,
1991; Cortelazzo et al., 1994; Niblack and Yin, 1995)). The algorithm iteratively computes the
quantities D(i; j), where D(i; j) is the NEM r -distance between the length-i prefix of X and the
length-j prefix of Y . The values of D(i; j) can be computed by D(1;
3 An Example
We now illustrate the definitions with a simple example. Another purpose of the example is to
show that the NEM-distance, where the stretching penalty r is 0, does not satisfy a relaxed triangle
inequality, and to show that the NEM r -distance does not satisfy the triangle inequality for a small
enough positive r. (In Section 4, we give a lower bound on the constant c in the relaxed triangle
inequality for NEM r ; since in particular this lower bound is bigger than 1 for every r, this shows
that for every r, the NEM r -distance fails to satisfy the triangle inequality.) The example in this
section also shows that the version of the NEM-distance involving a stretching penalty as described
in (McConnell et al., 1991) does not satisfy even a relaxed triangle inequality. Thus, it is important
how the stretching penalty r enters into the distance calculation: the method of (Niblack and Yin,
@
@
@
@
@
A

Figure

2: Three shapes used to illustrate distances between shapes.
1995), where r is additive, gives a relaxed triangle inequality, whereas that of (McConnell et al.,
1991), where r is multiplicative, does not.
Consider the three shapes shown in Figure 2. Note that each shape consists of five "short"
line segments and three "long" line segments. (Although the shapes in Figure 2 were chosen to be
polygons for simplicity, the NEM r -distance can be applied to more general shapes whose boundaries
are curved.) The first step is to convert each shape into a sequence of tangent angles by placing
sample points around the boundaries. To simplify the example suppose that, for each shape, one
sample point is placed on each short line segment, k sample points are placed along each of the two
long line segments that are part of the top of the shape, and m sample points are placed along the
long line segment forming the bottom of the shape. The total number of sample points is therefore
5. In each case we mark the starting point with an arrow, and we move clockwise
around the shape. These sample points give the following sequences of tangent angles:
z -
z -
7-
z -
z -
z -
z -
z -
z -
z -
Consider first NEM, where the stretching penalty r is 0. In Figure 2, 0: the small
triangular protrusion in shape B is stretched to perfectly match the large triangular protrusion in
shape A, and the short horizontal segments to the left and right of the large triangular protrusion
in shape A are stretched to exactly match the long horizontal segments to the left and right of the
small triangular protrusion in shape B; the rest of the boundaries of shapes A and B match exactly
without any stretching. For future reference, call this mapping the stretch mapping. For example,
the stretch mapping begins
Since a total of four short line segments of length 1 are stretched to match four long line segments
of length k, this mapping contains stretch-edges. But since r = 0, the stretch-cost
is 0. The distance-cost is 0 because each angle in angles(A) is mapped to the same angle in
angles(B). The NEM-distance between shapes B and C is small (although not zero): in this case,
the small triangular protrusion in shape B does not match the small square protrusion in shape
C, although this mismatch occurs only in a small part of the boundary, so the distance is small.
Specifically, -=2. The upper bound NEM(B;C) -=2 is shown by the
no-stretch mapping containing edges hi; ii for k-=2. The
lower bound, NEM(A;C) - k-=2, holds because the angles -=4 and 7-=4, occurring a total of
2k times in angles(A), differ by at least -=4 from every angle occurring in angles(C). The upper
shown by the no-stretch mapping. Since NEM(A;C) increases as k
increases, whereas NEM(A;B) and NEM(B;C) are constant independent of k, the NEM-distance
does not satisfy a relaxed triangle inequality (where the constant c is independent of the number
of sample points).
It is instructive to see why the example of Figure 2 does not cause the relaxed triangle inequality
to fail for NEM r , like it does for NEM. For NEM r , it is no longer true that the distance between A
and B is zero; it is not even "small". If we do much stretching to make the triangular protrusions
match at many points, then the distance includes a large term due to a large multiple of the
stretching penalty. If, on the other hand, we do little stretching, then the distance includes a
large term due to mismatch of tangent angles at many points. If we believe for aesthetic reasons
that shapes A and B are not "close", then another advantage of NEM r over NEM (in addition
to the advantage that NEM r satisfies a relaxed triangle inequality whereas NEM does not) is that
NEM r better fits our aesthetic idea of "closeness" of shapes. Although NEM r satisfies a relaxed
triangle inequality (as sketched in Section 4 and shown in the appendix), the shapes in Figure 2
show that it does not satisfy the triangle inequality if r ! -=8. First, NEM r
is shown by the stretch mapping; the distance-cost of this mapping is still 0 as above, but its
stretch-cost is now 4(k \Gamma 1)r. As above, NEM r (B; C) -=2 is shown by the no-stretch mapping.
But NEM r (A; C) - k-=2, by the same argument given above for NEM. Using these bounds, it is
easy to check that NEM r
Finally, we note that the version of the NEM-distance involving a stretching penalty as described
in (McConnell et al., 1991) does not satisfy a relaxed triangle inequality. In this version, the
stretching penalty r multiplies the distance-cost of a stretch-edge, instead of being added to it.
So we need r ? 1 in order that r impose a penalty. More formally, for sequences X and Y , a
mapping M between them, and an edge hi; ji in M , define cost
hi; ji is a stretch-edge of M , or b(x cost 0 (M;
cost 0 (e; M;X; Y ).
Let NEM 0
be the minimum cost 0 of a mapping between X and Y . The shapes in Figure 2
show that if r ? 1, then NEM 0
r does not satisfy a relaxed triangle inequality. The reason is that
r shown by the stretch mapping. The distance-cost of all edges is 0 in the
stretch mapping between A and B, so multiplying by r does not increase the cost. It is still true, as
described above for NEM, that NEM 0
r (A; C) - k-=2. So a relaxed triangle
inequality does not hold for NEM 0
r .
4 The Relaxed Triangle Inequality
In this section we show that NEM r satisfies a relaxed triangle inequality if r ? 0 and if b sup
is finite.
We consider first the case of equal-length sequences.
Theorem 4.1 For any base (S; b), any real r ? 0, any integer n ? 0, and any three sequences
Y; Z of length n,
Proof Sketch. We outline the main steps of the proof. A full proof is given in the appendix.
The basic strategy is to take a mapping MXY between X and Y having cost NEM r (X; Y ),
and a mapping M Y Z between Y and Z having cost NEM r (Y; Z), and paste them together in a
certain way to obtain a mapping MXZ between X and Z. The method of pasting together allows
us to place an upper bound on the cost of MXZ in terms of the cost of MXY and M Y Z , that is,
in terms of NEM r (X; Y ) and NEM r (Y; Z). And once we have an upper bound on the cost of some
mapping MXZ between X and Z, we have an upper bound on NEM r (X; Z). As a simple example,
suppose that the mappings MXY and M Y Z have no stretch-edges; i.e., these mappings both consist
of the edges hi; ii for 1 - i - n. Then we take MXZ to also consist of edges hi; ii for
Since the base distance b satisfies the triangle inequality (by assumption), it is easy to see that
the distance-cost of MXZ is at most the sum of the distance-cost of MXY and the distance-cost of
Y Z . Since the stretch-cost of all three mappings is zero, we actually get the triangle inequality,
Z), in this case. In general, however, the mappings MXY
and M Y Z can have stretch-edges, and this makes the construction of MXZ and the bounding of its
cost more complicated, and it also means that we do not get the triangle inequality in general.
Let MXY and M Y Z be minimal (n; n)-mappings such that
Since we will be referring to edges in different mappings, for clarity we name the points of X; Y; Z
using the notation x[i]; y[j]; z[k], respectively, for 1 - n. For example, an edge of MXY has
the form hx[i]; y[j]i for some i and j.
To prove the relaxed triangle inequality, we construct a minimal (n; n)-mapping MXZ and place
an upper bound on cost(MXZ ). Since we want to use the fact that b satisfies the triangle inequality
to help us bound the distance-cost of MXZ , we want MXZ to be a minimal (n; n)-mapping with
the following "midpoint property": For every edge hx[i]; z[k]i 2 MXZ , there is a "midpoint" y[j]
such that hx[i]; y[j]i 2 MXY and hy[j]; z[k]i 2 M Y Z . Then, the distance-cost of the edge hx[i]; z[k]i
is at most the sum of the distance-costs of hx[i]; y[j]i and hy[j]; z[k]i.
The first step is to show that some MXZ with the midpoint property exists. This is done in the
appendix by describing a construction of one such mapping by adding edges one at a time, such
that each added edge has a midpoint.
To bound the cost of MXZ , it is useful to divide the stretch-edges of a mapping into two classes,
depending on which sequence receives the stretching. For MXY , the stretch-edge hx[i]; y[j]i is an
X-stretch-edge if hx[i \Gamma 1]; y[j]i 2 MXY , or a Y -stretch-edge if hx[i];
cannot cross, exactly one of these holds). For M Y Z , the stretch-edges are divided similarly into
Y -stretch-edges and Z-stretch-edges. It is also useful to divide the stretch-cost of a mapping into
two parts, based on this division of the stretch-edges, as follows. Define X-s-cost(MXY ) (resp.,
Y -s-cost(M XY )) to be r times the number of X-stretch-edges (resp., Y -stretch-edges) of MXY .
Similarly define Y -s-cost(M Y Z ) and Z-s-cost(M Y Z ). Since X and Y have the same length, the
number of X-stretch-edges of MXY equals the number of Y -stretch-edges of MXY . Therefore, we
have the following equalities involving the stretch-cost s-cost :
Similarly, since Y and Z have the same length,
To prove the relaxed triangle inequality, it suffices to prove the following two bounds on the
stretch-cost s-cost and the distance-cost d-cost of MXZ .
Claim 1.
2.
r
The relaxed triangle inequality stated in the theorem follows by algebraic manipulation from
these two claims and (2), (3), (4), and (5).
To justify Claim 1, with each stretch-edge in MXZ we associate a distinct stretch-edge in either
MXY or M Y Z . Clearly such an association (which is given in the appendix) suffices to prove
Claim 1.
The final step is to justify Claim 2. Since we know that MXZ has the midpoint property, we
would like to use the fact that b satisfies the triangle inequality. A complication is shown by the
situation in Figure 3 where the distance-cost of hx[i]; y[j]i contributes t times to the distance-cost
of MXZ . The key observation in handling this complication is that each of the contributions
of d-cost(hx[i]; y[j]i) after the first contribution can be "balanced" by a Z-stretch-edge of M Y Z
that contributes r to the stretch-cost of M Y Z . There is a symmetric case where an edge in M Y Z
contributes several times to the distance-cost of MXZ , and the symmetric case is handled similarly,
using X-stretch-edges of MXY for the balancing. For more details, see the appendix. 2
A
A
A
A
A
A
A
A
c
c
c
c
c
c
c
c
c
c

Figure

3: A situation where the distance-cost of hx[i]; y[j]i contributes t times to the distance-cost
of MXZ .
Remark. We suggest two ways that the relaxed triangle inequality might be improved. First,
Claims 1 and 2 and (2), (3), (4), and (5) actually give the potentially tighter bound
where MXY and M Y Z are any mappings with NEM r (X; Y
Therefore, in the application to image databases mentioned in the introduction, it
might be advantageous in the clustering of database shapes to keep track of the stretch-cost of
mappings as well as their total cost. It is easy to modify the dynamic programming algorithm
to compute, together with the minimum total cost of a mapping, the minimum stretch-cost of a
mapping among the mappings having minimum total cost.
Second, in the proof of Claim 2, we use b sup as an upper bound on the distance-cost of any edge
in MXY and M Y Z . Therefore, another way to improve the relaxed triangle inequality in practice
would be to replace the gross upper bound b sup
by the actual maximum distance-cost of edges in
MXY and M Y Z . This would require computing and storing these maximum distance-costs during
the clustering preprocessing.
Although the remark above shows that we might get a better bound on NEM r (X; Z) in certain
cases, the next result shows that the constant (1 in the general relaxed triangle
inequality is essentially the best possible. The proof is given in the appendix.
Theorem 4.2 For any base (S; b) with b sup ? 0, any real r ? 0, and any real " ? 0, there is an
integer n and three sequences X; Y; Z of length n such that
We now give analogues of Theorems 4.1 and 4.2 for the case of unequal-length sequences.
The results are similar, except that the constant in the relaxed triangle inequality increases to
=r). The proofs in the unequal-length case are very similar to the proofs in the equal-length
case. The differences are outlined in the appendix.
Theorem 4.3 For any base (S; b), any real r ? 0, and any three sequences X; Y; Z,
Theorem 4.4 For any base (S; b) with b sup
real r ? 0, and any real " ? 0, there are three
sequences X; Y; Z such that

Acknowledgment

. We are grateful to Byron Dom, Martin Farach, Myron Flickner, Wayne
Niblack, Prabhakar Raghavan, and Baruch Schieber for helpful discussions and comments.



--R

An efficiently computable metric for comparing polygonal shapes
Trademark shapes description by string-matching techniques
Comparing images using the Hausdorff distance under translation
Fundamentals of Digital Image Processing



Mathematical theories of shape: do they model perception?

The QBIC project: querying images by content using color

A pseudo-distance measure for 2D shapes based on turning angle
Retrieving images by 2D shape: a comparison of computation methods with human perceptual judgments
Recognition and positioning of rigid objects using algebraic moment invariants
--TR

--CTR
Per-Ola Kristensson , Shumin Zhai, Relaxing stylus typing precision by geometric pattern matching, Proceedings of the 10th international conference on Intelligent user interfaces, January 10-13, 2005, San Diego, California, USA
Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
Yong-Sheng Chen , Yi-Ping Hung , Ting-Fang Yen , Chiou-Shann Fuh, Fast and versatile algorithm for nearest neighbor search based on a lower bound tree, Pattern Recognition, v.40 n.2, p.360-375, February, 2007
K. Seluk Candan , Prakash Yamuna, Similarity-Based Retrieval of Temporal Specifications and its Application to the Retrieval of Multimedia Documents, Multimedia Tools and Applications, v.27 n.1, p.143-180, September 2005
image database;distance measure;triangle inequality;shape matching;pattern matching