digital image processing FrequencyFiltering.ppt

digital image processing filtering

1. Frequency Domain Filtering
CS474/674 - Prof. Bebis
Sections 4.7, 4.8, 4.9, 4.10, 5.4

2. Frequency Domain Methods
Spatial Domain Frequency Domain
element-wise
complex
multiplication

3. Major filter categories
•Filters are classified based on their properties in the
frequency domain:
(1) Low-pass
(2) High-pass
(3) Band-pass
(4) Band-stop

4. Example
Original signal
Low-pass filtered
High-pass filtered
Band-pass filtered
Band-stop filtered

5. Low-pass filters
(i.e., smoothing filters)
•Preserve low frequencies.
–Useful for removing details and noise suppression.
frequency domain
Example:
representative
example

6. Low-pass filter - Example
•The rectangle function is a low pass filter!
Note: when discussing filters in the frequency
domain, we’ll illustrate their properties using
positive frequencies only; however,
keep in mind that there is a “symmetric”
component on the negative axis!
spatial domain frequency domain

7. High-pass filters
(i.e., sharpening filters)
•Preserve high frequencies.
–Useful for highlighting details.
frequency
domain
Example:
representative
example

8. Band-pass filters
•Preserve frequencies within a specific band.
–Useful in image restoration.
frequency
domain
Example:
representative
example

9. Band-stop filters
•Removes frequencies within a specific band.
–Useful in image restoration.

Band-pass Band-stop
representative
example

10. Frequency Domain Methods
Case 1: H(u,v) is specified directly in
the frequency domain.
Case 2: H(u,v) is specified indirectly
in the frequency domain by specifying
h(x,y) in the spatial domain.
complex
multiplication
Very important:
the centers of
F(u,v) and
H(u,v) must
coincide!
H(u,v)
|F(u,v)|
G(u,v)
g(x,y)
f(x,y)

11. Frequency domain filtering: Case 1
F(u,v) = R(u,v) + jI(u,v)
1. Given an input image f(x,y) of size M x N, set the padding sizes P and Q, e.g.,
P=2M and Q=2N (note: P and Q must also be a power of 2 to use FFT)
2. Form a padded image f
p
(x,y) of size P x Q
3. Multiply f
p
(x,y) by (-1)
x+y
to center its spectrum.
4. Compute the DFT, F(u,v), of the image from Step 3.

12. Frequency domain filtering: Case 1 (cont’d)
5. Create H(u,v) of size P x Q with center at (P/2, Q/2). This is typically
done by specifying and sampling the desired filter function.
Example:
6. Compute the product G(u,v)=H(u,v)F(u,v) using elementwise “complex”
multiplication. If H(u,v) is real, this is:
G(u,v)= F(u,v)H(u,v) = H(u,v) R(u,v) + jH(u,v)I(u,v)
where u=0,1,...,P-1, v=0,1,…,Q-1
Butterworth lowpass filter
F(u,v) = R(u,v) + jI(u,v)where

13. Frequency domain filtering: Case 1 (cont’d)
7. Obtain the filtered image g
p(x,y) by computing the inverse DFT of
G(u,v):
8. Obtain the final filtered result, g(x,y), of size M x N, by extracting the
M x N region from the top, left quadrant of g
p
(x,y) (i.e., “undo” padding).
explicitly disregard the
imaginary part
“undo” the centering
transformation

14. Example
f(x,y) f
p
(x,y) f
p
(x,y)(-1)
x+y
|F(u,v)||H(u,v)| – centered
(Gaussian)
G(u,v)=F(u,v)H(u,v)
|G(u,v)|
g(x,y)
g
p
(x,y)

15. Frequency domain filtering: Case 2
•Given an input image f(x,y) of size M x N, and a filter h(x,y) of size
K x L, set the padding sizes P and Q, e.g., P=M+K-1 and Q=N+L-1
(note: P and Q must also be a power of 2 to use FFT).
•Generate H(u,v) as described next.
•The rest of the steps are the same as before.
–Might need to enforce theoretical constraints!

16. Specify h(x,y) in the spatial domain (Case 2)
•When specifying h(x,y) in the spatial domain, H(u,v)
can be generated as follows:
1. Form h
p(x,y) by padding h(x,y) with zeroes.
2. Multiply h
p(x,y) by (-1)
x+y
to center its spectrum.
3. Compute its DFT to obtain H(u,v).

The symmetry of h(x,y) must be explicitly preserved
when padding with 0s; let’s see why!
*
*

