Partial matching of planar polylines under similarity transformations
Scott D. Cohen, Leonidas Guibas · 1997
Given two planar polylines T and P with n and m edges, respectively, we present an O(m 2 n 2 ) time, O(mn) space algorithm to find portions of the "text" T which are similar in shape to the "pattern" P . In the common case of a simple pattern, such as a line segment or corner, m = O(1) and our algorithm requires O(n 2 ) time and O(n) space. We use the well-known arclength versus cumulative turning angle graph to judge how well a scaled, rotated, and translated version of the pattern matches a piece of the text. Our match scoring function balances the length of a match against the mean squared error in the match; given two matches with the same mean squared error (length), the longer (lower mean squared error) match will have a higher score. The match score is a function of the pattern scale, orientation, and position within the text, and our algorithm seeks to find local maxima of the scoring function. An analytic formula for the highest scoring pattern orientation in terms of sc...