CNNs for Images Revisited

A convolutional layer applies a small learnable filter (also called a kernel), typically of size 3×3 or 5×5 spatially, across every position of its input, computing a weighted sum of the pixels under the filter plus a bias, followed by a pointwise nonlinearity such as ReLU. Formally, for an input feature map $X$ with channels indexed by $c$, and a filter $W$ of shape $(C_{in}, k, k)$, the output at spatial location $(i,j)$ for output channel $o$ is

Crucially, the same weights $W_o$ are used for every $(i,j)$ — this is weight sharing, and it is what distinguishes a convolutional layer from a locally-connected but unshared layer. Because the same filter is convolved everywhere, translating the input by some shift translates the output feature map by the same shift (ignoring border effects): this property is called <span class="wiki-link-missing">equivariance</span> to translation, not invariance — the representation shifts, but the detector itself does not need to be relearned per location. A pooling layer (max-pooling or average-pooling) partitions each channel of a feature map into small neighborhoods (commonly 2×2) and replaces each neighborhood with a single summary statistic — the maximum or the mean. Pooling has no learnable parameters. Its purpose is threefold: it reduces spatial resolution (and hence computation and memory in later layers), it introduces local translation invariance (a feature detected slightly shifted still produces the same pooled output), and it lets subsequent layers' receptive fields grow faster relative to depth. The receptive field of a unit in some layer is the set of input pixels that can affect its value through the chain of convolutions and poolings preceding it. Early layers have small receptive fields and detect low-level patterns (oriented edges, color blobs); because receptive fields compose (a 3×3 filter on top of a 3×3-filter feature map effectively spans 5×5 of the original input), deeper layers see larger regions and can represent higher-level, more abstract structures — textures, object parts, whole objects. This is the mechanism behind hierarchical feature learning: the architecture itself enforces a coarse-to-fine, local-to-global processing order, and Backpropagation then learns the actual filter weights that make each stage useful for the task.

Step 1 — Convolutional layer forward pass. Slide each of $C_{out}$ filters across the input spatially. For an input of size $H \times W \times C_{in}$, filter size $k \times k$, stride $s$, and zero-padding $p$ on each side, the output spatial size is:

Step 2 — Nonlinearity. Apply an elementwise activation (ReLU: $\max(0,x)$ is standard) to each output value — this is what lets the stacked linear convolutions represent nonlinear functions, exactly as in a standard feedforward network.

Step 3 — Pooling. Apply max- or average-pooling over disjoint or overlapping windows (commonly 2×2, stride 2) to downsample the feature map, typically after one or a few conv+ReLU layers.

Step 4 — Stack and repeat. Chain many (convolution → nonlinearity → \[pooling\]) blocks, increasing the number of channels $C_{out}$ as spatial resolution shrinks, so total computation per layer stays roughly balanced.

Step 5 — Head. Flatten or globally-pool the final feature map and feed it into fully-connected layers (or, in fully convolutional variants, further 1×1 convolutions) to produce the task output — class scores, a segmentation map, detections, etc. This connects directly to Image Classification with Deep Networks and Fully Convolutional Networks.

