Cross-Correlation vs Convolution: The Sliding-Window Math

Cross-Correlation vs Convolution: The Sliding-Window Math#

Twitter Handle LinkedIn Profile GitHub Profile Tag Tag

Open PyTorch’s nn.Conv2d or Keras’s Conv2D and the documentation calls the operation a convolution. It is not — not in the sense every signal-processing textbook uses. Deep learning computes a cross-correlation: the kernel slides over the image without being flipped, taking a dot product at every position. The difference is a single sign on the kernel indices, and because the kernel is learned it costs the network nothing. But the naming is a real divergence, and naming it honestly is the point of this page.

This is the concept half of the chapter. It is for you if you understood the intro’s three priors and now want the precise sliding-window operator behind them. By the end you can write down 2D cross-correlation entry by entry, derive the output shape under any stride and padding, explain the multi-channel weight tensor, and say exactly why a “convolutional” layer that omits the flip is still a convolutional layer.

Prerequisites

This page builds directly on the convolutional-kernels intro, which motivates locality, parameter sharing, and translation equivariance. The notation follows the deep-learning notation page. The from-scratch code for every operator defined here lives in the implementation chapter.

Cross-correlation: the sliding dot product#

Intuition first. Place a small kernel \(\mathbf{K}\) over the top-left corner of the image \(\mathbf{X}\), multiply overlapping entries element by element, sum the products into a single number, and write that number to the top-left entry of the output. Slide the kernel one column right and repeat; at the end of the row, drop one row down and start again. The output grid you fill in is the feature map: at every position it records how well the kernel matched the patch underneath.

That is the entire operator. Formally:

Definition 79 (2D cross-correlation)

Let \(\mathbf{X} \in \R^{H \times W}\) be an input image and \(\mathbf{K} \in \R^{K_h \times K_w}\) a kernel. The 2D cross-correlation of \(\mathbf{X}\) with \(\mathbf{K}\) is the matrix \(\mathbf{Y} \in \R^{(H - K_h + 1) \times (W - K_w + 1)}\) whose \((i, j)\) entry is

(158)#\[ Y_{i,j} \;\defeq\; \sum_{u=0}^{K_h-1} \sum_{v=0}^{K_w-1} X_{i+u,\; j+v}\, K_{u,v}. \]

Each output element is the dot product of the kernel with the \(K_h \times K_w\) patch of \(\mathbf{X}\) anchored at row \(i\), column \(j\). Equivalently, \(\mathbf{Y}\) is the matrix of inner products between \(\mathbf{K}\) and every same-shaped window of \(\mathbf{X}\).

Two conventions are hidden in that definition and are worth pulling out. There is no flip: the kernel index \(K_{u,v}\) multiplies \(X_{i+u, j+v}\) with the same sign on both axes, not \(X_{i-u, j-v}\). And there is no padding and unit stride: the kernel stops as soon as it no longer fits, which is why the output is smaller than the input. Both are relaxed below.

A worked example: a 3×3 kernel on a 5×5 input#

Example 31 (A 3×3 box kernel on a 5×5 input)

Take the \(5 \times 5\) input and \(3 \times 3\) all-ones kernel

\[\begin{split} \mathbf{X} = \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 \end{bmatrix}, \qquad \mathbf{K} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}. \end{split}\]

The output shape is \((5 - 3 + 1) \times (5 - 3 + 1) = 3 \times 3\). The top-left entry is the dot product of \(\mathbf{K}\) with the top-left \(3 \times 3\) patch of \(\mathbf{X}\):

(159)#\[ Y_{0,0} = 1 + 2 + 3 + 6 + 7 + 8 + 11 + 12 + 13 = 63. \]

One step down and one across, the window anchored at \(X_{1,1} = 7\) sums to

(160)#\[ Y_{1,1} = 7 + 8 + 9 + 12 + 13 + 14 + 17 + 18 + 19 = 117. \]

Repeating for all nine anchors gives the full feature map

(161)#\[\begin{split} \mathbf{Y} = \begin{bmatrix} 63 & 72 & 81 \\ 108 & 117 & 126 \\ 153 & 162 & 171 \end{bmatrix}. \end{split}\]

Two patterns are worth noticing. Each step right adds \(9\) — three rows times the \(+3\) gained by dropping column \(k\) and adding column \(k+3\) into the window. Each step down adds \(45\), three columns times the \(+15\) between adjacent rows of \(\mathbf{X}\). A box kernel is a local mass detector, and the feature map faithfully records how much mass sits under each window.

The arithmetic is mechanical, so let a machine check it. The cell below reproduces every entry of Example 31 using nothing but NumPy — the same operator we will package as cross_correlation_2d in the implementation chapter.

 1x = np.array(
 2    [
 3        [1.0, 2.0, 3.0, 4.0, 5.0],
 4        [6.0, 7.0, 8.0, 9.0, 10.0],
 5        [11.0, 12.0, 13.0, 14.0, 15.0],
 6        [16.0, 17.0, 18.0, 19.0, 20.0],
 7        [21.0, 22.0, 23.0, 24.0, 25.0],
 8    ]
 9)
