Abstract. Template matching is a fundamental problem in computer
vision, with many applications. Existing methods use sliding window
computation for choosing an image-window that best matches the template. For classic algorithms based on sum of square differences, sum of
absolute differences and normalized cross-correlation, efficient algorithms
have been developed allowing them to run in real-time. Current state of
the art algorithms are based on nearest neighbor (NN) matching of small
patches within the template to patches in the image. These algorithms
yield state-of-the-art results since they can deal better with changes in
appearance, viewpoint, illumination, non-rigid transformations, and occlusion. However, NN-based algorithms are relatively slow not only due
to NN computation for each image patch, but also since their sliding
window computation is inefficient. We therefore propose in this paper
an efficient NN-based algorithm. Its accuracy is similar (in some cases
slightly better) than the existing algorithms and its running time is 43-
200 times faster depending on the sizes of the images and templates used.
The main contribution of our method is an algorithm for incrementally
computing the score of each image window based on the score computed
for the previous window. This is in contrast to computing the score for
each image window independently, as in previous NN-based methods.
The complexity of our method is therefore O(|I|) instead of O(|I||T|),
where |I| and |T| are the sizes of the image and the template respectively