10
$\begingroup$

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

$\endgroup$

1 Answer 1

10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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