Frequency Domain Filtering

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

---

2. Algorithm / Approach Pattern

General pattern for frequency-domain filtering:

1. Transform image to frequency domain with 2D FFT.
2. Construct a filter mask $H(u,v)$ (same size as the image) that specifies which frequencies to keep/attenuate.
3. Multiply the spectrum and the filter elementwise.
4. 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.

---

3. Step-by-Step Strategy

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

1. Convert to floating point

I = I.astype(np.float32)

2. Compute 2D FFT

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

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

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

5. Apply filter

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

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

7. (Optional) For colored images

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

---

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

---

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