3
$\begingroup$

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

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

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.