\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{Differential Equations in Image Processing and Computer Vision \\ \large Assignment T3}}
\author{\shortstack[c]{Jan Hendrik Dithmar\\ \scriptsize 2031259} \\ Group 2: Thu, 12-14 (Markus Mainberger)}% \and \shortstack[c]{name\\ \scriptsize matr}}
\date{}

\pagestyle{fancy}

\lhead{Assignment T3}
\chead{}
\rhead{Dithmar (2031259)}
\lfoot{DIC}
\cfoot{Page \thepage}
\rfoot{SS 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{Discretisation of Anisotropic Nonlinear Diffusion}
\begin{enumerate}
	\item
		\begin{itemize}
			\item using forward differences for $\partial_y$ and $\partial_x$:
				\begin{eqnarray*}
					\partial_x & \approx & \frac{u_{i+1} - u_i}{2h_1} \\
					\partial_y & \approx & \frac{1}{2h_2} \left(b_{i,j+1} \frac{u_{i+1,j+1} - u_{i,j+1}}{2h_1} - b_{i,j} \frac{u_{i+1,j} - u_{i,j}}{2h_1}\right)
				\end{eqnarray*}
			\item using backward differences for $\partial_y$ and $\partial_x$:
				\begin{eqnarray*}
					\partial_x & \approx & \frac{u_i - u_{i-1}}{2h_1} \\
					\partial_y & \approx & \frac{1}{2h_2} \left(b_{i,j} \frac{u_{i,j} - u_{i-1,j}}{2h_1} - b_{i,j-1} \frac{u_{i,j-1} - u_{i-1,j-1}}{2h_1}\right)
				\end{eqnarray*}
			\item averaging both results:
				\begin{eqnarray*}
					& & \frac{1}{2} \left[\frac{1}{2h_2} \left(b_{i,j+1} \frac{u_{i+1,j+1} - u_{i,j+1}}{2h_1} - b_{i,j} \frac{u_{i+1,j} - u_{i,j}}{2h_1}\right) \right.\\
					& & \quad \left. + \frac{1}{2h_2} \left(b_{i,j} \frac{u_{i,j} - u_{i-1,j}}{2h_1} - b_{i,j-1} \frac{u_{i,j-1} - u_{i-1,j-1}}{2h_1}\right)\right] \\
					& = & \frac{1}{4h_2} \left(b_{i,j+1} \frac{u_{i+1,j+1} - u_{i,j+1}}{2h_1} - b_{i,j} \frac{u_{i+1,j} - 2u_{i,j} + u_{i-1,j}}{2h_1} \right. \\
					& & \quad \quad \quad \left. - b_{i,j-1} \frac{u_{i,j-1} - u_{i-1,j-1}}{2h_1}\right)
				\end{eqnarray*}
		\end{itemize}
	\item
		\begin{itemize}
			\item using forward differences for $\partial_y$ and backward differences for $\partial_x$:
				\begin{eqnarray*}
					\partial_x & \approx & \frac{u_i - u_{i-1}}{2h_1} \\
					\partial_y & \approx & \frac{1}{2h_2} \left(b_{i,j+1} \frac{u_{i,j+1} - u_{i-1,j+1}}{2h_1} - b_{i,j} \frac{u_{i,j} - u_{i-1,j}}{2h_1}\right)
				\end{eqnarray*}
			\item using backward differences for $\partial_y$ and forward differences for $\partial_x$:
				\begin{eqnarray*}
					\partial_x & \approx & \frac{u_{i+1} - u_i}{2h_1} \\
					\partial_y & \approx & \frac{1}{2h_2} \left(b_{i,j} \frac{u_{i+1,j} - u_{i,j}}{2h_1} - b_{i,j-1} \frac{u_{i+1,j-1} - u_{i,j-1}}{2h_1}\right)
				\end{eqnarray*}
			\item averaging both results:
				\begin{eqnarray*}
					& & \frac{1}{2} \left[\frac{1}{2h_2} \left(b_{i,j+1} \frac{u_{i,j+1} - u_{i-1,j+1}}{2h_1} - b_{i,j} \frac{u_{i,j} - u_{i-1,j}}{2h_1}\right) \right. \\
					& & \quad \left. + \frac{1}{2h_2} \left(b_{i,j} \frac{u_{i+1,j} - u_{i,j}}{2h_1} - b_{i,j-1} \frac{u_{i+1,j-1} - u_{i,j-1}}{2h_1}\right)\right] \\
					& = & \frac{1}{4h_2} \left(b_{i,j+1} \frac{u_{i,j+1} - u_{i-1,j+1}}{2h_1} + b_{i,j} \frac{u_{i+1,j} - 2u_{i,j} + u_{i-1,j}}{2h_1} \right. \\
					& & \quad \quad \quad \left. - b_{i,j-1} \frac{u_{i+1,j-1} - u_{i,j-1}}{2h_1}\right)
				\end{eqnarray*}
		\end{itemize}
	\item approximating the term $\partial_x (b \partial_y u) + \partial_y (b \partial_x u)$ in the following way:
		\begin{itemize}
			\item using forward differences for $\partial_y$ and $\partial_x$:
				\begin{eqnarray*}
					& & \partial_x (b \partial_y u) + \partial_y (b \partial_x u) \\
					& \approx & \frac{1}{2h_1} \left(b_{i+1,j} \frac{u_{i+1,j+1} - u_{i+1,j}}{2h_2} - b_{i,j} \frac{u_{i,j+1} - u_{i,j}}{2h_2}\right) \\
					& & \quad + \frac{1}{2h_2} \left(b_{i,j+1} \frac{u_{i+1,j+1} - u_{i,j+1}}{2h_1} - b_{i,j} \frac{u_{i+1,j} - u_{i,j}}{2h_1}\right) =: C_a
				\end{eqnarray*}
			\item using backward differences for $\partial_y$ and $\partial_x$:
				\begin{eqnarray*}
					& & \partial_x (b \partial_y u) + \partial_y (b \partial_x u) \\
					& \approx & \frac{1}{2h_1} \left(b_{i,j} \frac{u_{i,j} - u_{i,j-1}}{2h_2} - b_{i-1,j} \frac{u_{i-1,j} - u_{i-1,j-1}}{2h_2}\right) \\
					& & \quad + \frac{1}{2h_2} \left(b_{i,j} \frac{u_{i,j} - u_{i-1,j}}{2h_1} - b_{i,j-1} \frac{u_{i,j-1} - u_{i-1,j-1}}{2h_1}\right) =: C_b
				\end{eqnarray*}
			\item averaging both results:
				$$\frac{1}{2} (C_a + C_b)$$
			\item using forward differences for $\partial_y$ and backward differences for $\partial_x$:
				\begin{eqnarray*}
					& & \partial_x (b \partial_y u) + \partial_y (b \partial_x u) \\
					& \approx & \frac{1}{2h_1} \left(b_{i,j} \frac{u_{i,j+1} - u_{i,j}}{2h_2} - b_{i-1,j} \frac{u_{i-1,j+1}  - u_{i-1,j}}{2h_2}\right) \\
					& & \quad + \frac{1}{2h_2} \left(b_{i,j+1} \frac{u_{i,j+1} - u_{i-1,j+1}}{2h_1} - b_{i,j} \frac{u_{i,j} - u_{i-1,j}}{2h_1}\right) =: C_c
				\end{eqnarray*}
			\item using backward differences for $\partial_y$ and forward differences for $\partial_x$:
				\begin{eqnarray*}
					& & \partial_x (b \partial_y u) + \partial (b \partial_x u) \\
					& \approx & \frac{1}{2h_1} \left(b_{i+1,j} \frac{u_{i+1,j} - u_{i+1,j-1}}{2h_2} - b_{i,j} \frac{u_{i,j} - u_{i,j-1}}{2h_2}\right) \\
					& & \quad + \frac{1}{2h_2} \left(b_{i,j} \frac{u_{i+1,j} - u_{i,j}}{2h_1} - b_{i,j-1} \frac{u_{i+1,j-1} - u_{i,j-1}}{2h_1}\right) =: C_d
				\end{eqnarray*}
			\item averaging both results:
				$$\frac{1}{2} (C_c + C_d)$$
		\end{itemize}
\end{enumerate}

\exercise{Discretisation of Anisotropic Nonlinear Diffusion}
If I can find a condition number that is greater than the "magic number" presented in Lecture 8, slide 11, I have a situation where the "nonnegativity" criterion is violated. This is the case if the ratio between the eigenvalues is greater than 5.8284, especially for the following diffusion tensor:
$$\left(\begin{array}{cc}1 & 5 \\ 5 & 8\end{array}\right)$$
where the eigenvalues are
$$\frac{9}{2} \pm \frac{1}{2} \sqrt{149}.$$
This can also happen if we have a diagonally dominant diffusion tensor. An example would be the following tensor:
$$\left(\begin{array}{cc}30 & 5 \\ 5 & 30\end{array}\right)$$
where the eigenvalues are here 25 and 35.

\exercise{Stopping Time Selection: Decorrelation Criterion}
We have to smooth the signal
$$(3,5,3,5,-5,-3,-5,-3)$$
with
$$(0.25, 0.5, 0.25).$$
The convention for the following calculations is that $\textbf{f}$ denotes the "old" signal and $\textbf{g}$ denotes the "new" signal.
\begin{enumerate}[1.]
	\item iteration: $(3.5, 4, 4, 2, -2, -4, -4, -3.5)$
		\begin{eqnarray*}
			\bar{\textbf{f}} & = & \frac{1}{8} (3+5+3+5-5-3-5-3) = 0 \\
			\bar{\textbf{g}} & = & \frac{1}{8} (3.5+4+4+2-2-4-4-3.5) = 0 \\
			\mbox{var}(\textbf{f}) & = & \frac{1}{8} \cdot 136 = 17 \\
			\mbox{var}(\textbf{g}) & = & \frac{1}{8} \cdot 96.5 = 12.0625 \\
			\mbox{cov}(\textbf{f},\textbf{g}) & = & \frac{1}{8} \cdot 105 = 13.125 \\
			\mbox{corr}(\textbf{f},\textbf{g}) & = & \frac{13.125}{\sqrt{17} \cdot \sqrt{12.0625}} \approx 0.9165501
		\end{eqnarray*}
	\item iteration: $(3.625, 3.875, 3.5, 1.5, -1.5, -3.5, -3.875, -3.625)$ \\
		$\bar{\textbf{f}}$ now equals $\bar{\textbf{g}}$ of the previous iteration.
		\begin{eqnarray*}
			\bar{\textbf{f}} & = & 0 \\
			\bar{\textbf{g}} & = & 0 \\
			\mbox{var}(\textbf{f}) & = & 12.0625 \\
			\mbox{var}(\textbf{g}) & = & \frac{1}{8} \cdot 85.3125 = 10.6640625 \\
			\mbox{cov}(\textbf{f},\textbf{g}) & = & \frac{1}{8} \cdot 90.375 = 11.296875 \\
			\mbox{corr}(\textbf{f},\textbf{g}) & = & \frac{11.296875}{\sqrt{12.0625} \cdot \sqrt{10.6640625}} \approx 0.9960435
		\end{eqnarray*}
		Since this value is already larger than the correlation coefficient from the first iteration we can stop the process here.
\end{enumerate}

\exercise{Convex Functionals and Forward Diffusion}
According to Lecture 4, slide 6, we have to ensure that $$\Phi'(u_x) = (\Psi'(u_x^2)u_x)' > 0$$ to get forward diffusion.
\begin{eqnarray*}
	(\Psi'(u_x^2)u_x)' & = & \Psi''(u_x^2) \cdot 2 u_x \cdot u_x + \Psi'(u_x^2) \\
	& = & 2 \Psi''(u_x^2) u_x^2 + \Psi'(u_x^2)
\end{eqnarray*}
Let's see whether we have forward diffusion or not:
$$\underbrace{2 \underbrace{\Psi''(u_x^2)}_{\geq 0} u_x^2}_{\geq 0} + \underbrace{\Psi'(u_x^2)}_{>0} > 0$$
We know from the problem text that $\Psi''(u_x^2) \geq 0$. This means that the whole term $2 \Psi''(u_x^2) u_x^2 \geq 0$. From Lecture 10, slide 4, we know the assumption that $\Psi'(u_x^2) > 0$.

\end{document}
