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...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1057-7149
1941-0042
DOI:10.1109/TIP.2008.2004615