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 $N\times M$ image with a $m\times n$ filter from $𝒪(M\cdot N\cdot m\cdot n)$ down to $𝒪(M\cdot N\cdot (m+n))$.

Examples

1. A two-dimensional smoothing filter:

$\frac{1}{3}\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]*\frac{1}{3}\left[\begin{array}{ccc}1& 1& 1\end{array}\right]=\frac{1}{9}\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right]$

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

$\frac{1}{4}\left[\begin{array}{c}1\\ 2\\ 1\end{array}\right]*\frac{1}{4}\left[\begin{array}{ccc}1& 2& 1\end{array}\right]=\frac{1}{16}\left[\begin{array}{ccc}1& 2& 1\\ 2& 4& 2\\ 1& 2& 1\end{array}\right]$

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

$\left[\begin{array}{c}1\\ 2\\ 1\end{array}\right]*\left[\begin{array}{ccc}1& 0& -1\end{array}\right]=\left[\begin{array}{ccc}1& 0& -1\\ 2& 0& -2\\ 1& 0& -1\end{array}\right]$

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.