On curve matching
- 1 May 1990
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 12 (5) , 483-489
- https://doi.org/10.1109/34.55108
Abstract
Two algorithms to find the longest common subcurve of two 2D curves are presented. These algorithms are 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 find the longest matching subcurve. The first algorithm is of complexity O(n), where n is the number of sample points on the curves. The second one, while being theoretically somewhat less efficient, proved to be robust and efficient in practical applications. Both algorithms solve the problem of general curves without being dependent on some set of special points on the curves. The algorithms have industrial applications to problems of object assembly and object recognition. Experimental results are included. The algorithms can be easily extended to the 3D case.Keywords
This publication has 13 references indexed in Scilit:
- An improved model-based matching method using footprintsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On curve matchingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1990
- Solving jigsaw puzzles by computerAnnals of Operations Research, 1988
- Two-Dimensional, Model-Based, Boundary Matching Using FootprintsThe International Journal of Robotics Research, 1986
- HYPER: A New Approach for the Recognition and Positioning of Two-Dimensional ObjectsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Recognizing Partially Occluded PartsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Euclidean shortest paths in the presence of rectilinear barriersNetworks, 1984
- Shape description via the use of critical pointsPattern Recognition, 1978
- A Space-Economical Suffix Tree Construction AlgorithmJournal of the ACM, 1976
- Linear pattern matching algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1973