Fast template matching algorithm based on AMSP and initial threshold estimation

The Normalization Cross Correlation(NCC) measure is more stable than Sum of Absolute Differences(SAD) measure when the illumination changes. However, it needs large calculated amount, which is its disadvantage. Therefore, a fast template matching algorithm based on NCC combing Adaptive Multilevel Successive Partitioning (AMSP) with the initial threshold estimation was proposed in this paper. The template image was partitioned into different blocks steeply according to the gradient values of the different modules in the template image, the summation of cross correlation was partitioned into different levels with the partition order to get the upper bounds of each layer, and the Cauchy-Schwartz inequality was used to get the relation between different upper bounds, then the approach of adaptive multilevel successive partitioning elimination was formed. In order to further accelerate the matching speed, the initial threshold estimation was used to generate a large boundary threshold, which could eliminate lots of unmatched points as initial searching and reduce the number of search points. The experimental results demonstrate that the proposed algorithm has strong robustness, and the execution speed of the proposed approach is superior to traditional algorithms.