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

Question

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?

Answer 1

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.

Answer 2

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.