FFT for convolution about ndarray-vision HOT 8 OPEN

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

from ndarray-vision.

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

from ndarray-vision.