Fast Template Matching Based on Normalized Cross Correlation With Adaptive Multilevel Winner Update

• Published in: IEEE transactions on image processing 2008-11, Vol.17 (11), p.2227-2235
• Main Authors: Wei, Shou-Der, Lai, Shang-Hong
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Artificial Intelligence; Cross correlation; Distortion measurement; Exact sciences and technology; Fast algorithms; Image Enhancement - methods; Image Interpretation, Computer-Assisted - methods; Image matching; Image processing; Information, signal and communications theory; Matching; Mathematical analysis; Motion estimation; Multilevel; multilevel successive elimination; normalized cross correlation; Object detection; Partitioning algorithms; Partitions; Pattern matching; Pattern recognition; Pattern Recognition, Automated - methods; Reproducibility of Results; Sensitivity and Specificity; Signal processing; Subtraction Technique; Telecommunications and information theory; Upper bound; Upper bounds; Video compression; winner update strategy
• ISSN: 1057-7149; 1941-0042
• DOI: 10.1109/TIP.2008.2004615

In this paper, we propose a fast pattern matching algorithm based on the normalized cross correlation (NCC) criterion by combining adaptive multilevel partition with the winner update scheme to achieve very efficient search. This winner update scheme is applied in conjunction with an upper bound for the cross correlation derived from Cauchy-Schwarz inequality. To apply the winner update scheme in an efficient way, we partition the summation of cross correlation into different levels with the partition order determined by the gradient energies of the partitioned regions in the template. Thus, this winner update scheme in conjunction with the upper bound for NCC can be employed to skip unnecessary calculation. Experimental results show the proposed algorithm is very efficient for image matching under different lighting conditions.