Valid part of frequency convolution

Hi,

I am doing a digital image processing project which involves convolution. For our application purposes we are convolving images without any zero padding as in we only take the "valid" part of the convolution. Now we want use frequency convolution. I have read from Digital Image Processing by Rafael Gonzalez on how to do convolution in the frequency domain by padding to twice the image size with zeros, centering the DC component, doing a fft; then doing the same with the filter as well and do point wise multiplications. After all this is said and done we crop to the ORIGINAL image size.

The problem is in spatial convolution the valid convolution would be less than the original image size, and this is the result we want. Is there an equivalent of convolving only the valid part where the filter window is inside of the whole image in the frequency domain, as in the spatial domain?

If you have an answer please cite an accredited source

Answer 1

[Chris Turnes]

To answer your question, it's important to note what type of convolution you're doing. If you have two inputs of length N, for example, and you do ifft(fft(x).*fft(y)), you're doing a circular convolution of x and y.

It sounds as if what you want is a linear convolution, but only selecting the center portion of the linear convolution (to get something that is the same size as one of your inputs). In "conv2", this corresponds to passing in the 'same' flag (note: the 'valid' flag actually gives you a smaller result, because it only computes the convolution at shifts where both inputs fully overlap).

What you want, then, is something like this:

M = size(x);
N = size(y);
z = ifftn(fftn(x, M+N).*fftn(y, M+N));
z = z(ceil(N(1)/2):(ceil(N(1)/2)+M(1)-1), ceil(N(2)/2):(ceil(N(2)/2)+M(2)-1));

Or, alternatively, use conv2 with the 'same' flag.