\documentclass[a4paper,10pt,titlepage]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{pstricks}
\usepackage{pst-plot}

%opening
\title{\textsc{Computer Graphics I \\ \large Assignment 5}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \footnotesize ??} \and \shortstack[c]{Pascal Gwosdek\\ \footnotesize 2505221}}

\newcommand{\exercise}[1]{\subsection{#1}}
\renewcommand{\theenumi}{\textbf{\alph{enumi}}}


\setcounter{section}{5}

\begin{document}

\maketitle

\exercise{Fourier Transform}
Let
$$ B'(k) = \int_{-\infty}^\infty B(x) \cdot e^{-2 \pi i k x} dx.$$
Then:
\begin{align*}
B'(k) &= \int_{-\infty}^\infty B(x) \cdot e ^ {-2 \pi i k x} dx\\
&= \int_{-\infty}^{-1} 0 dx + \int_{-1}^1 e^{-2 \pi i k x} dx + \int_1^\infty 0 dx\\
&= \int_{-1}^1 e^{-2 \pi i k x} dx\\
&= \left[\dfrac{e^{-2 \pi i k x}}{-2 \pi i k}\right]_{-1}^1\\
&= \dfrac{e^{-2 \pi i k} - e^{2 \pi i k}}{-2 \pi i k}\\
&= \dfrac{\cos(-2 \pi k) + i \cdot \sin(-2 \pi k) - \cos(2 \pi k) - i \cdot \sin(2 \pi k)}{-2 \pi i k}\\
&= \dfrac{i (\sin(-2 \pi k) - \sin(2 \pi k))}{-2 \pi i k}\\
&= \dfrac{\sin(2 \pi  k) - \sin(-2 \pi k))}{2 \pi k}\\
&= \dfrac{2 \cdot \sin(2 \pi k)}{2 \pi k}\\
&= \dfrac{\sin(2 \pi k)}{\pi k}\\
&= 2 \cdot sinc(2k)\quad\quad\blacksquare
\end{align*}

\exercise{Sampling Theory}
\begin{enumerate}
\item \textbf{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 $\delta$ equally spaced with distance $T$. Then, we convolve the representation $F$ of $f$ in the fourier space with $\Delta$, a delta comb function with peak distances of $\frac1T$.

Thus, the the sampled signal $F_s$ in fourier domain is $\frac1T$-periodic. This means that the whole signal and its frequencies are represented in the interval $\left[ -\frac1{2T}, \frac1{2T} \right)$.

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.

\item The reconstruction of $f$ or $F$ in spatial and fourier domain, respectively, has to be performed as follows:
\begin{itemize}
\item \textbf{Image space:} $f_s(x)$ must be convolved with the $sinc$ function $sinc(Tx)$:
$$f(x) = f_s(x) \otimes sinc(Tx)$$
\item \textbf{Fourier space:} $F$ needs to be multiplied with the box function $B(x) = \begin{cases}1\quad &\mathrm{if}\ -\frac1{2T} \leqslant x < \frac1{2T}\\0&\mathrm{else}\end{cases}$:
$$F(x) = F_s(x) \cdot B(x)$$
\end{itemize}
\end{enumerate}

\exercise{Antialiasing}
\begin{enumerate}
\item
\textbf{Sampling}\\
The sampling of a continuous signal can be performed as follows:
\begin{itemize}
\item 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 $\delta(x)$:
$$f_s(x) = f(x) \cdot \delta(x)$$
\item In fourier domain, this operation corresponds to a convolution of the fourier-transformed delta comb $\delta$, which yields a delta comb $\Delta$ again, with the representation $F(x)$ of the function $f(x)$ in fourier space:
$$F_s(x) = F(x) \otimes \Delta(x)$$
Assume the distance between two adjacent peaks of the delta comb $\delta$ is $x$, then $\Delta$ has its peaks spaced by $\frac1x$.
\end{itemize}

\textbf{Aliasing}
\begin{itemize}
\item 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.
\item 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.
\end{itemize}

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

\begin{center}
\begin{pspicture}(-1,-2.5)(5,2.5)
\psset{xunit=0.0111cm,yunit=1cm}
\psplot[plotstyle=curve,linewidth=1.5pt,linestyle=dashed]{-20}{400}{x sin}
\psplot[plotstyle=curve,linewidth=1.5pt]{-20}{400}{x 1.8 mul 74 sub sin}

\psdot[dotsize=7pt](220,-0.62)
\psline[linestyle=dotted](220,1.5)(220,-1.5)
\psline[linestyle=dotted](90,1.5)(90,-1.5)
\psline{<-}(90,-1.2)(140,-1.2)
\psline{->}(170,-1.2)(220,-1.2)
\rput(155,-1.3){$d$}

\psline[linestyle=dotted](220,-0.62)(320,-0.62)
\psdot[dotsize=7pt,dotstyle=o](320,-0.62)
\psline{<-}(90,-1.5)(190,-1.5)
\psline{->}(220,-1.5)(320,-1.5)
\rput(205,-1.5){$d'$}
\end{pspicture}
\end{center}

Assume, $d$ is the current sampling distance, as depicted in the exercise description. Obviously, the sampled point ($\bullet$) 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), then can this be scaled to $p$, the period of the original image. Here, we search for the respective point in the \textit{bad} signal ($\circ$), denote its distance to the predecessing sampling point with $d'$ and use the proportion rule to yield $p$:
$$p = p' \cdot \frac{d}{d'}$$
$d'$ is given by
$$d' = d + 2 (\frac{p'}2 - d) = p' - d ,$$
hence
$$p = p' \cdot \frac{d}{p' - d}.$$
\end{enumerate}

