We chose to go with the FFT in place of the correlation as it has the potential to offer far greater performance , especially for larger images and templates.
Instead of N^2 computions (N sums and N multiplies), we have only 2 (N/2)^2 or (N^2)/2 computions. The sum can be broken down further until we have two-element sets, each with one even and one odd element. The calculations only increase logarithmically with N in this case, and the follow gains can be realized. The graph plots the data to the left, with number of calculations plotted against N. Notice that the scale is logarithmic.
The following formula is the implementation of the Fast Fourier Transform in Matlab. Like the correlation function, the Fourier function takes as its input two gifs (the template and the image), and returns the location, if the template exists in the image, of the template.
function FFTloc
clear
close all
tmpl = input('Template to find? ','s');
ref = input('Reference? ','s');
threshold = input('Threshold? ');
tic
flops(0)
[templ,map] = gifread(tmpl);
[refer,map] = gifread(ref);
refer=refer-1;
templ=flipud(fliplr(templ-1));
padding = size(refer)+size(templ)-[1,1];
refer_tr = fft2(refer, padding(1), padding(2));
templ_tr = fft2(templ, padding(1), padding(2));
raw = ifft2(refer_tr.*templ_tr);
refersqr = refer.^2;
flat = ones(size(templ));
refersqr_tr = fft2(refersqr, padding(1), padding(2));
flat_tr = fft2(flat, padding(1), padding(2));
norml = ifft2(refersqr_tr.*flat_tr);
rtnormal=norml.^0.5;
rtnormal=rtnormal+0.1;
normalized = real(raw./rtnormal);
most=max(max(normalized));
location =(normalized>=most-threshold)+1;
colormap(gray(2));
image(location);
flops
toc