17. Example: specify h(x,y) in the spatial domain
600 x 600
3 x 3
Sobel
spatial
frequency
Result of spatial
domain filtering:
Result of frequency
domain filtering:
f(x,y) F(u,v)
h(x,y)
H(u,v)
g(x,y)=f(x,y)*h(x,y)g(x,y)=F
-1
{G(u,v)=F(u,v)H(u,v)}
P=Q=600+3-1=602
f
p(x,y) and h
p(x,y) will be 602 x 602
602 x 602
602 x 602

18. Preserving symmetry
Example:
Sobel filter
•Since h(x,y) is real and odd, H(u,v) will be imaginary and odd.
•We must explicitly preserve the odd symmetry of h(x,y) when
padding with zeroes; otherwise, the results will not agree with
theory!

19. •By definition, an N x M filter h(x,y) has odd symmetry if:

•Does this hold true for the Sobel filter (N=M=3)?
Preserving symmetry (cont’d)
h(x,y) = -h(N-x, M-y)
h(x,y) = -h(3-x, 3-y)
-1 0 1
-2 0 2
-1 0 1
0 1 2
0







1







2







e.g., g(1,1) ≠ -g(2,2)
No!
Notation:
x
y

20. •We need to apply certain steps to make sure that the odd symmetry of
the Sobel mask is preserved.
•As shown in Example 4.10 (page 290-291), the first element of an odd
filter must be 0.
Step 1: add a leading row and column of 0s (see page 317):
Preserving symmetry (cont’d)
0 0 0 0
0 -1 0 1
0 -2 0 2
0 -1 0 1
-1 0 1
-2 0 2
-1 0 1
h(x,y) = -h(4-x, 4-y) ?
0 1 2 3
0






1







2






3


N=M=4
N=M=3
e.g., g(1,1) = -g(3,3)
Yes!

21. •Padding with zeroes can be thought as inserting a smaller array (e.g., Sobel mask) into a
larger array of zeroes, e.g.:
•As shown in Example 4.10 (page 291), inserting a 2-D array of even dimensions into a
larger array of zeros, also of even dimensions, preserves the symmetry of the smaller array,
provided that their centers coincide.
Preserving symmetry (cont’d)
0 0 0 0
0 -1 0 1
0 -2 0 2
0 -1 0 1
0






1






2







3


0 1 2 3
insert
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 2 3 4 5
0






1







2







3






4






5
6 x 6 array of 0s
0 0 0 0 0 0
0 0 0 0 0 0
0 0 -1 0 1 0
0 0 -2 0 2 0
0 0 -1 0 1 0
0 0 0 0 0 0
0 1 2 3 4 5
0






1







2







3






4






5
padded array

22. Step 2: Pad with zeros such that the centers coincide.
Preserving symmetry (cont’d)
0 0 0 0
0 -1 0 1
0 -2 0 2
0 -1 0 1
0






1






2







3


0 1 2 3
insert
4 x 4 array
center: (2,2)
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 2 3 4 5
0






1







2







3






4






5
6 x 6 array
center: (3,3)
0 0 0 0 0 0
0 0 0 0 0 0
0 0 -1 0 1 0
0 0 -2 0 2 0
0 0 -1 0 1 0
0 0 0 0 0 0
0 1 2 3 4 5
0






1








2






3






4






5
g(x,y) = -g(6-x, 6-y)
0 0 0 0 0 0
0 0 0 0 0 0
0 -1 0 1 0 0
0 -2 0 2 0 0
0 -1 0 1 0 0
0 0 0 0 0 0
0 1 2 3 4 5
0





1







2






3







4






5
g(x,y) ≠ -g(6-x, 6-y)
e.g., g(2,3)=-g(4,3)e.g., g(1,2) ≠ -g(5,4)
Misplacement by 1 pixel
will violate odd symmetry!

23. h(x,y) specified in spatial domain (Case 2)
•Steps for “real” filters exhibiting “odd” symmetry
(a similar procedure can be devised for other cases):
1.Add a leading row and column of 0s in h(x,y).
2. Obtain h
p
(x,y) by placing h(x,y) at the center of the padded array
3. Multiply by (-1)
x+y
to center its spectrum.
4. Compute H(u,v) using DFT.
5. Set real(H(u,v))=0 to account for parasitic effects.
(i.e., since only the imaginary part is non-zero).
6. Multiply the resulted H(u,v) by (-1)
u+v

