\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 T6}}
\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 T6}
\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}

\begin{center}
	\begin{tabular}{p{1.5cm}|p{1.5cm}|p{1.5cm}|p{1.5cm}||p{1.5cm}c}
		\centering 1 & \centering 2 & \centering 3 & \centering 4 & \centering$\sum$ & \\ \hline
		\phantom{x} & \phantom{x} & \phantom{x} & \phantom{x} & \phantom{x}
	\end{tabular}
\end{center}

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

\exercise{Discretisation of Hyberbolic PDEs}
\begin{enumerate}
	\item
		\begin{itemize}
			\item forward differences:
				\begin{eqnarray*}
					\frac{u_i^{k+1} - u_i^k}{\tau} & = & a \cdot \frac{u_{i+1}^k - u_i^k}{h} \\
					\Leftrightarrow u_i^{k+1} & = & a \tau \cdot \frac{u_{i+1}^k - u_i^k}{h} + u_i^k
				\end{eqnarray*}
			\item backward differences:
				\begin{eqnarray*}
					\frac{u_i^{k+1} - u_i^k}{\tau} & = & a \cdot \frac{u_i^k - u_{i-1}^k}{h} \\
					\Leftrightarrow u_i^{k+1} & = & a \tau \cdot \frac{u_i^k - u_{i-1}^k}{h} + u_i^k
				\end{eqnarray*}
			\item central differences:
				\begin{eqnarray*}
					\frac{u_i^{k+1} - u_i^k}{\tau} & = & a \cdot \frac{u_{i+1}^k - 2u_i^k + u_{i-1}^k}{2h} \\
					\Leftrightarrow u_i^{k+1} & = & a \tau \cdot \frac{u_{i+1}^k - 2u_i^k + u_{i-1}^k}{2h} + u_i^k
				\end{eqnarray*}
		\end{itemize}
	\item
		The results from above should now be represented as a convex combination.
		\begin{itemize}
			\item forward differences:
				$$u_i^{k+1} = \frac{a \tau}{h} u_{i+1}^k + \left(1 - \frac{a \tau}{h}\right) u_i^k$$
				To fullfill one criterion of the convex combination $\frac{a \tau}{h} > 0$ and since $\tau, h > 0$ it must hold that $a > 0$. For the other part of the convex combination you see that
				\begin{eqnarray*}
					1 - \frac{a \tau}{h} & > & 0 \\
					\Leftrightarrow \frac{a \tau}{h} & < & 1 \\
					\Leftrightarrow a & < & \frac{h}{\tau}
				\end{eqnarray*}
				If $0 < a < \frac{h}{\tau}$, the max-min-stability holds.
			\item backward differences:
				$$u_i^{k+1} = \left(1 + \frac{a \tau}{h}\right) u_i^k - \frac{a \tau}{h} u_{i-1}^k$$
				In this case, on the one hand side it must be fullfilled that $- \frac{a \tau}{h} > 0 \Leftrightarrow \frac{a \tau}{h} < 0$. On the other hand it must hold the following:
				\begin{eqnarray*}
					1 + \frac{a \tau}{h} & > & 0 \\
					\frac{a \tau}{h} & > & -1 \\
					a & > & -\frac{h}{\tau}
				\end{eqnarray*}
				If $-\frac{h}{\tau} < a < 0$, the max-min-stability holds.
			\item central differences:
				$$u_i^{k+1} = \left(1 - 2 \frac{a \tau}{h}\right) u_i^k + \frac{a \tau}{h} (u_{i+1}^k + u_{i-1}^k)$$
				In this case, $\frac{a \tau}{h} > 0 \Leftrightarrow a > 0$. Furthermore
				\begin{eqnarray*}
					1 - 2 \frac{a \tau}{h} & > & 0 \\
					2 \frac{a \tau}{h} & < & 1 \\
					a & < & \frac{h}{2 \tau}
				\end{eqnarray*}
				If $0 < a < \frac{h}{2 \tau}$, the max-min-stability holds.
		\end{itemize}
\end{enumerate}

