How to convert between 2d convolution and 2d cross-correlation?

Question

I am using cross-correlation for the purposes of image stabilisation. The images which I'm processing can sometimes be rather large. The contents of the image are often repeating patterns. For these reasons I'd like to leverage the Fast-Fourier transform in order to speed up computation time.

Currently, I am using the scipy.signal.correlate2d method in Python to find the cross-correlation between two arrays. Sadly, I'm unable to find an FFT method for this operation. However, there is a scipy.signal.fftconvolve function which convolves my two arrays incredibly quickly. I'd like to use this function (convolution) to find the correlation between two matrices. I understand they are similar, but I don't understand them well enough to know if this can be done.

For reference, I'll attach some figures that I've generated. These may or may not prove to be useful for context.

Answer 1

I figured this out. Convolution is correlation but with the kernel flipped. I'll illustrate this point with the following code:

(Let a be some array and b be some other array)

from scipy.signal import correlate2d, fftconvolve
from numpy import flip, arange, reshape

a = reshape(arange(16), (4,4))
b = reshape(arange(2,18),(4,4))

convolution = fftconvolve(a,b)
classical_correlation = correlate2d(a,b)
fft_correlation = fftconvolve(a,flip(b))

In this case, because we flip the kernel (which in my case is an image from a video a few frames later) we can see that classical_correlation is effectively equal to fft_correlation. However, in my case, the fftconvolve function is much faster than the correlate2d function. Note that this will not always be the case and depends on your data.

For my data above in the question above, I get the following results: [

Answer 2

Cross correlation is the same as convolution with the flipped image. Just convolve with X(−n,−m)

%% 2D cross correlation and convolution

% create two random matrics
n = 10;
x = randn(n,n);
y = randn(n,n);

% cross correlate
z0 = xcorr2(x,y);

% flip and convolve
yFlip = flip(flip(y,1),2);
z1 = conv2(x,yFlip);

% calucalte error
difference = z1-z0;

fprintf('Error = %f\n',mean(mean(difference^2)));