Convolution in computer vision, explained in 5 lines

Module 03 · Computer Vision · 22 concepts

In depth / 15 lines

Convolution, in more detail

Convolution is the operation that made neural networks work on images.

A dense layer would connect every pixel to every neuron, which is hopeless at scale.

One layer on a small colour image would need tens of millions of weights.

It would also have to learn what an edge is separately for every location.

Convolution slides a small grid of weights across the image instead.

At each position it multiplies overlapping numbers and sums them into a single output value.

That small grid is the kernel, and 3 by 3 is the usual size.

The same kernel is used at every position, which is called weight sharing.

So a pattern learned in one corner is detected anywhere in the image for free.

That is the right assumption for images, since an edge is an edge wherever it appears.

It also cuts the parameter count enormously, from millions to a few dozen per filter.

The output is a feature map showing where in the image that pattern was found.

Stacking convolutions widens what each output can see, which is the receptive field.

Early layers therefore see detail and later ones see structure.

The kernel weights are learned by ordinary backpropagation, not designed by hand.

Want the full technical article? Wikipedia ↗

Deep dive

What is underneath Convolution

The operation, written out

(I * K)(i, j) = \sum_{m} \sum_{n} I(i + m, \; j + n) \, K(m, n)

$I$ : the input image or feature map.
$K$ : the kernel, a small grid of learned weights.
$m, n$ : positions inside the kernel.

The kernel is placed over a patch, every overlapping pair is multiplied, and the products are summed into one output number.

Then it slides one position and does it again. The output is a map of how strongly that one pattern appears at every location.

Strictly this is cross-correlation. True convolution flips the kernel first, and since the kernel is learned the flip makes no difference to what the network can express.

The output size

O = \left\lfloor \frac{W - K + 2P}{S} \right\rfloor + 1

$W$ : the input width.
$K$ : the kernel size.
$P$ : the padding added to each side.
$S$ : the stride.

A 32-wide input with a 3-wide kernel, padding 1 and stride 1 gives 32 back, which is why that combination is the default almost everywhere.

P = \frac{K - 1}{2}

That padding keeps the size fixed for any odd kernel, and it is the reason kernels are odd-sized: an even kernel has no centre and cannot be padded symmetrically.

Across channels, which is the part usually skipped

O(i, j, c_{\mathrm{out}}) = \sum_{c_{\mathrm{in}}} \sum_{m} \sum_{n} I(i+m, \; j+n, \; c_{\mathrm{in}}) \, K(m, n, c_{\mathrm{in}}, c_{\mathrm{out}})

A kernel is not 3 by 3. It is 3 by 3 by every input channel, so it sees all channels at once and collapses them into a single number.

\text{parameters} = K \times K \times C_{\mathrm{in}} \times C_{\mathrm{out}} + C_{\mathrm{out}}

A layer taking 64 channels to 128 with 3 by 3 kernels holds 73,856 parameters, regardless of how large the image is.

One layer, in order

Pad the input on every side.
Place the kernel at the top left and take the weighted sum across all input channels.
Add the bias for that output channel.
Slide by the stride and repeat across the width, then down the height.
Repeat for each of the $C_{\mathrm{out}}$ kernels, stacking the results as channels.

Why this and not a dense layer

\text{dense} : (H W C)^2 \text{ parameters}, \qquad \text{conv} : K^2 C_{\mathrm{in}} C_{\mathrm{out}}

A fully connected layer on a 224 by 224 image needs billions of weights. A convolution needs thousands, because the same kernel is reused at every position.

That reuse is a claim about images: a pattern is worth detecting wherever it appears. The network cannot learn otherwise, and on images that constraint is correct.

\mathrm{FLOPs} = 2 \, H_{\mathrm{out}} W_{\mathrm{out}} K^2 C_{\mathrm{in}} C_{\mathrm{out}}

The cost is small in parameters and large in arithmetic, since each kernel is applied at every one of the output positions.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

Why does convolution use far fewer parameters than a fully connected layer?

Computer Vision

22 concepts in this module, then a graded test with every answer explained.

Study this module →