Fast template matching based on normalized cross correlation with adaptive multilevel winner update.
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.
Wei
Shou-Der
SD
Department of Computer Science, National Tsing Hua University, Hsinchu 300, Taiwan, R.O.C.
Lai
Shang-Hong
SH
D000465:Algorithms; D001185:Artificial Intelligence; D007089:Image Enhancement / Q000379:methods*; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D013382:Subtraction Technique