Using the "flops" and "tic/toc" commands in Matlab, we were able to make a number of performance measurements on the three implementations of the correlation function.
Clearly, from the measurements of millions of floating point operations (MFLOPs), the convolution is the clear winner for at least smaller images and templates. This may be attributed to the zero padding that both the Fourier transform and correlation functions must do before calculating.
We also considered the possibility that the number of floating point operations may be related to the ratio of the image to the template. The most noticeable difference here is that the Fourier function suffers greatly comparatively for large image/template disparities, indicated by the smaller numbers. Note: the numbers have been weighted by the size of the padded image. We believe this is due the Fourier transform having to deal with imaginary numbers in regions of zero padding as opposed to simple multiplies and sums.
These two following images clearly show the advantages of moving into the frequency domain when handling larger images and templates. Despite the fact that the Fourier implementation requires more floating point operations, the routine enjoys 10x the performance of either the convolution or correlation for the largest image/template combination used. Worthy of note is how the Fourier algorithm appoaches the convolution algorithm in performance for smaller images, and then surpasses it for larger images.
Finally, we look at the performance of the different alorithms as a function of the image/template ratio. It is interesting to note here that the last two images are identical, suggesting that time may also be some function of the ratio and the padded image size. Also, we notice the convolution really blows up for larger images, even faster than the correlation.