(i.e., placing h(x,y) at the center of the padded array
implies multiplying H(u,v) by (-1)
u+v
; step 6 undoes this).
Explicitly
enforce
theoretical
properties!

24. Low Pass (LP) Filters
•Ideal low-pass filter (ILPF)
•Butterworth low-pass filter (BLPF)
•Gaussian low-pass filter (GLPF)

25. Low-pass (LP) filtering
•Preserves low frequencies, attenuates high frequencies.
1D ILPF
D
0
: cut-off frequency – user specified
0
1 0
( )
0
if u D
H u
otherwise
 



26. Lowpass (LP) filtering (cont’d)
•In 2D, the cutoff frequency D
0
is specified by the radius of
a circle centered at the origin.
2D ILPF
0
2 2
1 ( , )
( , )
0
where ( , )
if D u v D
H u v
otherwise
D u v u v



 

27. Lowpass (LP) filtering (cont’d)
•Assuming that we have centered the filter at (P/2, Q/2), as
required, D(u,v) should be computed as:
2D ILPF
0
2 2
1 ( , )
( , )
0
where ( , ) ( /2) ( /2)
if D u v D
H u v
otherwise
D u v u P v Q



   

28. How should we choose D
0
?
•Most frequencies in an image are typically low frequencies,
concentrated around the origin/center of the spectrum.
(1) Take a circle centered at point (N/2, N/2) in the
frequency domain.
(2) Choose its radius r by specifying what percentage
of total power needs to be preserved.
Preserve a percent of the total power,
e.g, a=80%
a 100[ ( , )/ ]
T
u v
P u v P

29. How do we choose D
0
(cont’d)
•Examples:
r=8 (90% power)r=18 (93% power)
r=43 (95%) r=78 (99%) r=152 (99.5%)
original
r: radius

30. Why does ILPF perform smoothing?
*
=
freq. domain spatial domain
sinc
In the spatial domain,
this is equivalent to
convolving with a sync()!

31. How does D
0 control the amount of
smoothing? (cont’d)
•As D
0
increases, the amount of smoothing decreases.
•As D
0
decreases, the amount of smoothing increases.

32. Ringing Effect
•A very sharp cutoff frequency
produce an overshoot of image
features whose frequency is close to
the cutoff frequency (ringing effect).
h=f*g

33. Avoiding the Ringing Effect
•Need to attenuate high frequencies smoothly.
ILPF
In practice
0
1 0
( )
0
if u D
H u
otherwise
 



34. Butterworth LP filter (BLPF)
n=1
n=4n=16
Approaches an ILPF as n increases!
n: order of filter
2
0
2 2
1
( , )
1 [ ( , )/ ]
where ( , )
n
H u v
D u v D
D u v u v


 

35. Butterworth LP filter (BLPF) (cont’d)
n: order of filter
2
0
2 2
1
( , )
1 [ ( , )/ ]
where ( , ) ( /2) ( /2)
n
H u v
D u v D
D u v u P v Q


   
Assuming that we have centered the filter at (P/2, Q/2), as
required, D(u,v) should be computed as:

36. Spatial Representation of BLPFs
n=1 n=2 n=5 n=20
Approaches a sinc( ) function as n increases!

37. Comparison: ILPF and BLPF
ILPF BLPF
D
0
=10, 30,
60, 160,
460
n=2
D
0
=10, 30,
60, 160,
460

38. 2 2
[ ( , )] /2
2 2
2 2
( , )
where ( , )
or ( , ) ( /2) ( /2)
D u v
H u v e
D u v u v
D u v u P v Q


 
   
Gaussian LP filter (GLPF)
2 2
0
0
[ ( , )] /2
By letting
( , )
D u v D
D
H u v e




if centered

39. Spatial Representation of GLPF
2 2
- /2
( )
u
H u Ae


2 2 2
2
( ) 2
x
h x Ae
 



frequency
domain
spatial
domain

40. Example 1: smoothing using GLPF

41. 41
Example 2: smoothing by GLPF
D
0
=100
D
0
=80

42. High Pass (LP) Filters
•Ideal high-pass filter (IHPF)
•Butterworth high-pass filter (BHPF)
•Gaussian high-pass filter (GHPF)
•Difference of Gaussians
•Unsharp Masking and High Boost filtering

43. High-pass filtering
•Preserves high frequencies, attenuates low frequencies.
1D IHPF
2D IHPF
0
1
( )
0
if u D
H u
otherwise



