Convolution

Convolution combines an image with a small array of weights, the kernel, by sliding the kernel over the image and replacing each pixel with the weighted sum of the pixels under it. Blurring, sharpening, and differentiation are all convolutions with different kernels, and the same operation, learned rather than designed, is the core layer of convolutional neural networks. Every operation that is linear and treats all image positions alike is a convolution, which is why it appears wherever an image is filtered.

Definition

The convolution of an image $f$ with a kernel $h$ is a new image whose value at each position is a sum of the values of $f$ around that position, weighted by $h$, with the kernel reflected through its center. When the kernel is not reflected, the operation is called cross-correlation. Both are loosely called filtering, and for a kernel symmetric about its center they give the same result.

Intuition

Think of the kernel as a stencil laid over the image: at each pixel, multiply the pixels under the stencil by its weights and write the sum to the output. A $3 \times 3$ kernel of ninths averages each pixel with its eight neighbors and blurs the image; a kernel with $-1$ on one side and $+1$ on the other responds to changes in intensity and finds edges.

A second view explains the flip. Convolution can be read as “every input pixel stamps a scaled copy of the kernel onto the output”. An image that is zero except for one bright pixel, an impulse, therefore comes out as a copy of the kernel itself. The kernel is the system’s impulse response: it says how a single point of light is spread, which is why the kernel of a camera’s blur is called its point spread function. Cross-correlation instead leaves a copy of the kernel rotated by 180 degrees, as the example below shows.

Formal Definition

For continuous functions of two variables, convolution is

$$(f * h)(x, y) = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} f(u, v)\, h(x - u,\, y - v)\, du\, dv .$$

For a digital image $f[m, n]$ and a kernel $h[i, j]$ that is nonzero only for $|i|, |j| \le r$, the discrete convolution is

$$(f * h)[m, n] = \sum_{i=-r}^{r} \sum_{j=-r}^{r} h[i, j]\, f[m - i,\, n - j] .$$

The minus signs reflect the kernel through its center (a rotation by 180 degrees). Cross-correlation uses plus signs and no reflection:

$$(f \star h)[m, n] = \sum_{i=-r}^{r} \sum_{j=-r}^{r} h[i, j]\, f[m + i,\, n + j] .$$

Cross-correlation with $h$ equals convolution with the reflected kernel $h[-i, -j]$. Template matching by correlation, for example, slides an unflipped template over the image.

Deep-learning libraries implement cross-correlation but call it convolution: PyTorch’s documentation describes its Conv2d layer as computing a 2D cross-correlation. Dumoulin and Visin (2016) note that the two become interchangeable when the kernel is learned: a network can learn the flipped kernel as easily as the original. The distinction matters when a designed kernel is copied between a signal-processing library and a network.

Properties

• Linearity. $(a f_1 + b f_2) * h = a (f_1 * h) + b (f_2 * h)$.
• Shift invariance. Shifting the input shifts the output by the same amount; the same weights are used at every position. Conversely, every linear, shift-invariant (LSI) operation on images is a convolution with its impulse response, so LSI systems and convolutions are the same thing.
• Commutativity and associativity. $f * h = h * f$ and $(f * h_1) * h_2 = f * (h_1 * h_2)$. Two filters applied in sequence equal one filter with the combined kernel, so smoothing with a Gaussian and then differentiating equals convolving once with the derivative of a Gaussian. Cross-correlation has neither property in general. Both properties are exact for unbounded signals and for full (zero-padded, uncropped) convolution; other boundary treatments and cropping to the input size break them near the border.
• Identity. The impulse $\delta$, with a single 1 at the origin, leaves the image unchanged: $f * \delta = f$.
• Separability. A kernel that is the outer product of two 1D kernels, $h[i, j] = h_y[i]\, h_x[j]$, can be applied as a 1D convolution along the rows followed by one along the columns. For a $k \times k$ kernel this cuts the work per pixel from $k^2$ to $2k$ multiplications, from 225 to 30 for $k = 15$. The box filter, the Gaussian, and the Sobel kernels are separable; a kernel that is not can be approximated by a sum of a few separable ones using its singular value decomposition.

Boundaries and output size

Near the border the kernel reaches past the edge, so the missing pixels must be supplied or the output shrunk. Common extensions are zero padding (darkens the border of a smoothed image), replicate (repeat the edge pixel), reflect (mirror the image at its edge), and wrap (treat the image as periodic, which is what the discrete Fourier transform assumes). Libraries name these differently and disagree about whether a reflection repeats the edge pixel, so check the definition before comparing results.

For an $N$-pixel row and a $k$-tap kernel there are three conventions for the output size: full ($N + k - 1$, every partial overlap), same ($N$, centered on the input), and valid ($N - k + 1$, only positions where the kernel lies entirely inside the image).

The convolution theorem

The Fourier transform turns convolution into pointwise multiplication: the spectrum of $f * h$ is the product of the spectra of $f$ and $h$. The kernel’s spectrum, its frequency response, says how much of each spatial frequency the filter passes, which is how low-pass, high-pass, and band-pass filters are defined. The theorem also gives a fast algorithm. Direct convolution of an $N \times N$ image with a $k \times k$ kernel costs $O(N^2 k^2)$; transforming both with the fast Fourier transform (Cooley and Tukey, 1965), multiplying, and transforming back costs $O(N^2 \log N)$ regardless of $k$. FFT-based convolution pays off for large kernels, with a crossover that depends on the implementation. It is circular: unless the image is padded first, content wraps around from one border to the other.

Examples

• Box blur. A $k \times k$ kernel of equal weights $1/k^2$ averages a neighborhood. It is separable and can be computed with running sums at a cost independent of $k$, but its frequency response has ripples, so it does not suppress fine detail evenly.
• Gaussian smoothing. Weights sampled from a 2D Gaussian give a smooth, rotationally symmetric, separable blur whose width is set by the standard deviation. It is the usual choice for reducing noise and for smoothing before subsampling, as in an image pyramid.
• Derivatives. The central difference $(f[m, n+1] - f[m, n-1])/2$ approximates a horizontal derivative. Laid over the image as a template it is $\tfrac{1}{2}[-1, 0, 1]$; as a convolution kernel, flipped, it is $\tfrac{1}{2}[1, 0, -1]$. Combining it with smoothing in the other direction gives the Sobel kernels used to compute image gradients.
• Sharpening. Unsharp masking adds back a multiple of the detail a blur removes, $f + \alpha (f - g * f)$. By linearity this is a single convolution with the kernel $(1 + \alpha)\delta - \alpha g$, which has a large positive center and negative surround, like the common $3 \times 3$ kernel with 5 at the center and $-1$ at its four neighbors.

The code below shows the kernel flip, separability, and the effect of output-size and boundary modes in SciPy.

import numpy as np
from scipy import signal

# An image with a single bright pixel (an impulse) and an asymmetric kernel.
image = np.zeros((5, 5))
image[2, 2] = 1.0
kernel = np.array([[1, 2, 3],
                   [4, 5, 6],
                   [7, 8, 9]], dtype=float)

conv = signal.convolve2d(image, kernel, mode="same")
corr = signal.correlate2d(image, kernel, mode="same")
print("convolution of an impulse (the kernel itself):")
print(conv[1:4, 1:4].astype(int))
print("correlation of an impulse (the kernel rotated 180 degrees):")
print(corr[1:4, 1:4].astype(int))
print("correlate2d == convolve2d with the flipped kernel:",
      np.allclose(corr, signal.convolve2d(image, kernel[::-1, ::-1], mode="same")))

# Separability: a 2D Gaussian kernel is the outer product of two 1D kernels.
rng = np.random.default_rng(0)
img = rng.random((256, 256))
x = np.arange(-7, 8)
g = np.exp(-x**2 / (2 * 2.5**2))
g /= g.sum()                      # 15-tap 1D Gaussian, sigma = 2.5
G = np.outer(g, g)                # 15 x 15 2D kernel
full = signal.convolve2d(img, G, mode="valid")
rows = signal.convolve2d(img, g[None, :], mode="valid")
sep = signal.convolve2d(rows, g[:, None], mode="valid")
print(f"separable vs full 2D: max difference {np.abs(full - sep).max():.1e}")
print(f"multiplications per output pixel: full {G.size}, separable {2 * g.size}")

