Efficient 2-dimensional approximate matching of half-rectangular figures

Efficient algorithms exist for the approximate two dimensional matching problem for rectangles. This is the problem of finding all occurrences of an pattern in an 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. The authors make progress towards this goal by defining helf-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 . The authors show an algorithm which combines convolutions with dynamic programming. Note that the algorithm is superior to previous known solutions for k less than or equal to . At the heart of the problem 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.