Frequency Domain Filtering

hardFREEFourier TransformsFrequencyCV: Image Processing

Implement image filtering in the frequency domain using FFT.

Convolution in spatial domain = multiplication in frequency domain: $\mathcal{F}(f * g) = \mathcal{F}(f) \cdot \mathcal{F}(g)$

Algorithm:

Compute FFT of image: $F = \mathcal{F}(I)$
Create frequency domain filter $H$ (same size as image)
Multiply: $G = F \cdot H$
Inverse FFT: $I_{filtered} = \mathcal{F}^{-1}(G)$

Common filters:

Low-pass: Keep center (low frequencies) → blur
High-pass: Keep edges (high frequencies) → sharpen
Band-pass: Keep ring of frequencies

Mask definition (centred spectrum):

After shifting, the zero frequency sits at $(c_y, c_x) = (\lfloor h/2 \rfloor, \lfloor w/2 \rfloor)$ . Let $d(u, v)$ be the Euclidean distance of frequency $(u, v)$ from that centre and $D_{max} = \sqrt{c_y^2 + c_x^2}$ .
The radius is $r = \text{cutoff} \cdot D_{max}$ $r = cutoff \cdot D_{ma x}$ . The mask is 1 where:
- 'lowpass': $d \le r$
- 'highpass': $d \ge r$
- 'bandpass': $0.5\,r \le d \le 1.5\,r$
and 0 elsewhere. Return the real part of the inverse transform, same shape as the input.

Example

Input

image = 64×64 image with edges
filter_type = 'lowpass'
cutoff = 0.1

Output

Blurred image (edges smoothed)

Reasoning

Input: a concrete $64 \times 64$ edge image: every row is 32 zeros then 32 values of 255. The transform treats the image as periodic, so the right border wrapping to the left is a second edge.
Spectrum: all rows are identical, so only the centre row (zero vertical frequency) is non-zero. Its centre is $255 \cdot 2048 = 522240$ ; the edge adds odd harmonics of shrinking size ( $332602$ , $111224$ , $67166$ at offsets $\pm1, \pm3, \pm5$ ).
Mask: the centre is $(32, 32)$ , so $D_{max} = \sqrt{32^2 + 32^2} \approx 45.25$ and $r = 0.1 \cdot 45.25 \approx 4.53$ . Only 69 of 4096 frequencies survive; on the centre row that is the mean plus harmonics 1 and 3.
Output: Blurred image (edges smoothed). It is still $64 \times 64$ with mean $127.5$ (the centre frequency survives), but the 0→255 jump becomes a ramp: $-10.2, 26.2, 80.5, 143.4, 203.4, 249.6$ across columns 26–36.
Notice the overshoot to about $-25.2$ and $280.2$ , outside $[0, 255]$ : a sharp circular cut rings. A smaller cutoff blurs more.

Constraints

image: 2D grayscale array
filter_type: 'lowpass', 'highpass', or 'bandpass'
cutoff: Cutoff frequency (0-1, fraction of max frequency)
Return: Filtered image (real part)

Learn this in

Image ProcessingCV Study Plan

More from CV: Image Processing

Separable Filter Optimizationhard Contrast Limited Adaptive Histogram Equalizationmedium Frequency Component Energyeasy Low-Pass Filter (Frequency)medium 1D DFTmedium

Concept primer

Background Knowledge

In image processing, a 2D image can be seen as a discrete function $I(x,y)$ defined on a grid. The 2D Discrete Fourier Transform (DFT) represents this image in terms of spatial frequencies: low frequencies describe smooth, slowly varying regions; high frequencies describe rapid changes such as edges and fine details. The Fast Fourier Transform (FFT) is an efficient algorithm to compute the DFT in $O(N \log N)$ time instead of $O(N^2)$ .

A key property is the convolution theorem: convolution in the spatial domain corresponds to pointwise multiplication in the frequency domain:

