Consider filtering square $n\times n$ images by square, separable $m\times m$ filters.
Give general equations for the computation time for the following approaches to this:
- Filtering using FFT
- 2-D convolution
- Two 1-D convolutions
Use capital letters to indicate implementation-dependent constants.
For particular implementations of the methods of filtering in part 1) the following computation timings were recorded:
n=64 m=3 FFT=2,498,561 2-D convolution=73,829 two 1-D convolutions=245,761 n=256 m=5 FFT=53,084,161 2-D convolution=1,179,649 two 1-D convolutions=3,932,161 n=1024 m=3 FFT=1,059,061,761 2-D convolution=18,874,369 two 1-D convolutions=62,914,561 n=1024 m=11 FFT=1,059,061,761 2-D convolution=471,859,201 two 1-D convolutions=314,572,801
Estimate the values of the implementation-dependent constants to 1)
For the implementation in 2) give values of $m$ and $n$ for which the FFT implementation is expected to be fastest.
My point of view about:
- FFT is: Firstly, applying FFT to each column separately and then to each row. FFT for $N$ data points takes about $2N\log N$ multiplications, for $n\times n$ images it will be $2n\cdot 2n\cdot\log n$ multiplications. Secondly, inverse FFT to get back to sensible image. Another $2n\cdot 2n\cdot \log n$. Thirdly, multiply by FT of the kernel, it will be $n^2$ complex multiplication, that is $4\cdot n^2$ real multiplication. Thus the computation time for FFT is $\mathcal O_1\left(8\cdot n^2\log n +4\cdot n^2\right)$. Is that correct?
- 2-D convolution: I am confused about this. It could be $\mathcal O_2\left(n^2\cdot m^2\right)$. Is it correct?
- Two 1-D convolution: Firstly, convolution per row. It should be $(n+m-1)^2$. Secondly, transpose the matrix of the image. Will this process include the computation time? Thirdly, convolution on the rows again. Another $(n+m-1)^2$. Fourthly, second transpose, return the image back to its original orientation. Computation equation is $\mathcal O_3\left(2\cdot\left(n+m-1\right)^2\right)$.
However, according to my computation equations, I cannot compromise my equations to the recorded computation timings. In this way, I think I need to correct my equations to solve the problems in part 3).