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)

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.

  • $\begingroup$ Thanks. After padding the kernel with 0s, I ended up having a mostly black result. If I use my program without applying a filter, it gives correct results so I do not think there is a mistake in the code. Am i following the right path? 1-dft of kernel 2-dft of image 3-multiplication 4-imaginary and real parts after multiplication goes to inverse fourier 5-inverse fourier produces an almost black result. $\endgroup$ – Thunfische Nov 11 '18 at 1:47
  • $\begingroup$ is it true that hamburger comes from Hamburg? $\endgroup$ – Fat32 Nov 11 '18 at 10:27
  • 1
    $\begingroup$ who lives in hamburg can be called hamburger $\endgroup$ – Thunfische Nov 11 '18 at 10:48
  • $\begingroup$ I updated again. Where do you think my error is? Thanks $\endgroup$ – Thunfische Nov 11 '18 at 14:32
  • $\begingroup$ @Thunfische it could be your filter coefficients. Please indicate them in your post. $\endgroup$ – Fat32 Nov 11 '18 at 21:08

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.
  • $\begingroup$ I padded it with zeros and dft of it and multiply dft(image) and dft(kernel) with respect to its imaginary and real parts. And then i put it in my inverse dft function but the output was just a very black version of the original image. All the details are there, as far as I see but it became only a darker version of the original image. I think padding with zeros causes this. How exactly do i pad it with zeros? Thanks $\endgroup$ – Thunfische Nov 11 '18 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.