Fundamentals of Image Processing IMA – EIT VCC
BIMA – Mid term exam
7 December 2020 – 13:15
Notation of each exercise may be modified. Total is 20 points.
No document allowed. Your mobile should be off and put away. Calculator allowed. Respect of sanitary rules
Duration: 1 hour 30
Exercise 1 Histogram (5 points)
Let an image be quantified on 16 grayscales and having the following histogram:
k 0 1 2 3 4 5 6 7 8 9 10 11–15
H(k) 113 174 213 129 79 117 102 65 14 11 7 0
1. Determine the cumulative histogram Hc.
2. What is the dynamics of this image? Suppose that the image is squared, what are their dimensions? Rounding to the greatest integer lower or equal, give the median gray level value, the average gray level value.
3. Apply an histogram stretching using the greatest dynamics allowed by a 16-grayscale coding. Give the stretched histogram.
4. Apply an histogram equalization and give the new histogram. We remind the equalization formulae: k′ = ⌊ L−1 Hc(k)⌋.
N×M
5. Compare and discuss results between stretched and equalized histograms. Which of these trans-
formations are linear with respect to the gray level value? Justify your assertions.
6. Propose a non linear transformation on gray level values in order to enhance the image contrast.
Answer of exercise 1
1. Hc =[113,287,500,629,708,825,927,992,1006,1017,1024,1024,1024,1024,1024,1024]
2. Dynamics: 10
Size: N × M = 1024 so N = M = 32
Median: ksuchasHc[k]N×M/2=512. Sok=2
Average: E(k) = k k×H[k]/1024 = (0×113+1×174+2×213+3×129+)…)/1024 ≈ 3.16 = 3.
3. k′ =⌊(L−1)×(k−kmin)/(kmax−kmin)⌋. L=16,kmin =0,kmax =10,sok′ =⌊1.5×k⌋,New histogram:
k′ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 He(k′) 113 174 0 213 129 0 79 117 0 102 65 0 14 11 0 7
4. k′ = ⌊1.5Hc(k)⌋ New histogram:
k′ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
He(k′) 0 113 0 0 174 0 0 213 0 129 79 0 117 102 90 7
5. The two histograms are quite different: the gray levels are distributed differently and, in the case of equalization, the number of gray levels decreases. Both transformations increase the dynamics of the image, Equalization increases the contrast by reducing the number of pixels. of classes. The first transformation is linear, but not the second, because HI+J ̸= HI + HJ .
Sorbonne Universit ́e 1 Master 1 in Computer Science
Fundamentals of Image Processing IMA – EIT VCC 6. The image is too dark, we can apply the logarithmic transformation.
Exercise 2 Continuous Fourier transform (5 points)
Let’s remind the definition of the continuous Fourier transform of a continuous signal x:
f → FT(x)(f) = X(f) = and the inverse Fourier transform:
x(t)e−2iπftdt
t → FT−1(X)(t) = x(t) =
In appendix are reported essentials properties of Fourier transform as well as Fourier transform of usual
R
functions.
1. The convolution theorem applies with the inverse Fourier transform.
Show that: FT−1(x ⋆ y) = FT−1(x) × FT−1(y). One remind that x ⋆ y(t) = Indication: rearrange integrals and apply a change of variable.
2. Let x(t) = 1 + 2 sin(2πf0t) + 21 sin(6πf0t), t ∈ R be a continuous signal.
Derive its Fourier transform and draw its module spectrum. Indicate frequencies on the axis or
frequencies
Is this signal band-limited? If yes, what is the maximal frequency?
By justifying your answer: which space (temporal or frequency) is best suited to represent the x signal?
1 if|t|≤L2
3. Let’s consider the Gate function of length L defined by: RectL(t) = 0 otherwise . Derive its
Fourier transform.
4. Let xL be the signal x windowed on a length L = 2T0, T0 = 1 , i.e. we have xL(t) = x(t) Rect2T0 (x).
4.
f0
Derive its Fourier transform. Without drawing it, describe the look of the module of its spectrum.
Is this signal band-limited? If yes, what is the maximum frequency?
Answer of exercise 2
1. This is the same proof as the one seen in tutorial work.
2. We have sin(x) = eiπx−e−iπx . X(f) = δ(f)+(δ(f −f0)−δ(f +f0))/i+(δ(f −3f0)−δ(f +3f0))/4i.
R
X(f)e2iπftdf
R
x(u)y(t − u)du.
2i
Plot of the spectrum module: one Dirac located at f = 0, two Dirac at f = ±f0, two Dirac at f = ±3f0.
The signal is band-limited. The maximum frequency is 3f0. The x signal is difficult to draw (addition of 4 sinus functions) while the spectrum is easy to draw (5 Dirac)! So the frequency domain is more appropriate here, the signal is described with 3 frequencies and 3 amplitudes.
3. We can do the direct derivation or simply remark that RectL(t) = Rect(t/L) and apply the con- traction property of Fourier transform.
Sorbonne Universit ́e
2 Master 1 in Computer Science
XL = =
=
X ⋆ FT(Rect2T0 ) f→δ(f)+(δ(f−f0)−δ(f+f0))/i+(δ(f−3f0)−δ(f+3f0))/4i⋆ f → 2T0 sinc(2T0πf)
2T0(sinc(2T0πf) + 1i (sinc(2T0π(f − f0)) − sinc(2T0π(f + f0)))
+ 1 (sinc(2T0π(f − 3f0)) − sinc(2T0π(f + 3f0)))) 4i
Fundamentals of Image Processing IMA – EIT VCC
We draw a sinc centered at the origin, two sinc centered at ±f0 and two centered at ±3f0. The
zeros of the sinc are at a distance k , k ∈ Z∗ from the center of the sinc. The signal is not in band 2T0
limited since the support of its spectrum is not limited.
Exercise 3 Interpolation (7 points)
1−t, si|t|≤1
1. Let Tri be the function defined by: Tri(t) = .
0, sinon
Assuming that Tri = Rect1 ⋆ Rect1 , derive the Fourier transform of Tri.
2. Draw the graph of Tri and its spectrum. Clearly indicate the size of the support of Tri, and the frequencies that cancel out the spectrum.
3. Let us consider the windowing function w = Tri ⋆ Rect1 . Derive its Fourier transform.
4. Assume that the support of w is [−3, 3], what is the support of function wL(t) = w(3t)? Determine
its Fourier transform.
5. Consider signal x from exercise 2. We wish to sample x to obtain a signal xe.
What should be the sampling frequency fe if we want to reconstruct the original signal x without loss?
6. In the following, we consider any signal x . Let’s remind that xe(t) = x(t) Te (t) with Te = 1 . fe
Derive Xe, the spectrum of xe.
7. If we use wL as the transfer function of a low-pass filter, is it possible to recover the spectrum X
of signal x without loss? In this case, what should the L length be?
8. Interpolation consists in reconstructing the original signal x from its samples x(kTe) using the filter
whose transfer function is wL to get a “reconstructed” signal xr . Express xr as a function of samples x(kTe), k ∈ Z.
Help: determine the inverse Fourier transform of Xe (f )wL (f ) and admit that inverse Fourier transform of wL is identical to its Fourier transform.
Answer of exercise 3
1. We know that FT(Rect)(f) = sinc(πf) therefore by the convolution theorem, FT(Tri)(f) = FT(Rect)(f) × FT(Rect)(f) = sinc2(πf).
2. Graph of Tri: it is a triangle of base [−1; 1] and height of 1. The graph of the spectrum looks like that of | sinc | smoothed at intersections with the abscissa. The zeros of the spectrum are those of sinc(πf): ±k,k∈Z∗.
22L
3. W(f)=FT(Tri)(f)×FT(Rect)(f)=sinc3(πf).
4. Support is [−L, L]. Indeed, we have: |3t| < 3 ⇒ t < L. By applying the contraction property of
22L22 the Fourier transform: WL(f) = L3 W(L3 f)
5. The maximum frequency of x is 3f0, so it is necessary that fe ≥ 6f0 (Shannon). 6.
Xe(f) = feX⋆ fe(f)=feX⋆δ(f−kfe) k∈Z
= fX⋆δ(f−kf)=fX(f−kf) eeee
kk
Sorbonne Universit ́e
3 Master 1 in Computer Science
Fundamentals of Image Processing IMA - EIT VCC
7. Yes it is possible if the support of the spectrum of X remains in the support of wL. This support
being [−L2 , L2 ], one can take L = fe.
8. We follow the help given in the question:
xr(t)
Exercise 4
= FT−1(Xe(f)wL(f))(t) = L3 xe(t) ⋆ WL(L3 t) = L3(x(t)δ(t−kTe))⋆WL(L3t)
k
= Lx(kTe)WL(L(t−kTe)) 33
k
= L x(kTe) sinc3(t − kTe))
3
k
Filtrage spatial discret (3 points)
1. Let T be a discrete LTI operator. What properties are verified by T? Let x be a signal, express T[x] from the impulse response of T.
2. We want apply an anti-aliasing filter before sub-sample a 1-D signal.
(a) What are the frequency characteristics of an anti-aliasing filter?
(b) Consider the three following anti-aliasing filters having as transfer function: Gate function,
Butterworth function (B (f) = 1 ), Gaussian function. n,c 1+(f /c)2n
Which of these filters are ideal? How to choose their cut-off frequency?
Answer of exercise 4
1. linear Time Invariant: filter T is linear and invariant by time translation. It writes as the convo- lution between the signal and the filter impulse response: T (x) = x ⋆ h with h = T [δ].
2. (a) This is a low-pass filter that cancels out frequencies beyond the half of 1/2.
(b) Only the Gate is an ideal filter. The Butterworth is the approximation of an ideal filter is a
”smooth” door. Choice of cut-off frequencies: • Gate: fc =1/4⇒L=1/2.
• Butterworth: fc = c = 1/4. • Gaussian: fc = 3σ = 1/4.
Appendix
Properties of Fourier transform
linearity translation contraction convolution product
x(t) x(t) + λy(t)
x(t − t0) x(αt)
x ⋆ y(t) x(t) × y(t)
X (f )
X(f) + λY (f) X(f) e−2iπft0
1 X(f ) |α| α
X(f) × Y (f) X ⋆ Y (f)
Sorbonne Universit ́e
4 Master 1 in Computer Science
Fundamentals of Image Processing
Properties of Dirac distribution
• +∞ δ(t)dt = 1. −∞
• x(t)δ(t − t0) = x(t0)δ(t − t0)
• x⋆δ(t−t0)=x(t−t0)
• scaling property : |α| · δ(αt) = δ(t)
• TF [δ(t − t0)] = e−2iπft0 et TF e2iπf0t = δ(f − f0)
Fourier transform of usual functions
e2iπf0t δ(f − f0)
IMA - EIT VCC
Signal FT
1 δ(f)δ(t)1
Signal FT δ(t − t0) e−2iπft0
+∞
T(t)= δ(t−kT)
k=−∞
+∞
T1 1(f)=T1δ(f−Tk)
T k=−∞
Sorbonne Universit ́e
5
Master 1 in Computer Science