Chapter 10
Computational Aspects of Template Matching

The drawback of template matching is its high computational cost which has two distinct origins. A first source of complexity is the necessity of using multiple templates to accommodate the variability exhibited by the appearance of complex objects. A second source of complexity is related to the representation of the templates: the higher the resolution, i.e. the number of pixels, the heavier the computational requirements. Besides some computational tricks, like early jump-out techniques and the use of integral images, this chapter presents more organized, structural ways to improve the speed at which template matching can be performed: hierarchical matching, metric inequalities, FFT techniques, incremental PCA, and combined approaches. Another important aspect of template matching is the possibility of sub-pixel accuracy: perturbative image expansion and phase correlation techniques are discussed.

keywords: jump-out, hierarchical matching, FFT correlation, metric inequalities, phase correlation, sub-pixel matching.