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

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

• Is it homework? Commented Apr 2, 2013 at 13:54
• Yes, it is. And I really do not know how to answer it. Commented Apr 2, 2013 at 13:55
• It's fine! Mentioning it's homework should help you elicit better answers. Commented Apr 2, 2013 at 14:47
• OP, did Drazick answered your question? If you are satisfied with his answer, then please consider marking it as accepted.
– jojeck
Commented Oct 6, 2016 at 8:09
• 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. Commented Jul 28, 2018 at 15:19

## 1 Answer

I'm not sure exactly what you're after, but just to try to add data:

1. Using the separability property of the filter is always the right choice.
2. Given it is separable we now have to apply 1D convolutions. Selecting which method to do it (Frequency Domain / Spatial Domain) depends on the length of the filter and the number of pixels in each dimension of the image.
There are cases where it is better to do FFT on the Rows and Spatial Convolution on the Columns.
3. This is all true when "Counting" FLOPS. Real life timing is more than that. for instance, if you're using highly tuned Convolution implementation and yet "Classic" DFT implementation you might be faster doing the Spatial way even for dimensions the analytic calculation predict it is better to be done in frequency domain.