Matching shapes with a reference point

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Matching shapes with a reference point

Full text

Pdf (630 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the tenth annual symposium on Computational geometry table of contents

Stony Brook, New York, United States

Pages: 85 - 92

Year of Publication: 1994

ISBN:0-89791-648-4

Authors

Helmut Alt	Freie Universität Berlin, Fachbereich Mathematik und Informatik, Takustraβe 9, D-14195 Berlin, Germany
Oswin Aichholzer	Institut fur Grundlagen der Informationsverarbeitung, Technische Universität Graz, Schieβstattgasse 4, A-8010 Graz, Austria
Günter Rote	Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, A-8010 Graz, Austria

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 24, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/177424.177555 What is a DOI?

ABSTRACT

For two given point sets, we present a very simple (almost trivial) algorithm to translate one set so that the Hausdorff distance between the two sets is not larger than a constant factor times the minimum Hausdorff distance which can be achieved in this way. The algorithm just matches the so-called Steiner points of the two sets. The focus of our paper is the general study of reference points (like the Steiner point) and their properties with respect to shape matching. For more general transformations than translations, our method eliminates several degrees of freedom from the problem and thus yields good matchings with improved time bounds.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	ABB	Helmut Alt , Bernd Behrends , Johannes Blömer, Approximate matching of polygonal shapes (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.186-193, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109669]
	AG	H. ALT, M. GODAU, Computing the Hausdorff-distance in Higher Dimensions, in preparation.
	AST	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.72-82, September 1992, Orlando, Florida, United States
	B	B. BEHRENDS, "Algorithmen zur Erkennung der e-Kongruenz yon Punktmengen und Polygonen", Diplomarbeit, FB Mathematik, Freie Universitgt Berlin, 1990.
	CGHKKK	P. P. CHEW, M. T. GOODRICH, D. P. HUTTENLOCHER, K. KEDEM, J. M. KLEINBERG, D. KRAVETS, Geometric pattern matching under Euclidean motion, Proc. 5th Canadian Conference on Computational Geometry, 1993, pp. 151-156.
	CKS	P.P. CHEW~ K. KEDEM, S. SCHIRRA, On chracteristic points and approximate decision algorithms for Hausdorff distance, Report, Max-Planck-Institut fiir Informatik, Saarbriicken, 1993.
	G	B. GRi~NBAUM, Convex Polytopes, Wiley & Sons, 1967.
	H	Paul J. Heffernan, Generalized Approzimate Algorithms for Point Set Congruence, Proceedings of the Third Workshop on Algorithms and Data Structures, p.373-384, August 11-13, 1993
	HS	Paul J. Heffernan , Stefan Schirra, Approximate decision algorithms for point set congruence, Proceedings of the eighth annual symposium on Computational geometry, p.93-101, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142697]
	HK	Daniel P. Huttenlocher , Klara Kedem, Computing the minimum Hausdorff distance for point sets under translation, Proceedings of the sixth annual symposium on Computational geometry, p.340-349, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98599]
	HKS	D. P. HUTTENLOCHER, K. KEDEM, M. SHAalI~, The upper envelope of Voronoi surfaces and its applications, Discrete and Computational Geometry~ 9 (1993)~ 267- 291.
	HKR	D. P. Huttenlocher , G. A. Klanderman , W. A. Rucklidge, Comparing Images Using the Hausdorff Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.850-863, September 1993 [doi>10.1109/34.232073]
	S	G.C. SHEPHAI{D, The Steiner point of a convex polytope, Canadian J. Math., 18 (1966), 1294-1300.
	Sch	R. SCHNBiDER, Kriimmungsschwerpunkte konvexer KSrper, Abh. Math. Sere. Hamburg 37 (1972), 112-132.

CITED BY 4

	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
	Minkyoung Cho , David M. Mount, Embedding and similarity search for point sets under translation, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Goce Trajcevski , Hui Ding , Peter Scheuermann , Roberto Tamassia , Dennis Vaccaro, Dynamics-aware similarity of moving objects trajectories, Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, November 07-09, 2007, Seattle, Washington
	Kaleem Siddiqi , Juan Zhang , Diego Macrini , Ali Shokoufandeh , Sylvain Bouix , Sven Dickinson, Retrieving articulated 3-D models using medial surfaces, Machine Vision and Applications, v.19 n.4, p.261-275, May 2008