\exercise{Triangle Filter}
\begin{align*}
f'(x) &= \sum_{k = -\infty}^\infty f_s(k) \cdot T(x-k)\\
&= \left(\sum_{k = -\infty}^{\lfloor x \rfloor - 1} f_s(k) \cdot T(\underbrace{x-k}_{>1})\right) + \left(\sum_{k = \lfloor x \rfloor}^{\lceil x \rceil} f_s(k) \cdot T(x-k)\right) + \left(\sum_{k = \lceil x \rceil + 1}^\infty f_s(k) \cdot T(\underbrace{x-k}_{<1})\right)\\
&= 0 + \left(\sum_{k = \lfloor x \rfloor}^{\lceil x \rceil} f_s(k) \cdot T(x-k)\right) + 0\\
&= \begin{cases}f_s(x) \cdot T(0)&x=\lfloor x \rfloor\\f_s(\lfloor x \rfloor) \cdot T(x-\lfloor x \rfloor) + f_s(\lceil x \rceil) \cdot T(x-\lceil x \rceil)\quad\quad&\mathrm{else}\end{cases}\\
&= \begin{cases}f_s(x) \cdot 1&x=\lfloor x \rfloor\\f_s(\lfloor x \rfloor) \cdot T(x-\lfloor x \rfloor) + f_s(\lceil x \rceil) \cdot T(x-\lceil x \rceil)\quad\quad&\mathrm{else}\end{cases}\\
&= \begin{cases}f_s(x)&x=\lfloor x \rfloor\\f_s(\lfloor x \rfloor) \cdot T(x-\lfloor x \rfloor) + f_s(\lceil x \rceil) \cdot T(x-\lceil x \rceil)\quad\quad&\mathrm{else}\end{cases}
\end{align*}
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.

\exercise{Duality of Multiplication and Convolution}
\begin{align*}
\mathcal{F}[f \otimes g] &= \int_{-\infty}^\infty (f \otimes g) (x) \cdot e^{-2 \pi i k x} dx\\
&= \int_{-\infty}^\infty \int_{-\infty}^\infty f(\tau) \cdot g(x - \tau) d\tau \cdot e^{-2\pi i k x} dx\\
&= \int_{-\infty}^\infty \int_{-\infty}^\infty f(\tau) \cdot g(x - \tau) \cdot e^{-2 \pi i k x} d\tau dx\\
&\overset{\mbox{\tiny Fu}}= \int_{-\infty}^\infty \int_{-\infty}^\infty f(\tau) \cdot g(x - \tau) \cdot e^{-2 \pi i k x} dx d\tau\\
&= \int_{-\infty}^\infty f(\tau) \cdot \int_{-\infty}^\infty g(x - \tau) \cdot e^{-2 \pi i k x} dx d\tau\\
&\overset*= \int_\infty^{-\infty} f(\tau) \cdot \int_\infty^{-\infty} g(t) \cdot e^{-2 \pi i k (t + \tau)} dt d\tau\\
&= \int_\infty^{-\infty} f(\tau) \cdot e^{-2 \pi i k \tau} \cdot \int_\infty^{-\infty} g(t) \cdot e^{-2 \pi i k t} dt d\tau\\
&= \int_\infty^{-\infty} g(t) \cdot e^{-2 \pi i k t} dt \cdot \int_\infty^{-\infty} f(\tau) \cdot e^{-2\pi i k \tau}d\tau\\
&= \mathcal{F}[g] \cdot \mathcal{F}[f]\\
&= \mathcal{F}[f] \cdot \mathcal{F}[g]
\end{align*}
Hereby, Fu denotes application of Fubini's theorem, whereas $*$ describes a substitution:

Let $h(x) = g(x - \tau) \cdot e^{-2 \pi i k x}$. We substitute
$$\int h(x) dx = \left.\int h(\varphi(t)) \varphi'(t)dt \right|_{t = \varphi^{-1}(x)}.$$
Choose $\varphi(t) = t + \tau$, then $\varphi'(t) = 1, \varphi^{-1}(x) = x - \tau$ and
\begin{align*}
\int h(x) dx &= \left. \int h(t + \tau)dt\right|_{t = x - \tau}\\
&= \left. \int g(t + \tau - \tau) \cdot e^{-2 \pi i k (t + \tau)} dt \right|_{t = x - \tau}.
\end{align*}


\end{document}

