Efficient algorithms for image template and dictionary matching

Given a large text image and a small template image, the Template Matching Problem is that of finding every location within the text which looks like the pattern. This problem, which has received attention for low-level image processing, has been formalized by defining a distance metric between arra ys of pixels and finding all subarrays of the large image which are within some threshold distance of the template. These so-called metric methods ten ds to be too slow for many applications, since evaluating the distance func tion can take too much time. We present a method for quickly eliminating mo st positions of the text from consideration as possible matches. The remain ing candidate positions are then evaluated one by one against the template for a match. We are still guaranteed to find all matching positions, and ou r method gives significant speed-ups. Finally, we consider the problem of m atching a dictionary of templates against a text. We present methods which are much faster than matching the templates individually against the input image.