Computer Graphics I

Assignment 5

Group III (Yavor Kaloyanov)

Jan Hendrik Dithmar

2031259

Pascal Gwosdek

2505221

Assignment 5  Dithmar (2031259), Gwosdek (2505221)

5.1 Fourier Transformation

Let

B′(k) = ∫_{−∞}^{∞} B(x) · e^{−2πikx}dx.

Then:

B′(k) = ∫_{−∞}^{∞} B(x) · e^{−2πikx}dx

= ∫_{−∞}^{−1} 0dx + ∫_{−1}^{1} e^{−2πikx}dx + ∫_{1}^{∞} 0dx

= ∫_{−1}^{1} e^{−2πikx}dx

= [\frac{e^{−2πikx}}{−2πik} ]_{−1}^{1}

= \frac{e^{−2πik} − e^{2πik}}{−2πik}

= \frac{cos(−2πk) + i · sin(−2πk) − cos(2πk) − i · sin(2πk)}{−2πik}

= \frac{i(sin(−2πk) − sin(2πk))}{−2πik}

= \frac{sin(2πk) − sin(−2πk)}{2πk}

= \frac{2 · sin(2πk)}{2πk}

= \frac{sin(2πk)}{πk}

= 2 · sinc(2k) ■

5.2 Sampling Theory

a. Yes, this is possible. Let us sample a signal f with the sampling distance T, which is the product of f with the delta comb δ equally spaced with distance T. Then, we convolve the representation F of f in the fourier space with Δ, a delta comb function with peak distances of \frac{1}{T}.

Thus, the sampled signal F_{s} in fourier domain is \frac{1}{T} -periodic. This means that the whole signal and its frequencies are represented in the interval [−\frac{1}{2T} , \frac{1}{2T} ).

As long as the Nyquist property is satisfied, there are no overlapping frequency bands from different periods and hence a point in this interval has unique correspondance to one distinct band, which unambiguously defines the frequency of each occuring signal, so misinterpretations of frequencies are impossible.

The signal can be completely reconstructed.

b. The reconstruction of f or F in spatial and fourier domain, respectively, has to be performed as follows:

• Image space: f_{s}(x) must be convolved with the sinc function sinc(T x):

f(x) = f_{s}(x) ⊗ sinc(T x)

• Fourier space: F needs to be multiplied with the box function

B(x) = \begin{cases}1 & if − \frac{1}{2T} ⩽ x < \frac{1}{2T} \\ 0 & else \end{cases} :

F (x) = F_{s}(x) · B(x)

5.3 Antialiasing

a. Sampling The sampling of a continuous signal can be performed as follows:

• In the spatial domain, i.e. in signal space, the sampled function f_{s}(x) is calculated out of the continuous function f(x) by multiplication with the delta comb function δ(x):

f_{s}(x) = f(x) · δ(x)

• In fourier domain, this operation corresponds to a convolution of the fourier-transformed delta comb δ, which yields a delta comb Δ again, with the representation F (x) of the function f(x) in fourier space:

F_{s}(x) = F (x) ⊗ Δ(x)

Assume the distance between two adjacent peaks of the delta comb δ is x, then Δ has its peaks spaced by \frac{1}{x}.

Aliasing

• In signal space, aliasing acts as a lowpass filter, which means that periodic signal segments with high frequencies are misinterpreted to be lower frequential. This is due to the fact, that only every n-th period of the signal is found and those in between are lost.

• As mentioned above, sampling means a convolution in fourier space with a delta comb, which results in distinct (mirrored) copies of the convolved function shifted to the positions of the particular peaks. Are these images overlapping each other, a value within this overlapping region can no longer be assigned to one or another peak (representing frequency bands), which is perceived as aliasing.

b. In general, undersampled signals can not be restored uniquely. However, in this case we know that the signal is slightly undersampled, i.e. for the sampling distance d it holds that d_{max} ⩽ d < 1.25·d_{max}, where d_{max} denotes the maximum sampling distance allowed by the Nyquist theorem.

d d′

Assume, d is the current sampling distance, as depicted in the exercise description. Obviously, the sampled point (•) in the figure above is misinterpreted to be in the falling edge of the same period as the predecessor, instead of being in the rising edge of the following period.

Let p′ be the period of the malinterpreted signal (dashed line), then this can be scaled to p, the period of the original signal. Here, we search for the respective point in the bad signal (∘), denote its distance to the predecessing sampling point with d′ and use the proportion rule to yield p:

p = p′ · \frac{d}{d′}

d′ is given by

d′ = d + 2 · (\frac{p′}{2} − d) = p′ − d,

hence

p = p′ · \frac{d}{p′ − d}.

5.4 Triangle Filter

