Recently proposed fast template matching techniques employ rejection schemes derived from lower bounds on the match measure. This paper generalizes that idea and shows that in addition to lower bounds, upper bounds on the match measure can be used to accelerate the search. An algorithm is proposed that utilizes both lower and upper bounds to detect the k best matches in an image. The performance of this dual-bound algorithm is guaranteed; it always detects the k best matches. Theoretical analysis and experimental results show that its runtime compares favorably with previously proposed real-time exact template-matching schemes.

We describe a fast algorithm that searches for the k most likely locations of a template in an image according to the standard normalized correlations criterion. The algorithm is exact; it always finds the best matches. Its speed is achieved by utilizing an acceptance-rejection pruning scheme, applied to easily computed bounds on the normalized correlation values. Previously proposed rejection schemes require a rejection threshold that has to be provided or estimated from the data. Our algorithm does not use such thresholds explicitly, but performs as well as if the perfect rejection threshold is known.

The problem of finding a match for an image (`template') within a larger image is known as template matching. It is key to a variety of computer vision applications. Currently known template matching algorithms run in fixed time, or are guaranteed to find the best match. We present a novel algorithm which in many cases can guarantee that the best match is found. In other cases it finds a good approximation to the best match. This algorithm runs in fixed time (a.k.a. hard real time). It finds an optimal match very quickly when a good match exists.