Abstract

Template matching by normalized correlations is a common technique for determine the existence and compute the location of a shape within an image. In many cases the run time of computer vision applications is dominated by repeated computation of template match- ing, applied to locate multiple templates in varying scale and orientation. A straightforward implementation of template matching for an image size n and a template size k requires order of kn operations. There are fast algorithms that require order of n log n operations. We describe a new approximation scheme that requires order n operations. It is based on the idea of “Integral-Images”, recently introduced by Viola and Jones.