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)

Usage

The heart of running an NCC analysis is based on the python script norm_xcorr.py which is what is used to calculate the correlation as well as provide some other useful information.

Running:

python norm_xcorr.py -h

Will print out the usage header giving brief instructions to remind you of the syntax.

# USAGE: python norm_xcorr.py [-option] outfile image1 image2
#
#     -o   Use this followed by 'outfile' to
#          specify a unique output destination.
#          Default is corrOut.png
#
#     -h   Use this to print usage directions
#          to StdOut. (Prints the header)
#
#     -v   Use this to only output current
#          version number and exit. By default
#          the version will be sent to StdOut
#          at the beginning of each use.
#
########################################################