Computer Vision MT25, Convolutions

Created: October 15, 2025 · Updated: May 23, 2026 Read markdown About these notes View in context Study these flashcards

Flashcards

What notation convention is used for discrete functions applications $f : \mathbb Z \to \mathbb R$?

discrete-function-bracket-notation

Function application is denoted $f[x]$, like you’re indexing an array.

Suppose:

  • $f : \mathbb Z \to \mathbb R$
  • $g : \mathbb Z \to \mathbb R$

@Define the convolution $f \ast g$, and state which of these is the kernel or filter, and which is the input function.

1d-convolution-definition
\[(f \ast g)[x] = \sum^\infty _ {u = -\infty} f[u] g[x - u]\]
  • $f$ is the kernel or filter
  • $g$ is the input function

Suppose:

  • $f : \mathbb Z \to \mathbb R$
  • $g : \mathbb Z \to \mathbb R$
  • $f$ has finite support in the set $\mathcal M = \{0, \ldots, M - 1\}$, i.e. for all $m \in \mathbb Z \setminus \mathcal M$, $f[m] = 0$, or equivalently $f : \{ 0, \ldots, M-1 \} \to \mathbb R$

@Define the convolution $f \ast g$.

finite-support-1d-convolution
\[(f \ast g)[x] = \sum^{M-1} _ {u = 0} f[u] g[x - u]\]

(note that in particular, the order in which we look at the filter is right-to-left, this is to make it commutative).

Compute this @example convolution.

(note that there is no zero padding, so you may leave the far-left and far-right entries blank).

convolution-example-computation

Suppose:

  • $g : \mathbb Z \times Z \to \mathbb R$
  • $f : \{0, \ldots, M-1\} \times \{0, \ldots, N-1\} \to \mathbb R$

@Define the convolution $f \ast g$.

2d-convolution-definition
\[(f \ast g)[x, y] = \sum^{M-1} _ {u = 0} \sum^{N-1} _ {v = 0} f[u, v] g[x - u, y - v]\]

Bite-sized

Discrete convolution is commutative, i.e. $f \ast g = \class{cloze}{g \ast f}$. This is the algebraic reason the kernel is “flipped” (right-to-left) in the sum: it makes the kernel and signal interchangeable.

Source: Lecture 2, Discrete Convolution slide (and the parenthetical commutativity remark).

bite-convolution-commutative

At the boundary of a finite signal, the simplest convention for evaluating $g[x]$ outside its support is zero-padding: define $g[x] = 0$ for $x$ outside the support. Other common conventions are reflection, replication, and circular wrap-around (the latter implicit in DFT-based convolution).

Source: Lecture 2, Convolution Example boundary-cases discussion.

bite-convolution-boundary-padding

The naive cost of convolving a 1D signal of length $N$ with a filter of length $M$ is $\mathcal{O}(NM)$ multiply-adds. For 2D with $N \times N$ input and $M \times M$ kernel, the cost is $\mathcal O(N^2 M^2)$. (FFT-based convolution reduces this to $\mathcal O(N^2 \log N)$ for large kernels — see Notes - Computer Vision MT25, Fourier transform.)

Source: Lecture 2, Discrete Convolution slide; Lecture 3, Convolution Theorem: Complexity slide.

bite-convolution-naive-cost

@Justify why convolution kernels in CNNs are almost always given odd spatial size ($3 \times 3$, $5 \times 5$, $7 \times 7$, etc.) rather than even.

bite-odd-kernel-size-justification

An odd kernel size $M$ means:

  • There is a well-defined centre pixel, so the output at $(x, y)$ can be aligned with a single input pixel.
  • A “same-size” output needs zero-padding of $\tfrac{M-1}{2}$ on each side; this is an integer only when $M$ is odd, so symmetric padding works cleanly.
  • The output pixel $(x, y)$ then corresponds to a symmetric neighbourhood of the input.

Even-size kernels break this symmetry and require either asymmetric padding or a half-pixel output offset.

Source Lecture 2, Discrete Convolution with Finite Support slide.

Following the lecture’s convention, in $f \ast g$, $f$ is the kernel (filter) and $g$ is the input signal (image). Although mathematically $f \ast g = g \ast f$, this naming reflects which object is being slid over the other in implementation.

Source: Lecture 2, Discrete Convolution with Finite Support slide.

bite-convolution-kernel-vs-input-naming


Similar pages