6 Fourier Analysis and Frequency

Fourier analysis explains an image by decomposing it into oscillatory patterns. In the spatial domain, we see pixels, edges, textures, and objects. In the frequency domain, we see smooth components, sharp transitions, repeated texture, noise, aliasing, and the effect of filters. This chapter develops the mathematical theory of the discrete Fourier transform, convolution theorem, Parseval identity, frequency-domain filtering, sampling, aliasing, and AI connections such as spectral bias, frequency artifacts, and Fourier features.

6.1 Learning Goals

After reading this chapter, students should be able to:

represent one-dimensional and two-dimensional signals using complex exponential bases;
define the discrete Fourier transform and inverse discrete Fourier transform;
explain orthogonality of Fourier modes and the meaning of frequency indices;
interpret Fourier magnitude and phase for images;
prove and use the convolution theorem;
design ideal, Gaussian, high-pass, low-pass, and band-pass filters in the frequency domain;
explain the connection between sampling, aliasing, and the Nyquist frequency;
state Parseval’s identity and interpret frequency energy;
connect Fourier analysis with image denoising, compression, texture, CNN filters, positional encodings, and spectral bias in modern AI.

6.2 5.1 Why Frequency Matters in Computer Vision

Chapters 1–4 treated images as measurements, arrays, sampled functions, and vectors. Fourier analysis gives a complementary viewpoint:

\[ \text{image} = \text{sum of oscillatory patterns at different frequencies}. \]

Low frequencies describe broad smooth structure. High frequencies describe sharp edges, fine texture, noise, and abrupt transitions. This distinction appears throughout computer vision:

smoothing removes high-frequency variation;
sharpening amplifies high-frequency variation;
edge detectors respond to rapid intensity changes;
aliasing appears when high-frequency content is sampled too coarsely;
JPEG-style compression keeps important low- and mid-frequency coefficients;
CNN filters often learn oriented frequency-selective patterns;
transformers use positional encodings that can be understood through sinusoidal bases;
generative models may produce characteristic spectral artifacts;
neural networks often fit low-frequency structure before high-frequency detail.

The central idea of this chapter is:

\[ \text{spatial locality} \quad \longleftrightarrow \quad \text{frequency mixture}. \]

A localized edge is not a single frequency. It requires many frequencies. A smooth region is well described by a small number of low-frequency modes.

For computer vision, frequency analysis is not only a signal-processing tool. It provides a diagnostic language for data quality, augmentation, model behavior, and failure modes.

6.3 5.2 Complex Exponentials as Basis Functions

A real sinusoid has the form

\[ f(t) = A \cos(2\pi \omega t + \phi), \]

where $A$ is amplitude, $\omega$ is frequency, and $\phi$ is phase. Fourier analysis uses complex exponentials

\[ e^{2\pi i \omega t} = \cos(2\pi \omega t) + i\sin(2\pi \omega t) \]

because they make algebra simple. A signal is represented as a weighted sum of such oscillatory functions.

For a discrete signal $x = (x_0,\ldots,x_{N-1})$, the basic Fourier modes are

\[ \varphi_k[n] = e^{2\pi i kn/N}, \qquad k,n=0,1,\ldots,N-1. \]

The index $k$ counts how many cycles the mode completes over $N$ samples.

6.3.1 Orthogonality

The Fourier modes satisfy

\[ \sum_{n=0}^{N-1} e^{2\pi i (k-\ell)n/N} = \begin{cases} N, & k=\ell \pmod N,\\ 0, & k\ne \ell \pmod N. \end{cases} \]

This is the key algebraic fact. It says that different discrete frequencies are orthogonal with respect to the inner product

\[ \langle x,y\rangle = \sum_{n=0}^{N-1} x_n \overline{y_n}. \]

For real image data, the Fourier coefficients are complex. Their magnitudes encode amount of oscillation at a frequency; their phases encode spatial alignment.

6.3.2 Interactive: Fourier basis functions

The plot below compares several sinusoidal basis functions. Low frequency modes vary slowly. High frequency modes alternate rapidly.

6.4 5.3 The Discrete Fourier Transform

For $x\in \mathbb{C}^N$, the discrete Fourier transform, or DFT, is the vector $\widehat{x}\in \mathbb{C}^N$ defined by

\[ \widehat{x}_k = \sum_{n=0}^{N-1} x_n e^{-2\pi i kn/N}, \qquad k=0,1,\ldots,N-1. \]

The inverse transform is

\[ x_n = \frac{1}{N}\sum_{k=0}^{N-1} \widehat{x}_k e^{2\pi i kn/N}. \]

In matrix form,

\[ \widehat{x} = F_N x, \qquad x = F_N^{-1}\widehat{x}, \]

where

\[ (F_N)_{kn}=e^{-2\pi i kn/N}. \]

If we normalize by $1/\sqrt{N}$, the Fourier matrix becomes unitary:

\[ U_N = \frac{1}{\sqrt{N}}F_N, \qquad U_N^*U_N = I. \]

This matters statistically because a unitary transformation preserves energy and Euclidean norm.

6.4.1 Amplitude and Phase

Each Fourier coefficient can be written in polar form:

\[ \widehat{x}_k = r_k e^{i\theta_k}, \]

where

\[ r_k = |\widehat{x}_k|, \qquad \theta_k = \arg(\widehat{x}_k). \]

The magnitude $r_k$ measures how strongly frequency $k$ appears. The phase $\theta_k$ determines how the corresponding oscillation is shifted in space.

A common beginner mistake is to think that magnitude alone determines the image. It does not. Phase is essential for spatial structure. Magnitude describes how much of each frequency appears; phase determines where structures appear.

6.5 5.4 The Two-Dimensional DFT

A grayscale image $I\in\mathbb{R}^{H\times W}$ has two spatial indices. The two-dimensional DFT is

\[ \widehat{I}_{u,v} = \sum_{m=0}^{H-1}\sum_{n=0}^{W-1} I_{m,n} \exp\left(-2\pi i\left(\frac{um}{H}+\frac{vn}{W}\right)\right), \]

where

\[ u=0,1,\ldots,H-1, \qquad v=0,1,\ldots,W-1. \]

The inverse transform is

\[ I_{m,n} = \frac{1}{HW} \sum_{u=0}^{H-1}\sum_{v=0}^{W-1} \widehat{I}_{u,v} \exp\left(2\pi i\left(\frac{um}{H}+\frac{vn}{W}\right)\right). \]

The pair $(u,v)$ is a two-dimensional frequency. Large $u$ corresponds to vertical variation because it changes with row index $m$. Large $v$ corresponds to horizontal variation because it changes with column index $n$.

6.5.1 Separable Matrix Form

Let $F_H$ and $F_W$ be Fourier matrices of sizes $H$ and $W$. Then the 2D DFT can be written as

\[ \widehat{I} = F_H I F_W^T. \]

With unitary normalization, this is a change of orthonormal basis on the row and column spaces. This separable structure is why the 2D FFT is fast: first transform rows, then transform columns.

Index convention

Most numerical libraries store frequency zero at the upper-left corner of the Fourier array. For visualization, one often applies fftshift, which moves the zero frequency to the center. After shifting, low frequencies are near the center and high frequencies are farther away.

6.5.2 Interactive: 2D Fourier magnitude of synthetic images

This demo shows a synthetic image and its log Fourier magnitude. Notice that smooth blobs concentrate energy near the center, while stripes create peaks at oriented frequencies.

6.6 5.5 Frequency, Orientation, and Texture

A two-dimensional sinusoidal pattern can be written as

\[ I(x,y)=A\cos(2\pi(\xi x+\eta y)+\phi). \]

The frequency vector is

\[ \omega = (\xi,\eta). \]

Its magnitude

\[ \|\omega\|_2 = \sqrt{\xi^2+\eta^2} \]

controls the rate of oscillation. Its direction controls orientation. Lines of constant phase satisfy

\[ \xi x+\eta y = c, \]

so the visible stripe direction is perpendicular to $\omega$.

This explains why oriented textures create localized peaks in the Fourier domain. A vertical stripe pattern varies horizontally, so its frequency vector points in the horizontal frequency direction. A horizontal stripe pattern varies vertically.

6.7 5.6 Parseval’s Identity and Spectral Energy

For the unnormalized DFT convention above, Parseval’s identity is

\[ \sum_{n=0}^{N-1}|x_n|^2 =\frac{1}{N}\sum_{k=0}^{N-1}|\widehat{x}_k|^2. \]

