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 m x m pattern in an n x 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(an(2)). We show an O(k(2) root mlogm root klogk+k(2)n(2)) algorithm which combines convolutions with dynamic programming. Note that our algorithm is superior to previous known solutions for k less than or equal to m(1/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. (C) 1995 Academic Press, Inc.