From:boxer@acsu.buffalo.edu (Laurence Boxer)Newsgroups:comp.theorySubject:Re: metrics for resemblanceKeywords:computational geometry/visionDate:14 Jan 92 17:42:25 GMTOrganization: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.theorySubject:Re: metrics for resemblanceKeywords:computational geometry/visionDate:14 Jan 92 17:53:16 GMTOrganization: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.researchSubject:Re: Distance between setsDate:4 Jun 92 06:56:47 GMTOrganization: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