Efficient 2-dimensional approximate matching of non-rectangular figures
Efficient 2-dimensional approximate matching of non-rectangular figures
复制标题
非矩形图形的高效二维近似匹配
DOI：
10.1006/inco.1995.1047
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
Martín Farach
中科院分区：
文献类型：
--
作者：
A. Amir;Martín Farach
在不超过K不匹配，插入和删除错误的N×n文本中，找到所有高度M和A区域A的所有出现是计算机视觉中的重要问题。时间O（AN2）。提出了解决这两个问题的有效算法853-0083;
Finding all occurrences of a non-rectangular pattern of height m and area a in an n×n text with no more than k mismatch, insertion, and deletion errors is an important problem in computer vision. It can be solved using a dynamic programming approach in time O(an2). We show a O(kn2 √ m logm √ k log k + k2n2) algorithm which combines convolutions with dynamic programming. At the heart of the algorithm are the Smaller Matching Problem and the k-Aligned Ones with Location Problem. Efficient algorithms to solve both these problems are presented. The results presented in this paper appeared in the proceedings of the Second Symposium on Descrete Algorithms [AF91] College of Computing, Georgia Institute of Technology, Atlanta, GA 30332-0280; (404) 853-0083; amir@cc.gatech.edu; Partially supported by NSF grant IRI-9013055. DIMACS, Box 1179, Rutgers University, Piscataway, NJ 08855; (908) 932-5928; farach@dimacs.rutgers.edu