By the way, isn't that doing the fast Fourier transform can reduce the computation complexity of the 2D convolution (i.e. blur)? Is there any reason not using it?
kayvonf
FFT is NlgN. Convolving in the frequency domain is just a low-pass filter (multiplication with a box in the frequency domain). Bringing the low-pass result back into the spatial domain is an inverse FFT. (Another NlgN). So the cost is ~ 2NlgN.
The cost of directly implementing convolution in the spatial domain is CN, where C is proportional to the convolution kernel size: C=K x K. So very a large convolution window (e.g. a very wide blur, it can be more efficient to implement convolution in the frequency domain.
Nice shot
By the way, isn't that doing the fast Fourier transform can reduce the computation complexity of the 2D convolution (i.e. blur)? Is there any reason not using it?
FFT is NlgN. Convolving in the frequency domain is just a low-pass filter (multiplication with a box in the frequency domain). Bringing the low-pass result back into the spatial domain is an inverse FFT. (Another NlgN). So the cost is ~ 2NlgN.
The cost of directly implementing convolution in the spatial domain is CN, where C is proportional to the convolution kernel size:
C=K x K. So very a large convolution window (e.g. a very wide blur, it can be more efficient to implement convolution in the frequency domain.