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

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

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

G[i][j] = G_row[i] * G_col[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:

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

Which can be simplified to:

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

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