For images,

\[ \sum_{m,n}|I_{m,n}|^2 =\frac{1}{HW}\sum_{u,v}|\widehat{I}_{u,v}|^2. \]

With unitary normalization, the factor $1/(HW)$ disappears.

Parseval’s identity says that total image energy can be measured either in the spatial domain or in the frequency domain. This is useful for:

measuring how much energy is contained in low frequencies;
designing compression rules;
comparing denoising methods;
detecting high-frequency artifacts;
understanding why many natural images have spectra dominated by low frequencies.

A frequency mask $M_{u,v}\in\{0,1\}$ selects a subset of frequencies. The fraction of retained spectral energy is approximately

\[ \frac{\sum_{u,v}M_{u,v}|\widehat{I}_{u,v}|^2} {\sum_{u,v}|\widehat{I}_{u,v}|^2}. \]

For natural images, a small central low-frequency region often retains a large amount of energy, but not necessarily the sharp details needed for recognition.

6.8 5.7 Convolution Theorem

Let $x,h\in\mathbb{C}^N$. Their circular convolution is

\[ (x*h)_n = \sum_{r=0}^{N-1} x_r h_{n-r \pmod N}. \]

The convolution theorem states

\[ \widehat{x*h}_k = \widehat{x}_k\widehat{h}_k. \]

For images, if $K$ is a convolution kernel and $Y=K*I$, then

\[ \widehat{Y}_{u,v} = \widehat{K}_{u,v}\widehat{I}_{u,v}. \]

Thus convolution in the spatial domain becomes multiplication in the frequency domain.

This theorem explains the behavior of common filters:

a smoothing filter suppresses high frequencies;
a derivative filter amplifies high frequencies in a direction;
a sharpening filter boosts high frequencies;
a band-pass filter keeps a ring or band of frequencies;
a notch filter removes a small frequency region, often useful for periodic noise.

6.8.1 Proof Sketch

Using the DFT definition,

\[ \widehat{x*h}_k =\sum_{n=0}^{N-1}\left(\sum_{r=0}^{N-1}x_rh_{n-r}\right)e^{-2\pi i kn/N}. \]

Let $s=n-r$. Then $n=s+r$, and because the convolution is circular,

\[ \widehat{x*h}_k =\sum_{r=0}^{N-1}\sum_{s=0}^{N-1}x_rh_s e^{-2\pi i k(s+r)/N} =\left(\sum_{r=0}^{N-1}x_re^{-2\pi i kr/N}\right) \left(\sum_{s=0}^{N-1}h_se^{-2\pi i ks/N}\right). \]

Therefore

\[ \widehat{x*h}_k=\widehat{x}_k\widehat{h}_k. \]

The same argument extends to two-dimensional images.

6.9 5.8 Frequency-Domain Filters

A frequency-domain filter multiplies Fourier coefficients by a transfer function $H_{u,v}$:

\[ \widehat{Y}_{u,v} = H_{u,v}\widehat{I}_{u,v}. \]

Then the filtered image is obtained by inverse DFT:

\[ Y = \operatorname{IDFT}(H\odot \widehat{I}). \]

6.9.1 Ideal Low-Pass Filter

An ideal circular low-pass filter is

\[ H_{u,v}=\mathbf{1}\{D(u,v)\le R\}, \]

where $D(u,v)$ is distance from the zero frequency. This removes all frequencies outside radius $R$.

Ideal low-pass filtering is conceptually simple but can introduce ringing artifacts because a sharp cutoff in frequency corresponds to a long oscillatory kernel in space.

6.9.2 Gaussian Low-Pass Filter

A smoother alternative is

\[ H_{u,v}=\exp\left(-\frac{D(u,v)^2}{2\sigma_f^2}\right). \]

The Gaussian is special: the Fourier transform of a Gaussian is another Gaussian. Gaussian smoothing has no sharp frequency cutoff and usually avoids severe ringing.

6.9.3 High-Pass Filter

A high-pass filter can be formed as

\[ H_{high}(u,v)=1-H_{low}(u,v). \]

This keeps edges, texture, and noise while removing smooth background structure.

6.9.4 Interactive: low-pass and high-pass filtering

This demo applies simple radial frequency masks to a synthetic image. Low-pass filtering keeps smooth structure; high-pass filtering keeps edges and texture.

6.10 5.9 The Fourier View of Common Spatial Kernels

Consider a one-dimensional moving average kernel

\[ h = \frac{1}{3}[1,1,1]. \]

Its frequency response is

\[ \widehat{h}(\omega)=\frac{1}{3}(1+e^{-i\omega}+e^{-2i\omega}). \]

The magnitude $|\widehat{h}(\omega)|$ is large at low frequencies and smaller at high frequencies. Therefore a moving average is a low-pass filter.

A finite-difference kernel

\[ d=[-1,1] \]

has frequency response

\[ \widehat{d}(\omega)=1-e^{-i\omega}. \]

Its magnitude is

\[ |\widehat{d}(\omega)|=2|\sin(\omega/2)|. \]

This is small near $\omega=0$ and large near high frequencies. Therefore finite differences behave like high-pass filters.

This is the frequency-domain explanation for why gradients detect edges and amplify noise.

6.11 5.10 Sampling and Aliasing

Suppose a continuous signal contains a sinusoid

\[ f(t)=\cos(2\pi \omega t). \]

If we sample at locations $t_n=n\Delta$, then

\[ f[n]=\cos(2\pi \omega n\Delta). \]

Frequencies that differ by integer multiples of the sampling frequency produce the same sampled values. In normalized discrete time, frequencies $\omega$ and $\omega+k$ are indistinguishable.

The Nyquist principle says that to reconstruct a band-limited signal, the sampling rate must be more than twice the highest frequency present. If high-frequency content is sampled too coarsely, it aliases into lower frequencies.

For images, aliasing appears as:

jagged edges;
moire patterns;
false texture;
unstable resizing behavior;
misleading high-frequency artifacts in training data.

This is why antialiasing is important when downsampling images.

6.11.1 Interactive: aliasing from under-sampling

The same discrete samples can be consistent with different continuous frequencies. This is the core ambiguity behind aliasing.

6.12 5.11 Boundary Conditions and Padding

The DFT assumes periodic boundary conditions. A finite image is treated as if it repeats forever in both directions. This matters because a sudden jump between the right edge and left edge introduces artificial high-frequency content.

Common ways to handle boundaries include:

zero padding;
periodic padding;
reflection padding;
replication padding;
valid convolution, which avoids uncertain boundaries.

In mathematical notation, boundary handling changes the linear operator. For example, a convolution matrix may be circulant under periodic boundary conditions, Toeplitz-like under zero padding, or modified near the boundary under reflection padding.

This detail matters in both classical algorithms and neural networks. CNNs with zero padding can learn boundary artifacts. Reflection padding may be better for image restoration tasks.

6.13 5.12 DCT and Image Compression

The discrete cosine transform, or DCT, uses cosine basis functions instead of complex exponentials. A common one-dimensional DCT basis has the form

\[ \psi_k[n] = \alpha_k \cos\left(\frac{\pi(2n+1)k}{2N}\right), \qquad k=0,1,\ldots,N-1. \]

The DCT is widely used in image compression because natural image blocks often have most of their energy in low-frequency DCT coefficients. JPEG applies the DCT to small image blocks, quantizes coefficients, and stores the result efficiently.

From a linear algebra viewpoint, compression is projection and coefficient thresholding:

\[ x \approx \sum_{k\in S} c_k \psi_k, \]

where $S$ contains the selected basis functions. The approximation is good when the coefficient vector is compressible, meaning many coefficients are small.

6.14 5.13 Statistical Viewpoint: Spectra as Features

For MS Statistics students, the Fourier transform is also a feature map. For an image $I$, define features such as:

\[ z_1(I)=\sum_{D(u,v)\le R}|\widehat{I}_{u,v}|^2, \]

\[ z_2(I)=\sum_{R_1 < D(u,v)\le R_2}|\widehat{I}_{u,v}|^2, \]

and

\[ z_3(I)=\frac{z_2(I)}{z_1(I)+\epsilon}. \]

These features measure low-frequency energy, mid-frequency energy, and texture-to-smoothness ratios. They can be useful for quality control, blur detection, texture classification, medical imaging preprocessing, and synthetic-image detection.

A simple statistical model might be

\[ P(Y=1\mid I)=\sigma(\beta_0+\beta^Tz(I)), \]

