next up previous contents
Next: 13.3.3 Convolutions Using the Up: 13.3.2 The Convolution Operation Previous: 13.3.2.1 Two-Dimensional Convolutions

13.3.2.2 Separable Filters

In the general case, the two-dimensional convolution operation requires (width * height) multiplications for each output pixel. Separable filters are a special case of general convolution in which the filter

G[0..(width-1)][0..(height-1)]

can be expressed in terms of two vectors

\begin{displaymath}G_{row}[0..(width-1)] \\
G_{col}[0..(height-1)] \end{displaymath}

such that for each $(i,j) \epsilon ([0..(width-1)], [0..(height-1)])$

G[i][j] = Grow[i] * Gcol[j]

If the filter is separable, the convolution operation may be performed using only (width + height) multiplications for each output pixel. Applying the separable filter to Equation15 becomes:

\begin{displaymath}H[x][y] = \sum^{height - 1}_{j = 0}\sum^{width - 1}_{i = 0}
F[x+i][y+j]G_{row}[i]G_{col}[j]
\end{displaymath}

Which can be simplified to:

\begin{displaymath}H[x][y] = \sum^{height - 1}_{j = 0}G_{col}[j]\sum^{width - 1}_{i = 0}F[x+i][y+j]G_{row}[i]
\end{displaymath}

To apply the separable convolution, first apply Grow as though it were a width by 1 filter. Then apply Gcol as though it were a 1 by height filter.



David Blythe
1999-08-06