Image Processing and Computer

Vision

Assignment T1

Jan Hendrik Dithmar

2031259

Group T1: Tue, 14-16 (Sebastian Zimmer)

Assignment T1  Dithmar (2031259)

1.1 Signal-to-Noise Ratio

a. Let’s see, if SNR(f, g) = 0:

SNR(f, g) = 0
10 · log_{10} \frac{σ^{2}(g)}{σ^{2}(n)} = 0
log_{10} \frac{σ^{2}(g)}{σ^{2}(n)} = 0
log_{10} σ^{2}(g) − log_{10} σ^{2}(n) = 0
log_{10} σ^{2}(g) = log_{10} σ^{2}(n)
σ^{2}(g) = σ^{2}(n)

So this is the case, if the noise doesn’t affect the original image. b. For the sake of readability, I define a function as follows:

short(x, y) = ∑_{i=1}^{M} ∑_{j=1}^{N}(x − y)^{2}

SNR(u, g) = SNR(f, g) + 10dB
⇔ 10 · log_{10} \frac{\frac{1}{MN} · short(g_{i,j}, μ)}{\frac{1}{MN} · short(u_{i,j}, g_{i,j})} = 10 · log_{10} \frac{\frac{1}{MN} · short(g_{i,j}, μ)}{\frac{1}{MN} · short(f_{i,j}, g_{i,j})} + 10

⇔ log_{10} \frac{short(g_{i,j}, μ)}{short(u_{i,j}, g_{i,j})}

− log_{10} \frac{short(g_{i,j}, μ)}{short(f_{i,j}, g_{i,j})} = 1
⇔ log_{10} \frac{\frac{∑_{i=1}^{M} ∑_{j=1}^{N}(g_{i,j})^{2}}{∑_{i=1}^{M} ∑_{j=1}^{N}(u_{i,j}−g_{i,j})^{2}}}{\frac{∑_{i=1}^{M} ∑_{j=1}^{N}(g_{i,j})^{2}}{∑_{i=1}^{M} ∑_{j=1}^{N}(f_{i,j}−g_{i,j})^{2}}} = 1
⇔ log_{10} \frac{∑_{i=1}^{M} ∑_{j=1}^{N}(f_{i,j} − g_{i,j})^{2}}{∑_{i=1}^{M} ∑_{j=1}^{N}(u_{i,j} − g_{i,j})^{2}} = 1
⇔ \frac{∑_{i=1}^{M} ∑_{j=1}^{N}(f_{i,j} − g_{i,j})^{2}}{∑_{i=1}^{M} ∑_{j=1}^{N}(u_{i,j} − g_{i,j})^{2}} = 10

⇔ ∑_{i=1}^{M} ∑_{j=1}^{N}(f_{i,j} − g_{i,j})^{2} = 10 · ∑_{i=1}^{M} ∑_{j=1}^{N}(u_{i,j} − g_{i,j})^{2}

⇔ \frac{1}{MN} · ∑_{i=1}^{M} ∑_{j=1}^{N}(f_{i,j} − g_{i,j})^{2} = 10 · \frac{1}{MN} · ∑_{i=1}^{M} ∑_{j=1}^{N}(u_{i,j} − g_{i,j})^{2}
⇔ σ^{2}(n) = 10 · σ^{2}(n′)

where σ^{2}(n′) is the noise variance of the filtered image. Interpretation: As one can see, playing with the SNR can have a huge impact on the noise variance. The noise variance of the filtered image is 10 times higher than the noise variance of the original image.

c. • If the initial image is constant, the variance is also constant. For example:

g = 5 ⇒ σ^{2}(g) = \frac{1}{MN} ∑_{i=1}^{M} ∑_{j=1}^{N}(g_{i,j} − μ)^{2}

⇔^{μ=0} σ^{2}(g) = \frac{1}{MN} · 25 · M · N
σ^{2}(g) = 25 = 5^{2} = g^{2}

This means that the resulting image is the noise function with some additional weighting which is the constant image.

• Let’s try to calculate SNR(g, g):

