USING CYCLIC STRING MATCHING TO FIND ROTATIONAL AND REFLECTIONAL SYMMETRIES IN SHAPES

Symmetry is one of the shape features that is often used in computer vision. Some computer vision systems use symmetry-based indexing functions to retrieve images from an image database. Other computer vision applications need to detect the orientation of a shape before it is matched with a model and, if the shape is rotationally symmetric, a specific method has to be developed to find the principal axes of the shape. Symmetry is also useful to recover a planar symmetric figure from an image without the need of models. In this paper, a simple and fast method to detect perfect and distorted rotational symmetries of 2D objects is described. The boundary of a shape is polygonally approximated and represented as a string. A key observation is that the boundary of a rotationally symmetric shape consists of a sequence of identical substrings. Rotational symmetries are found by cyclic string matching between two identical copies of the shape string. The set of minimum cost edit sequences that transform the shape string to a cyclically shifted version of itself define the rotational symmetry and its order. Finally, it is observed that it is possible to find out if a shape string is reflectionally symmetric by computing the cyclic string matching between the string and a reversed version of itself. Thus, a modification of the algorithm is proposed to detect reflectional symmetries. Some experimental results are presented to show the reliability of the proposed algorithm.