Efficient 2-dimensional approximate matching of non-rectangular figures
Amihood Amir, Martı́n Farach-Colton · 1991
Finding all occurrences of a non-rectangular pattern of height m and area a in an nn 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(an 2). We show a O(kn 2 # m log m # k log k + k 2 n 2) 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.