TY - GEN
T1 - Efficient 2-dimensional approximate matching of non-rectangular figures
AU - Amir, Amihood
AU - Farach, Martin
N1 - Publisher Copyright:
© 1991 Association for Computing Machinery. All rights reserved.
PY - 1991/3/1
Y1 - 1991/3/1
N2 - 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 log m √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.
AB - 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 log m √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.
UR - http://www.scopus.com/inward/record.url?scp=84989853970&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84989853970&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84989853970
SN - 0897913760
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 212
EP - 223
BT - Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
PB - Association for Computing Machinery
T2 - 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
Y2 - 28 January 1991 through 30 January 1991
ER -