Lecture 3: Sampling, Aliasing, Antialiasing (60)

Here is my thinking. Suppose the image has nn pixels and the filter has mm pixels in total. Doing convolution in spatial domain will cost O(nm)\mathcal{O}(nm), as for each pixel there are mm multiplications and summations.

Doing Fast Fourier Transform (and the reverse transform?) of the image costs O(nlog(n))\mathcal{O}(n\log(n)), and doing multiplication costs O(n)\mathcal{O}(n) as we are doing it by "pixel" (frequency). The cost of transforming the filter consts O(mlog(m))\mathcal{O}(m\log(m)). Then in total the cost is O(nlog(n)+n+mlog(m))\mathcal{O}(n\log(n) + n + m\log(m)), or O(nlog(n))\mathcal{O}(n\log(n)) if mm is ignorable against nn.

Then we choose the most efficient one.

What do you guys think?


I generally agree with this.

I am curious tho if you can take advantage of parallelism/data locality to speed up the convolution. Because depending on the stride length of the convolution, you may be able to apply several convolutions to the image at once.

You must be enrolled in the course to comment