enter image description here

Find the minimum number of arithmetic operations required for 2D Filters

  • 1
    $\begingroup$ What have you found so far, so that we can guide the next steps. And I don't understand the 'dct' tag here $\endgroup$ – Laurent Duval Dec 5 '20 at 8:36
  • 2
    $\begingroup$ Please stop posting your homework problems, that's not what this site is about. $\endgroup$ – Matt L. Dec 5 '20 at 11:03

The steps you should do:

  1. Remove the zeros on borders in such manner that you have the smallest rectangle of non zero elements.
  2. Apply the SVD to get the separable form of the filters, if available (See How to Prove a 2D Filter Is Separable?).
  3. Calculate the multiplications / additions of the 1D filters / convolution. Pay attention that 1 means no need to multiply.
  4. Pay attention that sometimes 2 iterations of 1D convolution is still better.

To better understand the principles of filtering and using separable filters (which apparently is the purpose of that homework), I would suggest you to compute the number of operations in different settings: direct calculation, using the simplest separability (see How to find out if a transform matrix is separable?), or even looking for factoring tricks. The latter, in my opinion, makes the exercise a bit difficult (and I don't if the actual purpose goes that far).

For instance in $f_2$, computing $a+3b+5c+3d+e$ takes 4 adds and 3 multiplies, while $a+3(b+d)+5c+e$ takes 4 adds and 2 multiplies only.


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