Efficient 2-dimensional approximate matching of non-rectangular figures

Amihood Amir, Martin Farach

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
    PublisherAssociation for Computing Machinery
    Pages212-223
    Number of pages12
    ISBN (Print)0897913760
    StatePublished - Mar 1 1991
    Event2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 - San Francisco, United States
    Duration: Jan 28 1991Jan 30 1991

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

    Other

    Other2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
    Country/TerritoryUnited States
    CitySan Francisco
    Period1/28/911/30/91

    ASJC Scopus subject areas

    • Software
    • General Mathematics

    Fingerprint

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

    Cite this