spatial filtering

Spatial filtering processes an image by sliding a small grid of weights, called a kernel or mask, over every pixel and replacing each pixel with a weighted combination of its neighbours. Picture a 3-by-3 stencil hovering over the image; at each position you multiply the nine underlying pixels by the nine kernel weights, add them up, and write the result to the output. By choosing the weights you get blurring, sharpening, edge detection, embossing, and much more, all from the same machinery.

There are two closely related operations. Correlation computes sum over offsets (i,j) of f(x+i, y+j) * k(i,j): the kernel is laid directly over the image. Convolution, written (f * k)(x,y) = sum of f(x-i, y-j) * k(i,j), is identical except the kernel is flipped 180 degrees first. The flip seems pedantic but it makes convolution commutative and associative, and it is the operation that the convolution theorem ties to multiplication in the Fourier domain, the theoretical backbone of linear shift-invariant systems. For symmetric kernels (like a Gaussian) the two coincide; note that the convolution in convolutional neural networks is actually correlation.

Two practical issues always arise. First, boundaries: when the kernel hangs off the edge of the image you must invent values, by zero-padding, replicating the edge pixel, or reflecting the image, each with different artifacts. Second, cost: a k-by-k kernel naively costs k-squared multiplies per pixel, but a separable kernel that factors into an outer product of two 1D kernels can be applied as a horizontal pass then a vertical pass, cutting the cost to 2k per pixel, a large saving that Gaussian and Sobel filters exploit.