How unit 2 is examined
This unit covers the Fourier, fast Fourier, Walsh-Hadamard and cosine transforms; no topic was asked in the supplied papers, so each is kept to definition, formula and the points that earn marks.
Image transformations, Introduction to Fourier transforms
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>An image transform converts an image from the spatial domain to another domain, such as frequency, where it is easier to analyse, filter or compress, and the inverse transform recovers the image exactly.</mark>
Key points.
- Transforms are linear and reversible, so no information is lost.
- The Fourier transform expresses an image as a sum of sine and cosine waves of different frequencies.
- Low frequencies carry smooth regions and high frequencies carry edges and noise.
- The 2-D pair is $F(u,v)=\iint f(x,y)\,e^{-j2\pi(ux+vy)}\,dx\,dy$ with the inverse using $e^{+j2\pi(ux+vy)}$.
Discrete Fourier transforms
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. ==The 2-D DFT of an $M\times N$ image is $F(u,v)=\sum_{x=0}^{M-1}\sum_{y=0}^{N-1} f(x,y)\,e^{-j2\pi(ux/M+vy/N)}$, and the inverse carries the factor $\frac{1}{MN}$.==
Key points.
- The DFT works on sampled data, so it can be computed on a computer.
- It is separable: a row-wise 1-D DFT followed by a column-wise 1-D DFT gives the 2-D result.
- $F(0,0)$ is the sum of all pixels, so $F(0,0)/MN$ is the average gray level (DC term).
- The transform is periodic and conjugate symmetric, and multiplying $f(x,y)$ by $(-1)^{x+y}$ moves the origin to the centre.
Fast Fourier transform
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>The FFT is an algorithm that computes the DFT by repeatedly splitting an $N$-point transform into two $N/2$-point transforms, reducing the work from $N^2$ to $N\log_2 N$ operations.</mark>
Key points.
- Cooley-Tukey (decimation in time) splits the input into even- and odd-indexed samples.
- It requires $N$ to be a power of 2 and uses $W_N=e^{-j2\pi/N}$, with $F(u)=F_e(u)+W_N^{u}F_o(u)$.
- For $N=8$ direct computation needs 64 complex multiplications and the FFT needs $\frac{N}{2}\log_2 N=12$.
- Each butterfly combines two values, and the inverse FFT uses the same structure with conjugate weights.
Walsh transformation, Hadamard transformation
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>The Hadamard transform uses a matrix of only +1 and -1 whose rows are orthogonal, and the Walsh transform is the same matrix with rows reordered by sequency (number of sign changes).</mark>
Key points.
- The kernel is real and needs only additions and subtractions, so it is faster than the DFT.
- The matrix is built recursively: $H_2=\begin{bmatrix}1&1\\1&-1\end{bmatrix}$ and $H_{2N}=\begin{bmatrix}H_N&H_N\\H_N&-H_N\end{bmatrix}$.
- The 2-D transform is $T=\frac{1}{N}HfH$, and since $H^{-1}=\frac{1}{N}H$ the inverse has the same form.
- Walsh-Hadamard has good energy compaction and is used in compression and pattern matching.
Discrete Cosine Transformation
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. ==The DCT expresses an image block as a sum of cosine functions of increasing frequency: $C(u)=\alpha(u)\sum_{x=0}^{N-1} f(x)\cos\frac{(2x+1)u\pi}{2N}$, with $\alpha(0)=\sqrt{1/N}$ and $\alpha(u)=\sqrt{2/N}$ otherwise.==
Key points.
- The DCT is real-valued and its basis functions are orthogonal.
- It has strong energy compaction, so most of the energy lies in a few low-frequency coefficients.
- It avoids the boundary discontinuity of the DFT, giving fewer blocking artefacts.
- JPEG applies the 2-D DCT on 8x8 blocks, then quantizes and encodes the coefficients.
Last-minute revision
- An image transform is linear, reversible and moves the image to a domain like frequency.
- DFT: $F(u,v)=\sum\sum f(x,y)e^{-j2\pi(ux/M+vy/N)}$, inverse has $\frac{1}{MN}$.
- $F(0,0)$ is the sum of all pixels; divided by $MN$ it is the mean gray level.
- The DFT is separable, periodic and conjugate symmetric.
- Multiply by $(-1)^{x+y}$ to centre the spectrum.
- FFT cost is $N\log_2 N$ against $N^2$ for the DFT; $N$ must be a power of 2.
- For $N=8$: 64 multiplications direct, 12 with the FFT.
- Hadamard matrix has entries +1/-1; $H_{2N}$ is built from $H_N$ blocks.
- Walsh is Hadamard ordered by sequency.
- DCT has real coefficients and good energy compaction; JPEG uses 8x8 DCT.
Memory hooks
- DFT to FFT: "split even and odd, halve the work again and again".
- Hadamard: "plus-minus one, add and subtract only".
- Walsh = Hadamard sorted by sequency.
- DCT: "Compaction King, JPEG's engine".
Coverage checklist
- Image transformations, Introduction to Fourier transforms: definition, 2-D Fourier pair; no past questions.
- Discrete Fourier transforms: DFT formula, separability, DC term; no past questions.
- Fast Fourier transform: N log N cost, butterfly, N=8 count; no past questions.
- Walsh transformation, Hadmord transformation: matrix construction, sequency, 2-D form; no past questions.
- Discrete Cosine Transformation: formula, compaction, JPEG use; no past questions.