ON CURVE MATCHING

Two algorithms to find the longest common subcurve of two 2-D 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. Then direct curve matching is applied to 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 for 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 3-D case. © 1990 IEEE