Efficient 2-dimensional approximate matching of half-rectangular figures

Amihood Amir, Martin Farach

Research output: Contribution to journalArticlepeer-review

53 Scopus citations

Abstract

Efficient algorithms exist for the approximate two dimensional matching problem for rectangles. This is the problem of finding all occurrences of an m × m pattern in an n × n text with no more than k mismatch, insertion, and deletion errors. In computer vision it is important to generalize this problem to non-rectangular figures. We make progress towards this goal by defining half-rectangular figures of height m and area a. The approximate two dimensional matching problem for half-rectangular patterns can be solved using a dynamic programming approach in time O(an2). We show an O(kn2√ m log m √ k log k + k2n2) algorithm which combines convolutions with dynamic programming. Note that our algorithm is superior to previous known solutions for k ≤ m1/3. At the heart of the algorithm are the Smaller Matching Problem and the k-Aligned Ones with Location Problem. These are interesting problems in their own right. Efficient algorithms to solve both these problems are presented.

Original languageEnglish (US)
Pages (from-to)1-11
Number of pages11
JournalInformation and Computation
Volume118
Issue number1
DOIs
StatePublished - Apr 1995

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Efficient 2-dimensional approximate matching of half-rectangular figures'. Together they form a unique fingerprint.

Cite this