Lesson 15: The Fourier Transform and Frequency-Domain Filtering¶

Every filter so far has worked directly on pixel neighborhoods. The Fourier transform offers a completely different view: any image can be rewritten as a sum of sinusoidal gratings at different frequencies and orientations. Filtering can then be done by directly boosting or suppressing specific frequencies — and, thanks to the convolution theorem, this turns out to be mathematically the same operation as spatial convolution, just seen from a different angle.

1D warm-up: a signal as a sum of sinusoids¶

Any signal can be approximated by adding up sine and cosine waves of different frequencies. For example, a square wave is the sum of sine waves at increasing frequencies (odd harmonics, decreasing amplitude). The Fourier transform is the tool that goes the other way: given a signal, it tells you exactly which frequencies (and how much of each) are present.

This animation builds the square wave up one pair of odd harmonics at a time, showing the partial sum converge toward the true square wave while a fixed overshoot ("ringing") near each jump never fully disappears — the Gibbs phenomenon. The reason: reproducing an instantaneous jump exactly would require infinitely many frequencies, so truncating to a finite number of harmonics is really a hard cutoff in frequency — some frequencies kept completely, the rest discarded completely. That hard cutoff is what produces the ripple, a pattern that will reappear later in this lesson whenever frequencies are cut off sharply instead of faded out smoothly.

Fourier pairs: sharp in one domain, spread out in the other¶

The square wave above only used the 1D Fourier transform informally, as a sum of sines. More precisely, the Fourier transform turns any signal into a function of continuous frequency (its spectrum), and the two are linked as a Fourier pair: compact and sharp in one domain always corresponds to spread out in the other. The clearest example: a box pulse is sharp-edged and finite in space, but its transform is a sinc function that extends — and oscillates — forever (box ↔ sinc). An even simpler case is a pure sine wave, spread out forever in space, whose Fourier transform is two sharp spikes in frequency (sine ↔ spikes) — we'll see this next.

The 2D Fourier transform of an image¶

The 2D discrete Fourier transform (DFT) of an image decomposes it into 2D sinusoidal gratings at every combination of horizontal and vertical frequency. The algorithm for computing the DFT is the fast Fourier transform (FFT) (np.fft.fft2), which results in a complex-valued (real + imaginary) 2D array. Similar to the image gradient, we usually view the Fourier transform's magnitude (how much of each frequency is present) and orientation. Two common tricks for visualization: show the magnitude on a log scale, and shift the zero-frequency (average brightness) term from the top-left corner to the center.

The bright cross through the center comes from the square's sharp horizontal and vertical edges — a hard step edge contains energy at every frequency along the direction perpendicular to it, which is why a sharp-edged shape has such a spread-out spectrum (the Fourier-pairs principle from before: sharp in one domain, spread out in the other).

A grating reveals its frequency directly as a spectrum peak¶

As previewed above (sine ↔ spikes), a pure sinusoidal grating is the simplest possible test: its spectrum should be (almost) a single pair of bright dots, at a distance from the center equal to its frequency, in the direction perpendicular to its stripes.

Why a pair, not one dot? A real-valued sine wave is, by Euler's formula, a mix of two complex exponentials in equal amounts: $\sin(2\pi f x) = \frac{1}{2i}\left(e^{i2\pi fx} - e^{-i2\pi fx}\right)$. The Fourier transform of the first exponential is a spike at frequency $f$, and for the other it is at $-f$. Therefore, a real sinusoid produces two spikes at $+f$ and $-f$, symmetric about the zero-frequency (DC) center. In fact, for any real-valued image, its Fourier magnitude is symmetric: $|F(-f)|=|F(f)|$.

This animation rotates the grating through orientations and shows its spectrum updating live — the bright peak pair always sits in the direction perpendicular to the stripes, rotating in lockstep with them.

The below animation instead sweeps the grating's frequency (cycles across the image) from low to high and back (while holding the orientation fixed). The spectrum peak pair moves straight outward from the center as the frequency rises, and back inward (toward the origin) as it falls — with its direction unchanged.

