Computer Vision MT25, Fourier transform
Flashcards
1D case
@Define the Fourier transform of a function $f : \mathbb R \to \mathbb R$, and the inverse Fourier transform.
(where $\psi _ u(t) = e^{i2\pi u t}$).
In Fourier analysis, a function $f : \mathbb R \to \mathbb R$ is written as a weighted combination of orthonormal basis functions $\psi _ u (t)$. @Define $\psi _ u (t)$. With respect to which inner product are they orthonormal?
where $u \in (-\infty, \infty)$. They are orthonormal with respect to
\[\langle g, h \rangle = \int^\infty _ {-\infty} g(t) h^\ast (t) \text dt\]@Describe how you can interpret the Fourier transform as letting you write a function $f : \mathbb R \to \mathbb R$ as a weighted “sum” of basis functions.
The inverse Fourier transform says that you can write
\[f(t) = \int^\infty _ {-\infty} F(u) e^{i2\pi u t} \text du\]In this way, $f$ is a weighted combination of basis functions $e^{i 2\pi u t}$.
The Fourier transform associates with a function $f : \mathbb R \to \mathbb R$ a function
\[F(u) = \int^\infty _ {-\infty} f(t) e^{-i2\pi u t} \text dt = \langle f, \psi _ u \rangle\]
such that
\[f(t) = \int^\infty _ {-\infty} F(u) e^{i 2\pi u t} \text du\]
where $\psi _ u(t) = e^{i2\pi u t}$. Interpreting $F(u)$ as the (complex) weight of the sinusoid
\[A \sin(2\pi u t + \phi)\]
in the decomposition of $f(t)$, what is the amplitude $A$ and phase $\phi$ in terms of $F(u)$?
The Fourier transform associates with a function $f : \mathbb R \to \mathbb R$ a function
\[F(u) = \int^\infty _ {-\infty} f(t) e^{-i2\pi u t} \text dt = \langle f, \psi _ u \rangle\]
such that
\[f(t) = \int^\infty _ {-\infty} F(u) e^{i 2\pi u t} \text du\]
where $\psi _ u(t) = e^{i2\pi u t}$. When $f(t)$ is real, what useful identities are there surrounding the real and imaginary parts of $F$?
- $\text{re}(F(u)) = \text{re}(F(-u))$
- $\text{im}(F(u)) = -\text{im}(F(-u))$ (this is why undoing the Fourier transform doesn’t introduce complex values)
@Define the discrete Fourier transform of a function $f : \{0, 1, \ldots, N-1\} \to \mathbb R$, and the inverse discrete Fourier transform.
(where $\psi _ k(n) = e^{i\frac{2\pi k}{N} n}$).
The discrete Fourier transform of a function $f : \{0, 1, \ldots, N-1\} \to \mathbb R$, and the inverse discrete Fourier transform are given by
\[\begin{aligned}
F(k) &= \sum^{N-1} _ {n = 0} f(n) e^{-i \frac{2\pi k}{N}n} = \langle f, \psi _ k \rangle \\
f(n) &= \frac{1}{N} \sum^{N-1} _ {k = 0} F(k) e^{i \frac{2\pi k}{N}n}
\end{aligned}\]
where $\psi _ k(n) = e^{i\frac{2\pi k}{N} n}$. How could compute these via matrix-vector multiplications?
Consider $f$ as a vector in $\mathbb R^N$. Then $F$ is a vector in $\mathbb C^N$ given by
\[F = Uf\]where $U _ {k,n} := e^{-i 2\pi k n / N}$, and
\[f = U^{-1} F = \frac 1 N U^\ast F\]The discrete Fourier transform of a function $f : \{0, 1, \ldots, N-1\} \to \mathbb R$, and the inverse discrete Fourier transform are given by
\[\begin{aligned}
F(k) &= \sum^{N-1} _ {n = 0} f(n) e^{-i \frac{2\pi k}{N}n} = \langle f, \psi _ k \rangle \\
f(n) &= \frac{1}{N} \sum^{N-1} _ {k = 0} F(k) e^{i \frac{2\pi k}{N}n}
\end{aligned}\]
where $\psi _ k(n) = e^{i\frac{2\pi k}{N} n}$. What is always true about $F(k)$ and the result of any inverse DFT?
It is always periodic.
2D case
@Define the 2D Fourier basis function $\psi _ {u, v} (x, y)$.
@Visualise what the real parts of the 2D Fourier basis functions
\[\psi _ {u, v}(x, y) = e^{i 2\pi (ux + vy)}\]
look like for increasing values of $u$ and $v$.
What are plots of the 2D Fourier transform like the following are actually showing?
On the left is the original image, on the right is the plot of the magnitude of the Fourier coefficients $\psi _ {u, v}(x, y) = e^{i 2\pi (ux + vy)}$.
Convolution theorem
@State the convolution theorem.
The Fourier transform of the convolution of two functions is the (pointwise) product of their Fourier transforms:
\[\mathcal F\{ f\ast g \} = \mathcal F\{f\} \mathcal F\{g\}\]The inverse Fourier transform of the product of two Fourier transforms is the convolution of the two inverse Fourier transforms:
\[\mathcal F^{-1}\{FG\} = \mathcal F^{-1}\{F\} \ast \mathcal F^{-1}\{G\}\]The ∆convolution-theorem states that
The Fourier transform of the convolution of two functions is the product of their Fourier transforms:
\[\mathcal F\{ f\ast g \} = \mathcal F\{f\} \mathcal F\{g\}\]
The inverse Fourier transform of the product of two Fourier transforms is the convolution of the two inverse Fourier transforms:
\[\mathcal F^{-1}\{FG\} = \mathcal F^{-1}\{F\} \ast \mathcal F^{-1}\{G\}\]
How can this be used to speed up the calculation of a convolution $f \ast g$?
The Fourier transform of the convolution of two functions is the product of their Fourier transforms:
The inverse Fourier transform of the product of two Fourier transforms is the convolution of the two inverse Fourier transforms:
Computing $f \ast g$ in the spatial domain is $O(N^2)$, but the complexity of computing $\mathcal F^{-1} \{ \mathcal F\{f\} \mathcal F\{g\} \}$ is $O(N \log N)$ using the fast Fourier transform.
@State the time complexity of computing the DFT of a function $f : \{0, 1, \ldots, N-1\}$ and the IDFT of the corresponding $\mathcal F \{f\}$.
using the fast Fourier transform.
Filters using the Fourier transform
Explain and @visualise how you could implement a low- or high-pass filter on an image $f$.
Compute the DFT of the image $f$, remove the high or low frequencies, and then apply the IDFT.
Explain and visualise how you could remove the periodic pattern in this image
using the Fourier transform.
Calculate the DFT, remove the peaks, and then apply the IDFT.
Bite-sized
Euler’s formula: $e^{i\phi} = <span class="cloze" tabindex="0">\cos \phi + i \sin \phi</span>$. As a special case ($\phi = \pi$) we get Euler’s identity $e^{i\pi} + 1 = 0$. This is the algebraic foundation of the Fourier basis functions $\psi _ u(t) = e^{i 2\pi u t}$.
@State how translation, rotation, and scaling in the spatial domain affect the magnitude of the 2D Fourier transform of an image.
- Translation: leaves the FT magnitude unchanged (only the phase rotates). So
magnitude(FT(shifted image)) = magnitude(FT(image)). - Rotation by angle $\theta$ in the spatial domain rotates the FT magnitude by the same angle $\theta$.
- Scaling by factor $s$ in the spatial domain scales the FT magnitude by $1/s$ (i.e. inverse scaling) — making a feature larger in space makes its frequency content more concentrated near the origin.
These three identities are the standard reason FT magnitude (rather than phase) is what’s plotted: it captures content insensitive to position.
On a 2D Fourier-magnitude plot, points near the centre of the plot correspond to low frequencies (slow-varying content, large-scale features), while points far from the centre correspond to high frequencies (fast-varying content, fine detail and edges).
@Justify why vertical lines in an image produce horizontal lines (and vice versa) in the FT magnitude plot.
A vertical edge in an image is a function that varies fast in the horizontal direction and slowly in the vertical direction. Its energy is therefore concentrated at high horizontal spatial frequency and low vertical spatial frequency, which on the FT magnitude plot is a streak running along the $u$ (horizontal-frequency) axis — i.e. horizontally.
Equivalently: the 2D Fourier basis functions $\psi _ {u, v}(x, y) = e^{i 2\pi(ux + vy)}$ are plane waves whose wavefronts are perpendicular to the frequency vector $(u, v)$. So vertical wavefronts in the image (a vertical edge) correspond to a horizontal $(u, v)$ direction in frequency space.
The hybrid images construction (Oliva, Torralba, Schyns, SIGGRAPH 2006) combines two images $A$ and $B$ by low-pass filtering one and high-pass filtering the other before summation. From a distance the viewer sees the low-frequency image $A$; up close the viewer sees the high-frequency image $B$. The classic example given in the lecture is the Einstein / Marilyn Monroe hybrid.
For a 1D signal of length $N$, spatial convolution with a filter of length $N$ costs $O(N^2)$, but FFT-based convolution costs $O(<span class="cloze" tabindex="0">N \log N</span>)$ — compute $\mathrm{FFT}(f)$, $\mathrm{FFT}(g)$, multiply pointwise, then inverse-FFT. The crossover where FFT-based convolution becomes cheaper is roughly at moderate filter sizes; CUDA’s cuDNN chooses between the two strategies automatically.
@Justify why convolving an image with a box filter produces ringing/blocky artefacts, while a Gaussian filter does not — in terms of the Fourier transform of each filter.
By the convolution theorem, spatial convolution corresponds to pointwise multiplication of Fourier transforms.
- The Fourier transform of a box filter (rectangular function) is a 2D sinc function: a smooth central blob surrounded by oscillatory positive-and-negative sidelobes. Multiplying the image’s FT by this sidelobed sinc retains alternating-sign high-frequency content, producing visible ringing (Gibbs-style oscillations) in the spatial domain.
- The Fourier transform of a Gaussian is another Gaussian: a smooth monotonically-decaying blob with no sidelobes. Multiplying the image’s FT by this clean low-pass envelope cleanly attenuates high frequencies without introducing oscillations.
Hence the visual quality difference: box → ringing; Gaussian → smooth blur.
On a 2D Fourier-magnitude plot, the value at $(u, v) = (0, 0)$ is called the DC component and equals the sum (or mean, up to normalisation) of all pixel intensities in the image — it captures the image’s average brightness.
The Fourier transform of a Dirac delta $\delta(x - x _ 0)$ is a complex exponential $e^{-i 2\pi u x _ 0}$ (a constant magnitude function with all the position information in its phase). This is the formal reason translation only changes phase, not magnitude.
@Describe the practical recipe for removing periodic noise from an image using the Fourier transform, using Lecture 3’s lunar-orbiter example.
The lunar-orbiter image from 1966 has horizontal scan-line artefacts that show up as a bright vertical line of peaks in the FT magnitude (vertical because horizontal stripes have vertical spatial frequencies).
Recipe:
- Compute the 2D DFT of the noisy image.
- Identify the bright peaks in the magnitude that correspond to the periodic noise (they form a structured pattern: a regular noise period $T$ in space gives a bright spike at $1/T$ in frequency).
- Apply a notch filter: zero out a small neighbourhood around each offending peak in the complex-valued spectrum.
- Inverse-DFT back to the spatial domain.
The reconstructed image keeps essentially all the natural content (whose spectrum is broadband) but loses the narrow-band noise.
Natural-image power spectra (averaged over many photos of e.g. forests, mountains, coasts) tend to fall off roughly as $1/f^2$ with radial frequency $f$ — a strong low-frequency bias. Man-made scenes (high buildings, cityscapes) show this fall-off with additional strong concentrations along the horizontal and vertical axes, reflecting the dominance of vertical and horizontal edges.