\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}
\usepackage{multirow}

\title{\textsc{Image Processing and Computer Vision \\ \large Assignment T5}}
\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 T5}
\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}{5}

\exercise{Derivative Filters}
\begin{enumerate}
	\item The equation system looks as follows:
		\begin{eqnarray*}
			f_{i-2} & = & f_i - 2 h f_i' + 4 \frac{h^2}{2} f_i'' - 8 \frac{h^3}{6} f_i''' + 16 \frac{h^4}{24} f_i'''' + O(h^5) \\
			& = & f_i - 2 h f_i + 2 h^2 f_i' - \frac{4}{3} h^3 f_i''' + \frac{2}{3} h^4 f_i'''' + O(h^5) \\
			f_{i-1} & = & f_i - h f_i' + \frac{1}{2} h^2 f_i'' - \frac{1}{6} h^3 f_i''' + \frac{1}{24} h^4 f_i'''' + O(h^5) \\
			f_i & = & f_i \\
			f_{i+1} & = & f_i + h f_i' + \frac{1}{2} h^2 f_i'' + \frac{1}{6} h^3 f_i''' + \frac{1}{24} h^4 f_i'''' + O(h^5) \\
			f_{i+2} & = & f_i + 2 h f_i' + 4 \frac{h^2}{2} f_i'' + 8 \frac{h^3}{6} f_i''' + 16 \frac{h^4}{24} f_i'''' + O(h^5) \\
			& = & f_i + 2 h f_i + 2 h^2 f_i' + \frac{4}{3} h^3 f_i''' + \frac{2}{3} h^4 f_i'''' + O(h^5)
		\end{eqnarray*}
		$$\Rightarrow 0 \cdot f_i + 1 \cdot f_i' + 0 \cdot f_i'' = \alpha_{-2} f_{i-2} + \alpha_{-1} f_{i-1} + \alpha_0 f_i + \alpha_1 f_{i+1} + \alpha_2 f_{i+2}$$
		
		If you rewrite this, you get the following:
		\begin{eqnarray*}
			f_i' & = & \alpha_{-2} \cdot \left(f_i - 2 h f_i' + 2 h^2 f_i'' - \frac{4}{3} h^3 f_i''' + \frac{2}{3} h^4 f_i'''' + O(h^5)\right) \\
			& & + \alpha_{-1} \cdot \left(f_i - h f_i' + \frac{1}{2} h^2 f_i'' - \frac{1}{6} h^3 f_i''' + \frac{1}{24} h^4 f_i'''' + O(h^5)\right) \\
			& & + \alpha_0 \cdot f_i \\
			& & + \alpha_1 \cdot \left(f_i + h f_i' + \frac{1}{2} h^2 f_i'' + \frac{1}{6} h^3 f_i''' + \frac{1}{24} h^4 f_i'''' + O(h^5)\right) \\
			& & + \alpha_2 \cdot \left(f_i + 2 h f_i' + 2 h^2 f_i'' + \frac{4}{3} h^3 f_i''' + \frac{2}{3} h^4 f_i'''' + O(h^5)\right) \\
			& = & (\alpha_{-2} + \alpha_{-1} + \alpha_0 + \alpha_1 + \alpha_2) f_i + (-2\alpha_{-2} - \alpha_{-1} + \alpha_1 + 2\alpha_2) h f_i' \\
			& & + \left(2\alpha_{-2} + \frac{1}{2}\alpha_{-1} + \frac{1}{2}\alpha_1 + 2\alpha_2\right) h^2 f_i'' \\
			& & + \left(-\frac{4}{3}\alpha_{-2} - \frac{1}{6}\alpha_{-1} + \frac{1}{6}\alpha_1 + \frac{4}{3} \alpha_2\right) h^3 f_i''' \\
			& & + \left(\frac{2}{3}\alpha_{-2} + \frac{1}{24}\alpha_{-1} + \frac{1}{24}\alpha_1 + \frac{2}{3}\alpha_2\right) h^4 f_i'''' + O(h^5)
		\end{eqnarray*}
		This leads to the linear system of equations:
		$$\left(\begin{array}{rrrrr}1 & 1 & 1 & 1 & 1 \\ -2 & -1 & 0 & 1 & 2 \\ 2 & \frac{1}{2} & 0 & \frac{1}{2} & 2 \\ -\frac{4}{3} & -\frac{1}{6} & 0 & \frac{1}{6} & \frac{4}{3} \\ \frac{2}{3} & \frac{1}{24} & 0 & \frac{1}{24} & \frac{2}{3}\end{array}\right) \left(\begin{array}{c}\alpha_{-2} \\ \alpha_{-1} \\ \alpha_0 \\ \alpha_1 \\ \alpha_2\end{array}\right) = \left(\begin{array}{c}0 \\ \frac{1}{h} \\ 0 \\ 0 \\ 0\end{array}\right)$$
	\item As in the script, I extend the Taylor expansion by one degree:
		\begin{eqnarray*}
			f_{i-2} & = & f_i - 2 h f_i' + 2 h^2 f_i'' - \frac{4}{3} h^3 f_i''' + \frac{2}{3} h^4 f_i'''' - \frac{4}{15} h^5 f_i''''' + O(h^6) \\
			f_{i-1} & = & f_i - h f_i' + \frac{1}{2} h^2 f_i'' - \frac{1}{6} h^3 f_i''' + \frac{1}{24} h^4 f_i'''' - \frac{1}{120} h^5 f_i''''' + O(h^6) \\
			f_i & = & f_i \\
			f_{i+1} & = & f_i + h f_i' + \frac{1}{2} h^2 f_i'' + \frac{1}{6} h^3 f_i''' + \frac{1}{24} h^4 f_i'''' + \frac{1}{120} h^5 f_i''''' + O(h^6) \\
			f_{i+2} & = & f_i + 2 h f_i' + 2 h^2 f_i'' + \frac{4}{3} h^3 f_i''' + \frac{2}{3} h^4 f_i'''' + \frac{4}{15} h^5 f_i''''' + O(h^6)
		\end{eqnarray*}
		Using the filter mask, one gets:
		\begin{eqnarray*}
			f_i' & = & \frac{1}{12h}\left[(1-8+8-1) f_i + (-2+8+8-2) h f_i' \phantom{\frac{1}{1}} \right. \\
			& & \phantom{\frac{1}{1}} \quad \quad + (2-4+4-2) h^2 f_i'' \\
			& & \phantom{\frac{1}{1}} \quad \quad + \left(-\frac{4}{3} + \frac{4}{3} + \frac{4}{3} - \frac{4}{3}\right) h^3 f_i''' \\
			& & \phantom{\frac{1}{1}} \quad \quad + \left(\frac{2}{3} - \frac{1}{3} + \frac{1}{3} - \frac{2}{3}\right) h^4 f_i'''' \\
			& & \phantom{\frac{1}{1}} \quad \quad + \left(-\frac{4}{15} + \frac{1}{15} + \frac{1}{15} - \frac{4}{15}\right) h^5 f_i''''' \\
			& & \left. \phantom{\frac{1}{1}} \quad \quad + O(h^6)\right] \\
			& = & \frac{1}{12h} \left[12 h f_i' - \frac{2}{5} h^5 f_i''''' + O(h^6)\right] \\
			f_i' & = & f_i' - \frac{1}{30} h^4 f_i''''' + O(h^5)
		\end{eqnarray*}
		The order of consistency for this approximation is 4.
	\item If I want to approximate a derivative of order $d$ with $n$ points, it must be that $n>d$. \\
		For a value $j$, where $j \neq d$ and $j<n$, all the coefficients in front of $h^j f_i^{(j)}$ are 0 (this is also the case in part \textbf{b.}). What remains is $h^d f_i^{(d)}$ and $h^n f_i^{(n)}$ with their respective coefficients. \\
		The order of consistency is therefore $n-d$. If you compare this statement with my solution of part \textbf{b.}, you see that it is true, since we have order of consistency $n-d = 5-1 = 4$.
\end{enumerate}

\exercise{Hough Transform}
\begin{enumerate}
	\item First of all, I have to state the five trigonometric curves which belong to the five points given.
		\begin{enumerate}[1.]
			\item $(-1,1)$: $d = -\cos \phi + \sin \phi$
			\item $(2,0)$: $d = 2 \cdot \cos \phi$
			\item $(3,1)$: $d = 3 \cdot \cos \phi + \sin \phi$
			\item $(1,3)$: $d = \cos \phi + 3 \cdot \cos \phi$
			\item $(0,2)$: $d = 2 \cdot \sin \phi$
		\end{enumerate}
		Now I try to find the points which are on a line by using equality: \\[0.5cm]
		$1. = 2.$:
		\begin{eqnarray*}
			-\cos \phi + \sin \phi & = & 2 \cdot \cos \phi \\
			\sin \phi & = & 3 \cdot \cos \phi
		\end{eqnarray*}
		$1. = 3.$:
		\begin{eqnarray*}
			-\cos \phi + \sin \phi & = & 3 \cdot \cos \phi + \sin \phi \\
			4 \cdot \cos \phi & = & 0
		\end{eqnarray*}
		$1. = 4.$:
		\begin{eqnarray*}
			-\cos \phi + \sin \phi & = & \cos \phi + 3 \cdot \sin \phi \\
			-\cos \phi & = & \sin \phi
		\end{eqnarray*}
		$1. = 5.$:
		\begin{eqnarray*}
			-\cos \phi + \sin \phi & = & 2 \cdot \sin \phi \\
			-\cos \phi & = & \sin \phi
		\end{eqnarray*}
		It follows that the points $(-1,1)$, $(1,3)$ and $(0,2)$ belong to the same line.
	\item The equation for a circle looks like this:
		$$|x-a|^2 + |y-b|^2 - r^2 = 0$$
		where $(a,b)$ is the center and $r$ the radius of the circle. For this exercise, we have $r=2 \Rightarrow r^2 = 4$. \\
		I will now look at the different points:
			\begin{enumerate}[1.]
				\item $(-1,1)$: $|x+1|^2 + |y-1|^2 = 4$
				\item $(2,0)$: $|x-2|^2 + |y-0|^2 = 4$
				\item $(3,1)$: $|x-3|^2 + |y-1|^2 = 4$
				\item $(1,3)$: $|x-1|^2 + |y-3|^2 = 4$
				\item $(0,2)$: $|x-0|^2 + |y-2|^2 = 4$
			\end{enumerate}
			As one can easily see, the points 1, 3 and 4 belong to the same circle with radius 2 and the center point $(1,1)$.
\end{enumerate}

\exercise{Cooccurrence Matrices}
Since $d=(-1,-1)^\top$, we have to look at the upper left neighbor. \\
\begin{center}
\begin{tabular}{c|c|c|c|c|cc}
	\multicolumn{1}{c}{ } & \multicolumn{4}{c}{P[i,j]} \\ \cline{2-5}
	\multirow{4}{*}{$\displaystyle \frac{1}{30} \times$} & 1 & 2 & 1 & 1 & 0 & \multirow{4}{*}{\textit{i}} \\ \cline{2-5}
	& 2 & 5 & 1 & 1 & 1 \\ \cline{2-5}
	& 2 & 2 & 3 & 2 & 2 \\ \cline{2-5}
	& 1 & 2 & 2 & 2 & 3 \\ \cline{2-5}
	\multicolumn{1}{c}{ } & \multicolumn{1}{c}{0} & \multicolumn{1}{c}{1} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{3} \\
	\multicolumn{1}{c}{ } & \multicolumn{4}{c}{\textit{j}}
\end{tabular}
\end{center}

\end{document}
