# Filtering $n \times n$ Images by Separable $m \times m$ Filters. Computation Time for Filtering Using FFT, 2D Convolution and Two 1D Convolutions

Consider filtering square $n\times n$ images by square, separable $m\times m$ filters.

1. 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.

1. 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)

2. For the implementation in 2) give values of $m$ and $n$ for which the FFT implementation is expected to be fastest.

• 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).

• Is it homework? Apr 2 '13 at 13:54
• Yes, it is. And I really do not know how to answer it. Apr 2 '13 at 13:55
• It's fine! Mentioning it's homework should help you elicit better answers. Apr 2 '13 at 14:47
• There is no need to transpose when computing the 1D convolutions. The timings given for 2D spatial vs 2x1D spatial are ridiculous, that could be the cost of transposing. Whoever made this exercise didn’t do a good job implementing separable filters. A separable filter takes $2m$ multiplications and additions (per pixel), a non-separable one takes $m^2$. Even. For $m=3$, it is 6 vs 9. If the 2x1D takes longer for a small image that fits in the cache, the implementation is really bad. Jul 28 '18 at 15:19