This seemed really inefficient to me so I was wondering what optimizations could be used to speed it up. Looking it up there seems to be ways to use FFT to reduce the computation time to O(n^2 log^2(n)) (https://stackoverflow.com/questions/16164749/computational-complexity-of-convolution,different sources had different complexities so I'm not confident what the actual is). I wonder if these methods are preferred in most situations or is the method in the slide usually preferred.
NothernSJTU
FFT-based convolution is a method where the image and the kernel (the filter, such as Gaussian or box blur) are transformed into the frequency domain using FFT. In the frequency domain, the convolution operation (normally a time-consuming spatial operation) is reduced to simple multiplication, which is computationally cheaper. The result is then transformed back to the spatial domain using the inverse FFT.
This seemed really inefficient to me so I was wondering what optimizations could be used to speed it up. Looking it up there seems to be ways to use FFT to reduce the computation time to O(n^2 log^2(n)) (https://stackoverflow.com/questions/16164749/computational-complexity-of-convolution,different sources had different complexities so I'm not confident what the actual is). I wonder if these methods are preferred in most situations or is the method in the slide usually preferred.
FFT-based convolution is a method where the image and the kernel (the filter, such as Gaussian or box blur) are transformed into the frequency domain using FFT. In the frequency domain, the convolution operation (normally a time-consuming spatial operation) is reduced to simple multiplication, which is computationally cheaper. The result is then transformed back to the spatial domain using the inverse FFT.