Fast template matching using Correlation-based Adaptive Predictive Search

Abstract

We have developed the Correlation-based Adaptive Predictive Search (CAPS) as a fast search strategy for multidimensional template matching. A 2D template is analyzed, and certain characteristics are computed from its autocorrelation. The extracted information is then used to speed up the search procedure. This method provides a significant improvement in computation time while retaining the accuracy of traditional full-search matching. We have extended CAPS to three and higher dimensions. An example of the third dimension is rotation where rotated targets can be located while again substantially reducing the computational requirements. CAPS can also be applied in multiple steps to further speed up the template matching process. Experiments were conducted to evaluate the performance of 2D, 3D, and multiple-step CAPS algorithms. Compared to the conventional full-search method, we achieved speedup ratios of up to 66.5 and 145 with 2D and 3D CAPS, respectively. (C) 2003 Wiley Periodicals, Inc.