基于相对链码和改进 LCS 算法的图形匹配实现

研究相对链码和字符串的匹配算法，采用相对链码和改进的LCS算法实现图形的轮廓匹配。首先通过轮廓提取算法得到图形的轮廓，再通过轮廓跟踪算法得到轮廓的链码，由链码计算得到图形的相对链码，最后采用改进的最大公共子串算法计算两图形的相似度。该图形轮廓匹配算法具有计算量小，平移、旋转的不变性等优点。在Android系统上进行实验，实验结果表明该算法计算速度快，与人的视觉相吻合。

Implementation of Shape Matching Based on Relative Chain Codes and Improved LCS Algorithm

This paper researches relative chain codes and some string matching algorithms .It realizes two shapes ’ matching by u-sing relative chain codes and the improved LCS algorithm .First, through the contour extraction algorithm , we get the shapes con-tour, 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 .