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

Examples

1. A two-dimensional smoothing filter:

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

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

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

References

"Learning Separable Filters" (PDF). p. 3. Retrieved 2021-01-06.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] "Learning Separable Filters" (PDF). p. 3. Retrieved 2021-01-06.