Separable filter

A separable filter in image processing can be written as the product of two or more simple filters. Typically a 2-dimensional convolution operation is separated into two 1-dimensional filters. This reduces the computational costs on an N × M {\displaystyle N\times M} image with a m × n {\displaystyle m\times n} filter from O ( M ⋅ N ⋅ m ⋅ n ) {\displaystyle {\mathcal {O}}(M\cdot N\cdot m\cdot n)} down to O ( M ⋅ N ⋅ ( m + n ) ) {\displaystyle {\mathcal {O}}(M\cdot N\cdot (m+n))} . ^[1]

Examples

1. A two-dimensional smoothing filter:

1 3 [ 1 1 1 ] ∗ 1 3 [ 1 1 1 ] = 1 9 [ 1 1 1 1 1 1 1 1 1 ] {\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}}}

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

1 4 [ 1 2 1 ] ∗ 1 4 [ 1 2 1 ] = 1 16 [ 1 2 1 2 4 2 1 2 1 ] {\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}}}

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

[ 1 2 1 ] ∗ [ 1 0 − 1 ] = [ 1 0 − 1 2 0 − 2 1 0 − 1 ] {\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}}}

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.

Another notable example of a separable filter is the Gaussian blur whose performance can be greatly improved the bigger the convolution window becomes.

References