Image processing – how to multiply the spectra of two different dimensional images?

This is not a programming problem But I'm sure this is something widely known and understood in this community

I have an image X and a much smaller image y, and I need to convolute them by multiplying them But because of their different sizes, I don't know how to multiply in frequency domain

I use the (two-dimensional) FFT of X (this is an integer matrix with the size of 4096 x 4096), which gives the frequency domain representation of X (this is a complex matrix, and I think its dimension is 2048 x 2048)

Similarly, I use (y of two-dimensional FFT (this is a 64 x 64 integer matrix), which gives the frequency domain representation, y (also a complex matrix, I think its dimension is 32 x 32)

I am using the return function in the digital recipe, so my input matrices X and y must be folded into a one-dimensional array and replaced by their discrete Fourier transforms X and y The point is that even if this is a two-dimensional image problem, I am using a one-dimensional array

If I try to convolute two images of exactly the same size, X and Y. it's all very simple:

X = FFT(x)

 Y = FFT(y)

 Z = X * Y (term by term multiplication)

 Convolution of x and y = IFFT(Z)

But if the lengths of X and y are different, how do I multiply?

One possibility is to fill y to have the same size as X But it seems very inefficient Another possibility is to fill y with the same size as X But I don't know what this means in frequency space

This is another way to raise this question: if I want to use FFT to convolute two images with different dimensions, I can multiply their spectra (frequency domain representation). How should I multiply them?

thank you,

~ Michael

Solution

Filling a smaller array with zeros (convolution kernel, y in your case) to match the input image size (your matrix X) is the standard method If you convolute in the spatial domain, it will be very inefficient, but if you multiply the FFT, it is necessary, and the cost of calculating the FFT filling the array is not too bad