where $z(I)$ contains spectral features. This model is interpretable but limited: it discards spatial phase information and may fail when object geometry is essential.

6.15 5.14 AI Component: Frequency in Modern Vision Models

Frequency analysis remains relevant in modern AI vision.

6.15.1 CNN Filters

A learned convolution kernel has a frequency response. Early CNN layers often learn edge-like and texture-like filters, which are localized in space and selective in frequency/orientation.

For a learned kernel $K$, its transfer function is

\[ \widehat{K}_{u,v}. \]

By plotting $|\widehat{K}_{u,v}|$, one can inspect whether the filter behaves like a smoother, edge detector, orientation detector, or band-pass filter.

6.15.2 Spectral Bias

Many neural networks tend to learn smooth, low-frequency structure before high-frequency details. This phenomenon is often called spectral bias or frequency bias. For computer vision, it means that coarse structure may be learned earlier than fine texture.

6.15.3 Fourier Features

Some models improve high-frequency representation by mapping coordinates into sinusoidal features:

\[ \gamma(x)= \left(\sin(2\pi b_1^Tx),\cos(2\pi b_1^Tx),\ldots, \sin(2\pi b_m^Tx),\cos(2\pi b_m^Tx)\right). \]

Such features are important in implicit neural representations and neural fields, where a network represents an image, scene, or 3D shape as a continuous function.

6.15.4 Positional Encoding

Vision transformers split images into patches and then add position information. Sinusoidal positional encodings are Fourier-like coordinate features. They help the model know where each patch is located.

6.15.5 Frequency Artifacts

Generated images, upsampled images, or compressed images may contain unusual spectral signatures. Frequency plots can reveal periodic artifacts not obvious in the spatial domain.

6.15.6 AI-assisted investigation

Ask an AI assistant to compare two explanations:

“Convolution in the image domain becomes multiplication in the frequency domain.”
“Multiplication in the image domain becomes convolution in the frequency domain.”

Then verify the explanation by writing a small numerical example using numpy.fft. The goal is not to accept the AI answer but to test it mathematically.

6.16 5.15 Python Example: DFT and Spectrum Visualization

import numpy as np
import matplotlib.pyplot as plt

H, W = 128, 128
y, x = np.mgrid[0:H, 0:W]

# Smooth blob plus oriented sinusoidal texture
blob = np.exp(-((x - 64)**2 + (y - 64)**2) / (2 * 18**2))
texture = 0.25 * np.cos(2 * np.pi * (8 * x / W + 14 * y / H))
image = blob + texture

F = np.fft.fft2(image)
F_shift = np.fft.fftshift(F)
log_magnitude = np.log1p(np.abs(F_shift))

fig, axes = plt.subplots(1, 2, figsize=(10, 4))
axes[0].imshow(image, cmap="gray")
axes[0].set_title("synthetic image")
axes[0].axis("off")

axes[1].imshow(log_magnitude, cmap="magma")
axes[1].set_title("log Fourier magnitude")
axes[1].axis("off")

plt.show()

6.17 5.16 Python Example: Low-Pass and High-Pass Filtering

import numpy as np
import matplotlib.pyplot as plt

H, W = image.shape
cy, cx = H // 2, W // 2
Y, X = np.ogrid[:H, :W]
D = np.sqrt((Y - cy)**2 + (X - cx)**2)

radius = 16
low_mask = (D <= radius).astype(float)
high_mask = 1.0 - low_mask

F_shift = np.fft.fftshift(np.fft.fft2(image))

low_image = np.real(np.fft.ifft2(np.fft.ifftshift(F_shift * low_mask)))
high_image = np.real(np.fft.ifft2(np.fft.ifftshift(F_shift * high_mask)))

fig, axes = plt.subplots(1, 3, figsize=(12, 4))
for ax, img, title in zip(
    axes,
    [image, low_image, high_image],
    ["original", "low-pass", "high-pass"]
):
    ax.imshow(img, cmap="gray")
    ax.set_title(title)
    ax.axis("off")

plt.show()

6.18 5.17 Python Example: Blur Detection by High-Frequency Energy

import numpy as np
from scipy.ndimage import gaussian_filter

rng = np.random.default_rng(7243)

sharp = image
blurred = gaussian_filter(image, sigma=3.0)

def high_frequency_ratio(img, radius=20):
    H, W = img.shape
    F = np.fft.fftshift(np.fft.fft2(img))
    power = np.abs(F)**2
    cy, cx = H // 2, W // 2
    Y, X = np.ogrid[:H, :W]
    D = np.sqrt((Y - cy)**2 + (X - cx)**2)
    high = power[D > radius].sum()
    total = power.sum()
    return high / total

print("sharp high-frequency ratio:", high_frequency_ratio(sharp))
print("blurred high-frequency ratio:", high_frequency_ratio(blurred))

6.19 5.18 Python Example: A Tiny Spectral Feature Classifier

import numpy as np
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report

rng = np.random.default_rng(5110)

H, W = 64, 64
y, x = np.mgrid[0:H, 0:W]

def make_image(label):
    base = np.exp(-((x - 32)**2 + (y - 32)**2) / (2 * 12**2))
    noise = 0.10 * rng.normal(size=(H, W))
    if label == 0:
        texture = 0.18 * np.cos(2 * np.pi * (4 * x / W + 3 * y / H))
    else:
        texture = 0.18 * np.cos(2 * np.pi * (14 * x / W + 10 * y / H))
    return base + texture + noise

def spectral_features(img):
    F = np.fft.fftshift(np.fft.fft2(img))
    power = np.abs(F)**2
    cy, cx = img.shape[0] // 2, img.shape[1] // 2
    Y, X = np.ogrid[:img.shape[0], :img.shape[1]]
    D = np.sqrt((Y - cy)**2 + (X - cx)**2)
    low = power[D <= 8].sum()
    mid = power[(D > 8) & (D <= 18)].sum()
    high = power[D > 18].sum()
    total = power.sum()
    return np.array([low / total, mid / total, high / total])

images = []
labels = []
for label in [0, 1]:
    for _ in range(150):
        images.append(make_image(label))
        labels.append(label)

X_features = np.vstack([spectral_features(img) for img in images])
y_labels = np.array(labels)

X_train, X_test, y_train, y_test = train_test_split(
    X_features, y_labels, test_size=0.3, random_state=0, stratify=y_labels
)

clf = LogisticRegression()
clf.fit(X_train, y_train)
print(classification_report(y_test, clf.predict(X_test)))
print("coefficients:", clf.coef_)

6.20 5.19 TensorFlow Example: Frequency Loss for Image Reconstruction

A reconstruction model is often trained using pixel MSE:

\[ L_{pixel}(x,\widehat{x})=\|x-\widehat{x}\|_2^2. \]

One may also add a frequency-domain loss:

\[ L_{freq}(x,\widehat{x}) =\|\log(1+|F(x)|)-\log(1+|F(\widehat{x})|)\|_2^2. \]

import tensorflow as tf

@tf.function
def frequency_loss(y_true, y_pred):
    # y_true and y_pred are assumed to have shape (batch, height, width, channels)
    y_true_c = tf.cast(y_true, tf.complex64)
    y_pred_c = tf.cast(y_pred, tf.complex64)

    true_fft = tf.signal.fft2d(tf.transpose(y_true_c, [0, 3, 1, 2]))
    pred_fft = tf.signal.fft2d(tf.transpose(y_pred_c, [0, 3, 1, 2]))

    true_mag = tf.math.log1p(tf.abs(true_fft))
    pred_mag = tf.math.log1p(tf.abs(pred_fft))

    return tf.reduce_mean(tf.square(true_mag - pred_mag))

def combined_loss(y_true, y_pred, alpha=0.05):
    pixel = tf.reduce_mean(tf.square(y_true - y_pred))
    freq = frequency_loss(y_true, y_pred)
    return pixel + alpha * freq

This loss is not automatically better than pixel loss. It changes the model’s priorities. It may help preserve texture or reduce spectral artifacts, but it can also overemphasize frequencies that are not semantically important.

6.21 5.20 Common Mistakes

Mistake 1: Confusing frequency index with physical frequency

In an array, the index $k$ is not automatically measured in cycles per meter or cycles per degree. Physical frequency depends on pixel spacing.

Mistake 2: Ignoring phase

Magnitude spectra are useful, but phase carries much of the spatial arrangement. Reconstructing an image from the wrong phase usually destroys recognizable structure.

