1
$\begingroup$

enter image description here

Find the minimum number of arithmetic operations required for 2D Filters I could not understand the question 6 of Quiz-1. What is the number of operations (Multiplications and additions) per sample in the case of separable filter kernels?

How to calculate the number of arithmetic operations? Can anybody suggest how to calculate the number of arithmetic operations? Can anybody suggest a reference textbook?

Improve this question
$\endgroup$
2
  • 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, 2020 at 8:36
  • 3
    $\begingroup$ Please stop posting your homework problems, that's not what this site is about. $\endgroup$
    – Matt L.
    Dec 5, 2020 at 11:03

2 Answers 2

Reset to default
0
$\begingroup$

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.
Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

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