1-D fast normalized cross-correlation using additions
Jae-Chern Yoo, Byoung Deog Choi, Hyoung-Kee Choi · Digital Signal Processing · 2010
A new fast algorithm for the computation of the normalized cross-correlation (NCC) is presented. For a search window of size M and a template of size N, our fast NCC requires only approximately 3N⋅(M−N+1) additions/subtractions without multiplications. Numerical results with 100,000 test signals show that the use of the fast NCC instead of the traditional approaches for the determination of the degree of similarity between a test signal and a reference signal (template) brings about a significant improvement in terms of false negative rate, identification rate and computational cost without a significant increase in false positive rate, especially when signal to noise ratio (SNR) is higher than 4 dB.