Low-Pass Filter (Frequency)

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:

1. Transform the image to frequency domain (2D FFT).
2. Shift the zero-frequency component to the center for easier mask definition.
3. Construct a frequency-domain mask $H(u,v)$ encoding the filter (here: ideal low-pass).
4. Apply the filter by pointwise multiplication: $G(u,v) = F(u,v) \cdot H(u,v)$.
5. Inverse transform back to spatial domain (inverse FFT).
6. 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):

1. Convert to float (optional but common)

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

2. Compute 2D FFT

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

3. 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

4. Create ideal low-pass mask

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

5. Apply the filter in frequency domain

G_shift = F_shift * H_mask

6. Inverse shift and inverse FFT

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

7. 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).