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.