Transform Theory & the 2-D DFT

Why transform an image at all

A pixel grid is a perfectly good way to store an image, but a bad way to reason about it. 2-D transforms rewrite an image in a different basis — one where enhancement, restoration, coding, and compression all become much simpler operations. This unit covers four of the classic ones: the Fourier, discrete cosine, Walsh–Hadamard, and Haar transforms. (A fifth, the data-dependent Karhunen–Loève transform, is worth knowing exists but is out of scope here.)

Orthogonal & unitary kernels

Every transform in this unit is built from a unitary matrix $C$ : one where $(C^{T})^{*} = C^{- 1}$ . If $C$ is real, that condition simplifies to $C^{T} = C^{- 1}$ — an orthogonal matrix. A rotation matrix is the textbook example:

R_{z} = [cos θ sin θ - sin θ cos θ] = [v_{1 r} v_{2 r}]

Its rows $v_{1}$ and $v_{2}$ are unit length and perpendicular for every $θ$ — $v_{1} \cdot v_{2} = 0$ and $v_{1} \cdot v_{1} = v_{2} \cdot v_{2} = 1$ . That's orthonormality, and it's the property every transform kernel in this unit is built to have.

Interactive · Orthogonal Basis

Rotation angle θ

v₁ and v₂ are the rows of the rotation matrix R_z. Spin θ all the way around — the two arrows stay perpendicular and unit-length at every angle, which is exactly what makes R_z orthogonal.

The general transform pair

Every 2-D transform this course covers has the same shape. Given a forward kernel $k_{f}$ , the transform and its inverse are:

T (u, v) = k_{f} (x, u) f (x, y) k_{f} (y, v)^{T *} f (x, y) = k_{i} (x, u) T (u, v) k_{i} (y, v)^{T *}

where $k_{i} = k_{f}^{- 1} = k_{f}^{T *}$ when the kernel is orthogonal. When the kernel is also real and symmetric — true for the DCT, Hadamard, and Haar kernels used later in this unit — the forward and inverse kernels collapse to the same matrix $K$ , and the whole family reduces to one clean pattern:

T = K f K f = K T K

Keep that formula in mind — it's exactly what powers every basis-image widget for the rest of this unit, just with a different $K$ plugged in each time.

The discrete Fourier transform of an image

The Fourier transform is the special case where the kernel is a complex exponential:

F (u, v) = \frac{1}{N} x = 0 \sum N - 1 y = 0 \sum N - 1 f (x, y) e^{- j 2 π (ux + v y) / N}, f (x, y) = u = 0 \sum N - 1 v = 0 \sum N - 1 F (u, v) e^{j 2 π (ux + v y) / N}

Because $e^{- j 2 π (ux + v y) / N} = e^{- j 2 π ux / N} \cdot e^{- j 2 π v y / N}$ , the kernel is separable: a full 2-D DFT can be computed as a 1-D DFT of every row, followed by a 1-D DFT of every column of the result. That's what makes 2-D transforms tractable at all — nobody computes the double sum directly.

Interactive · 2-D DFT

f(x, y)

|F(u, v)|, log-scaled

Center the spectrum

Why the spectrum gets centered and log-scaled

Multiplying $f (x, y)$ by $(- 1)^{x + y}$ before transforming shifts the origin of $F (u, v)$ to the middle of the display instead of the corners — purely a display convenience, and exactly what the checkbox above toggles.

Separately, real spectra decay so fast with frequency that the high-frequency detail is invisible next to the huge DC term. Displaying $D (u, v) = lo g (1 + ∣ F (u, v) ∣)$ instead of $∣ F (u, v) ∣$ directly compresses that huge dynamic range so both ends stay visible — the same trick the widget above uses to render its spectrum panel.

Properties worth carrying forward

Spectrum & power spectrum — with $F (u, v) = R (u, v) + j I (u, v)$ , the magnitude $∣ F (u, v) ∣ = R^{2} + I^{2}$ is the Fourier spectrum, and $∣ F (u, v) ∣^{2}$ is the power (or energy) spectrum.
Periodicity — $F (u, v) = F (u + N, v) = F (u, v + N)$ : the DFT is inherently periodic, which is also why it can wrap around and alias if you're not careful.
Conjugate symmetry — for a real image, $F (u, v) = F^{*} (- u, - v)$ , so $∣ F (u, v) ∣ = ∣ F (- u, - v) ∣$ : the spectrum is mirror-symmetric about the origin.
Distributivity, but not over products — $F [f_{1} + f_{2}] = F_{1} + F_{2}$ , but $F [f_{1} \cdot f_{2}] \neq = F_{1} \cdot F_{2}$ . Multiplying two images and transforming is not the same as multiplying their transforms — instead, convolution in space corresponds to multiplication in frequency: $f * g ⟷ F \cdot G$ . That's the identity behind the sampling argument from the previous lesson.

A fact the continuous Fourier transform doesn't get

The continuous Fourier transform only exists for functions satisfying certain convergence conditions. The discrete Fourier transform has no such worry: because the exponential kernel is orthogonal over a finite sum, $F (u, v)$ exists for every finite discrete image, no exceptions. One less thing to check before you use it.

Check your understanding

Multiplying f(x, y) by (−1)^(x+y) before taking the DFT is done in order to: