The Convolution Operation: The Mathematics Behind Computer Vision

Introduction

Convolution is a mathematical operation that combines two functions to produce a third function expressing how the shape of one is modified by the other. It appears across mathematics, physics, and engineering — from probability theory (the sum of independent random variables) to signal processing (filtering a signal with a kernel) to differential equations (Green's functions).

In deep learning, convolution serves a specific purpose: it is the mechanism by which a neural network can learn to detect patterns in spatially structured data. Understanding the mathematics of convolution at a deep level is essential for designing CNN architectures, debugging dimension mismatches, implementing efficient operations, and reasoning about what a network learns.

This post provides a thorough mathematical treatment of convolution as used in CNNs. We cover the discrete convolution theorem, the distinction between convolution and cross-correlation, how stride and padding affect output dimensions, the mechanics of dilated and transposed convolution, and modern variants including grouped, depthwise separable, and deformable convolution.

For a broader overview of CNN architecture, see our guide on CNN architecture from the ground up.

Discrete Convolution: Definition and Intuition

For discrete signals, the convolution of two sequences f and g is defined as:

(f * g)[n] = sum{m=-infty}^{infty} f[m] * g[n - m]

The asterisk * denotes the convolution operator. The operation has an intuitive interpretation: one function is reversed and slid across the other; at each position, the overlap is multiplied and summed.

The key detail is the reversal of g. In signal processing, this reversal ensures that convolution is commutative (f * g = g * f) and associative (f * (g * h) = (f * g) * h). These properties are mathematically elegant but largely irrelevant for deep learning — what matters is that the operation captures pattern matching through weighted summation.

def conv1d(signal, kernel):
    N, M = len(signal), len(kernel)
    output_len = N + M - 1
    output = np.zeros(output_len)
    for n in range(output_len):
        acc = 0
        for m in range(M):
            k = n - m
            if 0 <= k < N:
                acc += signal[k] * kernel[m]
        output[n] = acc
    return output

Cross-Correlation: What CNNs Actually Use

Deep learning frameworks do not actually perform convolution. They perform cross-correlation, which eliminates the kernel reversal:

(f star g)[n] = sum_m f[m] * g[n + m]

The difference is the sign in the index of g. In convolution, we use g[n - m] (reversed). In cross-correlation, we use g[n + m] (not reversed). Since convolution kernels are learned from data, the reversal is irrelevant — the network simply learns the weights that produce the desired response, effectively learning the reversed kernel implicitly.

Throughout this post and in virtually all deep learning literature, “convolution” refers to cross-correlation. This is a deliberate simplification; the mathematical distinction matters only when interpreting pretrained kernels or implementing custom operations.

Kernels as Feature Detectors

A convolution kernel is a pattern detector. The output value at each spatial position measures the similarity between the kernel and the local input region. High activation means the pattern matches. Low activation means it does not.

Classical image processing provides intuitive examples. A Sobel edge-detection kernel:

G_x = [[-1, 0, 1], [-2, 0, 2], [-1, 0, 1]]

When convolved with an image, this kernel produces high responses at vertical edges (sharp changes in intensity along the x-axis). The response is positive on one side of the edge and negative on the other, encoding both edge strength and direction.

A Gaussian blur kernel:

G = (1/16) * [[1, 2, 1], [2, 4, 2], [1, 2, 1]]

This computes a weighted average of neighbouring pixels, suppressing high-frequency noise. The weights follow a Gaussian distribution, giving more importance to the centre pixel and less to distant neighbours.

Trained CNNs discover far more sophisticated kernels. Early layers learn Gabor-like filters (oriented edge detectors at various frequencies), colour blobs, and centre-surround detectors analogous to those found in the mammalian primary visual cortex (V1). Middle layers learn texture detectors, part detectors, and pattern combinations. Deep layers learn semantically meaningful concepts.

Output Dimension Calculus

The output spatial dimensions of a convolution are determined by four hyperparameters. The formula is essential knowledge for any CNN practitioner:

H_out = floor((H_in + 2*padding - dilation*(kernel_size-1) - 1)/stride + 1)

Several special cases arise frequently:

• Same convolution: padding = (kernel_size - 1) / 2, stride = 1. Output dimensions equal input dimensions.
• Half-resolution: padding = (kernel_size - 1) / 2, stride = 2. Output dimensions approximately halved.
• Valid convolution: padding = 0. Output smaller than input.

A common mistake is assuming integer division. The formula uses floor because the kernel must fit entirely within the padded input. If the dimensions do not align, the last partial step is dropped.

Stride: Controlling the Step Size

Stride determines how many pixels the kernel moves between consecutive applications. Stride 1 produces a densely computed output map where the kernel overlaps with every possible position. Stride 2 skips every other position, reducing the output resolution by approximately half in each dimension.

The effect of stride is a form of down-sampling, but unlike pooling, the down-sampling is learned — the convolution weights determine which information is preserved and which is discarded. This is why modern architectures increasingly use stride-2 convolutions instead of max pooling.

Padding Strategies and Their Effects

Padding adds extra pixels around the input boundary, controlling how the kernel interacts with edge regions. Without padding, the output is smaller than the input and edge pixels receive less attention than centre pixels.

Zero Padding

The standard approach. Zeros are added around the border. For same convolution with a 3x3 kernel, padding 1 preserves dimensions. Zero padding has a mild boundary effect — features near the edge are partially computed against zeros, which slightly reduces their activation.

Replication and Reflection Padding

Alternative padding modes extend the image by replicating edge pixels or mirroring the image content. These can reduce boundary artifacts compared to zero padding, especially when the image content near the boundary carries information. However, they introduce computational overhead and are rarely used in practice.

Dilated Convolution: Expanding the Receptive Field

Dilated (atrous) convolution introduces gaps between kernel elements, controlled by a dilation rate parameter. A dilation rate of 2 with a 3x3 kernel effectively covers a 5x5 region but uses only 9 parameters.

Y[i, j] = sum_m sum_n X[i + d*m, j + d*n] * K[m, n]

Dilated convolution is used in semantic segmentation (DeepLab), audio generation (WaveNet), and multi-scale feature extraction. Stacking dilated convolutions with exponentially increasing rates produces receptive fields that grow exponentially with depth.

def conv2d(input, kernel, stride=1, padding=0, dilation=1):
    C, H, W = input.shape
    F, _, kH, kW = kernel.shape
    dkH = kH + (kH - 1) * (dilation - 1)
    dkW = kW + (kW - 1) * (dilation - 1)
    if padding > 0:
        input = np.pad(input, ((0,0), (padding, padding), (padding, padding)), mode='constant')
        H += 2 * padding; W += 2 * padding
    out_h = (H - dkH) // stride + 1
    out_w = (W - dkW) // stride + 1
    output = np.zeros((F, out_h, out_w))
    for f in range(F):
        for c in range(C):
            for i in range(out_h):
                for j in range(out_w):
                    for m in range(kH):
                        for n in range(kW):
                            h_idx = i * stride + m * dilation
                            w_idx = j * stride + n * dilation
                            output[f, i, j] += input[c, h_idx, w_idx] * kernel[f, c, m, n]
        output[f] += bias[f]
    return output

Grouped Convolution

Grouped convolution splits the input channels into g groups and applies separate convolution filters to each group. The parameter count drops by a factor of g. Grouped convolution was introduced in AlexNet as an engineering compromise to split the model across two GPUs. It was later discovered to have beneficial regularisation effects: each group learns specialised features without interference. ResNeXt uses 32 groups (called cardinality), showing that increasing cardinality is more effective than increasing depth or width for the same parameter budget.

Depthwise Separable Convolution

Depthwise separable convolution factorises a standard convolution into two stages: a depthwise convolution that applies a single filter per input channel, and a pointwise 1x1 convolution that combines the channel outputs. For a convolution with C_in = C_out = 256 and 3x3 kernels, a standard convolution uses 589,824 parameters. A depthwise separable convolution uses 68,608 parameters — an 8.6x reduction. This efficiency gain makes depthwise separable convolutions the backbone of MobileNet and EfficientNet.

class DepthwiseSeparableConv(nn.Module):
    def __init__(self, in_channels, out_channels, kernel_size=3):
        super().__init__()
        self.depthwise = nn.Conv2d(in_channels, in_channels, kernel_size=kernel_size, padding=kernel_size//2, groups=in_channels, bias=False)
        self.pointwise = nn.Conv2d(in_channels, out_channels, kernel_size=1, bias=True)
    def forward(self, x):
        x = self.depthwise(x)
        x = self.pointwise(x)
        return x

Transposed Convolution: Learning to Upsample

Transposed convolution (often misnamed deconvolution) performs the inverse spatial transformation of a standard convolution: it increases spatial resolution. The operation can be understood as a standard convolution with fractional stride. Conceptually, you insert zeros between input elements, then apply a standard convolution. The kernel learns to fill in the missing spatial information.

Transposed convolutions are used in image super-resolution, semantic segmentation decoders (U-Net, DeepLab), and generative models. However, they can produce checkerboard artifacts when the kernel size is not evenly divisible by the stride. Modern architectures increasingly prefer interpolation-based up-sampling combined with standard convolutions.

def transposed_conv2d(input, kernel, stride=2, padding=1):
    C, H, W = input.shape
    _, F, kH, kW = kernel.shape
    out_h = (H - 1) * stride + kH - 2 * padding
    out_w = (W - 1) * stride + kW - 2 * padding
    output = np.zeros((F, out_h, out_w))
    for c in range(C):
        for f in range(F):
            for i in range(H):
                for j in range(W):
                    h_start = i * stride - padding
                    w_start = j * stride - padding
                    for m in range(kH):
                        for n in range(kW):
                            h_idx = h_start + m
                            w_idx = w_start + n
                            if 0 <= h_idx < out_h and 0 <= w_idx < out_w:
                                output[f, h_idx, w_idx] += input[c, i, j] * kernel[c, f, m, n]
    return output

Computational Complexity and FLOPs

The computational cost of a convolution layer is measured in FLOPs (floating-point operations). For a standard convolution:

FLOPs = C_in * C_out * kH * kW * H_out * W_out * 2

For a layer with 256 input channels, 256 output channels, 3x3 kernels, and a 28x28 output feature map, that is approximately 925 million FLOPs. A ResNet-50 requires about 4.1 GFLOPs for a single 224x224 forward pass. MobileNet requires only 0.6 GFLOPs — a 7x reduction over ResNet-50 with minimal accuracy trade-off.

Implementation: The im2col Algorithm

Naively implementing convolution with nested loops is extremely slow. Most deep learning frameworks use the im2col (image-to-column) algorithm, which converts the convolution into a matrix multiplication. The im2col algorithm unfolds each receptive field window into a column of a large matrix. The kernel weights are similarly unfolded into rows. The convolution then becomes a single matrix multiplication between the unfolded kernel matrix and the unfolded input matrix, which GPUs execute extremely efficiently through optimised GEMM kernels.

The trade-off is memory. For a 256-channel 28x28 output with 3x3 kernels, im2col creates a matrix of 1.8 million entries consuming 7 MB of memory. For high-resolution inputs, this memory cost can be prohibitive, which is why frameworks also provide specialised convolution kernels (cuDNN, MKL-DNN) that use Winograd or FFT-based algorithms for certain kernel sizes.

Deformable Convolution

Standard convolution samples from a fixed rectangular grid. Deformable convolution (Dai et al., 2017) adds learnable 2D offsets to each sampling point, allowing the kernel to adapt its shape to the image content. The offsets are predicted by a separate small convolution layer applied to the same input feature map. During training, both the convolution weights and the offset predictor are learned jointly.

Deformable convolution has become standard in object detection and instance segmentation (Deformable DETR, Mask R-CNN variants). It provides a 15-30% improvement in average precision on standard benchmarks, particularly for objects with non-rigid deformations.