\documentclass[12pt,a4paper]{article}

\usepackage{amstext}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{cancel}
\usepackage{fancyhdr}
\usepackage{listings}
\usepackage{pstricks}
\usepackage{pst-plot}
%\usepackage{gastex}
%\usepackage{ngerman}
\usepackage{wasysym}
\usepackage{rotating}

\title{\textsc{Image Processing and Computer Vision \\ \large Assignment T1}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \scriptsize 2031259} \\ Group T1: Tue, 14-16 (Sebastian Zimmer)}% \and \shortstack[c]{name\\ \scriptsize matr}}
\date{}

\pagestyle{fancy}

\lhead{Assignment T1}
\chead{}
\rhead{Dithmar (2031259)}
\lfoot{IPCV}
\cfoot{Page \thepage}
\rfoot{WS 2007/2008}

\begin{document}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

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

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[2]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[#1]{#2}\\[0.2cm]
	\end{figure}
	}

\newcommand{\m}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\+}{\phantom{-}}
\newcommand{\f}{\frac}

\maketitle

\thispagestyle{empty}

\newpage
\setcounter{page}{1}
\setcounter{section}{1}

\exercise{Signal-to-Noise Ratio}
\begin{enumerate}
\item Let's see, if $\mathsf{SNR}(f,g) = 0$:
	\begin{eqnarray*}
		\mathsf{SNR}(f,g) & = & 0 \\
		10 \cdot \log_{10}\frac{\sigma^2 (g)}{\sigma^2 (n)} & = & 0 \\
		\log_{10}\frac{\sigma^2(g)}{\sigma^2(n)} & = & 0 \\
		\log_{10} \sigma^2(g) - \log_{10} \sigma^2(n) & = & 0 \\
		\log_{10} \sigma^2(g) & = & \log_{10} \sigma^2(n) \\
		\sigma^2(g) & = & \sigma^2(n)
	\end{eqnarray*}
	So this is the case, if the noise doesn't affect the original image.
