• Normalized Cross-Correlation

Normalized Cross-Correlation

By TC

Description

Normalized Cross-Correlation (NCC) is by definition the inverse Fourier transform of the convolution of the Fourier transform of two (in this case) images, normalized using the local sums and sigmas (see below). If this is complete gibberish, not to worry! Thankfully you don't need to understand any of that to make it work (I'm not sure I entirely do). A brief description of the algorithm is provided below, but if you don't care and just want to know how to use the program skip to the Usage section.

It is important to note that the NCC algorithm used follows directly with the MATLAB routine normxcorr2.m and for further documentation to better understand the methodology behind NCC please see Fast Normalized Cross-Correlation, Lewis 1995 and Fast Template Matching, Lewis 1995.

Algorithm

T = "template" image (This is the image you are searching for in matrix form)
A = "search" image (This is the region in which you are trying to find "template")

Ft = FFT(T)
Fa = FFT(A) (Here FFT() denotes the fast Fourier transform. This code uses the built in FFT module in the Python Scipy library.)

Xcorr = IFFT(Ft*Fa) (Here IFFT() denotes the inverse fast Fourier transform.)

cSumA = cumulative_sum(A)
cSumA2 = cumulative_sum(A^2)

sigmaA = (cSumA2-(cSumA^2)/size(T))^(1/2)

sigmaT = std_dev(T)*(size(T)-1)^(1/2)

nXcorr = (Xcorr-cSumA*mean(T))/(sigmaT*sigmaA) (This is the matrix of normalized cross-correlation coefficients)