This is not a "programming" question. But I'm sure it's something that is widely known and understood in this community.
I have an image, x, and a much smaller image, y, and I need to convolve the two by multiplying their FFTs. But since they are not the same size I don't know how to do the frequency domain multiplication.
I take the (two-dimensional) FFT of x (which is an integer matrix of dimensions 4096 x 4096), which gives me the frequency domain representation, X (which is a matrix of complex numbers and I think it's dimension is 2048 x 2048).
Similarly, I take the (two-dimensional FFT of y (which is an integer matrix of dimension 64 x 64), which gives me the frequency domain representation, Y (which is also a matrix of complex numbers and I think it's dimension is 32 x 32).
I'm using the fourn function in Numerical Recipes, so my input matrices, x and y must be collapsed into one-dimensional arrays, which get replaced by their discrete Fourier transforms, X and Y. The point being that even though this is a two-dimensional problem with images, I am working with one-dimensional arrays.
If I were trying to convolve two images of the exact same dimensions, x and y. It would all be very straightforward:
X = FFT(x)
Y = FFT(y)
Z = X * Y (term by term multiplication)
Convolution of x and y = IFFT(Z)
But if X and Y are different lengths, how do I do the multiplication?
One possibility is to pad out y to have the same dimensions as x. But this seems horribly inefficient. Another possibility is to pad out Y to have the same dimensions as X. But I don't know what this means in frequency space.
Here's another way of asking this question: If I want to convolve two images of very different dimensions using FFTs so I can do multiplication of their spectra (frequency domain representation), how do I do that multiplication?
Thanks,
~Michael.