4.3 Frequency Domain Filtering
49
Filtering in Frequency Domain
• Filtering is achieved by linear convolution:
, ∗,
• Convolution theorem in DFT stated that:
• The output , can be obtained by first multiplying the DFT of and and perform an inverse DFT.
• But note that instead of
∗ , is recovered, so appropriate padding is needed.
50
Frequency Domain Filtering
Note: FFT (Fast Fourier Transform) is a quick way to compute DFT.
51
Why Filtering in Frequency Domain?
1. The filter may be simpler to specify or compute in one of the domains
2. Computational advantage of filtering in frequency domain
Size of Image: × Size of kernel: ×
# ops required for spatial conv
# ops required for
• >1when>7
• approaches 1000 when 201
52
Python Example
• DFT spectrums of both the image and kernel are shifted to the centre (using fftshift)
• Multiply DFT of image and kernel
• Shift back the resulting spectrum to origin (using ifftshift) before getting the time- domain image using ifft
53
Python Example
54
Pitfall: Circular Convolution
Wraparound error along the edges, such as here
55
Circular Convolution
• The dashed area corresponds to the original image
• Note that:
• Both kernel and image are periodic in circular convolution.
• Filtering output along the dash line is the average of the top of the image and part of the bottom of the image immediately above it (see blue square)
• Recall that circular convolution becomes linear convolution with zero padding
56
Filtering Workflow
1. Givenanimage , ofsize×,padthe image to size 2 × 2 using zero-, mirror- or replicate padding.
2. ComputetheDFT,,,andshiftspectrumto the centre using fftshift.
3. Constructafiltertransferfunction,[,],ofsize 2 × 2 centering at [, ].
4. Compute,, andshiftbacktoorigin using ifftshift.
5. ComputetheinverseFFT,resultingin[,].
6. Obtainthefinalfilteredresult,,,by extracting the × region from top left quadrant of [,]
57
Filtering Workflow
58
2D Ideal Lowpass Filter (ILPF)
59
Spatial Representation of ILPF
• IDFT of ILPF is a “sinc-like” function.
• Width of ILPF small, spread of the sinc-like function large, and vice versa.
60
ILPF Example
DFT of original image with circles with the following radii superimposed:
10, 20, 60, 160, 460
r = 160
Note that ringing effect due to the convolution of a sinc-like function.
Original Image
r = 10
r = 20
r= 60
r = 460
61
Python Implementation of ILPF
Caution: Padding is not performed in this code. Thus, there will be wraparound error.
62
Python Implementation of ILPF
512 × 512
Radius = 30 pixels
pixels
Note that ringing near sharp edges
63
Cutoff frequency with and without padding
No Padding (Radius = 30 pixels)
With Padding (Radius = 60 pixels)
0.5 0.5 0.5× 0.5×
0.5 0.5 0.5×2 0.5×2
64
Gaussian Lowpass Filter (GLPF)
• AGaussianinthefrequencydomainisalsoa Gaussian in the spatial domain
• Smoother transition in frequency spectrum, so no ringing.
, ,
where , is the distance from the centre
isthecutofffrequency.
65
Python Implementation of Gaussian Filter
Note again of the wraparound error
66
ILPF vs. GLPF
Images filtered by ILPFs
Cutoff Frequencies:
Images filtered by GLPFs
10, 20,
60, 160, 460
67
Butterworth Lowpass Filter (BLPF)
(, ) 1+
1
– , is the distance from the origin – is the cutoff frequency
– istheorderofthefilter
• Properties:
≈1,, ≪ ≈0,, ≫
,
– For large , BLPF approaches ideal
• Advantage:
lowpass filter.
,
, ,
– Reduces“ringing”whilekeepingclear cutoff.
68
The Spatial Representation of BLPFs
n = 1 n = 2 n = 5 n = 20
69
Python Implementation of 2nd order BLFP
Note again of the wraparound error
70
ILPF vs. BLPF
Images filtered by ILPFs
Cutoff Frequencies:
Images filtered by BLPFs with n = 2.25
10, 20,
60, 160, 460
71
Highpass Filters
• Highpass filter can be obtained by: , 1− ,
• Ideal
, 0,, ≤ 1,, >
• Gaussian
,
, 1−
• Butterworth
,
1+
,
1
• Ideal highpass
• Gaussian highpass
• Butterworth highpass
72
Filtering results by different types of HPFs
IHPF GHPF BHPF (n = 2)
60 for all HPFs
73
Selective Filtering
• Non-selective filters
– Operate over the entire frequency rectangle
• Selective filters
– Bandreject or bandpass filters: process specific bands
– Notch filters: process small neighbourhoods around specific frequencies
74
Bandpass and Bandreject Filters
• Bandreject filters, , • Bandpass filters
, 1− (,)
75
Notch Filters
• Notchfilterssuppressneighbourhoodsaround frequency points.
• Filterswithrealvaluesinfrequencydomain(zero- phase shift filters) are symmetric about the origin. If the frequency , is suppressed, (,) is suppressed as well.
• Thegeneralformofnotchfilters:
, (, )(, )
where , and (, ) are highpass filters
centred at (,) and , , respectively.
76
Notch Filtering Example 1
Butterworth filter with 9 and 4.
77
Notch Filtering Example 2
• Horizontal scan lines corrupting the image of Saturn rings.
• Noisecanbefiltered by a notch filter suppressing vertical (v-direction) sinusoids.
78
Need to know …
•
• Effect of circular convolution in 2D filtering and how to mitigate the effect.
• The ideal, Gaussian, Butterworth lowpass and highpass filters.
• The ideal, Gaussian, Butterworth bandpass and bandreject filters.
• Construction of notch filters using highpass filters.
• Python implementations of all these filters.
79