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 ${\displaystyle N\times M}$ image with a ${\displaystyle m\times n}$ filter from ${\displaystyle {\mathcal {O}}(M\cdot N\cdot m\cdot n)}$ down to ${\displaystyle {\mathcal {O}}(M\cdot N\cdot (m+n))}$. [1]

Examples

1. A two-dimensional smoothing filter:

${\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:

${\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:

${\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

1. "Learning Separable Filters" (PDF). p. 3. Archived from the original (PDF) on 2020-07-09. Retrieved 2021-01-06.