Previous | Next --- Slide 43 of 66
Back to Lecture Thumbnails

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.