0
$\begingroup$

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.

The convolution between my two arrays (padded with zeros)

The cross-correlation between my two arrays

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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: Obtained with the scipy.signal.correlate2d function [Obtained with the scipy.signal.fftconvolve function but with the the kernel flipped using np.flip or b::-1,::-1

$\endgroup$
1
  • $\begingroup$ I am mildly surprised that np.correlate2d doesn't give you the option of using the FFT under the hood. I was motivated enough to look for it and found this discussion. $\endgroup$
    – TimWescott
    Oct 29, 2022 at 18:27
0
$\begingroup$

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)));
$\endgroup$
1
  • $\begingroup$ Thanks for your response, I hadn't seen it before posting my own! $\endgroup$ Oct 28, 2022 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.