Premium
Fast template matching using correlation‐based adaptive predictive search
Author(s) -
Sun Shijun,
Park HyunWook,
Haynor David R.,
Kim Yongmin
Publication year - 2003
Publication title -
international journal of imaging systems and technology
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.359
H-Index - 47
eISSN - 1098-1098
pISSN - 0899-9457
DOI - 10.1002/ima.10055
Subject(s) - speedup , computer science , autocorrelation , matching (statistics) , computation , dimension (graph theory) , algorithm , template matching , process (computing) , rotation (mathematics) , pattern recognition (psychology) , artificial intelligence , mathematics , parallel computing , image (mathematics) , statistics , pure mathematics , operating system
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. © 2003 Wiley Periodicals, Inc. Int J Imaging Syst Technol 13, 169–178, 2003; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ima.10055