基于后缀树的图像识别研究

Research of Image Recognition Based on Suffix Tree

分析了后缀树在一维和二维字符串处理方面的优势,以后缀树为索引,将后缀树和最低公共祖先问题相结合,提出了一个在仅考虑平移变换操作的条件下,进行图像精确识别的算法,并从时间复杂度上证明了其优于传统的二维精确模式匹配算法。

The suffix tree is a versatile data structure. After analyzing its advantages of processing one-dimensional and two-dimensional strings, this paper makes use of the suffix tree as an index and combines the suffix tree and the problem of lowest common ancestor. Then, on the condition of the translation operation only, an algorithm applied to exact image recognition is proposed and proved outperforming the traditional two-dimensional exact pattern matching from the time complexity.