Description
Task 1: Noise Reduction
1. Consider the signals
y(t) = sin(2π50t) + sin(2π120t) and yϵ(t) = y(t) + ϵ
defined in the unit time domain T = [0, 1]. The ϵ represents some random noise added to the
original signal. As it is shown in Figure 1, discretize the domain T in n evenly spaced subintervals
and visualize both functions.
Figure 1: Noisy and Clean Signals
2. Compute the Fast Fourier Transform of the discretized function yϵ(t),
yϵ(t)
F(·)
−−−→ F{y(t)ϵ}(ω) := z
3. Compute the power density spectrum (PSD) of z by multiplying it element-wise by its conjugate,
and dividing it by the number of points n then visualize the PSD, as in Figure 2.
z
PSD
−−−→
zz¯
n
Figure 2: Power Density Spectrum
4. Based on your observations set a PDS-threshold τ to keep just the most representative frequencies,
i.e. just keep the elements in the PDS that are less than threshold τ
indices = {i | z[i] > PSD-threshold}
2
Figure 3: Signal Filtering
5. Return to the discretized function ˆyϵ(ω), and using the indices as a filter set to zero the elements
whose index is not in your set of indices, and compute the Inverse Fast Fourier Transform, which is
your reconstructed function.
z[indices] F
−1{·} −−−−−→ F −1
{z[indices]}
Figure 4: Noise Reduction
If done correct, then your signal with no noise should accurately resemble the original y(t) function.
3
Task 2: Image Compression
Choose an image to play with. Figure 5 shows the picture for this toy example.
Figure 5: Lion Waiting In Namibia, taken from Wikipedia
1. Visualize your image, and convert it from RGB format to a grayscale format, i.e. the dimensions of
your original picture (thinking of it as a three dimensional array) will be reduced one dimension
Aw×h×c → Aw×h
where w, h, and c stand for weight, height and channel, respectively.
Figure 6: The Lion in Grayscale Format
2. Compute the Fast Fourier Transform in two dimensions (since you are working now with a two
dimensional array) to get the spectrum of your image, then shift the zero-frequency to the center of
that spectrum
Aw×h
F
2
(·)
−−−→ F2
(A)w×h
4
3. Compute the magnitude (a.k.a. module, absolute value, etc) of the shifted spectrum to work with
an homogeneous spectrum
F
2
(A)w×h
| · |
−−→
F
2
(A)
w×h
4. Compute the (natural) logarithm adding 1 to the argument of your spectrum (to avoid values close
to 0 that could make the operation to blow up)
F
2
(A)
w×h
log( · )
−−−−→ log(
F
2
(A)
+ 1)w×h
visualize the spectrum.
Figure 7: Image Spectrum
5. Reduce the dimension of your original shifted matrix in one array of one single dimension with the
length being the product of the weight and the height of F
2
(A)w×h, i.e. reshape it
F
2
(A)w×h
reshape −−−−−→ F2
(A)wh×1
6. Compute the magnitude of your reshaped array
F
2
(A)wh×1
| · |
−−→
F
2
(A)
wh×1
:= Af
7. Sort your array
F
2
(A)
wh×1
sort −−→ sort(
F
2
(A)
)wh×1 := a ∈ R
wh
8. Set a value for τ , it should be sufficiently small, i.e. τ ≪ 1, multiply it by the length of your array to
keep the values that are useful for the reconstruction, then floor the computation (i.e. approximate
it to the smaller integer)
(1 − τ )wh ⌊ · ⌋ −−−→ ⌊(1 − τ )wh⌋ := b ∈ N
9. Define your threshold as that number whose index is given by b in your sorted array a,
threshold = a[b] := c ∈ R
5
10. Zero out all small coefficients by keeping just the indices of the elements of
F
2
(A)
wh×1
that are
above the threshold
indices = {(i, j) | Af (i, j) > threshold}
Figure 8: Filtered Spectrum
11. Finally return to your initial matrix F
2
(A)w×h and select those indices and apply the shifting,
absolute value and the logarithm as before and display it
log(
F
2
(A)
+ 1)w×h[indices]
if everything was done correctly, and the selected threshold was appropriate, then you should see
your reconstructed image.
Figure 9: Reconstruction
6