10box = np.ones((3, 3))
11
12# Manual sliding-window cross-correlation.
13out_h, out_w = x.shape[0] - box.shape[0] + 1, x.shape[1] - box.shape[1] + 1
14y = np.zeros((out_h, out_w))
15for i in range(out_h):
16    for j in range(out_w):
17        y[i, j] = np.sum(x[i : i + 3, j : j + 3] * box)
18
19print("shape:", y.shape)        # (3, 3)
20print("Y[0, 0]:", y[0, 0])      # 63.0
21print("Y[1, 1]:", y[1, 1])      # 117.0
22print(y)

shape: (3, 3)
Y[0, 0]: 63.0
Y[1, 1]: 117.0
[[ 63.  72.  81.]
 [108. 117. 126.]
 [153. 162. 171.]]

Stride and padding#

The definition above shrinks the output by \(K_h - 1\) rows and \(K_w - 1\) columns. Two knobs restore control over the output size.

Padding \(P\) surrounds the input with \(P\) rings of zeros on every side, so the kernel can sit against — and even hang over — the original border. With \(P = 1\) and a \(3 \times 3\) kernel, the feature map keeps the input’s height and width (the so-called “same” padding).

Stride \(S\) is how far the kernel steps between anchors. \(S = 1\) visits every position; \(S = 2\) visits every other, halving each spatial dimension and turning the convolutional layer into a learned downsampler.

Putting both into Definition 79 gives the output-shape formula that every framework’s Conv2d obeys:

(162)#\[ H_{out} = \left\lfloor \frac{H_{in} + 2P - K_h}{S} \right\rfloor + 1, \qquad W_{out} = \left\lfloor \frac{W_{in} + 2P - K_w}{S} \right\rfloor + 1. \]

The floor is what handles strides that do not divide the padded input evenly; the framework simply drops the sliver of input the last kernel position would need. Sanity checks: with \(P = 0\), \(S = 1\) the formula recovers \(H - K_h + 1\) from Definition 79; with \(P = 1\), \(S = 1\), \(K_h = 3\) it gives \(H_{out} = H_{in}\).

Multiple input and output channels#

Real images are not single-channel. An RGB input has \(C_{in} = 3\) channels, and a hidden layer deep in a network may have hundreds. The operator generalises by giving the kernel its own depth.

Each output channel \(c\) is produced by a stack of \(C_{in}\) two-dimensional kernels \(\mathbf{W}_{c, c'} \in \R^{K_h \times K_w}\), one per input channel. Cross-correlate each kernel with its matching input channel and sum the results, then add a per-channel bias \(b_c\):

(163)#\[ Y_{c,\, i,\, j} \;\defeq\; b_c + \sum_{c'=1}^{C_{in}} \sum_{u, v} X_{c',\, i+u,\, j+v}\, W_{c,\, c',\, u,\, v}. \]

The full weight tensor is therefore \(\mathbf{W} \in \R^{C_{out} \times C_{in} \times K_h \times K_w}\), with a bias vector \(\mathbf{b} \in \R^{C_{out}}\). The spatial shape formula (162) is unchanged; it now describes each of the \(C_{out}\) output channels independently. This is the tensor shape you will see reported by any framework’s Conv2d, and it is the reason a single convolutional layer holds \(C_{out} \cdot C_{in} \cdot K_h \cdot K_w\) kernel weights rather than just \(K_h \cdot K_w\).

Why we still call it “convolution”#

Remark 46 (Convolution flips the kernel; deep learning does not)

In signal processing, 2D convolution flips the kernel in both axes before sliding it:

(164)#\[ (\mathbf{X} * \mathbf{K})_{i,j} \;\defeq\; \sum_{u, v} X_{i-u,\; j-v}\, K_{u,v}. \]

The operator every framework calls Conv2d drops that flip — it computes Definition 79, not (164). This is a genuine divergence in notation, and it is worth saying plainly rather than papering over.

It is also harmless in practice. Because the kernel entries are learned, a network trained under cross-correlation with kernel \(\mathbf{K}\) computes exactly the family of functions it would under convolution with the flipped \(\widetilde{\mathbf{K}}_{u,v} = K_{-u,-v}\). Gradient descent simply learns the flipped version if it needs to. So the misnomer changes nothing about representational power — only the sign convention on the indices — which is why the entire field has tolerated it for decades.

Summary

If this page had to be one sentence: deep learning’s “convolution” is an unflipped cross-correlation — a shared kernel taking a dot product at every sliding position — and its output shape is \(\lfloor (H_{in} + 2P - K)/S \rfloor + 1\) per spatial axis, with \(C_{out} \times C_{in}\) kernels turning one input stack into \(C_{out}\) output channels.

  • Cross-correlation (no flip) is what Conv2d actually computes; true convolution (164) flips the kernel, but the flip is absorbed by learning (Remark 46).

  • The output-shape formula (162) unifies padding \(P\) and stride \(S\); it specialises to \(H - K + 1\) when \(P = 0, S = 1\).

  • Multi-channel convolution (163) sums one cross-correlation per input channel, producing a \(\R^{C_{out} \times C_{in} \times K_h \times K_w}\) weight tensor.

Next: the from-scratch NumPy implementation, which packages the operator above into cross_correlation_2d and runs a Sobel-style edge detector on a synthetic image. For the motivating priors, see the intro.

Further reading