From: boxer@acsu.buffalo.edu (Laurence Boxer)
Newsgroups: comp.theory
Subject: Re: metrics for resemblance
Keywords: computational geometry/vision
Date: 14 Jan 92 17:42:25 GMT
Organization: State University of New York at Buffalo/Comp Sci
In article <24949@skye.dcs.ed.ac.uk> pwg@dcs.ed.ac.uk (Paul Goldberg) writes:
>
> I would like to know some examples of metrics on geometrical objects
>(in particular polygons in the plane) which reflect some intuitive
>notion of resemblance. That is, if two polygons "look similar" then their
>distance apart using the metric will be small. Examples of the sort of
>thing I'm looking for is the Hausdorff metric, usable for many classes
>of point sets, or for polygons in particular the Frechet metric.
>
> I have heard that there are many other metrics which are intended to do
>a similar job, but I don't know about them. Can anyone mail me some
>pointers/references to these? I am particularly interested in ones for
>which the distance between two polygons is unique modulo classes of
>translation/rotations, but right now all are welcome.
>
>Paul Goldberg
>pwg@dcs.ed.ac.uk
\begin{thebibliography}{XXXX99X}
\bibitem{Alt&etal}
Alt, H.; Behrends, B.; and Bl\"{o}mer, J. (1991).
Approximate matching of polygonal shapes,
{\em Proceedings ACM Symp. on Computational Geometry}, 186-193.
\bibitem{Atallah:1}
Atallah, M.J. (1983).
A linear time algorithm for the Hausdorff distance between convex polygons,
{\em Information Processing Letters} 17, 207-209.
\bibitem{Beyer:1}
Beyer, W.T. (1969).
Recognition of topological invariants by iterative arrays,
Ph.D. thesis, Dept. of Math., MIT.
\bibitem{Bhattacharya&ElGindy:1}
Bhattacharya, B.K. and El Gindy, H. (1984).
A new linear convex hull algorithm for simple polygons,
{\em IEEE Trans. on Information Theory} IT-30, 85-88.
\bibitem{Borsuk:1}
Borsuk, K. (1954).
On some metrizations of the hyperspace of compact sets,
{\em Fundamenta Mathematicae} 41, 168-202.
\bibitem{Borsuk:3}
Borsuk, K. (1977).
On a metrization of the hyperspace of a metric space,
{\em Fundamenta Mathematicae} 94, 191-207.
\bibitem{Boxer:1}
Boxer, L. (1983).
Hyperspaces where convergence to a calm limit implies eventual
shape equivalence,
{\em Fundamenta Mathematicae} 115, 213-222.
\bibitem{Cerin:1}
\v{C}erin, Z. (1979).
$\cal C$-calmly regular convergence,
{\em Topology Proceedings} 4, 29-49.
\bibitem{Cerin:2}
\v{C}erin, Z. (1980).
$\cal C$-movably regular convergence,
{\em Houston J. of Math.} 6, 471-490.
\bibitem{Dugundji:1}
Dugundji, J. (1966).
{\em Topology},
Allyn and Bacon, Boston.
\bibitem{Huttenlocher&Kedem}
Huttenlocher, D.P., and Kedem, K. (1990).
Computing the minimum Hausdorff distance for point sets under translation,
{\em Proc. ACM Symp. on Computational Geometry}, 340-349.
\bibitem{Nadler:1}
Nadler, S.B., Jr. (1978).
{\em Hyperspaces of Sets},
Marcel Dekker, Inc., New York.
\bibitem{Shonkwiler:1}
Shonkwiler, R. (1989).
An image algorithm for computing the Hausdorff distance efficiently in
linear time,
{\em Information Processing Letters} 30, 87-89.
\bibitem{Stern:1}
Stern, H.I. (1989).
Polygonal entropy: a convexity measure,
{\em Pattern Recognition Letters} 10, 229-235.
\bibitem{Stout:1}
Stout, Q.F. (1983).
Topological matching,
{\em Proc. 15th Annual ACM Symposium on Theory of Computing}, 24-31.
\end{thebibliography}
From: boxer@acsu.buffalo.edu (Laurence Boxer)
Newsgroups: comp.theory
Subject: Re: metrics for resemblance
Keywords: computational geometry/vision
Date: 14 Jan 92 17:53:16 GMT
Organization: State University of New York at Buffalo/Comp Sci
Topologists have written a number of papers concerned with this notion,
namely, describing a metric in which closeness implies not only
closeness with respect to the Hausdorff metric, but also resemblance
of figures with respect to some topological or geometric property.
Unfortunately, from the standpoint of computer science, most are
unsatisfactory for the following reasons:
a) Most of the interesting results obtained by topologists
for these metrics are along the lines of: Suppose two
figures A and B are sufficiently close in such a metric.
Then they have in common the following properties ....
where the properties in question are often not of interest
to computational geometers.
b) Most of the metrics described by the topology papers
written for this purpose (at least, those papers I've
read) are difficult or impractical to compute.
I have a paper, soon to appear in Pattern Recognition Letters,
in which I describe several metrics in which closeness of two
polygons A and B implies that A and B are close with respect
to the Hausdorff metric and that they have similar deviations
from convexity. The results aren't real deep, nor are they
always satisfying from the standpoint of the goal of describing
a metric that is efficiently computable and in which closeness
would imply "similar geometry" -- but the paper is a start
in the direction of developing efficiently-computable metrics
that are stronger than the Hausdorff metric with respect to
measuring how well one figure approximates another geometrically,
as well as positionally. The paper of Stern, cited below, is
another such attempt.
Below are some references on metrics (Hausdorff and beyond).
Some are topology references that may be useful to computational
geometers only from the standpoint of originating the suggestion
of adding another comparison of two figures to their Hausdorff
distance in order to obtain a stronger metric. Others are
computational geometry references.
Atallah, M.J. (1983).
A linear time algorithm for the Hausdorff distance between convex polygons,
Information Processing Letters 17, 207-209.
Borsuk, K. (1954).
On some metrizations of the hyperspace of compact sets,
Fundamenta Mathematicae 41, 168-202.
Borsuk, K. (1977).
On a metrization of the hyperspace of a metric space,
Fundamenta Mathematicae 94, 191-207.
Boxer, L. (1983).
Hyperspaces where convergence to a calm limit implies eventual
shape equivalence,
Fundamenta Mathematicae 115, 213-222.
Cerin, Z. (1979).
C-calmly regular convergence,
Topology Proceedings 4, 29-49.
Cerin, Z. (1980).
C-movably regular convergence,
Houston J. of Math. 6, 471-490.
Huttenlocher, D.P., and Kedem, K. (1990).
Computing the minimum Hausdorff distance for point sets under translation,
Proc. ACM Symp. on Computational Geometry, 340-349.
Nadler, S.B., Jr. (1978).
Hyperspaces of Sets,
Marcel Dekker, Inc., New York.
Shonkwiler, R. (1989).
An image algorithm for computing the Hausdorff distance efficiently in
linear time,
Information Processing Letters 30, 87-89.
Stern, H.I. (1989).
Polygonal entropy: a convexity measure,
Pattern Recognition Letters 10, 229-235.
I hope this is helpful.
Dr. Laurence Boxer Permanent address:
Department of Computer Science Department of Computer
SUNY - Buffalo and Information Sciences
Buffalo, NY Niagara University
Niagara University, NY 14109
From: fry@tara.harvard.edu (David Fry)
Newsgroups: sci.math.research
Subject: Re: Distance between sets
Date: 4 Jun 92 06:56:47 GMT
Organization: Harvard Math Department
In article <1992Jun3.200054.22189@pasteur.Berkeley.EDU> luzeaux@roma.berkeley.edu (Dominique Luzeaux) writes:
>In article <1603@junon.thomson-lcr.fr>, juliette@thomson-lcr.fr
>(Juliette Mattioli) writes:
>|> I am looking for distances between sets, or compact sets of R^n. The
>question
>|> is : How can I characterize that two compact sets are shape close.
>
>Looks like you could use a dilatation operator on your set, and then use
>Haussdorff.
>
>By the way, how do you define shape? If it has some relationship with measure,
>then if your sets are given by union of some sets, get first rid of the
>null-measure
>sets.
>
>I would use the first method. There is a metric used in image processing which
>does about what you want, but I do not remember the name (sorry!, it is
>not my field,
>I just used to do maths with some of these guys). It definitely had
>something to do with
>dilatation.
You're thinking of "mathematical morphology," the image processing
area that uses dilation. The Hausdorff metric has been called the
basis of mathematical morphology, for whatever that's worth.
As the original post hinted, the Hausdorff metric is sensitive to
outlying points in a shape. The so-called template metric, the other
one mentioned in the original post ( d(x,y) = area(x-y) + area(y-x),
where x and y are shapes ), ignores outliers, and the construction
of the Minkowski sum of a shape and a small ball (i.e. dilation)
is not continuous in this metric.
The issue of what is a "shape" is, of course, important, but we in the
image processing world try to ignore such details when possible. I
realize that's not appropriate here. In general, the natural domain
of the Hausdorff metric is the set of compact shapes, and the natural
domain of the template metric is the space of measurable subsets. As
noted, we can ignore sets of measure zero for the template metric, but
not for the Hausdorff metric.
But there are many other ways to define metrics between shapes. One I
use in my work is the transport, or Monge-Kantorovich metric:
For S_1,S_2 subsets of the real plane, d(S_1,S_2) =
inf { int_{S_1} int_{S_2} abs(x_1 - x_2) dp(x_1,x_2) },
where the inf is taken over all probability measures p on S_1 x S_2
with fixed marginals:
int_{S_1} int_{U_2} dp(x_1,x_2) = area(U_2)/area(S_2),
int_{U_1} int_{S_2} dp(x_1,x_2) = area(U_1)/area(S_1).
Think of this as the amount of work required to rearrange the pieces
of shape S_1 into the shape of S_2. The transport metric is a good
combination of the template and Hausdorff metrics in practice, since
it gives equal weight to all points of a shape. Its natural domain is
the space of probability measures, if we assign a measure
p_S (U) = area(S \cap U) / area(S)
to each shape S. In this way we can also discuss "fuzzy shapes,"
where membership in a shape near a boundary is not a binary
decision.
The transport metric can be quickly calculated with linear
programming.
Another popular metric in image processing now has been studied at
Brown: the optimal diffeomorphism metric d(S_1,S_2) =
inf { int_{S_1} |Jp|^2 + int_{S_2} |J(p^{-1})|^2 },
where the inf is taken over all one-to-one, onto differentiable
maps p:S_1 -> S_2 with inverse p^{-1}, and J is its Jacobian.
The main problem with this metric is that two shapes identical except
for an infinitesimal tear will be infinitely far apart because they
are not topologically equivalent and admit no diffeomorphisms.
There have been extensions and changes to this metric to deal with
these situations.
Note that the question of "what metric to use to find a distance
between shapes" is very dependent on what you're trying to do. I
think the transport metric gives answers that are fairly close to what
humans would give, but if you're trying to find a hairline crack
defect in a machine tool, that's not a very good solution. So
consider your needs while you're considering your metrics.
Suggested references:
David Mumford, "Mathematical theories of shape: do they model
perception?", _SPIE Proceedings Volume 1570_, San Diego, 1991.
David Mumford, "The problem of robust shape descriptors,"
_Proceedings of the IEEE First International Conference on Computer
Vision_, London, 1987, 602-606.
S. Rachev, "The Monge-Kantorovich mass transference problem and
its stochastical applications", _Theory of Probability and
Applications_, volume 29 (1985), 647-676.
Y. Amit, "A non-linear variational problem for image matching",
preprint, Brown Department of Applied Mathematics, 1991.
This is the basic topic of my PhD thesis, so I'd love to have any
other references people can provide.
David Fry fry@math.harvard.EDU
Division of Applied Sciences fry@huma1.bitnet
Harvard University ...!harvard!huma1!fry
Cambridge, MA 02138