SNR(g, g) = 10 · log_{10} \frac{\frac{1}{MN} · ∑_{i=1}^{M} ∑_{j=1}^{N}(g_{i,j} − μ)^{2}}{\underbrace{\frac{1}{MN} · ∑_{i=1}^{M} ∑_{j=1}^{N}(g_{i,j} − g_{i,j})^{2}}_{=0}}

One cannot calculate this, because of the division by 0. Since this SNR is not defined, one can interpret the result as follows: Measuring how much your original image is deteriorated in comparison to your original image doesn’t make sense, because you compare an image with itself.

1.2 Discrete vs. Continuous Convolution

a.

f_{i} = \{ \begin{matrix}\frac{1}{2} & (i ∈ \{0, 1\}) \\ 0 & (else) \end{matrix}
(f ∗ f)_{k} = ∑_{i} f_{k−i} · f_{i} = ∑_{i=0}^{1} f_{k−i} · f_{i}
= \frac{1}{2} · ∑_{i=0}^{1} f_{k−i} = \frac{1}{2} · (f_{k} + f_{k−1}) = g
(g ∗ f)_{k} = ∑_{i} g_{k−i} · f_{i} = ∑_{i=0}^{1} g_{k−i} · f_{i}
= \frac{1}{2} · ∑_{i=0}^{1} g_{k−i} = \frac{1}{2} · ∑_{i=0}^{1} (\frac{1}{2} · (f_{k} + f_{k−1}))_{k−i}
= \frac{1}{4} · ((f_{k} + f_{k−1}) + (f_{k−1} + f_{k−2})) = h
(h ∗ f)_{k} = ∑_{i} h_{k−i} · f_{i} = ∑_{i=0}^{1} h_{k−i} · f_{i}
= \frac{1}{2} ∑_{i=0}^{1} h_{k−i} = \frac{1}{2} · \frac{1}{4} · ∑_{i=0}^{1}((f_{k} + f_{k−1}) + (f_{k−1} + f_{k−2}))_{k−i}
= \frac{1}{8}[((f_{k} + f_{k−1}) + (f_{k−1} + f_{k−2})) + ((f_{k−1} + f_{k−2}) + (f_{k−2} + f_{k−3}))]
= \frac{1}{8}((f_{k} + f_{k−1}) + 2 · (f_{k−1} + f_{k−2}) + (f_{k−2} + f_{k−3})) = l
(l ∗ f)_{k} = ∑_{i} l_{k−i} · f_{i} = \frac{1}{2} · ∑_{i=0}^{1} l_{k−i}
= \frac{1}{2} · \frac{1}{8} · ∑_{i=0}^{1}((f_{k} + f_{k−1}) + 2 · (f_{k−1} + f_{k−2}) + (f_{k−2} + f_{k−3}))_{k−i}
= \frac{1}{16} · [(f_{k} + f_{k−1}) + 2 · (f_{k−1} + f_{k−2}) + (f_{k−2} + f_{k−3})
+(f_{k−1} + f_{k−2}) + 2 · (f_{k−2} + f_{k−3}) + (f_{k−3} + f_{k−4})]
= \frac{1}{16} · [(f_{k} + f_{k−1}) + 3 · (f_{k−1} + fk − 2)
+3 · (f_{k−2} + f_{k−3}) + (f_{k−3} + f_{k−4})]

b. For this exercise, I have a strong evidence that my solution is not correct. Nevertheless I want to put it here because of a small chance that it’s right anyway ;-)