0
2 2
2 2
1 ( , )
( , )
0
where ( , )
( , ) ( / 2) ( / 2)
if D u v D
H u v
otherwise
D u v u v
or D u v u P v Q



 
   
if centered

44. High-Pass filtering (cont’d)

•A high-pass filter can be obtained from a low-pass filter:
( , ) 1 ( , )
HP LP
H u v H u v 
= 1 -

45. Butterworth high pass filter (BHPF)
•In practice, we use filters that attenuate low frequencies
smoother (e.g., Butterworth HP filter) to reduce ringing
effects.
1 -
BLPF BHPF
2
0
1
( , )
1 [ ( , )/ ]
n
H u v
D u v D


2
0
1
( , )
1 [ / ( , )]
n
H u v
D D u v



46. Gaussian HP filter
2 2
0
[ ( , )] /2
( , ) 1
D u v D
H u v e

 
GHPF
BHPF
GLPFGHPF

47. Spatial Representation of High-pass Filters
IHPF BHPF GHPF
( , ) 1 ( , )
HP LP
H u v H u v 
1
( , ) (1 ( , ))
HP LP
h x y F H u v

  
1 1
( , ) (1) ( ( , ))
HP LP
h x y F F H u v
 
  
( , ) ( , ) ( , )
HP LP
h x y x y h u v 
F
-1

48. Comparison: IHPF and BHPF
IHPF
BHPF
D
0
=30,60,160
n=2
D
0
=30,60,160

49. Comparison: BHPF and GHPF
GHPF
BHPF D
0
=30,60,160
n=2
D
0
=30,60,160

50. Example: High-pass Filtering
for Fingerprint Image Enhancement
BHPF
(order 4 with a
cutoff frequency 50)
thresholding

51. Difference of Gaussians (DoG) filter
2 22 2
1 2
/2 /2- -
1 2
( )
with and
u u
H u Ae Be
A B
 
 
 
 
2 2 2 2 2 2
1 2
2 2
1 2
( ) 2 2
x x
h x Ae Be
   
 
 
 
Suppose H(u) is the difference of
two Gaussians:
The corresponding filter in the spatial
domain approximates the Laplacian
(high pass filter).

