Low-Pass Filter (Frequency)

mediumFREEFourier TransformsSignal ProcessingCV: Image Processing

Implement an ideal low-pass filter in the frequency domain to remove high-frequency components from an image spectrum. This process involves modifying the frequency representation of an image to only retain frequency components below a specified cutoff frequency.

The concept of filtering in the frequency domain is rooted in the Fourier Transform, which decomposes a signal into its constituent frequencies. In image processing, this allows for the separation of low-frequency components, representing overall brightness and shape, from high-frequency components, representing details and noise. By applying a low-pass filter, we can reduce noise and blur an image.

To achieve this, we follow these steps:

Obtain the frequency spectrum of the image.
Identify the cutoff frequency, below which frequency components are retained.
Set frequency components above the cutoff to zero.

F'(u, v) = \begin{cases} F(u, v) & \text{if } |u| \leq D_0 \text{ and } |v| \leq D_0 \\ 0 & \text{otherwise} \end{cases}

Your function works on a 1D spectrum given in standard (unshifted) FFT order, so negative frequencies wrap around to the end of the list. Return a list of the same length with the removed components set to $0$ .

This technique is widely used in image denoising applications.

Example

Input

low_pass_filter([10, 5, 3, 1, 1, 3, 5], 2)

Output

[10, 5, 3, 0, 0, 3, 5]

Reasoning

Inputs: spectrum is a 1D magnitude spectrum of length $N = 7$ in standard (unshifted) FFT order, and cutoff is $D_0 = 2$ , the highest frequency allowed through.
In that order, entry $i$ does not hold frequency $i$ . Past the middle the frequencies are negative and wrap around, so entry $i$ has $|u| = \min(i, N - i)$ . For $N = 7$ that gives $|u| = 0, 1, 2, 3, 3, 2, 1$ .
Apply $F'(u) = F(u)$ when $|u| \le 2$ , else $0$ . Entries with $|u| \in \{0, 1, 2\}$ keep their values 10, 5, 3 at the front and 3, 5 at the back. Both entries with $|u| = 3$ (the 1, 1 in the middle) become $0$ .
Output: [10, 5, 3, 0, 0, 3, 5]. It still has length 7.
Notice that the low frequencies sit at both ends, so the zeroed band is in the middle. $u$ and $-u$ always pass or fail together. With $D_0 = 0$ , only the DC term at index $0$ survives.

Constraints

cutoff is the maximum frequency index to keep (0-indexed)
Return filtered magnitude spectrum

Learn this in

Image FormationCV Study Plan Image ProcessingCV Study Plan

More from CV: Image Processing

Frequency Domain Filteringhard Separable Filter Optimizationhard Contrast Limited Adaptive Histogram Equalizationmedium Frequency Component Energyeasy 1D DFTmedium

Concept primer

You are working in the frequency domain: take the image’s Fourier transform, modify its spectrum, then invert it. An ideal low-pass filter means you keep only frequencies whose distance from the origin is below a cutoff radius and set all others to zero.

1. Background Knowledge (Concepts & Theory)

A 2D Fourier Transform represents an image as a sum of complex sinusoids of different spatial frequencies.
Low frequencies encode smooth, slowly varying structures (overall shapes, illumination).
High frequencies encode edges, fine details, and noise.
In the frequency domain, a filter is just a mask (or transfer function) $H(u, v)$ that you multiply with the transform $F(u, v)$ .
A low-pass filter lets low frequencies pass (kept near original value) and attenuates or removes high frequencies.
An ideal low-pass filter is a hard cutoff:

H(u,v) = \begin{cases} 1 & \text{if } D(u,v) \leq D_0 \\ 0 & \text{if } D(u,v) > D_0 \end{cases}

where $D(u,v)$ is distance from the origin in frequency space and $D_0$ is the cutoff.

Practically, for digital images:
The 2D DFT is implemented with an FFT and is usually centered using a shift so that the zero frequency is at the image center, making circular masks convenient.
Multiplying by an ideal circular mask in frequency domain corresponds to convolving with a sinc-like kernel in spatial domain, which can cause ringing near edges (Gibbs phenomenon).

2. Algorithm / General Approach

General pattern for “filter in frequency domain” problems:

Transform the image to frequency domain (2D FFT).
Shift the zero-frequency component to the center for easier mask definition.
Construct a frequency-domain mask $H(u,v)$ encoding the filter (here: ideal low-pass).
Apply the filter by pointwise multiplication: $G(u,v) = F(u,v) \cdot H(u,v)$ .
Inverse transform back to spatial domain (inverse FFT).
Post-process (take real part, rescale or clip intensities if needed).

For ideal low-pass, the mask is a binary disk: 1 inside radius $R$ , 0 outside.

3. Step-by-Step Strategy

Assume input is a 2D grayscale image img (H×W), and cutoff radius is R (in frequency pixels):

Convert to float (optional but common)

Ensure img is in a float type to avoid precision issues in transforms.

Compute 2D FFT

F = fft2(img) # 2D FFT
F_shift = fftshift(F) # move low freq to center

Build coordinate grids and distance map

Compute coordinates relative to center:

H, W = img.shape
cy, cx = H // 2, W // 2
y = np.arange(H) - cy
x = np.arange(W) - cx
X, Y = np.meshgrid(x, y)
D = np.sqrt(X**2 + Y**2) # distance from center in frequency domain

Create ideal low-pass mask

R = cutoff # given
H_mask = (D <= R).astype(float) # 1 inside radius, 0 outside

Apply the filter in frequency domain

G_shift = F_shift * H_mask

Inverse shift and inverse FFT

G = ifftshift(G_shift)
img_filtered_complex = ifft2(G)
img_filtered = np.real(img_filtered_complex)

Normalize or clip if required by platform

E.g., if original is 0–255, you might clip and cast back:

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

This pattern is easily adaptable: changing the mask formula changes the filter type (e.g., Gaussian low-pass, high-pass, band-pass, etc.).

4. Common Pitfalls

Forgetting fftshift / ifftshift
If you build a circular mask assuming low frequency at center, you must use fftshift before masking and ifftshift before inverse FFT. Otherwise the mask is misaligned.
Incorrect radius units
The cutoff R is in pixels in the frequency grid, not in cycles per unit distance.
For non-square images, remember the grid extents differ in each dimension.
Ignoring complex output
ifft2 yields complex values due to numerical errors; always take np.real(...) before further use.
Aliasing / wrap-around assumptions
The FFT assumes periodic boundaries. Very sharp filters (like ideal) can introduce ringing artifacts near edges and around sharp transitions.
Type and scaling issues
Mixing integer images with FFTs can be problematic.
You might need to normalize (/255.0) or scale back after filtering, depending on how the judge expects output.

5. Time & Space Complexity

Let the image size be $H \times W$ with $N = H \cdot W$ :

Time Complexity
2D FFT: $O(N \log N)$
2D inverse FFT: $O(N \log N)$
Mask construction and pointwise multiply: $O(N)$
Total: $O(N \log N)$
Space Complexity
Need to store: original image, complex spectrum, mask, filtered spectrum, and output.
Each is $O(N)$ , so overall $O(N)$ auxiliary space (constant-factor overhead for a few additional arrays).

solution.py

Python 3.13

Test results