Is it true that convolving a 3x3 matrix and a Full HD (1920×1080) image is slower with FFT, than with normal for-loops? Because you have to do zeropadding to get to a power of 2? (with the traditional Cooley-Tukey FFT for example)
Because when using the FFT, you have to zeropad the 3x3 kernel as well... log(1920*1080)/log(2) is roughly 21. That means I need 21 adds and 15.5 multiplies is 36.5 operations for each pixels. But I need to do 2 FFT and one IFFT. So, I need to multiply 36.5 by 3: 36.5*3=109.5 operations for each pixel?
When calculating the convolution directly using for-loops, you need 9 multiplications and 9 additions = 18 operations for each pixel.
I guess I made a mistake somewhere. One of those is '21 multiplies'... Please provide a better mathmatical proof.