52. Highboost Filtering (revisited)
( , ) ( , ) ( , )
mask LP
g x y f x y f x y 
Unsharp Masking: k=1
Highboost filtering: k>1:
),(),()1(),( yxfyxfAyxg
HP
( , ) ( , ) ( , )
( , ) ( ( , ) ( , ))
mask
LP
g x y f x y kg x y
f x y k f x y f x y
  
 

53. Highboost Filtering (revisited)
( , ) { ( , ) ( ( , ) ( , ))}
LP
G u v f x y k f x y f x y   F
Highboost Filter
FT
( , ) ( , ) ( ( , ) ( , ))
LP
g x y f x y k f x y f x y  
[1 (1 ( , ))] ( , )
LP
k H u v F u v  
( , ) ( ( , ) ( , ) ( , ))
LP
F u v k F u v H u v F u v  
( , )
HP
H u v
[1 ( , )] ( , )
HP
kH u v F u v

54. Highboost and High-Frequency-Emphasis Filters
1
1+k
k
1
k
1
+k
2
Highboost High-frequency -emphasis

( , ) [1 ( , )] ( , )
HP
G u v kH u v F u v 
1 2
( , ) [ ( , )] ( , )
HP
G u v k k H u v F u v 

55. High-Frequency
Emphasis filtering
using a Gaussian filter
k
1=0.5, k
2=0.75
D
0=40
Example
GHPF
High-freq emphasisHigh-freq emphasis
and histogram equal.

56. Homomorphic filtering
•Removes shading effects due to uneven illumination.
–Enhance high frequencies.
–Attenuate low frequencies but preserve fine detail.

57. Homomorphic Filtering (cont’d)
•Consider the following model of image formation:
•Illumination i(x,y) varies slowly and affects low frequencies
mostly.
•Reflection r(x,y) varies faster and affects high frequencies
mostly.
i(x,y): illumination component
r(x,y): reflection component

58. Homomorphic Filtering (cont’d)
•When applying filtering, it is impossible to manipulate
them separately.
( , ) ( , )* ( , )F u v I u v Ru v
( , ) ( , ) [ ( , )* ( , )] ( , )F u v H u v I u v Ru v H u v
•Low frequencies from i(x,y) and high frequencies
from r(x,y) are convolved (intermixed) together.

59. Can we separate them?
•Consider the ln(f(x,y))
(low and high frequencies have been de-convolved)

60. Steps of Homomorphic Filtering
(1) Take
(2) Apply FT:

or
(3) Apply H(u,v)

61. Steps of Homomorphic Filtering (cont’d)
(4) Take Inverse FT:
or
(5) Take exp( ) or
),(),(),(
00
yxryxiyxg 

62. where c controls the
slope of the function
Example Using High Emphasis Filter
Attenuate the contribution
made by illumination and
amplify the contribution
made by reflectance
Attenuate the contribution
made by illumination and
amplify the contribution
made by reflectance
(high-emphasis filter)
If γ
L
<1 and γ
H
>1 then
the low frequencies
are attenuated and the
high frequencies are
amplified!
2 2
0
([ ( , )] / )
( , ) ( )[1 ]
c D u v D
H L L
H u v e  

   

63. Homomorphic Filtering - Example

64. Homomorphic Filtering - Example
0
0.25
2
1
80
L
H
c
D







65. Band-reject filters
Ideal Butterworth Gaussian
2 2
( , )D D u v u v  

66. Band-reject filters (cont’d)
Ideal Gaussian Butterworth

67. Band-reject filters (cont’d)
•Very effective for removing periodic noise which can arise
from interferences during image acquisition.
noisy image spectrum
additive sinusoidal noise
f(x,y)+sin(x,y)
F{f(x,y)+sin(x,y)}=
F{f(x,y)}+F{sin(x,y)}
Periodic noise shows up
as spikes away from the
origin of the spectrum.

68. Band-reject filters (cont’d)
•Band-reject filters could be very effective in removing periodic
noise.
•Their main weakness is that they also remove additional
frequencies, not necessarily related to noise.
•Notch filters can better address this problem.

69. Band-pass filters
•Perform the opposite operation of band-reject filters:
H
BP(u,v) = 1 - H
BR(u,v)

70. Notch Filters
•A notch filter rejects (or passes) frequencies in a pre-
defined area (neighborhood) about the center of the
frequency domain.
•Notch filters are symmetric about the origin, so the
notches must occur in symmetric pairs (i.e., at (u
0
,v
0
)
and at (-u
0
, -v
0
)).

71. Notch Reject Filters
•An notch-reject filter of radius D
0
with center frequency
(u
0
,v
0
) is given by:


2 2
1 0 0
( , ) ( ) ( )
2 2
P Q
D u v u u v v     
1 0 2 0
0 ( , ) ( , )
( , )
1
if D u v D orD u v D
H u v
otherwise
 


2 2
2 0 0
( , ) ( ) ( )
2 2
P Q
D u v u u v v     
Assuming that we
have centered the
filter as required,
the notches must
specified with
respect to (P/2,Q/2)
(P/2,Q/2)
D
0 D
0

72. Notch Reject Filters (cont’d)
•Notch reject filters can be constructed as products of high-
pass filters whose centers have been translated to the notch
locations.
BHPF

73. Notch Reject Filters (cont’d)
•General form:
•H
k
(u,v) and H
-k
(u,v) are highpass filters whose centers are
at (u
k
,v
k
) and (-u
k
,-v
k
).
•Q is the number of notches.
1
( , ) ( , ) ( , )
Q
NR k k
k
H u v H u v H u v




74. Notch Reject Filters (cont’d)
•General form for a Butterworth notch reject filter of order
n with three notch pairs:
•The constant D
0k is the same for each pair of notches, but
can be different for different pairs.
3
2 2
1 0 0
1 1
( , ) [ ][ ]
1 [ / ( , )] 1 [ / ( , )]
NR n n
k k k k k
H u v
D D u v D D u v
 

 

2 2
( , ) ( ) ( )
2 2
k k k
N N
D u v u u v v     
2 2
( , ) ( ) ( )
2 2
k k k
N N
D u v u u v v

     

75. Notch Reject Filters - Example
spectrum
notch filter, D
0
=2

76. Notch Pass Filters
•A notch pass filter can be obtained as follows:
( , ) 1 ( , )
NP NR
H u v H u v 
notch pass

77. Problem #1

78. Problem #2
Low-pass

79. Problem #3

80. Problem #4

81. Quiz #5
•When: Monday, November 8, 2021 @ 1pm
•What: Frequency Filtering
•Duration: 10 minutes