Separable filter

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 two 1-dimensional filters. This reduces the computational costs on an [math]\displaystyle{ N\times M }[/math] image with a [math]\displaystyle{ m\times n }[/math] filter from [math]\displaystyle{ \mathcal{O}(M\cdot N\cdot m\cdot n) }[/math] down to [math]\displaystyle{ \mathcal{O}(M\cdot N\cdot (m + n)) }[/math].

Examples

1. A two-dimensional smoothing filter:

[math]\displaystyle{ \frac{1}{3} \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} \frac{1}{3} \begin{bmatrix} 1 & 1 & 1 \end{bmatrix} = \frac{1}{9} \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix} }[/math]

2. Another two-dimensional smoothing filter with stronger weight in the middle:

[math]\displaystyle{ \frac{1}{4} \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix} \frac{1}{4} \begin{bmatrix} 1 & 2 & 1 \end{bmatrix} = \frac{1}{16} \begin{bmatrix} 1 & 2 & 1 \\ 2 & 4 & 2 \\ 1 & 2 & 1 \end{bmatrix} }[/math]

3. The Sobel operator, used commonly for edge detection:

[math]\displaystyle{ \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & -1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & -1 \\ 2 & 0 & -2 \\ 1 & 0 & -1 \end{bmatrix} }[/math]

This works also for the Prewitt operator.

In the examples, there is a cost of 3 multiply–accumulate operations for each vector which gives six total (horizontal and vertical). This is compared to the nine operations for the full 3x3 matrix.