Abstract: This paper researches relative chain codes and some string matching algorithms. It realizes two shapes’ matching by using relative chain codes and the improved LCS algorithm. First, through the contour extraction algorithm, we get the shapes contour, then, we get the Freeman chain codes through the contour tracking algorithm, and get the relative chain codes by computing chain codes, at last, using the improved longest common subsequences algorithm, we compute the similarity of two shapes. The method is of less computation, good effect on moving shape and rotating invariance. And it is implemented on Android system, the experimental results show that it is an effective method to decide whether two shapes are similar to each other.


Key words: Freeman chain codes, relative chain codes, longest common subsequences, shape matching, contour extraction