Mistake 3: Forgetting boundary assumptions

The DFT assumes periodicity. Edges of a finite image can create artificial high-frequency components.

Mistake 4: Thinking high frequency means noise

Edges, fine anatomical structures, text, and texture are also high-frequency. Removing all high frequencies may destroy important information.

Mistake 5: Applying frequency tricks without validating task performance

Frequency filtering can improve visual quality while hurting downstream classification, detection, or segmentation. Always evaluate on the actual task.

6.22 5.21 Summary

Fourier analysis provides a second coordinate system for images. Instead of describing an image by pixel values, we describe it by frequencies, amplitudes, and phases. This viewpoint explains smoothing, sharpening, convolution, compression, aliasing, and many artifacts in modern AI vision systems.

The main mathematical takeaways are:

the DFT is a change of basis into orthogonal complex exponential modes;
the 2D DFT decomposes images by horizontal and vertical oscillations;
Fourier magnitude describes energy by frequency, while phase describes spatial alignment;
convolution in space becomes multiplication in frequency;
low-pass filters smooth, high-pass filters emphasize edges and noise, and band-pass filters capture texture;
sampling without sufficient resolution causes aliasing;
spectral features can be useful statistically but must be interpreted carefully;
modern CNNs, transformers, neural fields, and generative models all have meaningful frequency-domain behavior.

6.23 Exercises

6.23.1 Conceptual Exercises

Explain why a smooth image has most of its Fourier energy near zero frequency.
Why does an edge require high-frequency components?
What information is lost if we keep Fourier magnitude but discard Fourier phase?
Explain why downsampling without low-pass filtering can create aliasing.
Why might a high-pass filter amplify both edges and noise?

6.23.2 Mathematical Exercises

Prove the orthogonality identity \[ \sum_{n=0}^{N-1} e^{2\pi i(k-\ell)n/N}=0 \] when $k\ne \ell \pmod N$.
Derive the inverse DFT formula from the orthogonality of Fourier modes.
Prove Parseval’s identity for the unitary DFT matrix.
Let $h=[1/2,1/2]$. Compute its frequency response and show that it suppresses high frequencies.
Let $d=[-1,1]$. Compute $|\widehat{d}(\omega)|$ and interpret it as an edge detector.
Show that the two-dimensional DFT can be written as \[ \widehat{I}=F_HIF_W^T. \]
For a sinusoidal image \[ I(x,y)=\cos(2\pi(\xi x+\eta y)), \] describe the orientation of its visible stripes.

6.23.3 Python Exercises

Generate a $128\times128$ image containing two sinusoids with different orientations. Plot its log Fourier magnitude.
Implement ideal low-pass, high-pass, and band-pass filters using numpy.fft.
Compare Gaussian blur in the spatial domain with Gaussian-like attenuation in the frequency domain.
Write a function that computes the fraction of spectral energy above a radius $R$.
Use spectral energy features to classify synthetic smooth images versus textured images.
Downsample an image with and without antialiasing. Compare their spectra.
Use Fourier magnitude to detect periodic noise and design a simple notch filter.

6.23.4 AI and Modeling Exercises

Ask an AI assistant to explain the convolution theorem. Then write your own proof and identify any missing assumptions.
Ask an AI assistant for code that performs low-pass filtering with numpy.fft. Check whether it uses fftshift and ifftshift correctly.
Compare the Fourier spectra of natural images, blurred images, and noisy images.
Train a small CNN on synthetic stripe images. Visualize the spectra of the first-layer filters.
Investigate whether a classifier trained on synthetic images relies more on low-frequency shape or high-frequency texture.
Design a prompt for an AI assistant that asks it to distinguish between Fourier magnitude, phase, power spectrum, and energy.

6.24 Further Reading

Fourier methods and classical image filtering are discussed in Gonzalez and Woods (2018) and Szeliski (2022). For broader connections between signal representations, learning, and modern deep models, see Goodfellow et al. (2016) and LeCun et al. (1998). Frequency ideas also appear in modern representation learning, implicit neural representations, and transformer positional encodings, which will be revisited in later chapters.

Gonzalez, Rafael C., and Richard E. Woods. 2018. Digital Image Processing. 4th ed. Pearson.

Goodfellow, Ian, Yoshua Bengio, and Aaron Courville. 2016. Deep Learning. MIT Press. https://www.deeplearningbook.org/.

LeCun, Yann, Léon Bottou, Yoshua Bengio, and Patrick Haffner. 1998. “Gradient-Based Learning Applied to Document Recognition.” Proceedings of the IEEE 86: 2278–324.

Szeliski, Richard. 2022. Computer Vision: Algorithms and Applications. 2nd ed. Springer. https://szeliski.org/Book/.

