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

Question

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.

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

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

Answer 1

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.