\item For the sake of readability, I define a function as follows:
	$$short(x,y) = \sum_{i=1}^M \sum_{j=1}^N (x - y)^2$$
	\begin{eqnarray*}
		\mathsf{SNR}(u,g) & = & \mathsf{SNR}(f,g) + 10 \mathsf{dB} \\
		\Leftrightarrow 10 \cdot \log_{10}\frac{\frac{1}{MN} \cdot short(g_{i,j}, \mu)}{\frac{1}{MN} \cdot short(u_{i,j}, g_{i,j})} & = & 10 \cdot \log_{10}\frac{\frac{1}{MN} \cdot short(g_{i,j}, \mu)}{\frac{1}{MN} \cdot short(f_{i,j}, g_{i,j})} + 10 \\
		\Leftrightarrow \log_{10}\frac{short(g_{i,j}, \mu)}{short(u_{i,j}, g_{i,j})} \\
		- \log_{10}\frac{short(g_{i,j}, \mu)}{short(f_{i,j}, g_{i,j})} & = & 1 \\[0.2cm]
		\Leftrightarrow \log_{10}\frac{\frac{\sum_{i=1}^M\sum_{j=1}^N (g_{i,j})^2}{\sum_{i=1}^M\sum_{j=1}^N (u_{i,j} - g_{i,j})^2}}{\frac{\sum_{i=1}^M\sum_{j=1}^N (g_{i,j})^2}{\sum_{i=1}^M\sum_{j=1}^N (f_{i,j} - g_{i,j})^2}} & = & 1 \\[0.2cm]
		\Leftrightarrow \log_{10} \frac{\sum_{i=1}^M\sum_{j=1}^N (f_{i,j} - g_{i,j})^2}{\sum_{i=1}^M\sum_{j=1}^N (u_{i,j} - g_{i,j})^2} & = & 1 \\[0.2cm]
		\Leftrightarrow \frac{\sum_{i=1}^M\sum_{j=1}^N (f_{i,j} - g_{i,j})^2}{\sum_{i=1}^M\sum_{j=1}^N (u_{i,j} - g_{i,j})^2} & = & 10 \\
	\end{eqnarray*}
	\begin{eqnarray*}
		\Leftrightarrow \sum_{i=1}^M\sum_{j=1}^N (f_{i,j} - g_{i,j})^2 & = & 10 \cdot \sum_{i=1}^M \sum_{j=1}^N (u_{i,j} - g_{i,j})^2 \\
		\Leftrightarrow \frac{1}{MN} \cdot \sum_{i=1}^M\sum_{j=1}^N (f_{i,j} - g_{i,j})^2 & = & 10 \cdot \frac{1}{MN} \cdot \sum_{i=1}^M \sum_{j=1}^N (u_{i,j} - g_{i,j})^2 \\
		\Leftrightarrow \sigma^2(n) & = & 10 \cdot \sigma^2(n')
	\end{eqnarray*}
	where $\sigma^2(n')$ is the noise variance of the filtered image. \\
	Interpretation: \\
	As one can see, playing with the \textsf{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.
\item
	\begin{itemize}
		\item If the initial image is constant, the variance is also constant. For example:
			\begin{eqnarray*}
				g = 5 \Rightarrow \sigma^2(g) & = & \frac{1}{MN} \sum_{i=1}^M\sum_{j=1}^N (g_{i,j} - \mu)^2 \\
				\stackrel{\mu=0}{\Leftrightarrow} \sigma^2(g) & = & \frac{1}{MN} \cdot 25 \cdot M \cdot N \\
				\sigma^2(g) & = & 25 = 5^2 = g^2
			\end{eqnarray*}
			This means that the resulting image is the noise function with some additional weighting which is the constant image.
		\item Let's try to calculate $\mathsf{SNR}(g,g)$:
			$$\mathsf{SNR}(g,g) = 10 \cdot \log_{10} \frac{\displaystyle \frac{1}{MN} \cdot \sum_{i=1}^M \sum_{j=1}^N (g_{i,j} - \mu)^2}{\underbrace{\frac{1}{MN} \cdot \sum_{i=1}^M \sum_{j=1}^N (g_{i,j} - g_{i,j})^2}_{=0}}$$
			One cannot calculate this, because of the division by 0. \\
			Since this $\mathsf{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.
	\end{itemize}
\end{enumerate}

\exercise{Discrete vs. Continuous Convolution}
\begin{enumerate}
\item
	\begin{eqnarray*}
		f_i & = & \left\{ \begin{array}{cl}\frac{1}{2} & (i \in \{0,1\}) \\ 0 & (\mbox{else})\end{array}\right. \\[0.3cm]
		(f * f)_k & = & \sum_i f_{k-i} \cdot f_i = \sum_{i=0}^1 f_{k-i} \cdot f_i \\
		& = & \frac{1}{2} \cdot \sum_{i=0}^1 f_{k-i} = \frac{1}{2} \cdot (f_k + f_{k-1}) = g \\
		(g * f)_k & = & \sum_i g_{k-i} \cdot f_i = \sum_{i=0}^1 g_{k-i} \cdot f_i \\
		& = & \frac{1}{2} \cdot \sum_{i=0}^1 g_{k-i} = \frac{1}{2} \cdot \sum_{i=0}^1 \left(\frac{1}{2} \cdot (f_k + f_{k-1})\right)_{k-i} \\
		& = & \frac{1}{4} \cdot \left((f_k + f_{k-1}) + (f_{k-1} + f_{k-2})\right) = h \\
		(h * f)_k & = & \sum_i h_{k-i} \cdot f_i = \sum_{i=0}^1 h_{k-i} \cdot f_i \\
		& = & \frac{1}{2} \sum_{i=0}^1 h_{k-i} = \frac{1}{2} \cdot \frac{1}{4} \cdot \sum_{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 \cdot (f_{k-1} + f_{k-2}) + (f_{k-2} + f_{k-3})) = l \\
		(l * f)_k & = & \sum_i l_{k-i} \cdot f_i = \frac{1}{2} \cdot \sum_{i=0}^1 l_{k-i} \\
		& = & \frac{1}{2} \cdot \frac{1}{8} \cdot \sum_{i=0}^1 ((f_k + f_{k-1}) + 2 \cdot (f_{k-1} + f_{k-2}) + (f_{k-2} + f_{k-3}))_{k-i} \\
		& = & \frac{1}{16} \cdot [(f_k + f_{k-1}) + 2 \cdot (f_{k-1} + f_{k-2}) + (f_{k-2} + f_{k-3}) \\
		& & \quad \quad + (f_{k-1} + f_{k-2}) + 2 \cdot (f_{k-2} + f_{k-3}) + (f_{k-3} + f_{k-4})] \\
		& = & \frac{1}{16} \cdot [(f_k + f_{k-1}) + 3 \cdot (f_{k-1} + f{k-2}) \\
		& & \quad \quad + 3 \cdot (f_{k-2} + f_{k-3}) + (f_{k-3} + f_{k-4})]
	\end{eqnarray*}
\item 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 ;-)
	\begin{eqnarray*}
		(f*f)(x) & = & \int_{-\infty}^\infty f(x-y) \cdot f(y) dy \\
		& = & \int_{-\infty}^{-2} f(x-y) \cdot f(y) dy + \int_{-2}^0 f(x-y) \cdot f(y) dy \\
		& & + \int_0^2 f(x-y) \cdot f(y) dy + \int_2^\infty f(x-y) \cdot f(y) dy \\
		& = & \int_{-2}^0 f(x-y) \cdot f(y) dy + \int_0^2 f(x-y) \cdot f(y) dy \\
		& = & \int_{-2}^{-1} f(x-y) \cdot f(y) dy + \int_{-1}^1 f(x-y) \cdot f(y) dy + \int_1^2 f(x-y) \cdot f(y) dy \\
		& = & \int_{-1}^1 f(x-y) \cdot f(y) dy = \frac{1}{2} \cdot \int_{-1}^1 f(x-y) dy \\
		& = & \frac{1}{2} \cdot \int_{x-1}^{x+1} \frac{1}{2} dy = \frac{1}{2} \cdot \left[\frac{1}{2}y\right]_{x-1}^{x+1} \\
		& = & \frac{1}{2} \cdot \left(\frac{1}{2} \cdot (x+1) - \frac{1}{2} \cdot (x-1)\right) \\
		& = & \frac{1}{2} \cdot \left(\frac{1}{2}x + \frac{1}{2} - \frac{1}{2}x + \frac{1}{2}\right) \\
		& = & \frac{1}{2}
	\end{eqnarray*}
	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.
\end{enumerate}

\exercise{Properties of the Discrete Convolution}
\begin{enumerate}
\item To show: $(\alpha \cdot f + \beta \cdot g) * w = \alpha \cdot (f * w) + \beta \cdot (g * w) \quad \forall \alpha, \beta \in \SetR$
	\begin{eqnarray*}
		((\alpha \cdot f + \beta \cdot g) * w)_i & = & \sum_{k=-\infty}^\infty (\alpha \cdot f + \beta \cdot g)_{i-k} \cdot w_k \\
		& = & \sum_{k=-\infty}^\infty (\alpha \cdot f \cdot w_{2k-i} + \beta \cdot g \cdot w_{2k-i})_{i-k} \\
		& = & \sum_{k=-\infty}^\infty ((\alpha \cdot f \cdot w_{2k-i})_{i-k} + (\beta \cdot g \cdot w_{2k-i})_{i-k}) \\
		& = & \sum_{k=-\infty}^\infty (\alpha \cdot (f \cdot w_{2k-i})_{i-k} + \beta \cdot (g \cdot w_{2k-i})_{i-k}) \\
		& = & \sum_{k=-\infty}^\infty \alpha \cdot (f \cdot w_{2k-i})_{i-k} + \sum_{k=-\infty}^\infty \beta \cdot (g \cdot w_{2k-i})_{i-k} \\
		& = & \alpha \cdot \sum_{k=-\infty}^\infty f_{i-k} \cdot w_k + \beta \cdot \sum_{k=-\infty}^\infty g_{i-k} \cdot w_k \\
		& = & \alpha \cdot (f * w)_i + \beta \cdot (g * w)_i
	\end{eqnarray*}
\item To show: $f * w = w * f$
	\begin{eqnarray*}
		(f * w)_i & = & \sum_{k=-\infty}^\infty f_{i-k} \cdot w_k = \sum_{k=-\infty}^\infty w_k \cdot f_{i-k} \\
		& = & \sum_{k=-\infty}^\infty w_{k-i} \cdot f_{-k} = \sum_{k=\infty}^{-\infty} w_{i-k} \cdot f_k \\
		& \stackrel{(*)}{=} & \sum_{k=-\infty}^\infty w_{i-k} \cdot f_k \\
		& = & (w * f)_i
	\end{eqnarray*}
	where $(*)$ is because of the symmetry of the sum.
\item Claim:
	$$e = \left\{\begin{array}{cl}1 & x = 0 \\ 0 & x \neq 0\end{array}\right.$$
	Proof:
	$$(f*e)_i = \sum_{k=-\infty}^\infty f_{i-k} \cdot e_k = \underbrace{\sum_{-\infty}^{-1} f_{i-k} \cdot e_k}_{=0} + f_i \cdot 1 + \underbrace{\sum_1^\infty f_{i-k} \cdot e_k}_{=0} = f_i$$
\end{enumerate}

\exercise{Continous Fourier Transform}
\begin{enumerate}
\item We have the 1-D hat function:
	$$f(x) = \left\{\begin{array}{cl}\frac{2-|x|}{4} & (-2 \leq x \leq 2) \\ 0 & (\mbox{else})\end{array}\right.$$
	To make life easier, I re-define the function $f$ as follows:
	$$f(x) = \left\{\begin{array}{cl}\frac{2+x}{4} & (-2 \leq x < 0) \\ \frac{2-x}{4} & (0 \leq x \leq 2) \\ 0 & (\mbox{else})\end{array}\right.$$
	Let's compute the Fourier transform:
	\begin{eqnarray*}
		\hat{f}(u) & = & \mathcal{F}[f](u) = \int_{-\infty}^\infty f(x) \cdot e^{-i 2 \pi u x} dx \\
		& = & \int_{-2}^2 f(x) \cdot e^{-i 2 \pi u x} dx \\
		& = & \int_{-2}^0 f(x) \cdot e^{-i 2 \pi u x} dx + \int_0^2 f(x) \cdot e^{-i 2 \pi u x} dx \\
		& = & \int_{-2}^0 \frac{2+x}{4} \cdot e^{-i 2 \pi u x} dx + \int_0^2 \frac{2-x}{4} \cdot e^{-i 2 \pi u x} dx \\
		& = & \left[ \frac{2+x}{4} \cdot \left(-\frac{1}{i 2 \pi u}\right) \cdot e^{-i 2 \pi u x}\right]_{-2}^0 - \int_{-2}^0 \frac{1}{4} \cdot \left(-\frac{1}{i 2 \pi u}\right) \cdot e^{-i 2 \pi u x} dx \\
		& & + \left[\frac{2-x}{4} \cdot \left(-\frac{1}{i 2 \pi u}\right) \cdot e^{-i 2 \pi u x}\right]_0^2 - \int_0^2 \left(-\frac{1}{4}\right) \cdot \left(-\frac{1}{i 2 \pi u}\right) \cdot e^{-i 2 \pi u x} dx \\
		& = & \frac{1}{2} \cdot \left(-\frac{1}{i 2 \pi u}\right) \cdot e^0 - \frac{1}{4} \cdot \left(-\frac{1}{i 2 \pi u}\right) \cdot \left[-\frac{1}{i 2 \pi u} \cdot e^{-i 2 \pi  u x}\right]_{-2}^0 \\
		& & + \left(0 - \frac{1}{2} \cdot \left(-\frac{1}{i 2 \pi u}\right) \cdot e^0\right) - \left(-\frac{1}{4}\right) \cdot \left(-\frac{1}{i 2 \pi u}\right) \cdot \left[-\frac{1}{i 2 \pi u} \cdot e^{-i 2 \pi u x}\right]_0^2
	\end{eqnarray*}
	\begin{eqnarray*}
		\phantom{\hat{f}(u)} & = & \frac{1}{2} \cdot \left(-\frac{1}{i 2 \pi u}\right) - \frac{1}{4} \cdot \left(-\frac{1}{i 2 \pi u}\right) \cdot \left[\left(-\frac{1}{i 2 \pi u}\right) - \left(-\frac{1}{i 2 \pi u}\right) \cdot e^{-i 2 \pi u (-2)}\right] \\
		& & -\frac{1}{2} \cdot \left(-\frac{1}{i 2 \pi u}\right) - \left(-\frac{1}{4}\right) \cdot \left(-\frac{1}{-i 2 \pi u}\right) \cdot \left[-\frac{1}{i 2 \pi u} \cdot e^{-i 2 \pi u \cdot 2} - \left(-\frac{1}{i 2 \pi u}\right)\right] \\
		& = & -\frac{1}{2} \cdot \frac{1}{i 2 \pi u} - \frac{1}{4} \cdot \left(\frac{1}{i 2 \pi u}\right)^2 - \frac{1}{4} \cdot \left(\frac{1}{i 2 \pi u}\right)^2 \cdot e^{-i 2 \pi u \cdot (-2)} \\
		& & + \frac{1}{2} \cdot \frac{1}{i 2 \pi u} + \frac{1}{4} \cdot \left(\frac{1}{i 2 \pi u}\right)^2 \cdot e^{-i 2 \pi u \cdot 2} - \frac{1}{4} \cdot \left(\frac{1}{i 2 \pi u}\right)^2 \\
		& = & -\frac{1}{2} \cdot \left(\frac{1}{i 2 \pi u}\right)^2 + \frac{1}{4} \cdot \left(\frac{1}{i 2 \pi u}\right)^2 \cdot \left(e^{-i 2 \pi u \cdot 2} - e^{i 2 \pi u \cdot 2}\right) \\
		& = & -\frac{1}{2} \cdot \frac{1}{i^2 4 \pi^2 u^2} + \frac{1}{4} \cdot \frac{1}{i^2 4 \pi^2 u^2} \cdot e^4 \left(e^{-i \pi u} - e^{i \pi u}\right) \\
		& = & -\frac{1}{2} \cdot \frac{1}{i^2 4 \pi^2 u^2} + \frac{1}{4} \cdot \frac{1}{i^2 4 \pi^2 u^2} \cdot e^4 \cdot \left(-2i \sin(\pi u)\right) \\
		& = & -\frac{1}{2} \cdot \frac{1}{i^2 4 \pi^2 u^2} + \frac{1}{4} \cdot \frac{1}{-i 2 \pi^2 u^2} \cdot e^4 \cdot \sin(\pi u) \\
		& = & -\frac{1}{8 i^2 \pi^2 u^2} - \frac{e^4 \cdot \sin(\pi u)}{8 i \pi^2 u^2} \\
		& = & \frac{-1 - e^4 \cdot \sin(\pi u) \cdot i}{8 i^2 \pi^2 u^2} \\
		& = & -\frac{1}{8 i^2 \pi^2 u^2} \cdot (1 + e^4 \cdot \sin(\pi u) \cdot i) \\
		& \stackrel{i^2 = -1}{=} & \frac{1}{8 \pi^2 u^2} \cdot (1 + e^4 \cdot \sin(\pi u) \cdot i)
	\end{eqnarray*}
\item
	\begin{eqnarray*}
		|\hat{f}(u)| & = & \left|\frac{1}{8 \pi^2 u^2}\right| \cdot \left|1 + e^4 \cdot \sin(\pi u) \cdot i\right| \\
		& = & \frac{1}{8 \pi^2 u^2} + \left|\frac{e^4 \cdot \sin(\pi u) \cdot i}{8 \pi^2 u^2}\right| \\
		& = & \frac{1}{8 \pi^2 u^2} + \left|\frac{e^4 \cdot i}{8 \pi u}\right| \cdot \left|\frac{\sin(\pi u)}{\pi u}\right| \\
		& = & \frac{1}{8 \pi^2 u^2} + \left|\frac{e^4 \cdot i}{8 \pi u}\right| \cdot \left|\mbox{sinc}(\pi u)\right|
	\end{eqnarray*}
\end{enumerate}

\end{document}
