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:
- Remove the zeros on borders in such manner that you have the smallest rectangle of non zero elements.
- Apply the SVD to get the separable form of the filters, if available (See How to Prove a 2D Filter Is Separable?).
- Calculate the multiplications / additions of the 1D filters / convolution. Pay attention that 1 means no need to multiply.
- 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.