About implementing conv2d with fft.

[FrontMage]

Hi, I read your answer on stack exchange and I managed to implement fast conv2d with fft using rust.

Thank you for the amazing answer.

However, I ran into some problems when I tried to implement full conv2d. I can't find the correct way to pad the image.

When conv2d is on valid mode, the image needs no padding, because the result is the same size as the image.

When conv2d is on full mode, the result is (image_width + kernel_width -1) * (image_height + kernel_height -1).

Then how do I pad the image? Can you help me with this? Thanks!

[RoyiAvital]

I'd be happy if you used the answer as reference that you'd link to it in the code. Also please +1 :-).

Regarding your question, FFT based convolution always applies Circular Convolution. There is no way around it. Hence if you want (image_width + kernel_width -1) * (image_height + kernel_height -1) output of linear convolution, pad the image to size (image_width + kernel_width - 1 + kernel_width) * (image_height + kernel_height - 1 + kernel_height) and crop the middle part to get the valid linear convolution of the size you're after.

[FrontMage]

@RoyiAvital I Will do that, actually, I was working on my stack exchange reputation. My code will be on GitHub as soon as I get full conv2d working.

---

So if I'm reading this correctly, I need to circular zero pad the image and kernel to (image_width + kernel_width - 1 + kernel_width) * (image_height + kernel_height - 1 + kernel_height), fft them, multiply, ifft back then crop the middle kernel_width * kernel_height part?

[RoyiAvital]

Yep. I think I have a MATLAB code for that. If you want, ask such question in DSP and I will answer it with MATLAB code so you'll have a reference.

I'd appreciate if you credit me in the package and the code.

[FrontMage]

Sorry for the late reply, I was working on the StackExchange reputation.

For some reason it requires 500 reps to just make a custom question tag...and I still not quite getting it.

Reposted it!

Here is the question https://dsp.stackexchange.com/questions/74803/to-calculate-full-convolution-2d-with-fast-fourier-transform-how-do-i-pad-the-i

I will certainly credit you in the package description and in the code comments, great work! @RoyiAvital

[RoyiAvital]

I posted code as an answer and +1.

Enjoy...

[FrontMage]

Thank you again!

Although the implementation was borrowed from ZRHan's answer, I couldn't have done it without your help from the start.

I've managed to implement conv2 and xcorr2 using fft, and optimized them with simd, they are almost as fast as Matlab's functions.

The code is here https://github.com/FrontMage/matlab_rust.

I quoted your answer in the code comment and the README.md hope you don't mind.

[RoyiAvital]

@FrontMage , Please link to the relevant answer on DSP:

https://dsp.stackexchange.com/questions/74803

And the previous answer you mentioned at the first post.

[FrontMage]

@RoyiAvital Done!