How to implement Fast Fourier Transform for correlation of two 2-dimensional arrays?
I want to do this with large arrays, but to figure it out, I'll use a smaller example.
Let's say I have the following array:
A = [[0, 0, 100],
[0, 0, 0],
[0, 0, 0]]
If I want to calculate the correlation of this array with another by multiplying the corresponding entries. For example, A * A will equal A (1 * 1 = 1, zeros everywhere). I read that Fast Fourier Transforms can be used to speed up this with large arrays. From what I read, I was under the impression that if I wanted to multiply two arrays A and B like in * B, then I could do it faster with the following (using numpy in python):
a = np.conj(np.fft.fftn(A))
b = np.fft.fftn(B)
c = np.fft.ifft(a*b)
So, take fft from A, take fft from B, multiply the two results and then get the opposite result. However, I tried this with case A above, multiplying myself. I was hoping that back multiplication would give me
[[0, 0, 10000],
[0, 0, 0 ],
[0, 0, 0 ]]
However, I have something different, closer to
[[10000, 0, 0],
[10000, 0, 0],
[10000, 0, 0]]
Does anyone know what's going on? Sorry, I'm guessing I'm misunderstanding something about fft.
source to share
Should be used instead scipy.signal.fftconvolve
.
It has already been implemented and has undergone extensive testing, especially regarding border handling. The only extra step needed to go from convolution to correlation operator in 2D is rotating the filter matrix 180 ° (see this answer ).
source to share
If you must implement your own, you should know that multiplication in the frequency domain corresponds to circular convolution in the time domain. To get the required linear convolution, you need to overlay both arrays with zeros to a length at least twice the size of your original matrix 1 :
s = [2*x for x in np.shape(A)]
a = np.conj(np.fft.fftn(A,s))
b = np.fft.fftn(B,s)
c = np.fft.ifftn(a*b)
1 strictly speaking, a 2n-1 size (instead of 2n) will do, but FFTs perform better when dealing with sizes that are multiples of small prime factors.
source to share