\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 T3}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \scriptsize 2031259} \\[0.5cm] Group T1: Tue, 14-16 (Sebastian Zimmer)}% \and \shortstack[c]{name\\ \scriptsize matr}}
\date{}

\pagestyle{fancy}

\lhead{Assignment T3}
\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}{3}

\exercise{Interpolation}
\begin{enumerate}
	\item We have
		$$\beta_5(k) = \left\{\begin{array}{cl}\frac{1}{120} & k = \pm 2 \\[0.3cm] \frac{13}{60} & k = \pm 1 \\[0.3cm] \frac{11}{20} & k = 0 \\[0.3cm] 0 & \mbox{for other integer values } k\end{array}\right.$$
		Now I state the equation system:
		$$\left(\begin{array}{cccccccccccc}\frac{11}{20} & \frac{13}{60} & \frac{1}{120} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\[0.3cm] \frac{13}{60} & \frac{11}{20} & \frac{13}{60} & \frac{1}{120} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\[0.3cm] \frac{1}{120} & \frac{13}{60} & \frac{11}{20} & \frac{13}{60} & \frac{1}{120} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\[0.3cm] & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots \\[0.3cm] 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{120} & \frac{13}{60} & \frac{11}{20} & \frac{13}{60} & \frac{1}{120} \\[0.3cm] 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{120} & \frac{13}{60} & \frac{11}{20} & \frac{13}{60} \\[0.3cm] 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{120} & \frac{13}{60} & \frac{11}{20}\end{array}\right) \cdot \left(\begin{array}{c}c_1 \\[0.3cm] c_2 \\[0.3cm] c_3 \\[0.3cm] \vdots \\[0.3cm] c_{N-2} \\[0.3cm] c_{N-1} \\[0.3cm] c_N\end{array}\right) = \left(\begin{array}{c}f_1 \\[0.3cm] f_2 \\[0.3cm] f_3 \\[0.3cm] \vdots \\[0.3cm] f_{N-2} \\[0.3cm] f_{N-1} \\[0.3cm] f_N\end{array}\right)$$
	\item
		\begin{eqnarray*}
			\left(\begin{array}{ccc}\frac{2}{3} & \frac{1}{6} & 0 \\[0.3cm] \frac{1}{6} & \frac{2}{3} & \frac{1}{6} \\[0.3cm] 0 & \frac{1}{6} & \frac{2}{3}\end{array}\right) \cdot \left(\begin{array}{c}c_1 \\ c_2 \\ c_3\end{array}\right) & = & \left(\begin{array}{c}f_1 \\ f_2 \\ f_3\end{array}\right) \\[0.3cm]
			\left(\begin{array}{ccc}\frac{2}{3} & \frac{1}{6} & 0 \\[0.3cm] \frac{1}{6} & \frac{2}{3} & \frac{1}{6} \\[0.3cm] 0 & \frac{1}{6} & \frac{2}{3}\end{array}\right) \cdot \left(\begin{array}{c}c_1 \\ c_2 \\ c_3\end{array}\right) & = & \left(\begin{array}{c}4 \\ 28 \\ 24\end{array}\right) \\[0.3cm]
			\left(\begin{array}{ccccc}\frac{2}{3} \cdot c_1 & + & \frac{1}{6} \cdot c_2 \\[0.3cm] \frac{1}{6} \cdot c_1 & + & \frac{2}{3} \cdot c_2 & + & \frac{1}{6} \cdot c_3 \\[0.3cm] & & \frac{1}{6} \cdot c_2 & + & \frac{2}{3} \cdot c_3\end{array}\right) & = & \left(\begin{array}{c}4 \\ 28 \\ 24\end{array}\right)
		\end{eqnarray*}
		This results in three equations with three unknowns:
		\begin{eqnarray*}
			\begin{array}{ccccc} \phantom{\frac{1}{6} \cdot c_1} & \phantom{+} & \displaystyle \frac{1}{6} \cdot c_2 & \phantom{+} & \phantom{\frac{1}{6} \cdot c_3}\end{array} & = & 4 - \frac{2}{3} \cdot c_1 \\[0.3cm]
			\begin{array}{ccccc} \displaystyle \frac{1}{6} \cdot c_1 & + & \displaystyle \frac{2}{3} \cdot c_2 & + & \displaystyle \frac{1}{6} \cdot c_3\end{array} & = & 28 \\[0.3cm]
			\begin{array}{ccccc} \phantom{\frac{1}{6} \cdot c_1} & \phantom{+} & \phantom{\frac{2}{3} \cdot c_2} & \phantom{+} & \displaystyle \frac{2}{3} \cdot c_3\end{array} & = & 24 - \frac{1}{6} \cdot c_2 = 24 - \left(4 - \frac{2}{3} \cdot c_1\right) \\
			& & \quad \quad \quad \quad \quad = 20 + \frac{2}{3} \cdot c_1
		\end{eqnarray*}
		Let's use the second equation to get $c_1$:
		\begin{eqnarray*}
			\frac{1}{6} \cdot c_1 + \frac{2}{3} \cdot 6 \cdot \left(4 - \frac{2}{3} \cdot c_1\right) + \frac{1}{6} \cdot \frac{3}{2} \cdot \left(20 + \frac{2}{3} \cdot c_1\right) & = & 28 \\[0.3cm]
			\frac{1}{6} \cdot c_1 + 16 - \frac{8}{3} \cdot c_1 + 5 + \frac{1}{6} \cdot c_1 & = & 28 \\[0.3cm]
			-\frac{7}{3} \cdot c_1 + 21 & = & 28 \\
			-\frac{7}{3} & = & 7 \\
			c_1 & = & -3
		\end{eqnarray*}
		Now, one can use the third equation to get $c_3$:
		\begin{eqnarray*}
			\frac{2}{3} \cdot c_3 & = & 20 + \frac{2}{3} \cdot c_1 \\[0.3cm]
			\frac{2}{3} \cdot c_3 & = & 20 + \frac{2}{3} \cdot (-3) \\[0.3cm]
			\frac{2}{3} \cdot c_3 & = & 20 -2 \\[0.3cm]
			\frac{2}{3} \cdot c_3 & = & 18 \\[0.3cm]
			c_3 & = & 27
		\end{eqnarray*}
		And now, let's compute $c_2$:
		\begin{eqnarray*}
			\frac{1}{6} \cdot c_2 & = & 4 - \frac{2}{3} \cdot c_1 \\[0.3cm]
			\frac{1}{6} \cdot c_2 & = & 4 + 2 \\[0.3cm]
			c_2 & = & 6 \cdot 6 \\
			c_2 & = & 36
		\end{eqnarray*}
		Having the coefficients, I compute the interpolation values for the points $\frac{1}{2}$ and $\frac{3}{2}$:
		\begin{eqnarray*}
			f(x) & = & \sum_{k \in \SetZ} c_k \cdot \varphi(x-k) \\
			& = & \sum_{k \in \SetZ} c_k \cdot \beta_3(x-k) \\[0.5cm]
			f\left(\frac{1}{2}\right) & = & c_1 \cdot \beta_3\left(-\frac{1}{2}\right) + c_2 \cdot \beta_3\left(-\frac{3}{2}\right) + c_3 \cdot \beta_3\left(-\frac{5}{2}\right) \\
			& = & -3 \cdot \frac{23}{48} + 36 \cdot \frac{1}{48} + 27 \cdot 0 \\
			& = & -\frac{11}{16} \\[0.3cm]
			f\left(\frac{3}{2}\right) & = & c_1 \cdot \beta_3\left(\frac{1}{2}\right) + c_2 \cdot \beta_3\left(-\frac{1}{2}\right) + c_3 \cdot \beta_3\left(-\frac{3}{2}\right) \\
			& = & -3 \cdot \frac{23}{48} + 36 \cdot \frac{23}{48} + 27 \cdot \frac{1}{48} \\
			& = & \frac{131}{8}
		\end{eqnarray*}
\end{enumerate}

\newpage
\exercise{Multiple Choice}
\begin{enumerate}
	\item \textbf{false} \\
		Since you can compute the discrete Wavelet coefficients in optimal complexity and the Wavelet transform is separable, you would get simply a factor more per dimension, i.e. $2 \cdot N \in \OnotO(N)$ for 2-D instead of $1 \cdot N \in \OnotO(N)$ for 1-D.
	\item \textbf{true} \\
		Since all letters have the same probability it does not matter which letter is at which position in the tree built by the Huffman coding and because this does not matter, it is some kind of arbitrary assigning of codes to letters.
	\item \textbf{true} \\
		We have $(7)_2 = 00000111$ and $(8)_2 = 00001000$. \\
		Since the first 4 bits do not change you have the possibility to store these bits efficiently with bitplane coding while you cannot do this with runlength coding.
	\item \textbf{false} \\
		Since we already know that cubic B-splines can be efficiently solved using the Thomas algorithm, the coefficients for the cubic B-splines require less computational effort, namely $\OnotO(n)$ instead of $\OnotO(n^3)$, where quadratic B-splines require $\OnotO(n^2) > \OnotO(n)$.
	\item \textbf{true} \\
		If the histogram equalisation function is known, one can do the "back-calculation" which results in the original histogram.
	\item \textbf{false} \\
		Using a lowpass and highpass filter subsequently results in a bandpass filtered image and not in the original image.
\end{enumerate}

\newpage
\exercise{Linear Filters}
\begin{enumerate}
	\item
		\begin{itemize}
			\item $x$-direction: Gaussian, approximated by $\frac{1}{12}$ \begin{tabular}{|c|c|c|}\hline 1 & 2 & 1 \\ \hline\end{tabular} \\
				$\Rightarrow$ lowpass filter
			\item $y$-direction: scaled box filter $\frac{1}{12}$ \begin{tabular}{|c|c|c|}\hline 1 & 1 & 1 \\ \hline\end{tabular} \\
				$\Rightarrow$ lowpass filter
		\end{itemize}
	\item $x$-direction and $y$-direction: difference between identity and lowpass filter \\
		$\Rightarrow$ highpass filter
		$$\frac{1}{12} \begin{tabular}{|r|r|r|}\hline -1 & -2 & -1 \\ \hline 2 & 4 & 2 \\ \hline -1 & -2 & -1 \\ \hline\end{tabular} = \begin{tabular}{|c|c|c|}\hline 0 & 0 & 0 \\ \hline 0 & 1 & 0 \\ \hline 0 & 0 & 0 \\ \hline\end{tabular} - \frac{1}{12} \begin{tabular}{|r|r|r|}\hline 1 & 2 & 1 \\ \hline -2 & 8 & -2 \\ \hline 1 & 2 & 1 \\ \hline\end{tabular}$$
	\item $x$-direction and $y$-direction: difference between two lowpass filters \\
		$\Rightarrow$ bandpass filter
		$$\frac{1}{256} \begin{tabular}{|r|r|r|r|r|}\hline -1 & -4 & -6 & -4 & -1 \\ \hline -4 & 0 & 8 & 0 & -4 \\ \hline -6 & 8 & 28 & 8 & -6 \\ \hline -4 & 0 & 8 & 0 & -4 \\ \hline -1 & -4 & -6 & -4 & 1 \\ \hline\end{tabular} = \frac{1}{256} \left(\phantom{p}\begin{tabular}{|c|c|c|c|c|}\hline 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 16 & 32 & 16 & 0 \\ \hline 0 & 32 & 64 & 32 & 0  \\ \hline 0 & 16 & 32 & 16 & 0 \\ \hline 0 & 0 & 0 & 0 & 0 \\ \hline\end{tabular} - \begin{tabular}{|c|c|c|c|c|}\hline 1 & 4 & 6 & 4 & 1 \\ \hline 4 & 16 & 24 & 16 & 4 \\ \hline 6 & 24 & 36 & 24 & 6 \\ \hline 4 & 16 & 24 & 16 & 4 \\ \hline 1 & 4 & 6 & 4 & 1 \\ \hline\end{tabular}\phantom{p}\right)$$
\end{enumerate}
\end{document}
