An efficiently computable metric for comparing polygonal shapes
IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 1 March 1991
Esther M. Arkin, L. Paul Chew, D.P. Huttenlocher, Klara Kedem, Joseph S. B. Mitchell
Citations622
SJR quartileQ1
SJR score3.91
SNIP5.99
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A method for comparing polygons that has these properties and works for both convex and nonconvex polygons and runs in time O(mn log mn) where m is the number of vertices in one polygon and n is the size of the polygons in the other.
Abstract
A method for comparing polygons that is a metric, invariant under translation, rotation, and change of scale, reasonably easy to compute, and intuitive is presented. The method is based on the L/sub 2/ distance between the turning functions of the two polygons. It works for both convex and nonconvex polygons and runs in time O(mn log mn), where m is the number of vertices in one polygon and n is the number of vertices in the other. Some examples showing that the method produces answers that are intuitively reasonable are presented.>
Keywords
Computer Science
The International Journal of Robotics ResearchIdentification of Partially Obscured Objects in Two and Three Dimensions by Matching Noisy Characteristic Curves
231 Citations1987Jacob T. Schwartz, Micha Sharir
Efficient methods for smoothing the noisy data and for matching portions of the observed object boundaries (or of characteristic curves lying on bounding surfaces of 3-D objects) to prestored models are described.
IEEE Transactions on Pattern Analysis and Machine IntelligenceOn curve matching
223 Citations1990Haim J. Wolfson
Two algorithms to find the longest common subcurve of two 2D curves are presented, based on conversion of the curves into shape signature strings and application of string matching techniques to find long matching substrings, followed by direct curve matching of the corresponding candidate subcurves to finding the longest matching subCurve.
Computing the minimum Hausdorff distance for point sets under translation
120 Citations1990Daniel P. Huttenlocher, Klara Kedem
The problem of computing a translation that minimizes the Hausdorff distance between two sets of points is considered and the results for the one-dimensional case are applied to the problem of comparing polygons under general affine transformations, where they extend the recent results of Arkin et al on polygon resemblance under rigid body motion.
IEEE Transactions on Pattern Analysis and Machine IntelligenceOrganization of Relational Models for Scene Analysis
104 Citations1982Linda G. Shapiro, Robert M. Haralick
A simple relational distance measure is defined, it is proved it is a metric, and using this measure, two organizational/access methods are described: clustering and binary search trees.
An improved model-based matching method using footprints
37 Citations2003Jiawei Hong, Haim J. Wolfson
A method for recognition of partially occluded and overlapping objects in composite scenes is presented and experimental results from large databases are presented, including results that could not be obtained by the previous technique.
Pattern Recognition LettersOptimal matching of convex polygons
34 Citations1989Pedro Cox, Henri Maı̂tre +2 more
A solution method, based on nonlinear programming techniques, is presented for the problem of matching two series of observations of a 2-D contour, in which each sampling of the contour has different hidden parts.
IEEE Transactions on Information TheoryA combinational approach to polygon similarity
28 Citations1983David Avis, Hossam ElGindy
A new approach is presented to the classification problem of planar shapes represented by polygons where a shape is abstracted combinatorially by means of its visibility graph, and two shapes are deemed similar whenever their graphs are cyclically isomorphic.
Machine intelligence and pattern recognitionCurve Similarity via Signatures
20 Citations1985
It is demonstrated in several experiments that the signature distance between two curves has appealing behavior, especially when applied to slanted handwriting samples.
Recognize The Similarity Between Shapes Under Affine Transformation
12 Citations2005Hong Jai-Wei, Xiaonan Tan
The canonical form of a shape is introduced and a linear algorithm for transforming a shape to its canonical form and this approach reduces the similarity recognition under affine transformation from a search problem in six dimensional space into one dimensional search problem.