(f ∗ f)(x) = ∫_{−∞}^{∞} f(x − y) · f(y)dy
= ∫_{−∞}^{−2} f(x − y) · f(y)dy + ∫_{−2}^{0} f(x − y) · f(y)dy
+ ∫_{0}^{2} f(x − y) · f(y)dy + ∫_{2}^{∞} f(x − y) · f(y)dy
= ∫_{−2}^{0} f(x − y) · f(y)dy + ∫_{0}^{2} f(x − y) · f(y)dy
= ∫_{−2}^{−1} f(x − y) · f(y)dy + ∫_{−1}^{1} f(x − y) · f(y)dy + ∫_{1}^{2} f(x − y) · f(y)dy
= ∫_{−1}^{1} f(x − y) · f(y)dy = \frac{1}{2} · ∫_{−1}^{1} f(x − y)dy
= \frac{1}{2} · ∫_{x−1}^{x+1} \frac{1}{2}dy = \frac{1}{2} · [\frac{1}{2}y]_{x−1}^{x+1}
= \frac{1}{2} · (\frac{1}{2} · (x + 1) − \frac{1}{2} · (x − 1))
= \frac{1}{2} · (\frac{1}{2}x + \frac{1}{2} − \frac{1}{2}x + \frac{1}{2})
= \frac{1}{2}

This result is why I’m not sure whether it is right or wrong. If you would repeat this convolution step 3 times as the exercise requests it you would get the same result again.

1.3 Properties of the Discrete Convolution

a. To show: (α · f + β · g) ∗ w = α · (f ∗ w) + β · (g ∗ w) ∀α, β ∈ ℝ

((α · f + β · g) ∗ w)_{i} = ∑_{k=−∞}^{∞}(α · f + β · g)_{i−k} · w_{k}
= ∑_{k=−∞}^{∞}(α · f · w_{2k−i} + β · g · w_{2k−i})_{i−k}
= ∑_{k=−∞}^{∞}((α · f · w_{2k−i})_{i−k} + (β · g · w_{2k−i})_{i−k})
= ∑_{k=−∞}^{∞}(α · (f · w_{2k−i})_{i−k} + β · (g · w_{2k−i})_{i−k})
= ∑_{k=−∞}^{∞} α · (f · w_{2k−i})_{i−k} + ∑_{k=−∞}^{∞} β · (g · w_{2k−i})_{i−k}
= α · ∑_{k=−∞}^{∞} f_{i−k} · w_{k} + β · ∑_{k=−∞}^{∞} g_{i−k} · w_{k}
= α · (f ∗ w)_{i} + β · (g ∗ w)_{i}

b. To show: f ∗ w = w ∗ f

(f ∗ w)_{i} = ∑_{k=−∞}^{∞} f_{i−k} · w_{k} = ∑_{k=−∞}^{∞} w_{k} · f_{i−k}
= ∑_{k=−∞}^{∞} w_{k−i} · f_{−k} = ∑_{k=∞}^{−∞} w_{i−k} · f_{k}
=^{(∗)} ∑_{k=−∞}^{∞} w_{i−k} · f_{k}
= (w ∗ f)_{i}

where (∗) is because of the symmetry of the sum. c. Claim:

e = \{ \begin{matrix}1 & x = 0 \\ 0 & x ≠ 0 \end{matrix}

Proof:

(f ∗ e)_{i} = ∑_{k=−∞}^{∞} f_{i−k} · e_{k} = \underbrace{∑_{−∞}^{−1} f_{i−k} · e_{k}}_{=0} +f_{i} · 1 + \underbrace{∑_{1}^{∞} f_{i−k} · e_{k}}_{=0} = f_{i}

1.4 Continous Fourier Transform

a. We have the 1-D hat function:

f(x) = \{ \begin{matrix}\frac{2−|x|}{4} & (−2 ≤ x ≤ 2) \\ 0 & (else) \end{matrix}

To make life easier, I re-define the function f as follows:

f(x) = \{ \begin{matrix}\frac{2+x}{4} & (−2 ≤ x < 0) \\ \frac{2−x}{4} & (0 ≤ x ≤ 2) \\ 0 & (else) \end{matrix}

Let’s compute the Fourier transform:

f̂(u) = F[f](u) = ∫_{−∞}^{∞} f(x) · e^{−i2πux}dx
= ∫_{−2}^{2} f(x) · e^{−i2πux}dx
= ∫_{−2}^{0} f(x) · e^{−i2πux}dx + ∫_{0}^{2} f(x) · e^{−i2πux}dx
= ∫_{−2}^{0} \frac{2 + x}{4} · e^{−i2πux}dx + ∫_{0}^{2} \frac{2 − x}{4} · e^{−i2πux}dx
= [\frac{2 + x}{4} · (−\frac{1}{i2πu}) · e^{−i2πux}]_{−2}^{0} − ∫_{−2}^{0} \frac{1}{4} · (−\frac{1}{i2πu}) · e^{−i2πux}dx

+ [\frac{2 − x}{4} · (−\frac{1}{i2πu}) · e^{−i2πux}]_{0}^{2} − ∫_{0}^{2} (−\frac{1}{4}) · (−\frac{1}{i2πu}) · e^{−i2πux}dx

= \frac{1}{2} · (−\frac{1}{i2πu}) · e^{0} − \frac{1}{4} · (−\frac{1}{i2πu}) · [−\frac{1}{i2πu} · e^{−i2πux}]_{−2}^{0}

+ (0 − \frac{1}{2} · (−\frac{1}{i2πu}) · e^{0}) − (−\frac{1}{4}) · (−\frac{1}{i2πu}) · [−\frac{1}{i2πu} · e^{−i2πux}]_{0}^{2}

= \frac{1}{2} · (−\frac{1}{i2πu}) − \frac{1}{4} · (−\frac{1}{i2πu}) · [(−\frac{1}{i2πu}) − (−\frac{1}{i2πu}) · e^{−i2πu(−2)}]

−\frac{1}{2} · (−\frac{1}{i2πu}) − (−\frac{1}{4}) · (−\frac{1}{−i2πu}) · [−\frac{1}{i2πu} · e^{−i2πu·2} − (−\frac{1}{i2πu})]

= −\frac{1}{2} · \frac{1}{i2πu} − \frac{1}{4} · (\frac{1}{i2πu})^{2} − \frac{1}{4} · (\frac{1}{i2πu})^{2} · e^{−i2πu·(−2)}

+\frac{1}{2} · \frac{1}{i2πu} + \frac{1}{4} · (\frac{1}{i2πu})^{2} · e^{−i2πu·2} − \frac{1}{4} · (\frac{1}{i2πu})^{2}

= −\frac{1}{2} · (\frac{1}{i2πu})^{2} + \frac{1}{4} · (\frac{1}{i2πu})^{2} · (e^{−i2πu·2} − e^{i2πu·2})
= −\frac{1}{2} · \frac{1}{i^{2}4π^{2}u^{2}} + \frac{1}{4} · \frac{1}{i^{2}4π^{2}u^{2}} · e^{4} (e^{−iπu} − e^{iπu})
= −\frac{1}{2} · \frac{1}{i^{2}4π^{2}u^{2}} + \frac{1}{4} · \frac{1}{i^{2}4π^{2}u^{2}} · e^{4} · (−2i sin(πu))
= −\frac{1}{2} · \frac{1}{i^{2}4π^{2}u^{2}} + \frac{1}{4} · \frac{1}{−i2π^{2}u^{2}} · e^{4} · sin(πu)
= −\frac{1}{8i^{2}π^{2}u^{2}} − \frac{e^{4} · sin(πu)}{8iπ^{2}u^{2}}
= \frac{−1 − e^{4} · sin(πu) · i}{8i^{2}π^{2}u^{2}}
= −\frac{1}{8i^{2}π^{2}u^{2}} · (1 + e^{4} · sin(πu) · i)
=^{i^{2}=−1} \frac{1}{8π^{2}u^{2}} · (1 + e^{4} · sin(πu) · i)

b.

|f̂(u)| = |\frac{1}{8π^{2}u^{2}} | · |1 + e^{4} · sin(πu) · i|
= \frac{1}{8π^{2}u^{2}} + |\frac{e^{4} · sin(πu) · i}{8π^{2}u^{2}} |
= \frac{1}{8π^{2}u^{2}} + |\frac{e^{4} · i}{8πu}| · |\frac{sin(πu)}{πu}|
= \frac{1}{8π^{2}u^{2}} + |\frac{e^{4} · i}{8πu}| · |sinc(πu)|