# Output sizes and boundary handling.
for mode in ["full", "same", "valid"]:
    print(f"mode={mode:5s}: output shape {signal.convolve2d(img, G, mode=mode).shape}")
ramp = np.tile(np.arange(1.0, 6.0), (5, 1))     # columns 1, 2, 3, 4, 5
box = np.ones((3, 3)) / 9
for boundary in ["fill", "symm", "wrap"]:
    out = signal.convolve2d(ramp, box, mode="same", boundary=boundary)
    print(f"boundary={boundary}: middle row {np.round(out[2], 3)}")

Output:

convolution of an impulse (the kernel itself):
[[1 2 3]
 [4 5 6]
 [7 8 9]]
correlation of an impulse (the kernel rotated 180 degrees):
[[9 8 7]
 [6 5 4]
 [3 2 1]]
correlate2d == convolve2d with the flipped kernel: True
separable vs full 2D: max difference 7.8e-16
multiplications per output pixel: full 225, separable 30
mode=full : output shape (270, 270)
mode=same : output shape (256, 256)
mode=valid: output shape (242, 242)
boundary=fill: middle row [1. 2. 3. 4. 3.]
boundary=symm: middle row [1.333 2.    3.    4.    4.667]
boundary=wrap: middle row [2.667 2.    3.    4.    3.333]

The separable Gaussian matches the full 2D convolution to rounding error. On a ramp, the box filter is exact in the interior, but zero padding (fill) pulls the right edge down from 5 to 3, wrapping mixes in the opposite edge, and SciPy’s symm reflection, which repeats the edge pixel, stays closest to the true values; for a $3 \times 3$ kernel it coincides with replicating the edge.

Convolution in CNNs

A convolutional layer applies many learned kernels at once. Its input has $C_{\text{in}}$ channels, and each of its $C_{\text{out}}$ kernels spans all input channels, so the weights form a $C_{\text{out}} \times C_{\text{in}} \times k \times k$ array and each output channel is the sum of per-channel correlations plus a bias. Two parameters control the output size. Padding adds $p$ zeros (or another extension) around the input, and stride $s$ evaluates the kernel only at every $s$-th position. Dumoulin and Visin (2016) give the resulting output size for an input of size $i$ as

$$o = \left\lfloor \frac{i + 2p - k}{s} \right\rfloor + 1 ,$$

so $p = \lfloor k/2 \rfloor$ with $s = 1$ keeps the size (“same” padding for odd $k$). PyTorch’s formula adds a dilation factor that spaces out the kernel taps. A stride greater than one is a convolution followed by subsampling, which is not shift-invariant and can alias; see sampling and aliasing.

Common Misconceptions

• “A convolutional layer computes a convolution.” It computes a cross-correlation; the two coincide only for kernels symmetric under a 180-degree rotation, and an antisymmetric designed kernel such as a derivative changes sign between conventions.
• “Convolution is shift-invariant, so a CNN is too.” Each stride-1 layer is shift-equivariant up to border effects, but striding and pooling subsample, and the network as a whole is not.
• “FFT convolution is always faster.” For the small kernels common in image processing, direct or separable convolution is usually faster.
• “Border handling is a detail.” For large kernels or small images, the boundary extension changes a large fraction of the output.

Where It Is Used

• Linear filtering. Smoothing, sharpening, and band-pass filtering use designed kernels; nonlinear filters such as the median filter are not convolutions.
• Derivatives and features. The Sobel and Laplacian operators and the derivative-of-Gaussian filters behind edge and corner detection are convolutions.
• Multi-scale representations. Each level of an image pyramid is computed by smoothing and then subsampling, a step that sampling and aliasing explains.
• Image formation and restoration. Optical blur and camera shake are modeled as convolution with a point spread function, and deblurring tries to invert it.
• Motion and matching. The window sums of gradient products in dense Lucas–Kanade and window-based cost aggregation in a cost volume are box or Gaussian convolutions.
• Convolutional neural networks. Stacks of learned convolutions, nonlinearities, and subsampling are the backbone of networks for classification, detection, and segmentation.