Computer Vision MT25, Convolutions
Flashcards
What notation convention is used for discrete functions applications $f : \mathbb Z \to \mathbb R$?
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.
- $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$.
(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).
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$.
Bite-sized
Discrete convolution is commutative, i.e. $f \ast g = <span class="cloze" tabindex="0">g \ast f</span>$. This is the algebraic reason the kernel is “flipped” (right-to-left) in the sum: it makes the kernel and signal interchangeable.
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).
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 transformU.)
@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.
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.
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.