Gaussian & separability

The Gaussian is the standard blur kernel. Its 2D kernel is the product of two 1D kernels, so the image can be filtered along the rows and then along the columns, with a fraction of the work. And if you blur with a simple box often enough, you get a Gaussian anyway.

1D kernel Gσ(x)G_\sigma(x) sampled at the integers, truncated at ±⌈3σ⌉\pm\lceil 3\sigma \rceil
2D kernel Gσ(x) Gσ(y)G_\sigma(x) \, G_\sigma(y)
Two 1D passes filter the rows, then the columns of the result
original
after the horizontal pass
after both passes = 2D Gaussian
Repeated box filter bars: box of width ww convolved nn times, line: Gaussian with the same variance

The Gaussian kernel

The Gaussian weights neighbors by their distance from the center, with a standard deviation σ\sigma that sets the amount of blur:

Gσ=12πσ2 e−x2+y22σ2G_\sigma = \frac{1}{2\pi\sigma^2} \, e^{-\frac{x^2 + y^2}{2\sigma^2}}

It never reaches zero, so in practice it is cut off at ±3σ\pm 3\sigma, which keeps 99.7 % of the weight in each direction, and the samples are normalized to sum to 1. A kernel for σ\sigma is then P=2⌈3σ⌉+1P = 2\lceil 3\sigma \rceil + 1 pixels wide.

Separability

The Gaussian is a separable kernel: the exponential of a sum is a product, so the 2D Gaussian factors into a product of two 1D Gaussians,

Gσ(x,y)=Gσ(x) Gσ(y),Gσ(x)=12π σ e−x22σ2G_\sigma(x, y) = G_\sigma(x) \, G_\sigma(y), \qquad G_\sigma(x) = \frac{1}{\sqrt{2\pi}\,\sigma} \, e^{-\frac{x^2}{2\sigma^2}}

As a matrix, the 2D kernel is the outer product of a column and a row vector, a matrix of rank 1. A small example with integer weights:

[121242121]=[121][121]\begin{bmatrix} 1 & 2 & 1 \\ 2 & 4 & 2 \\ 1 & 2 & 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 1 \end{bmatrix}

Because convolution is associative, filtering with the 2D kernel is the same as filtering with the row kernel and then with the column kernel:

I∗Gσ(x,y)=(I∗Gσ(x))∗Gσ(y)I * G_\sigma(x, y) = \big( I * G_\sigma(x) \big) * G_\sigma(y)

An M×NM \times N image with a P×QP \times Q filter requires MNPQMNPQ multiplications, the two passes only MN(P+Q)MN(P + Q). The saving grows with the filter size: for a 9×99 \times 9 filter the speedup is (9⋅9)/(9+9)=4.5(9 \cdot 9)/(9 + 9) = 4.5. Every kernel of rank 1 is separable, for example the box filter and the Sobel filter Sx=[121][ −1    0    1 ]S_x = \left[\begin{smallmatrix} 1 \\ 2 \\ 1 \end{smallmatrix}\right] [\,-1 \;\; 0 \;\; 1\,]; whether a kernel is separable, and into which vectors, can be read off its singular value decomposition.

Repeated box filtering

Convolving a box filter with itself gives a triangle, then a piecewise quadratic, and so on: if you convolve many times with a box filter, it converges to a Gaussian. This is the central limit theorem: the sum of many independent random variables tends to a normal distribution. Variances add under convolution, and a box of width ww has variance (w2−1)/12(w^2 - 1)/12, so nn boxes give

σ2=n w2−112.\sigma^2 = n \, \frac{w^2 - 1}{12}.

A box filter can be computed with a running sum at a cost that does not depend on its width, so a few box passes are a cheap way to approximate a large Gaussian. A Gaussian convolved with a Gaussian is again a Gaussian, and the variances add as well, σ2=σ12+σ22\sigma^2 = \sigma_1^2 + \sigma_2^2: convolving two times with width σ\sigma is the same as convolving once with width σ2\sigma \sqrt{2}.

Try this