FFT for convolution

[ViliamVadocz]

I wanted to use this library for a CNN. After a quick look at the source, it doesn't look like you use the the FFT algorithm for fast convolution. It is probably worth implementing.

[xd009642]

Not currently, I went for a simpler implementation to start with. Also, I'm not sure how well FFT implementations perform for different sized inputs and whether it will really lead to gains for common use cases i.e. the default filters implemented in this crate 🤔.

I've got a lot on my plate right now so probably won't have time to work on this. However, I'm always open to PRs and can offer reviews and guidance. Any PR would also need benchmarks included as well to help measure the performance change. Alternatively, maybe someone on the cv discord would be willing to help. I'll post a link to this issue there https://discord.gg/N82kexYM

[xd009642]

A comment on the discord:

I believe it reduces the complexity mainly when matrices sizes get bigger. The price of FFT is N log(N) and kernel convolutions are then element-wise multiplications so N. While basic convolution of a Kernel containing K elements (say K = 5x5 = 25) involves N * K multiplications. So as soon as K reaches log(N) it's worth. Imagine we have a full HD image, so 2 million pixels. Log(2000000) = 14.5 = roughly 4x4 kernel. So basically, as soon as your convolution kernel gets bigger than 3x3 it's worth it (roughly)

So the original implementation should stay but maybe be called something like SpatialConvolutionExt, add an FftConvolutionExt and then have ConvolutionExt pick the appropriate one based on input sizes etc

[TYPEmber]

Hey, I've made a crate provides N-Dimension FFT acceleration convolution for ndarray.
Maybe ndarray-vision could depend on my crate.
https://crates.io/crates/ndarray-conv
And there is the benchmark result:

[TYPEmber]

And ndarray-conv also provides normal convolution and a lot of padding and convolution mode.

[xd009642]

@TYPEmber I've got no issues with depending on your crate, would you be willing to help out with a PR? 👀

[TYPEmber]

Of course, but would you like to expose ndarray-conv's interface directly?

[xd009642]

I've had a brief look and yeah I'm happy to expose the interface directly - it'll be a minor bump when it's released but that's fine

[TYPEmber]

OK, I will try to make a PR recently.