\newpage
\exercise{Slope Transform}
We know that
$$\mathcal{S}[f](u) := \underset{x}{\mbox{stat}} (f(x) - ux)$$
Since $\underset{x}{\mbox{stat}} g(x) := {g(x) | g'(x) = 0}$ we can plug this in:
\begin{eqnarray*}
	\mathcal{S}[f_p](u) & = & \underset{x}{\mbox{stat}} (f_p(x) - ux) \\
	& = & \left\{f_p(x) - ux \; | \; f_p'(x) - u = 0\right\} \\
	& = & \left\{cx^p - ux \; \large| \; pcx^{p-1} - u = 0\right\} \\
	& = & \left\{x\left(cx^{p-1} - u\right) \; \Big| \; x^{p-1} = \frac{u}{pc}\right\} \\
	& = & \left\{x\left(\frac{u}{p} - u\right) \; \Big| \; x = \mbox{sgn}(u) \left|\frac{u}{pc}\right|^{\frac{1}{p-1}}\right\} \\
	& = & \left\{\mbox{sgn}(u) \left|\frac{u}{pc}\right|^{\frac{1}{p-1}} \left(\frac{u}{p} - u\right)\right\} \\
	\mathcal{S}[f_p](u) & = & \left\{\mbox{sgn}(u) \left|\frac{u}{pc}\right|^{\frac{1}{p-1}} \frac{u}{p}(1-p)\right\}
\end{eqnarray*}
For the case that $p=2$ we get the following:
\begin{eqnarray*}
	\mathcal{S}[f_2](u) & = & \left\{cx^2 - ux \; |�\; 2cx - u = 0\right\} \\
	& = & \left\{x(cx - u) \; | \; x = \frac{u}{2c}\right\} \\
	& = & \left\{\frac{u}{2c} \left(\frac{u}{2} - u\right)\right\} \\
	& = & \left\{-\frac{u^2}{4c}\right\}
\end{eqnarray*}
In this case the slope transform remains a quadratic function. This shows the fact that parabolas remain parabolas (to be more precise "paraboloids") under the slope transform (Lecture 21, slide 13).

\exercise{Curvature-Based Morphology}
We know from Lecture 22, slide 3 that
\begin{eqnarray*}
	\partial_t u & = & \Delta u \\
	& = & \partial_{xx} u + \partial_{yy} u \quad (\mbox{by the definition of } \Delta) \\
	& = & \partial_{\eta \eta} u + \partial_{\xi \xi} u \quad (\eta \parallel \nabla u, \xi \perp \nabla u)
\end{eqnarray*}
We want with MCM a smoothing along isophotes, so $\partial_{\eta \eta} u$ vanishes, since this term smoothes across the edge. \\
So it remains to show that
\begin{eqnarray*}
	\partial_{\xi \xi} u & = & \frac{u_y^2u_{xx} - 2 u_x u_y u_{xy} + u_x^2 u_{yy}}{u_x^2 + u_y^2} \quad \quad (1) \\
	& = & \Delta u - \frac{1}{|\nabla u|^2} \nabla u^\top \mbox{Hess}(u) \nabla u \; \quad (2) \\
	& = & |\nabla u| \mbox{div}\left(\frac{\nabla u}{|\nabla u|}\right) \quad \quad \quad \quad \quad \quad (3)
\end{eqnarray*}
Let's show that (1) = (2):
\begin{eqnarray*}
& & \Delta u - \frac{1}{|\nabla u|^2} \nabla u^\top \mbox{Hess}(u) \nabla u \\
& = & u_{xx} + u_{yy} - \frac{1}{u_x^2 + u_y^2} \nabla u^\top \mbox{Hess}(u) \nabla u \\
& = & u_{xx} + u_{yy} - \frac{1}{u_x^2 + u_y^2} (u_x, u_y) \left(\begin{array}{cc}u_{xx} & u_{xy} \\ u_{yx} & u_{yy}\end{array}\right) \left(\begin{array}{c}u_x \\ u_y\end{array}\right) \\
& = & \frac{(u_x^2 + u_y^2) (u_{xx} + u_{yy})}{u_x^2 + u_y^2} - \frac{1}{u_x^2 + u_y^2} (u_x, u_y) \left(\begin{array}{c}u_{xx}u_x + u_{xy}u_y \\ u_{yx}u_x + u_{yy}u_y\end{array}\right) \\
& = & \frac{(u_x^2 + u_y^2)(u_{xx} + u_{yy})}{u_x^2 + u_y^2} - \frac{1}{u_x^2 + u_y^2} \left(u_{xx}u_x^2 + u_{xy}u_yu_x + u_{yx}u_xu_y + u_{yy}u_y^2\right) \\
& = & \frac{u_x^2 u_{xx} + u_x^2 u_{yy} + u_y^2 u_{xx} + u_y^2 u_{yy} - u_{xx} u_x^2 - 2 u_x u_y u_{xy} - u_{yy} u_y^2}{u_x^2 + u_y^2} \\
& = & \frac{u_y^2 u_{xx} - 2 u_x u_y u_{xy} + u_x^2 u_{yy}}{u_x^2 + u_y^2}
\end{eqnarray*}
Let's show that (1) = (3):
\begin{eqnarray*}
	&& |\nabla u| \mbox{div}\left(\frac{\nabla u}{|\nabla u|}\right) \\
	& = & \sqrt{u_x^2 + u_y^2} \left(\partial_x \frac{u_x}{\sqrt{u_x^2 + u_y^2}} + \partial_y \frac{u_y}{\sqrt{u_x^2 + u_y^2}}\right) \\
	& = & \sqrt{u_x^2 + u_y^2} \left(\frac{u_{xx} \sqrt{u_x^2 + u_y^2} - u_x \frac{1}{2 \sqrt{u_x^2 + u_y^2}} (2 u_x u_{xx} + 2 u_y u_{yx})}{u_x^2 + u_y^2}\right. \\
	& & \quad \quad \quad \quad \quad \quad + \left. \frac{u_{yy} \sqrt{u_x^2 + u_y^2} - u_y \frac{1}{2 \sqrt{u_x^2 + u_y^2}} (2 u_x u_{yx} + 2 u_y u_{yy})}{u_x^2 + u_y^2}\right) \\
	& = & \frac{u_{xx}(u_x^2 + u_y^2) - u_x (u_x u_{xx} + u_y u_{yx})}{u_x^2 + u_y^2} + \frac{u_{yy}(u_x^2 + u_y^2) - u_y (u_x u_{yx} + u_y u_{yy})}{u_x^2 + u_y^2} \\
	& = & \frac{u_{xx}u_x^2 + u_{xx}u_y^2 - u_x^2u_{xx} - u_xu_yu_{xy} + u_{yy}u_x^2 + u_{yy}u_y^2 - u_xu_yu_{xy} - u_y^2u_{yy}}{u_x^2 + u_y^2} \\
	& = & \frac{u_y^2u_{xx} - 2u_xu_yu_{xy} + u_x^2u_{yy}}{u_x^2 + u_y^2}
\end{eqnarray*}

\exercise{Multiple Choice}
\begin{enumerate}
	\item NO
	\item NO
	\item NO
	\item NO
\end{enumerate}

\end{document}