How do I multiply the spectra of two images of different dimensions?
convolution, fft, image-processing, signal-processing
Solution
Padding the smaller array (the convolution kernel, y in your case) with zeroes to match the input image size (your matrix x) is the standard approach. That would be horribly inefficient if you were doing the convolution in the spatial domain, but if you're multiplying the FFTs, it's necessary, and the cost of computing the FFT of the padded array isn't too bad.
Problem
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.