\mathcal{F}(f * g) = \mathcal{F}(f)\cdot\mathcal{F}(g)

This is why we can implement filtering either by convolving with a kernel in the image domain, or by multiplying with a filter in the frequency domain. Low-pass filters keep low frequencies (central region in the spectrum) and suppress high ones, leading to blurring; high-pass filters do the opposite, enhancing edges and fine details. Band-pass filters keep only a ring of frequencies, removing both very low and very high components.

In practice, for discrete images, we work with the 2D FFT and its inverse (IFFT). Because the DFT assumes periodic extension, boundaries can create artifacts, and because the zero-frequency component is at the corner of the FFT output, we often shift the spectrum so that the DC/low frequencies are in the center (using operations like fftshift / ifftshift) to make filter design more intuitive.

Algorithm / Approach Pattern

General pattern for frequency-domain filtering:

Transform image to frequency domain with 2D FFT.
Construct a filter mask $H(u,v)$ (same size as the image) that specifies which frequencies to keep/attenuate.
Multiply the spectrum and the filter elementwise.
Transform back with inverse 2D FFT and take the real part.

You can vary only the design of $H$ to implement low-pass, high-pass, or band-pass filters while keeping the same overall pipeline.

Step-by-Step Strategy

Assume a grayscale image I of size (H, W):

Convert to floating point

I = I.astype(np.float32)

Compute 2D FFT

F = np.fft.fft2(I)
F_shifted = np.fft.fftshift(F) # optional but helpful for designing H

Create frequency grid

Get indices:

rows, cols = I.shape
crow, ccol = rows // 2, cols // 2

Create a distance map from the center (for circular filters):

u = np.arange(rows) - crow
v = np.arange(cols) - ccol
V, U = np.meshgrid(v, u)
D = np.sqrt(U**2 + V**2)

Design filter $H$ (same size as image)

Ideal low-pass with cutoff radius D0:

H = (D <= D0).astype(np.float32)

Ideal high-pass:

H = (D >= D0).astype(np.float32)

Band-pass between D1 and D2:

H = ((D >= D1) & (D <= D2)).astype(np.float32)

Apply filter

G_shifted = F_shifted * H
G = np.fft.ifftshift(G_shifted)

Inverse FFT and post-process

I_filtered_complex = np.fft.ifft2(G)
I_filtered = np.real(I_filtered_complex)

Optionally normalize or clip:

I_filtered = np.clip(I_filtered, 0, 255).astype(np.uint8)

(Optional) For colored images

Apply the same process per channel (R, G, B) or convert to another color space and filter only luminance.

Common Pitfalls

Not matching shapes: $H$ must be exactly the same size as the FFT of the image; mismatches cause broadcasting errors.
Forgetting fftshift / ifftshift consistency:
If you design $H$ assuming low frequencies are at the center, you must apply it to the shifted spectrum and then unshift before IFFT.
Ignoring complex output:
After IFFT, results are complex due to numerical error; you should take np.real(...) before displaying or saving.
Ringing artifacts:
Ideal (sharp cutoff) filters often cause ringing (Gibbs phenomenon). In practice, smoother filters (Gaussian, Butterworth) reduce artifacts.
Border artifacts & padding:
Convolution via DFT is circular. If you want linear convolution, zero-pad image and filter appropriately before FFT.
Scaling issues:
Some libraries scale FFT/IFFT differently. Stick to the same FFT/IFFT pair from one library to avoid extra scaling factors.

Time & Space Complexity

Let the image size be $N = H \times W$ .

Time complexity
2D FFT: $O(N \log N)$
Elementwise multiplication with $H$ : $O(N)$
2D inverse FFT: $O(N \log N)$ Overall: $O(N \log N)$
Space complexity
Need space for the image, the complex spectrum, the filter $H$ , and the filtered spectrum. Each is $O(N)$ . Overall: $O(N)$ additional space (with a constant factor for complex arrays and the mask).

solution.py

Python 3.13

Test results