Classification Of Partial Shapes Using String-To-String Matching
Hong-Chih Liu, Mandyam D. Srinath · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1989
In this paper, we present an algorithm that enables us to recognize a partial shape without regard to its size, rotation or location. The algorithm uses the curvature function obtained from the digital representation of the shape. The curvature function is next represented by a string, by slicing it with horizontal lines. By using as primitives the sign of the curvature function slope within a pair of such lines, a symbol string is obtained which describes the relative amplitude of the peaks and valleys on the waveform and is invariant to size or location of the object within the scene. Since the curvature function is periodic, it can be made rotation invariant by suitably choosing the start point of the string. The resulting strings are matched using a standard measure of dissimilarity such as the number of operations such as substitution, deletion and insertion needed to transform one string to another. To obtain rotation invariance, we determine the dissimilarity measure by trying all the characters of one string (the test string) as start points. The algorithm has been successfully tested on several partial shapes, using two sets of data. The first set consisted of 4 classes of various types of aircraft, while the second set consisted of shapes of different lakes. The algorithm works reasonably well even in the presence of a moderate amount of noise.