A separable filter in image processing can be written as product of two more simple filters. Typically a 2-dimensional convolution operation is separated into 2 onedimensional filters. This reduces the cost of computing the operator.
Why is the cost of computing lower, if I use separable filter? I can not understand, why having 2 filters instead of one will increase performance
Answer
Assume you have a $N\times M$ sized image.
If you know take what is classically used, a square filter kernel, of let's say size $L\times L$, you'd need to convolve that with the picture – which gives you $N\times M$ pixels, each needing $L^2$ multiply-accumulates. So you end up with $A_{2D}=L^2MN$ operations.
Now, if you can decompose that filter into an $L$-sized horizontal and an L-sized vertical 1D-filter, you could first do all rows – that's $M$ values per row, each needing $L$ operations, so $LMN$ for all rows – and then you'd do the same with the vertical filter, so $LNM$ for all columns – and you end up with $A_{1D}=2LMN$, and you'd only need to show that
$$\begin{align} A_{1D} &< A_{2D}\\ \iff\\ 2LMN &< L^2MN &&||:LMN, \text{ legal since $L,M,N >0$}\\ \iff\\ 2 &< L \end{align}$$
most filters are larger than 2.
No comments:
Post a Comment