# Fourier Analysis and Frequency ::: {.hero-box} Fourier analysis explains an image by decomposing it into oscillatory patterns. In the spatial domain, we see pixels, edges, textures, and objects. In the frequency domain, we see smooth components, sharp transitions, repeated texture, noise, aliasing, and the effect of filters. This chapter develops the mathematical theory of the discrete Fourier transform, convolution theorem, Parseval identity, frequency-domain filtering, sampling, aliasing, and AI connections such as spectral bias, frequency artifacts, and Fourier features. ::: ## Learning Goals After reading this chapter, students should be able to: 1. represent one-dimensional and two-dimensional signals using complex exponential bases; 2. define the discrete Fourier transform and inverse discrete Fourier transform; 3. explain orthogonality of Fourier modes and the meaning of frequency indices; 4. interpret Fourier magnitude and phase for images; 5. prove and use the convolution theorem; 6. design ideal, Gaussian, high-pass, low-pass, and band-pass filters in the frequency domain; 7. explain the connection between sampling, aliasing, and the Nyquist frequency; 8. state Parseval's identity and interpret frequency energy; 9. connect Fourier analysis with image denoising, compression, texture, CNN filters, positional encodings, and spectral bias in modern AI. ## 5.1 Why Frequency Matters in Computer Vision Chapters 1--4 treated images as measurements, arrays, sampled functions, and vectors. Fourier analysis gives a complementary viewpoint: $$ \text{image} = \text{sum of oscillatory patterns at different frequencies}. $$ Low frequencies describe broad smooth structure. High frequencies describe sharp edges, fine texture, noise, and abrupt transitions. This distinction appears throughout computer vision: - smoothing removes high-frequency variation; - sharpening amplifies high-frequency variation; - edge detectors respond to rapid intensity changes; - aliasing appears when high-frequency content is sampled too coarsely; - JPEG-style compression keeps important low- and mid-frequency coefficients; - CNN filters often learn oriented frequency-selective patterns; - transformers use positional encodings that can be understood through sinusoidal bases; - generative models may produce characteristic spectral artifacts; - neural networks often fit low-frequency structure before high-frequency detail. ::: {.math-spine} The central idea of this chapter is: $$ \text{spatial locality} \quad \longleftrightarrow \quad \text{frequency mixture}. $$ A localized edge is not a single frequency. It requires many frequencies. A smooth region is well described by a small number of low-frequency modes. ::: For computer vision, frequency analysis is not only a signal-processing tool. It provides a diagnostic language for data quality, augmentation, model behavior, and failure modes. ## 5.2 Complex Exponentials as Basis Functions A real sinusoid has the form $$ f(t) = A \cos(2\pi \omega t + \phi), $$ where $A$ is amplitude, $\omega$ is frequency, and $\phi$ is phase. Fourier analysis uses complex exponentials $$ e^{2\pi i \omega t} = \cos(2\pi \omega t) + i\sin(2\pi \omega t) $$ because they make algebra simple. A signal is represented as a weighted sum of such oscillatory functions. For a discrete signal $x = (x_0,\ldots,x_{N-1})$, the basic Fourier modes are $$ \varphi_k[n] = e^{2\pi i kn/N}, \qquad k,n=0,1,\ldots,N-1. $$ The index $k$ counts how many cycles the mode completes over $N$ samples. ### Orthogonality The Fourier modes satisfy $$ \sum_{n=0}^{N-1} e^{2\pi i (k-\ell)n/N} = \begin{cases} N, & k=\ell \pmod N,\\ 0, & k\ne \ell \pmod N. \end{cases} $$ This is the key algebraic fact. It says that different discrete frequencies are orthogonal with respect to the inner product $$ \langle x,y\rangle = \sum_{n=0}^{N-1} x_n \overline{y_n}. $$ For real image data, the Fourier coefficients are complex. Their magnitudes encode amount of oscillation at a frequency; their phases encode spatial alignment. ::: {.interactive-card} ### Interactive: Fourier basis functions The plot below compares several sinusoidal basis functions. Low frequency modes vary slowly. High frequency modes alternate rapidly. <div id="cv-ch05-basis-demo" class="plotly-demo"></div> ::: ## 5.3 The Discrete Fourier Transform For $x\in \mathbb{C}^N$, the discrete Fourier transform, or DFT, is the vector $\widehat{x}\in \mathbb{C}^N$ defined by $$ \widehat{x}_k = \sum_{n=0}^{N-1} x_n e^{-2\pi i kn/N}, \qquad k=0,1,\ldots,N-1. $$ The inverse transform is $$ x_n = \frac{1}{N}\sum_{k=0}^{N-1} \widehat{x}_k e^{2\pi i kn/N}. $$ In matrix form, $$ \widehat{x} = F_N x, \qquad x = F_N^{-1}\widehat{x}, $$ where $$ (F_N)_{kn}=e^{-2\pi i kn/N}. $$ If we normalize by $1/\sqrt{N}$, the Fourier matrix becomes unitary: $$ U_N = \frac{1}{\sqrt{N}}F_N, \qquad U_N^*U_N = I. $$ This matters statistically because a unitary transformation preserves energy and Euclidean norm. ### Amplitude and Phase Each Fourier coefficient can be written in polar form: $$ \widehat{x}_k = r_k e^{i\theta_k}, $$ where $$ r_k = |\widehat{x}_k|, \qquad \theta_k = \arg(\widehat{x}_k). $$ The magnitude $r_k$ measures how strongly frequency $k$ appears. The phase $\theta_k$ determines how the corresponding oscillation is shifted in space. A common beginner mistake is to think that magnitude alone determines the image. It does not. Phase is essential for spatial structure. Magnitude describes how much of each frequency appears; phase determines where structures appear. ## 5.4 The Two-Dimensional DFT A grayscale image $I\in\mathbb{R}^{H\times W}$ has two spatial indices. The two-dimensional DFT is $$ \widehat{I}_{u,v} = \sum_{m=0}^{H-1}\sum_{n=0}^{W-1} I_{m,n} \exp\left(-2\pi i\left(\frac{um}{H}+\frac{vn}{W}\right)\right), $$ where $$ u=0,1,\ldots,H-1, \qquad v=0,1,\ldots,W-1. $$ The inverse transform is $$ I_{m,n} = \frac{1}{HW} \sum_{u=0}^{H-1}\sum_{v=0}^{W-1} \widehat{I}_{u,v} \exp\left(2\pi i\left(\frac{um}{H}+\frac{vn}{W}\right)\right). $$ The pair $(u,v)$ is a two-dimensional frequency. Large $u$ corresponds to vertical variation because it changes with row index $m$. Large $v$ corresponds to horizontal variation because it changes with column index $n$. ### Separable Matrix Form Let $F_H$ and $F_W$ be Fourier matrices of sizes $H$ and $W$. Then the 2D DFT can be written as $$ \widehat{I} = F_H I F_W^T. $$ With unitary normalization, this is a change of orthonormal basis on the row and column spaces. This separable structure is why the 2D FFT is fast: first transform rows, then transform columns. ::: {.callout-note} ### Index convention Most numerical libraries store frequency zero at the upper-left corner of the Fourier array. For visualization, one often applies `fftshift`, which moves the zero frequency to the center. After shifting, low frequencies are near the center and high frequencies are farther away. ::: ::: {.interactive-card} ### Interactive: 2D Fourier magnitude of synthetic images This demo shows a synthetic image and its log Fourier magnitude. Notice that smooth blobs concentrate energy near the center, while stripes create peaks at oriented frequencies. <div id="cv-ch05-spectrum-demo" class="plotly-demo"></div> ::: ## 5.5 Frequency, Orientation, and Texture A two-dimensional sinusoidal pattern can be written as $$ I(x,y)=A\cos(2\pi(\xi x+\eta y)+\phi). $$ The frequency vector is $$ \omega = (\xi,\eta). $$ Its magnitude $$ \|\omega\|_2 = \sqrt{\xi^2+\eta^2} $$ controls the rate of oscillation. Its direction controls orientation. Lines of constant phase satisfy $$ \xi x+\eta y = c, $$ so the visible stripe direction is perpendicular to $\omega$. This explains why oriented textures create localized peaks in the Fourier domain. A vertical stripe pattern varies horizontally, so its frequency vector points in the horizontal frequency direction. A horizontal stripe pattern varies vertically. ## 5.6 Parseval's Identity and Spectral Energy For the unnormalized DFT convention above, Parseval's identity is $$ \sum_{n=0}^{N-1}|x_n|^2 =\frac{1}{N}\sum_{k=0}^{N-1}|\widehat{x}_k|^2. $$ For images, $$ \sum_{m,n}|I_{m,n}|^2 =\frac{1}{HW}\sum_{u,v}|\widehat{I}_{u,v}|^2. $$ With unitary normalization, the factor $1/(HW)$ disappears. Parseval's identity says that total image energy can be measured either in the spatial domain or in the frequency domain. This is useful for: - measuring how much energy is contained in low frequencies; - designing compression rules; - comparing denoising methods; - detecting high-frequency artifacts; - understanding why many natural images have spectra dominated by low frequencies. A frequency mask $M_{u,v}\in\{0,1\}$ selects a subset of frequencies. The fraction of retained spectral energy is approximately $$ \frac{\sum_{u,v}M_{u,v}|\widehat{I}_{u,v}|^2} {\sum_{u,v}|\widehat{I}_{u,v}|^2}. $$ For natural images, a small central low-frequency region often retains a large amount of energy, but not necessarily the sharp details needed for recognition. ## 5.7 Convolution Theorem Let $x,h\in\mathbb{C}^N$. Their circular convolution is $$ (x*h)_n = \sum_{r=0}^{N-1} x_r h_{n-r \pmod N}. $$ The convolution theorem states $$ \widehat{x*h}_k = \widehat{x}_k\widehat{h}_k. $$ For images, if $K$ is a convolution kernel and $Y=K*I$, then $$ \widehat{Y}_{u,v} = \widehat{K}_{u,v}\widehat{I}_{u,v}. $$ Thus convolution in the spatial domain becomes multiplication in the frequency domain. This theorem explains the behavior of common filters: - a smoothing filter suppresses high frequencies; - a derivative filter amplifies high frequencies in a direction; - a sharpening filter boosts high frequencies; - a band-pass filter keeps a ring or band of frequencies; - a notch filter removes a small frequency region, often useful for periodic noise. ### Proof Sketch Using the DFT definition, $$ \widehat{x*h}_k =\sum_{n=0}^{N-1}\left(\sum_{r=0}^{N-1}x_rh_{n-r}\right)e^{-2\pi i kn/N}. $$ Let $s=n-r$. Then $n=s+r$, and because the convolution is circular, $$ \widehat{x*h}_k =\sum_{r=0}^{N-1}\sum_{s=0}^{N-1}x_rh_s e^{-2\pi i k(s+r)/N} =\left(\sum_{r=0}^{N-1}x_re^{-2\pi i kr/N}\right) \left(\sum_{s=0}^{N-1}h_se^{-2\pi i ks/N}\right). $$ Therefore $$ \widehat{x*h}_k=\widehat{x}_k\widehat{h}_k. $$ The same argument extends to two-dimensional images. ## 5.8 Frequency-Domain Filters A frequency-domain filter multiplies Fourier coefficients by a transfer function $H_{u,v}$: $$ \widehat{Y}_{u,v} = H_{u,v}\widehat{I}_{u,v}. $$ Then the filtered image is obtained by inverse DFT: $$ Y = \operatorname{IDFT}(H\odot \widehat{I}). $$ ### Ideal Low-Pass Filter An ideal circular low-pass filter is $$ H_{u,v}=\mathbf{1}\{D(u,v)\le R\}, $$ where $D(u,v)$ is distance from the zero frequency. This removes all frequencies outside radius $R$. Ideal low-pass filtering is conceptually simple but can introduce ringing artifacts because a sharp cutoff in frequency corresponds to a long oscillatory kernel in space. ### Gaussian Low-Pass Filter A smoother alternative is $$ H_{u,v}=\exp\left(-\frac{D(u,v)^2}{2\sigma_f^2}\right). $$ The Gaussian is special: the Fourier transform of a Gaussian is another Gaussian. Gaussian smoothing has no sharp frequency cutoff and usually avoids severe ringing. ### High-Pass Filter A high-pass filter can be formed as $$ H_{high}(u,v)=1-H_{low}(u,v). $$ This keeps edges, texture, and noise while removing smooth background structure. ::: {.interactive-card} ### Interactive: low-pass and high-pass filtering This demo applies simple radial frequency masks to a synthetic image. Low-pass filtering keeps smooth structure; high-pass filtering keeps edges and texture. <div id="cv-ch05-filter-demo" class="plotly-demo"></div> ::: ## 5.9 The Fourier View of Common Spatial Kernels Consider a one-dimensional moving average kernel $$ h = \frac{1}{3}[1,1,1]. $$ Its frequency response is $$ \widehat{h}(\omega)=\frac{1}{3}(1+e^{-i\omega}+e^{-2i\omega}). $$ The magnitude $|\widehat{h}(\omega)|$ is large at low frequencies and smaller at high frequencies. Therefore a moving average is a low-pass filter. A finite-difference kernel $$ d=[-1,1] $$ has frequency response $$ \widehat{d}(\omega)=1-e^{-i\omega}. $$ Its magnitude is $$ |\widehat{d}(\omega)|=2|\sin(\omega/2)|. $$ This is small near $\omega=0$ and large near high frequencies. Therefore finite differences behave like high-pass filters. This is the frequency-domain explanation for why gradients detect edges and amplify noise. ## 5.10 Sampling and Aliasing Suppose a continuous signal contains a sinusoid $$ f(t)=\cos(2\pi \omega t). $$ If we sample at locations $t_n=n\Delta$, then $$ f[n]=\cos(2\pi \omega n\Delta). $$ Frequencies that differ by integer multiples of the sampling frequency produce the same sampled values. In normalized discrete time, frequencies $\omega$ and $\omega+k$ are indistinguishable. The Nyquist principle says that to reconstruct a band-limited signal, the sampling rate must be more than twice the highest frequency present. If high-frequency content is sampled too coarsely, it aliases into lower frequencies. For images, aliasing appears as: - jagged edges; - moire patterns; - false texture; - unstable resizing behavior; - misleading high-frequency artifacts in training data. This is why antialiasing is important when downsampling images. ::: {.interactive-card} ### Interactive: aliasing from under-sampling The same discrete samples can be consistent with different continuous frequencies. This is the core ambiguity behind aliasing. <div id="cv-ch05-aliasing-demo" class="plotly-demo"></div> ::: ## 5.11 Boundary Conditions and Padding The DFT assumes periodic boundary conditions. A finite image is treated as if it repeats forever in both directions. This matters because a sudden jump between the right edge and left edge introduces artificial high-frequency content. Common ways to handle boundaries include: - zero padding; - periodic padding; - reflection padding; - replication padding; - valid convolution, which avoids uncertain boundaries. In mathematical notation, boundary handling changes the linear operator. For example, a convolution matrix may be circulant under periodic boundary conditions, Toeplitz-like under zero padding, or modified near the boundary under reflection padding. This detail matters in both classical algorithms and neural networks. CNNs with zero padding can learn boundary artifacts. Reflection padding may be better for image restoration tasks. ## 5.12 DCT and Image Compression The discrete cosine transform, or DCT, uses cosine basis functions instead of complex exponentials. A common one-dimensional DCT basis has the form $$ \psi_k[n] = \alpha_k \cos\left(\frac{\pi(2n+1)k}{2N}\right), \qquad k=0,1,\ldots,N-1. $$ The DCT is widely used in image compression because natural image blocks often have most of their energy in low-frequency DCT coefficients. JPEG applies the DCT to small image blocks, quantizes coefficients, and stores the result efficiently. From a linear algebra viewpoint, compression is projection and coefficient thresholding: $$ x \approx \sum_{k\in S} c_k \psi_k, $$ where $S$ contains the selected basis functions. The approximation is good when the coefficient vector is compressible, meaning many coefficients are small. ## 5.13 Statistical Viewpoint: Spectra as Features For MS Statistics students, the Fourier transform is also a feature map. For an image $I$, define features such as: $$ z_1(I)=\sum_{D(u,v)\le R}|\widehat{I}_{u,v}|^2, $$ $$ z_2(I)=\sum_{R_1 < D(u,v)\le R_2}|\widehat{I}_{u,v}|^2, $$ and $$ z_3(I)=\frac{z_2(I)}{z_1(I)+\epsilon}. $$ These features measure low-frequency energy, mid-frequency energy, and texture-to-smoothness ratios. They can be useful for quality control, blur detection, texture classification, medical imaging preprocessing, and synthetic-image detection. A simple statistical model might be $$ P(Y=1\mid I)=\sigma(\beta_0+\beta^Tz(I)), $$ where $z(I)$ contains spectral features. This model is interpretable but limited: it discards spatial phase information and may fail when object geometry is essential. ## 5.14 AI Component: Frequency in Modern Vision Models Frequency analysis remains relevant in modern AI vision. ### CNN Filters A learned convolution kernel has a frequency response. Early CNN layers often learn edge-like and texture-like filters, which are localized in space and selective in frequency/orientation. For a learned kernel $K$, its transfer function is $$ \widehat{K}_{u,v}. $$ By plotting $|\widehat{K}_{u,v}|$, one can inspect whether the filter behaves like a smoother, edge detector, orientation detector, or band-pass filter. ### Spectral Bias Many neural networks tend to learn smooth, low-frequency structure before high-frequency details. This phenomenon is often called spectral bias or frequency bias. For computer vision, it means that coarse structure may be learned earlier than fine texture. ### Fourier Features Some models improve high-frequency representation by mapping coordinates into sinusoidal features: $$ \gamma(x)= \left(\sin(2\pi b_1^Tx),\cos(2\pi b_1^Tx),\ldots, \sin(2\pi b_m^Tx),\cos(2\pi b_m^Tx)\right). $$ Such features are important in implicit neural representations and neural fields, where a network represents an image, scene, or 3D shape as a continuous function. ### Positional Encoding Vision transformers split images into patches and then add position information. Sinusoidal positional encodings are Fourier-like coordinate features. They help the model know where each patch is located. ### Frequency Artifacts Generated images, upsampled images, or compressed images may contain unusual spectral signatures. Frequency plots can reveal periodic artifacts not obvious in the spatial domain. ::: {.ai-component} ### AI-assisted investigation Ask an AI assistant to compare two explanations: 1. "Convolution in the image domain becomes multiplication in the frequency domain." 2. "Multiplication in the image domain becomes convolution in the frequency domain." Then verify the explanation by writing a small numerical example using `numpy.fft`. The goal is not to accept the AI answer but to test it mathematically. ::: ## 5.15 Python Example: DFT and Spectrum Visualization ```{python} #| label: py-ch05-fft-spectrum #| eval: false #| code-fold: false import numpy as np import matplotlib.pyplot as plt H, W = 128, 128 y, x = np.mgrid[0:H, 0:W] # Smooth blob plus oriented sinusoidal texture blob = np.exp(-((x - 64)**2 + (y - 64)**2) / (2 * 18**2)) texture = 0.25 * np.cos(2 * np.pi * (8 * x / W + 14 * y / H)) image = blob + texture F = np.fft.fft2(image) F_shift = np.fft.fftshift(F) log_magnitude = np.log1p(np.abs(F_shift)) fig, axes = plt.subplots(1, 2, figsize=(10, 4)) axes[0].imshow(image, cmap="gray") axes[0].set_title("synthetic image") axes[0].axis("off") axes[1].imshow(log_magnitude, cmap="magma") axes[1].set_title("log Fourier magnitude") axes[1].axis("off") plt.show() ``` ## 5.16 Python Example: Low-Pass and High-Pass Filtering ```{python} #| label: py-ch05-frequency-filtering #| eval: false #| code-fold: false import numpy as np import matplotlib.pyplot as plt H, W = image.shape cy, cx = H // 2, W // 2 Y, X = np.ogrid[:H, :W] D = np.sqrt((Y - cy)**2 + (X - cx)**2) radius = 16 low_mask = (D <= radius).astype(float) high_mask = 1.0 - low_mask F_shift = np.fft.fftshift(np.fft.fft2(image)) low_image = np.real(np.fft.ifft2(np.fft.ifftshift(F_shift * low_mask))) high_image = np.real(np.fft.ifft2(np.fft.ifftshift(F_shift * high_mask))) fig, axes = plt.subplots(1, 3, figsize=(12, 4)) for ax, img, title in zip( axes, [image, low_image, high_image], ["original", "low-pass", "high-pass"] ): ax.imshow(img, cmap="gray") ax.set_title(title) ax.axis("off") plt.show() ``` ## 5.17 Python Example: Blur Detection by High-Frequency Energy ```{python} #| label: py-ch05-blur-detection #| eval: false #| code-fold: false import numpy as np from scipy.ndimage import gaussian_filter rng = np.random.default_rng(7243) sharp = image blurred = gaussian_filter(image, sigma=3.0) def high_frequency_ratio(img, radius=20): H, W = img.shape F = np.fft.fftshift(np.fft.fft2(img)) power = np.abs(F)**2 cy, cx = H // 2, W // 2 Y, X = np.ogrid[:H, :W] D = np.sqrt((Y - cy)**2 + (X - cx)**2) high = power[D > radius].sum() total = power.sum() return high / total print("sharp high-frequency ratio:", high_frequency_ratio(sharp)) print("blurred high-frequency ratio:", high_frequency_ratio(blurred)) ``` ## 5.18 Python Example: A Tiny Spectral Feature Classifier ```{python} #| label: py-ch05-spectral-classifier #| eval: false #| code-fold: false import numpy as np from sklearn.linear_model import LogisticRegression from sklearn.model_selection import train_test_split from sklearn.metrics import classification_report rng = np.random.default_rng(5110) H, W = 64, 64 y, x = np.mgrid[0:H, 0:W] def make_image(label): base = np.exp(-((x - 32)**2 + (y - 32)**2) / (2 * 12**2)) noise = 0.10 * rng.normal(size=(H, W)) if label == 0: texture = 0.18 * np.cos(2 * np.pi * (4 * x / W + 3 * y / H)) else: texture = 0.18 * np.cos(2 * np.pi * (14 * x / W + 10 * y / H)) return base + texture + noise def spectral_features(img): F = np.fft.fftshift(np.fft.fft2(img)) power = np.abs(F)**2 cy, cx = img.shape[0] // 2, img.shape[1] // 2 Y, X = np.ogrid[:img.shape[0], :img.shape[1]] D = np.sqrt((Y - cy)**2 + (X - cx)**2) low = power[D <= 8].sum() mid = power[(D > 8) & (D <= 18)].sum() high = power[D > 18].sum() total = power.sum() return np.array([low / total, mid / total, high / total]) images = [] labels = [] for label in [0, 1]: for _ in range(150): images.append(make_image(label)) labels.append(label) X_features = np.vstack([spectral_features(img) for img in images]) y_labels = np.array(labels) X_train, X_test, y_train, y_test = train_test_split( X_features, y_labels, test_size=0.3, random_state=0, stratify=y_labels ) clf = LogisticRegression() clf.fit(X_train, y_train) print(classification_report(y_test, clf.predict(X_test))) print("coefficients:", clf.coef_) ``` ## 5.19 TensorFlow Example: Frequency Loss for Image Reconstruction A reconstruction model is often trained using pixel MSE: $$ L_{pixel}(x,\widehat{x})=\|x-\widehat{x}\|_2^2. $$ One may also add a frequency-domain loss: $$ L_{freq}(x,\widehat{x}) =\|\log(1+|F(x)|)-\log(1+|F(\widehat{x})|)\|_2^2. $$ ```{python} #| label: py-ch05-tensorflow-frequency-loss #| eval: false #| code-fold: false import tensorflow as tf @tf.function def frequency_loss(y_true, y_pred): # y_true and y_pred are assumed to have shape (batch, height, width, channels) y_true_c = tf.cast(y_true, tf.complex64) y_pred_c = tf.cast(y_pred, tf.complex64) true_fft = tf.signal.fft2d(tf.transpose(y_true_c, [0, 3, 1, 2])) pred_fft = tf.signal.fft2d(tf.transpose(y_pred_c, [0, 3, 1, 2])) true_mag = tf.math.log1p(tf.abs(true_fft)) pred_mag = tf.math.log1p(tf.abs(pred_fft)) return tf.reduce_mean(tf.square(true_mag - pred_mag)) def combined_loss(y_true, y_pred, alpha=0.05): pixel = tf.reduce_mean(tf.square(y_true - y_pred)) freq = frequency_loss(y_true, y_pred) return pixel + alpha * freq ``` This loss is not automatically better than pixel loss. It changes the model's priorities. It may help preserve texture or reduce spectral artifacts, but it can also overemphasize frequencies that are not semantically important. ## 5.20 Common Mistakes ::: {.callout-warning} ### Mistake 1: Confusing frequency index with physical frequency In an array, the index $k$ is not automatically measured in cycles per meter or cycles per degree. Physical frequency depends on pixel spacing. ::: ::: {.callout-warning} ### Mistake 2: Ignoring phase Magnitude spectra are useful, but phase carries much of the spatial arrangement. Reconstructing an image from the wrong phase usually destroys recognizable structure. ::: ::: {.callout-warning} ### Mistake 3: Forgetting boundary assumptions The DFT assumes periodicity. Edges of a finite image can create artificial high-frequency components. ::: ::: {.callout-warning} ### Mistake 4: Thinking high frequency means noise Edges, fine anatomical structures, text, and texture are also high-frequency. Removing all high frequencies may destroy important information. ::: ::: {.callout-warning} ### Mistake 5: Applying frequency tricks without validating task performance Frequency filtering can improve visual quality while hurting downstream classification, detection, or segmentation. Always evaluate on the actual task. ::: ## 5.21 Summary Fourier analysis provides a second coordinate system for images. Instead of describing an image by pixel values, we describe it by frequencies, amplitudes, and phases. This viewpoint explains smoothing, sharpening, convolution, compression, aliasing, and many artifacts in modern AI vision systems. The main mathematical takeaways are: 1. the DFT is a change of basis into orthogonal complex exponential modes; 2. the 2D DFT decomposes images by horizontal and vertical oscillations; 3. Fourier magnitude describes energy by frequency, while phase describes spatial alignment; 4. convolution in space becomes multiplication in frequency; 5. low-pass filters smooth, high-pass filters emphasize edges and noise, and band-pass filters capture texture; 6. sampling without sufficient resolution causes aliasing; 7. spectral features can be useful statistically but must be interpreted carefully; 8. modern CNNs, transformers, neural fields, and generative models all have meaningful frequency-domain behavior. ## Exercises ### Conceptual Exercises 1. Explain why a smooth image has most of its Fourier energy near zero frequency. 2. Why does an edge require high-frequency components? 3. What information is lost if we keep Fourier magnitude but discard Fourier phase? 4. Explain why downsampling without low-pass filtering can create aliasing. 5. Why might a high-pass filter amplify both edges and noise? ### Mathematical Exercises 1. Prove the orthogonality identity $$ \sum_{n=0}^{N-1} e^{2\pi i(k-\ell)n/N}=0 $$ when $k\ne \ell \pmod N$. 2. Derive the inverse DFT formula from the orthogonality of Fourier modes. 3. Prove Parseval's identity for the unitary DFT matrix. 4. Let $h=[1/2,1/2]$. Compute its frequency response and show that it suppresses high frequencies. 5. Let $d=[-1,1]$. Compute $|\widehat{d}(\omega)|$ and interpret it as an edge detector. 6. Show that the two-dimensional DFT can be written as $$ \widehat{I}=F_HIF_W^T. $$ 7. For a sinusoidal image $$ I(x,y)=\cos(2\pi(\xi x+\eta y)), $$ describe the orientation of its visible stripes. ### Python Exercises 1. Generate a $128\times128$ image containing two sinusoids with different orientations. Plot its log Fourier magnitude. 2. Implement ideal low-pass, high-pass, and band-pass filters using `numpy.fft`. 3. Compare Gaussian blur in the spatial domain with Gaussian-like attenuation in the frequency domain. 4. Write a function that computes the fraction of spectral energy above a radius $R$. 5. Use spectral energy features to classify synthetic smooth images versus textured images. 6. Downsample an image with and without antialiasing. Compare their spectra. 7. Use Fourier magnitude to detect periodic noise and design a simple notch filter. ### AI and Modeling Exercises 1. Ask an AI assistant to explain the convolution theorem. Then write your own proof and identify any missing assumptions. 2. Ask an AI assistant for code that performs low-pass filtering with `numpy.fft`. Check whether it uses `fftshift` and `ifftshift` correctly. 3. Compare the Fourier spectra of natural images, blurred images, and noisy images. 4. Train a small CNN on synthetic stripe images. Visualize the spectra of the first-layer filters. 5. Investigate whether a classifier trained on synthetic images relies more on low-frequency shape or high-frequency texture. 6. Design a prompt for an AI assistant that asks it to distinguish between Fourier magnitude, phase, power spectrum, and energy. ## Further Reading Fourier methods and classical image filtering are discussed in @gonzalez2018digital and @szeliski2022computer. For broader connections between signal representations, learning, and modern deep models, see @goodfellow2016deep and @lecun1998gradient. Frequency ideas also appear in modern representation learning, implicit neural representations, and transformer positional encodings, which will be revisited in later chapters. <script> (function() { function waitForPlotly(callback) { if (typeof Plotly !== 'undefined') callback(); else setTimeout(function() { waitForPlotly(callback); }, 100); } function ch05MakeImage(n) { const z = []; for (let i = 0; i < n; i++) { const row = []; const y = -1 + 2 * i / (n - 1); for (let j = 0; j < n; j++) { const x = -1 + 2 * j / (n - 1); const blob = Math.exp(-6 * ((x - 0.15) * (x - 0.15) + (y + 0.1) * (y + 0.1))); const stripe = 0.35 * Math.cos(2 * Math.PI * (5 * x + 9 * y)); const edge = x + 0.35 * y > 0.2 ? 0.55 : -0.05; row.push(blob + stripe + edge); } z.push(row); } return z; } function ch05Dft2Magnitude(img) { const H = img.length; const W = img[0].length; const mag = Array.from({length: H}, () => Array(W).fill(0)); for (let u = 0; u < H; u++) { for (let v = 0; v < W; v++) { let re = 0; let im = 0; for (let m = 0; m < H; m++) { for (let n = 0; n < W; n++) { const angle = -2 * Math.PI * (u * m / H + v * n / W); re += img[m][n] * Math.cos(angle); im += img[m][n] * Math.sin(angle); } } mag[u][v] = Math.log(1 + Math.sqrt(re * re + im * im)); } } // fftshift for visualization const shifted = Array.from({length: H}, () => Array(W).fill(0)); for (let i = 0; i < H; i++) { for (let j = 0; j < W; j++) { shifted[i][j] = mag[(i + Math.floor(H/2)) % H][(j + Math.floor(W/2)) % W]; } } return shifted; } function renderBasis() { const el = document.getElementById('cv-ch05-basis-demo'); if (!el) return; const N = 200; const x = []; for (let n = 0; n < N; n++) x.push(n / (N - 1)); const freqs = [1, 2, 5, 11]; const traces = freqs.map(function(k) { return { x: x, y: x.map(function(t) { return Math.cos(2 * Math.PI * k * t); }), mode: 'lines', name: 'k = ' + k, hovertemplate: 't=%{x:.3f}<br>value=%{y:.3f}<extra></extra>' }; }); Plotly.newPlot(el, traces, { title: 'Real parts of Fourier basis functions', margin: {t: 60, r: 20, b: 50, l: 55}, xaxis: {title: 'normalized position t'}, yaxis: {title: 'cos(2πkt)', range: [-1.15, 1.15]} }, {responsive: true, displaylogo: false}); } function renderSpectrum() { const el = document.getElementById('cv-ch05-spectrum-demo'); if (!el) return; const img = ch05MakeImage(32); const spec = ch05Dft2Magnitude(img); Plotly.newPlot(el, [ { z: img, type: 'heatmap', colorscale: 'Greys', showscale: false, xaxis: 'x', yaxis: 'y', hovertemplate: 'row=%{y}, col=%{x}<br>value=%{z:.3f}<extra></extra>' }, { z: spec, type: 'heatmap', colorscale: 'Viridis', showscale: false, xaxis: 'x2', yaxis: 'y2', hovertemplate: 'freq row=%{y}, freq col=%{x}<br>log magnitude=%{z:.3f}<extra></extra>' } ], { title: 'Image and shifted log Fourier magnitude', margin: {t: 60, r: 20, b: 55, l: 60}, grid: {rows: 1, columns: 2, pattern: 'independent'}, xaxis: {title: 'column', constrain: 'domain'}, yaxis: {title: 'row', autorange: 'reversed', scaleanchor: 'x'}, xaxis2: {title: 'frequency column', constrain: 'domain'}, yaxis2: {title: 'frequency row', autorange: 'reversed', scaleanchor: 'x2'}, annotations: [ {text: 'spatial domain', x: 0.20, y: 1.08, xref: 'paper', yref: 'paper', showarrow: false}, {text: 'frequency domain', x: 0.82, y: 1.08, xref: 'paper', yref: 'paper', showarrow: false} ], showlegend: false }, {responsive: true, displaylogo: false}); } function ch05SeparableSmooth(img, radius) { const H = img.length; const W = img[0].length; const out = Array.from({length: H}, () => Array(W).fill(0)); const r = radius; for (let i = 0; i < H; i++) { for (let j = 0; j < W; j++) { let s = 0, wsum = 0; for (let di = -r; di <= r; di++) { for (let dj = -r; dj <= r; dj++) { const ii = Math.min(H - 1, Math.max(0, i + di)); const jj = Math.min(W - 1, Math.max(0, j + dj)); const w = Math.exp(-(di * di + dj * dj) / (2 * r * r)); s += w * img[ii][jj]; wsum += w; } } out[i][j] = s / wsum; } } return out; } function ch05Subtract(A, B) { return A.map(function(row, i) { return row.map(function(v, j) { return v - B[i][j]; }); }); } function renderFilter() { const el = document.getElementById('cv-ch05-filter-demo'); if (!el) return; const img = ch05MakeImage(64); const low = ch05SeparableSmooth(img, 4); const high = ch05Subtract(img, low); Plotly.newPlot(el, [ {z: img, type: 'heatmap', colorscale: 'Greys', showscale: false, xaxis: 'x', yaxis: 'y', name: 'original'}, {z: low, type: 'heatmap', colorscale: 'Greys', showscale: false, xaxis: 'x2', yaxis: 'y2', name: 'low-pass'}, {z: high, type: 'heatmap', colorscale: 'RdBu', showscale: false, xaxis: 'x3', yaxis: 'y3', name: 'high-pass'} ], { title: 'Filtering intuition: original, low-pass, and high-pass components', margin: {t: 60, r: 20, b: 55, l: 50}, grid: {rows: 1, columns: 3, pattern: 'independent'}, xaxis: {title: 'original'}, yaxis: {autorange: 'reversed', scaleanchor: 'x'}, xaxis2: {title: 'low-pass'}, yaxis2: {autorange: 'reversed', scaleanchor: 'x2'}, xaxis3: {title: 'high-pass'}, yaxis3: {autorange: 'reversed', scaleanchor: 'x3'}, showlegend: false }, {responsive: true, displaylogo: false}); } function renderAliasing() { const el = document.getElementById('cv-ch05-aliasing-demo'); if (!el) return; const dense = []; const yLow = []; const yHigh = []; const samplesX = []; const samplesY = []; const fLow = 2; const fHigh = 10; const sampleN = 9; for (let i = 0; i < 600; i++) { const t = i / 599; dense.push(t); yLow.push(Math.cos(2 * Math.PI * fLow * t)); yHigh.push(Math.cos(2 * Math.PI * fHigh * t)); } for (let n = 0; n < sampleN; n++) { const t = n / (sampleN - 1); samplesX.push(t); samplesY.push(Math.cos(2 * Math.PI * fLow * t)); } Plotly.newPlot(el, [ {x: dense, y: yLow, mode: 'lines', name: 'low frequency'}, {x: dense, y: yHigh, mode: 'lines', name: 'higher frequency'}, {x: samplesX, y: samplesY, mode: 'markers', marker: {size: 10}, name: 'samples'} ], { title: 'Aliasing: different continuous frequencies can agree on sampled points', margin: {t: 60, r: 20, b: 50, l: 55}, xaxis: {title: 'position'}, yaxis: {title: 'signal value', range: [-1.2, 1.2]} }, {responsive: true, displaylogo: false}); } waitForPlotly(function() { renderBasis(); renderSpectrum(); renderFilter(); renderAliasing(); }); })(); </script>