How do you apply a filter after DFT on an image?

Question

Let's say size of the image is 100 x 100 and the kernel matrix is 5x5. I took the DFT of both the image and the kernel. But how do I multiple these two matrices? And which parts involve in these multiplication? real, imaginary or magnitude? Thanks

Is this what am I supposed to do? And at what locations I put 0s to make the kernel 100x100?

    for i to 102
            for j to 102
            {
                newReal = realImage * realKernel - imaginaryImage * imaginaryKernel
                newImaginary = realImage * imaginaryKernel + imaginaryImage * realKernel
            }

        and do InverseFourierTransform(newReal, newImaginary)

Answer 1

Based on your C++ snipped, the correct way to do complex multiplication between samples of DFT sequences should be as follows:

$$ Z[k] = X[k]\cdot Y[k] = (a + jb)(c+jd) = (ac-bd) + j (ad+bc) $$

Where the real part of the result is $ac-bd$, and the imaginary part is $ad+bc$.

Then you can take the inverse 2D-DFT.

Note that, for an alias free circular convolution implementation, your DFT length should be at least $100 + (5-1)/2 = 102 \times 102$ points. Then after the inverse DFT of $ 102 \times 102 $ points, discard the first $2$ rows and columns and reatin the remaining $100 \times 100$ part which are the samples of the filtered image.

Answer 2

You're trying to implement convolution through multiplication in frequency domain.

That means

1. you need to do complex multiplication. Not "real or imaginary or magnitude", but complex multiplication; your signal and your filter are complex-valued, and there's as much information in the real part as in the imaginary part, and you mustn't drop that information.
2. Your transforms of image and kernel must be of the same size. So, zero-pad your kernel to 100×100, or implement segmented convolution (which is a pretty involved thing to do from here)
3. What you'll do is cyclic convolution, because for the discrete Fourier transform, multiplication in frequency domain is equivalent to cyclic convolution in time domain; that's something different than what's normally called "convolution". Again, if you need that acyclic convolution, you'll have to implement segmented convolution (look for "overlap-add" and "overlap-save" methods. You'll find them for 1D signals everywhere, for 2D, too, likely, but understand the 1D case first!); if you then implement the DFT by an FFT, you get what we call "fast convolution"; maybe that's the term you want to google for.