Filtering by editing the spectrum¶

An ideal low-pass filter keeps only frequencies inside a circle around the center (blurs); an ideal high-pass filter keeps only frequencies outside it (edge-enhances).

Once an image is transformed to the frequency domain, we can filter it by masking frequencies directly, then transforming back with the inverse transform. Since the mask is the same size as the image, we can simply elementwise-multiply in the frequency domain. Watch for one side effect in the result below: cutting frequencies off sharply introduces faint ringing near sharp edges — the same hard-cutoff ringing seen in the square-wave demo above, now reappearing as ripples radiating from the photo's sharp edges. The reason is the same box↔sinc Fourier pair from before, just mirrored: since the ideal filter's mask is a hard box in the frequency domain, its spatial kernel is a sinc (which, as shown above, has ripples).

This animation shows the effect of changing the ideal low-pass cutoff radius, with the filtered image updating live. With a large enough radius all frequencies are passed, and the image is unchanged. As the radius shrinks, more and more frequencies get discarded outright, and the ringing noted above becomes increasingly visible.

Avoiding ringing with a Gaussian mask¶

As explained, the faint ripples radiating from the shape edges — the Gibbs phenomenon — are caused by the ideal filter's hard on/off cutoff in frequency. A Gaussian mask, which falls off smoothly instead of cutting off sharply, avoids this entirely.

The convolution theorem¶

Why does frequency-domain filtering work? The convolution theorem

$$\mathcal{F}\{f * g\} = \mathcal{F}\{f\} \cdot \mathcal{F}\{g\}$$

says that convolving two signals in the spatial domain is exactly the same as multiplying their Fourier transforms elementwise, then transforming back — convolution becomes multiplication, and vice versa.

A catch: the DFT gives circular convolution¶

The DFT implicitly treats the image as if it were infinitely repeating (imagine seamless tiles extending forever in both directions). There's no "outside the image", only "the next copy of the same image." So multiplying two DFTs and transforming back doesn't give the ordinary ("linear") convolution from Lesson 10, where the kernel eventually slides off the edge into some explicit border (zero, replicate, reflect); rather, it gives circular convolution, where the kernel that slides off the right edge wraps around and picks up pixels from the left edge instead. The two only agree if the border handling on the spatial side is also wraparound (cv2.BORDER_WRAP).

In practice, though, frequency-domain filtering is rarely used in everyday computer vision. Most kernels — box blur, Gaussian, Sobel, sharpen — are small (3x3 or 5x5), and direct spatial convolution is already fast at those sizes, so the fixed overhead of two forward FFTs and one inverse FFT usually isn't worth paying. The DFT earns its keep mainly once kernels get large.

Exercises¶

1. Rotate the grating in the spectrum-peak experiment (make the stripes diagonal instead of vertical) by building it as a function of x*cos(theta) + y*sin(theta). Predict, then verify, where the spectrum peak moves to.
2. Build a band-pass frequency mask (an annulus: keep frequencies between an inner and outer radius, block everything else) and apply it to photo. What kind of image content survives?
3. Try apply_frequency_filter with a very small Gaussian mask sigma (e.g. 3) versus a large one (e.g. 60) on a photo-like test image, and describe the trend as sigma increases toward the image size.
4. Get linear (not circular) convolution out of an FFT: zero-pad both test_img and kernel to at least (image_size + kernel_size - 1) along each axis before transforming, multiply the spectra, inverse-transform, then crop back down. Compare the result to cv2.filter2D(..., borderType=cv2.BORDER_CONSTANT) (zero-padding border) instead of BORDER_WRAP.
5. Using %timeit, measure direct convolution (cv2.filter2D) against FFT-based convolution (as in freq_result above) for Gaussian kernel sizes 5, 15, 31, 63, and 127 on a 256x256 image. At roughly what kernel size does the FFT approach start winning?