Step 6 — Backward pass. Gradients flow back through pooling (routed only to the max location for max-pool, or spread evenly for average-pool) and through convolution (the gradient with respect to the input is itself a convolution with the flipped filter, and the gradient with respect to each filter weight sums contributions from every spatial position it touched — because the same weight was reused everywhere) using Backpropagation. ``` function CONV2D_FORWARD(X, W, b, stride, pad):

# X: (H, W, Cin), W: (Cout, Cin, k, k), b: (Cout) Xp = ZERO_PAD(X, pad) Hp, Wp, Cin = SHAPE(Xp) Cout, _, k, _ = SHAPE(W) Hout = floor((Hp - k) / stride) + 1 Wout = floor((Wp - k) / stride) + 1 Y = ARRAY(Hout, Wout, Cout) for o in 1..Cout: for i in 0..Hout-1: for j in 0..Wout-1: acc = b[o] for c in 1..Cin: for u in 0..k-1: for v in 0..k-1: acc += W[o][c][u][v] Xp[istride+u][jstride+v][c] Y[i][j][o] = acc return Y function MAXPOOL_FORWARD(X, pool, stride): H, W, C = SHAPE(X) Hout = floor((H - pool) / stride) + 1 Wout = floor((W - pool) / stride) + 1 Y = ARRAY(Hout, Wout, C) ARGMAX = ARRAY(Hout, Wout, C) # store winning index for backward pass for c in 1..C: for i in 0..Hout-1: for j in 0..Wout-1: window = X[istride : istride+pool, jstride : jstride+pool, c] Y[i][j][c] = MAX(window) ARGMAX[i][j][c] = ARGMAX_INDEX(window) return Y, ARGMAX function MAXPOOL_BACKWARD(dY, ARGMAX, X_shape, pool, stride): dX = ZEROS(X_shape) Hout, Wout, C = SHAPE(dY) for c in 1..C: for i in 0..Hout-1: for j in 0..Wout-1: (u, v) = ARGMAX[i][j][c] # position of the max within its window dX[istride+u][j*stride+v][c] += dY[i][j][c] return dX function CONV2D_BACKWARD(dY, X, W, stride, pad):

# returns dX, dW, db -- dY has shape of forward output Y dW = ZEROS(SHAPE(W)) db = ZEROS(Cout) dXp = ZEROS(SHAPE(ZERO_PAD(X, pad))) Xp = ZERO_PAD(X, pad) Hout, Wout, Cout = SHAPE(dY) for o in 1..Cout: for i in 0..Hout-1: for j in 0..Wout-1: db[o] += dY[i][j][o] for c in 1..Cin: for u in 0..k-1: for v in 0..k-1: dW[o][c][u][v] += Xp[istride+u][jstride+v][c] dY[i][j][o] dXp[istride+u][jstride+v][c] += W[o][c][u][v] dY[i][j][o] dX = REMOVE_PAD(dXp, pad) return dX, dW, db ```

Time complexity of one convolutional layer. For an output of size $H_{out} \times W_{out} \times C_{out}$, each output element requires $C_{in} \cdot k \cdot k$ multiply-adds, so the total cost is

This is the exact operation count of the naive triple/quadruple-nested loop in the pseudocode above; no hidden asymptotic slack exists — every multiply-add is necessary to the definition of the convolution sum. Compare this to a fully-connected layer mapping the same $H\times W\times C_{in}$ input to an $H_{out}\times W_{out}\times C_{out}$ output: it would cost $O(H\,W\,C_{in}\cdot H_{out}\,W_{out}\,C_{out})$ — larger by a factor of roughly $\frac{HW}{k^2}$, which for a 224×224 image and a 3×3 filter is a factor of about 5500. This gap is the quantitative justification for why weight sharing matters: the inductive bias that "the same detector is useful everywhere" converts a quadratic-in-image-size cost into a cost that is independent of image size (per output pixel).

Parameter count. A convolutional layer has $C_{out}\,(C_{in} k^2 + 1)$ parameters — independent of $H$ and $W$. A fully-connected layer mapping the same input to the same output size would need $H\,W\,C_{in}\cdot H_{out}\,W_{out}\,C_{out}$ parameters. This is the core statistical argument for CNNs: fewer parameters means a smaller hypothesis space, which by standard learning-theory bounds (VC-dimension or Rademacher-complexity arguments) implies lower sample complexity for a given generalization gap — CNNs need less training data to reach the same test error than an equivalently-sized fully-connected network, provided the translation-equivariance assumption approximately holds for the data, which it does for natural images.

Space complexity. Storing all intermediate activations for backpropagation costs $O\!\left(\sum_\ell H_\ell W_\ell C_\ell\right)$ over all layers $\ell$ — this is the classical memory bottleneck of training deep CNNs, and is why techniques like gradient checkpointing trade recomputation for memory in very deep networks.

Correctness of the backward pass. The claim that $\partial L/\partial X$ is a convolution of $\partial L/\partial Y$ with the flipped kernel, and that $\partial L/\partial W_o(c,u,v)$ sums $X_c(i+u,j+v)\cdot \partial L/\partial Y_o(i,j)$ over all $(i,j)$, follows directly from the multivariate chain rule applied to the forward formula: since $Y_o(i,j)$ depends on $W_o(c,u,v)$ additively across all its uses, and the same weight is reused at every $(i,j)$, the total gradient with respect to that weight is a sum over all positions that used it — this is exactly weight sharing acting in reverse during backpropagation, and it is the same reasoning used for any tied-weight computation graph.

Receptive field recursion. If layer $\ell$ has kernel size $k_\ell$ and stride $s_\ell$, the receptive field size $r_\ell$ of a unit at layer $\ell$, expressed in input pixels, satisfies the exact recursion

Proof sketch: a unit at layer $\ell$ depends on a $k_\ell \times k_\ell$ window of layer $\ell-1$ units, each spaced $\prod_{i<\ell} s_i$ input-pixels apart because of accumulated striding; the receptive field therefore extends the previous one by $(k_\ell - 1)$ steps of that accumulated stride. Applying this recursion confirms, for example, that two stacked 3×3 convolutions (stride 1) yield a receptive field of 5×5, and three yield 7×7 — matching the intuition used in the figure above, and explaining why deep stacks of small filters (as in VGG-style networks) can match the receptive field of one large filter while using fewer parameters ($3\times(3^2)=27$ vs. $7^2=49$ per channel pair) and more nonlinearities.

Tradeoffs. Pooling buys translation invariance and cheaper computation but discards precise spatial information, which hurts tasks needing exact localization (this is precisely the problem Fully Convolutional Networks address by avoiding aggressive pooling near the output). Weight sharing is a strong, usually-correct prior for natural images, but it is not automatically correct for data lacking translation symmetry (e.g., aligned face landmarks or tabular data), where it can underfit by forcing an unhelpful symmetry.

Consider a tiny 5×5 grayscale image (one channel) convolved with a single 3×3 edge-detecting filter, stride 1, no padding. Input $X$ (a vertical edge: dark left half, bright right half): ``` 0 0 5 5 5 0 0 5 5 5 0 0 5 5 5 0 0 5 5 5 0 0 5 5 5 ``` Filter $W$ (a horizontal Sobel-like vertical-edge detector), bias $b=0$: ``` -1 0 1 -2 0 2 -1 0 1 ``` Output size: $H_{out} = \lfloor(5-3)/1\rfloor+1 = 3$, so $Y$ is 3×3. Compute $Y(0,0)$ using the top-left 3×3 window of $X$: ``` 0 0 5 0 0 5 0 0 5 ```

By symmetry every window straddling the edge (columns 0–2, 1–3, or 2–4, any row) gives the same computation pattern, so:

Full output $Y$ after ReLU (all values already ≥0 here): ``` 20 20 0 20 20 0 20 20 0 ``` The filter fires strongly (value 20) exactly where the 3×3 window straddles the true edge (columns 1–3), and gives zero where the window is entirely inside the bright region (columns 2–4, which is uniform, so all directional derivatives vanish) — this confirms the filter is correctly detecting the vertical edge location, and because the same 9 weights produced this correct response at three different row positions without being retrained, it directly demonstrates weight sharing giving translation-equivariant detection. Now apply 2×2 max-pooling, stride 2, to this 3×3 output. With no padding only one full 2×2 window fits (top-left):

giving a 1×1 pooled output of value 20 — a compact, position-summarized signal that "an edge was detected in this region," discarding exactly where within the region it was, which is the intended local-invariance effect of pooling.

CNNs are the backbone of virtually every deployed vision system built before the rise of vision transformers, and remain heavily used today for efficiency reasons. Photo organization and reverse image search use CNN embeddings for similarity. Medical imaging systems use CNNs for tumor detection and segmentation in radiology scans. Autonomous vehicles use convolutional backbones for real-time object detection and lane segmentation, often with architectures directly descended from Fully Convolutional Networks. Face recognition and verification systems on phones run small, efficient convolutional networks on-device. Optical character recognition, industrial defect inspection, satellite image analysis, and video action recognition all rely on the same core primitives — local weight-shared filters, pooling, and hierarchical depth — described here, and the same reasoning about receptive fields and parameter efficiency underlies architecture design in Image Classification with Deep Networks and beyond.

Ask the tutor: How do dilated (atrous) convolutions change the receptive-field recursion, and why do they help in dense prediction tasks like segmentation?