f′(x) = ∑_{k=−∞}^{∞} f_{s}(k) · T (x − k)

= ( ∑_{k=−∞}^{⌊x⌋−1} f_{s}(k) · T (\underbrace{x − k}_{>1})) + ( ∑_{k=⌊x⌋}^{⌈x⌉} f_{s}(k) · T (x − k))

+ ( ∑_{k=⌈x⌉+1}^{∞} f_{s}(k) · T (\underbrace{x − k}_{<1}))

= 0 + ( ∑_{k=⌊x⌋}^{⌈x⌉} f_{s}(k) · T (x − k)) + 0

= \begin{cases}f_{s}(x) · T (0) \\ f_{s}(⌊x⌋) · T (x − ⌊x⌋) + f_{s}(⌈x⌉) · T (x − ⌈x⌉) \end{cases}  \begin{matrix}x = ⌊x⌋ \\ else \end{matrix}

= \begin{cases}f_{s}(x) · 1 \\ f_{s}(⌊x⌋) · T (x − ⌊x⌋) + f_{s}(⌈x⌉) · T (x − ⌈x⌉) \end{cases}  \begin{matrix}x = ⌊x⌋ \\ else \end{matrix}

= \begin{cases}f_{s}(x) \\ f_{s}(⌊x⌋) · T (x − ⌊x⌋) + f_{s}(⌈x⌉) · T (x − ⌈x⌉) \end{cases}  \begin{matrix}x = ⌊x⌋ \\ else \end{matrix}

= \begin{cases}f_{s}(x) \\ f_{s}(⌊x⌋) · (−(x − ⌊x⌋) + 1) + f_{s}(⌈x⌉) · ((x − ⌈x⌉) + 1) \end{cases}  \begin{matrix}x = ⌊x⌋ \\ else \end{matrix}

= \begin{cases}f_{s}(x) \\ f_{s}(⌊x⌋) · (−x + ⌊x⌋ + 1) + f_{s}(⌈x⌉) · ((x − (⌊x⌋ + 1)) + 1) \end{cases}  \begin{matrix}x = ⌊x⌋ \\ else \end{matrix}

= \begin{cases}f_{s}(x) \\ f_{s}(⌊x⌋) · (⌈x⌉ − x) + f_{s}(⌈x⌉) · (x − ⌊x⌋ − 1 + 1) \end{cases}  \begin{matrix}x = ⌊x⌋ \\ else \end{matrix}

= \begin{cases}f_{s}(x) \\ f_{s}(⌊x⌋) · (⌈x⌉ − x) + f_{s}(⌈x⌉) · (x − ⌊x⌋) \end{cases}  \begin{matrix}x = ⌊x⌋ \\ else \end{matrix}

The shown result describes a linear interpolation between two adjacent sampling points, or one point itself if the variable x happens to directly hit it.

5.5 Duality of Multiplication and Convolution

F[f ⊗ g] = ∫_{−∞}^{∞}(f ⊗ g)(x) · e^{−2πikx}dx

= ∫_{−∞}^{∞} ∫_{−∞}^{∞} f(τ) · g(x − τ)dτ · e^{−2πikx}dx

= ∫_{−∞}^{∞} ∫_{−∞}^{∞} f(τ) · g(x − τ) · e^{−2πikx}dτdx

=^{Fu} ∫_{−∞}^{∞} ∫_{−∞}^{∞} f(τ) · g(x − τ) · e^{−2πikx}dxdτ

= ∫_{−∞}^{∞} f(τ) · ∫_{−∞}^{∞} g(x − τ) · e^{−2πikx}dxdτ

=^{∗} ∫_{∞}^{−∞} f(τ) · ∫_{∞}^{−∞} g(t) · e^{−2πik(t+τ)}dtdτ

= ∫_{∞}^{−∞} f(τ) · e^{−2πikτ} · ∫_{∞}^{−∞} g(t) · e^{−2πikt}dtdτ

= ∫_{∞}^{−∞} g(t) · e^{−2πikt}dt · ∫_{∞}^{−∞} f(τ) · e^{−2πikτ}dτ

= F[g] · F[f] = F[f] · F[g]

Hereby, Fu denotes application of Fubini’s theorem, whereas ∗ describes a substitution:

Let h(x) = g(x − τ) · e^{−2πikx}. We substitute

∫ h(x)dx = ∫ h(φ(t))φ′(t)dt|_{t=φ^{−1}(x)} .

Choose φ(t) = t + τ, then φ′(t) = 1, φ^{−1}(x) = x − τ and

∫ h(x)dx = ∫ h(t + τ)dt|_{t=x−τ}
= ∫ g(t + τ − τ) · e^{−2πik(t+τ)}dt|_{t=x−τ} .