# Applying Convolution (In 2D) Theorem Swaps Quadrants

For educational purposes I implemented the DFT and inverse DFT for images using OpenCV. Applying the DFT to an image and taking the inverse DFT of the spectrum yields the original image, so this works. I do not rearrange the spectral image from $$[0,N)$$ to $$[-N/2, N/2)$$.

Now, using the convolution theorem I want to filter an image. I use a 3x3 averaging kernel and pad it with zeroes to the same size as the input image. I then take the DFT of it, and do a piecewise multiplication of the image spectrum and the kernel spectrum.

The inverse DFT of the resulting spectrum yields an interesting result: The image is filtered (smoothed) correctly, however the quadrants are swapped. Interestingly, if I filter it twice (or any even number), the quadrants are properly arranged. This works for both

$$\mathcal{F}^{-1}\{ (\mathcal{F}\{I\}\mathcal{F}\{H\})\mathcal{F}\{H\} \} =$$ $$\mathcal{F}^{-1}\{ \mathcal{F}\{I\}(\mathcal{F}\{H\}\mathcal{F}\{H\}) \}$$

with the image $$I$$ and kernel $$H$$. This makes sense to me since convolution is associative.

What is the cause of the swapped quadrants?

It's probably due to how you padded the filter before DFT'ing it. I bet you had it in a corner instead of in the middle. Since convolution via DFT is circular convolution, it's not so much of a quadrant swap as it is a wrap around. I believe that if you put the non-zero taps in the middle that it will fix the problem.

• Thanks for the suggestion, but the kernel is in the middle. Dec 20 '14 at 19:35
• Try moving it to the "lowest" spots then (the 0 through 2 spots), since it sounds like I got it backwards. Dec 20 '14 at 19:44
• It actually needs to have Circular Extension. See dsp.stackexchange.com/questions/70908.
– Royi
Oct 18 '20 at 5:40