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.

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